Compiler/syntax analyzer: Difference between revisions

[https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form Extended Backus-Naur Form (EBNF)]:

 

stmt_list = {stmt} ;

 

| '(' expr ')'

| ('+' | '-' | '!') primary

 

The resulting AST should be formulated as a Binary Tree.

|-

| style="vertical-align:top" |

while (count < 10) {

print("count is: ", count, "\n");

count = count + 1;

 

| style="vertical-align:top" |

[https://en.wikipedia.org/wiki/Recursive_descent_parser Recursive Descent] for statement parsing. The AST is also built:

 

if tok is "("

x = paren_expr()

t = make_node(Sequence, t, stmt())

until tok is end-of-file

 

;Once the AST is built, it should be output in a [[Flatten_a_list|flattened format.]] This can be as simple as the following:

 

if t == NULL

print(";\n")

print("\n")

prt_ast(t.left)

 

;If the AST is correctly built, loading it into a subsequent program should be as simple as:

 

line = readline()

# Each line has at least one token

left = load_ast()

right = load_ast()

 

Finally, the AST can also be tested by running it against one of the AST Interpreter [[Compiler/AST_interpreter|solutions]].

|-

| style="vertical-align:top" |

Simple prime number generator

*/

}

}

 

| style="vertical-align:top" |

 

=={{header|ALGOL W}}==

% parse tree nodes %

record node( integer type

while begin

if tkType = tString then begin

readToken

end

reference(node) listNode;

listNode := null;

listNode

end parseStatementList ;

 

tOp_multiply := 1; tkName( tOp_multiply ) := "Op_multiply"; tkPrec( tOp_multiply ) := 5;

tOp_divide := 2; tkName( tOp_divide ) := "Op_divide"; tkPrec( tOp_divide ) := 5;

tkNode( tOp_multiply ) := nMultiply; tkNode( tOp_divide ) := nDivide; tkNode( tOp_mod ) := nMod;

tkNode( tOp_add ) := nAdd; tkNode( tOp_subtract ) := nSubtract; tkNode( tOp_less ) := nLess;

tkNode( tOp_equal ) := nEqual; tkNode( tOp_notequal ) := nNotEqual; tkNode( tOp_not ) := nNot;

tkNode( tOp_and ) := nAnd; tkNode( tOp_or ) := nOr;

readToken;

writeNode( parseStatementList( tEnd_of_input ) )

{{out}}

Output from parsing the Prime Numbers example program.

=={{header|ATS}}==

 

(* Usage: parse [INPUTFILE [OUTPUTFILE]]

If INPUTFILE or OUTPUTFILE is "-" or missing, then standard input

end

 

 

 

=={{header|AWK}}==

Tested with gawk 4.1.1 and mawk 1.3.4.

function Token_assign(tk, attr, attr_array, n, i) {

n=split(attr, attr_array)

prt_ast(t)

}

 

{{out|case=count}}

=={{header|C}}==

Tested with gcc 4.81 and later, compiles warning free with -Wall -Wextra

#include <stdlib.h>

#include <string.h>

init_io(&dest_fp, stdout, "wb", argc > 2 ? argv[2] : "");

prt_ast(parse());

 

{{out|case=prime numbers AST}}

Code by Steve Williams. Tested with GnuCOBOL 2.2.

 

identification division.

*> this code is dedicated to the public domain

.

end program printast.

 

{{out|case=Primes}}

 

 

#|-*- mode:lisp -*-|#

#|

(uiop:quit 0)))

 

 

{{out}}

=={{header|Forth}}==

Tested with Gforth 0.7.3.

: PEEK BUF @ 0= IF KEY BUF ! THEN BUF @ ;

: GETC PEEK 0 BUF ! ;

: -EOI? TOKEN-TYPE End_of_input <> ;

: PARSE $NULL GETTOK BEGIN -EOI? WHILE STMT $SEQUENCE REPEAT ;

 

{{out|case=Count AST}}

{{works with|gfortran|11.2.1}}

The following is Fortran 2008/2018 code with C preprocessing directives. If you call the program source ‘parse.F90’, with a capital ‘F’, then gfortran will know to run the C preprocessor.

!!! An implementation of the Rosetta Code parser task:

!!! https://rosettacode.org/wiki/Compiler/syntax_analyzer

end subroutine print_usage

 

{{out}}

=={{header|Go}}==

{{trans|C}}

 

import (

scanner = bufio.NewScanner(source)

prtAst(parse())

 

{{out}}

 

 

# The Rosetta Code Tiny-Language Parser, in Icon.

#

}

return s

 

{{out}}

Implementation:

 

tkref=: tokenize 'End_of_input*/%+--<<=>>===!=!&&||print=print(if{else}while;,putc)a""0'

end.

}}

 

Some quirks worth noting:

Task example:

 

primes=: {{)n

/*

String "\n"

;

 

=={{header|Java}}==

Usage: java Parser infile [>outfile]

{{trans|Python}}

import java.io.File;

import java.io.FileNotFoundException;

}

}

 

=={{header|Julia}}==

Julia tends to discourage large numbers of global variables, so this direct port from the Python reference implementation moves the globals into a function wrapper.

{{trans|Python}}

nodetype::Int

left::Union{Nothing, ASTnode}

 

# syntaxanalyzer(length(ARGS) > 1 ? ARGS[1] : stdin) # for use as in the Python code

 

=={{header|M2000 Interpreter}}==

 

 

Module syntax_analyzer(b$){

enum tokens {

43 1 End_of_Input

}

 

{{out}}

Using the third version of Nim lexer.

 

 

type NodeKind* = enum

let code = if paramCount() < 1: stdin.readAll() else: paramStr(1).readFile()

let tree = parse(code)

 

{{out}}

 

 

#

# The Rosetta Code Tiny-Language Parser, in Object Icon.

}

return s

 

{{out}}

=={{header|Perl}}==

Tested on perl v5.26.1

 

use strict; # parse.pl - inputs lex, outputs flattened ast

$_[0] <= 0 && /$h Op_or \n/gcx ? "Or\n$ast" . expr(1) :

return $ast while 1;

 

{{out|case=Count AST}}

=={{header|Phix}}==

Reusing lex.e (and core.e) from the [[Compiler/lexical_analyzer#Phix|Lexical Analyzer task]], and again written as a reusable module.

<span style="color: #000080;font-style:italic;">--

-- demo\rosetta\Compiler\parse.e

<span style="color: #008080;">return</span> <span style="color: #000000;">t</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

And a simple test driver for the specific task:

<span style="color: #000080;font-style:italic;">--

-- demo\rosetta\Compiler\parse.exw

--main({0,0,"primes.c"}) -- as Algol, C, Python (apart from spacing)

--main({0,0,"count.c"}) -- as AWK ( "" )</span>

{{out}}

<pre>

=={{header|Python}}==

Tested with Python 2.7 and 3.x

import sys, shlex, operator

 

error(0, 0, "Can't open %s" % sys.argv[1])

t = parse()

 

{{out|case=prime numbers AST}}

 

=={{header|RATFOR}}==

{{works with|gfortran|11.2.1}}

{{works with|f2c|20100827}}

 

 

 

''However'', it is perfectly possible to implement a recursive language ''in'' FORTRAN 77 and do the programming in ''that''.

 

Printing the abstract syntax tree is done with a quite ordinary non-recursive tree traversal written directly in Ratfor.

 

 

#

# The Rosetta Code parser in Ratfor 77.

 

i = 1

i = i + 2

ipfind = i

{

i = dtpop (dstack, idstck)

ip = ipfind (code, code(ip + 1))

else

end

 

 

 

The following code implements a configurable (from a symbol map provided as a parameter) Precedence Climbing parser for the output of the [http://rosettacode.org/wiki/Compiler/lexical_analyzer#Scala lexer]. The recursive descent language parser is closely based on the pseudo code given in the task description.

 

package xyz.hyperreal.rosettacodeCompiler

 

 

}

 

=={{header|Scheme}}==

Code implements a recursive descent parser based on the given grammar. Tested against all programs in [[Compiler/Sample programs]].

 

(import (scheme base)

(scheme process-context)

(display-ast (parse-file (cadr (command-line))))

(display "Error: provide program filename\n"))

 

=={{header|Wren}}==

{{libheader|Wren-fmt}}

{{libheader|wren-ioutil}}

 

var tokens = [

lines = FileUtil.readLines("source.txt")

lineCount = lines.count

 

{{out}}

 

=={{header|Zig}}==

const std = @import("std");

 

return result;

}