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

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}}

#

# The Rosetta Code parser in Ratfor 77.

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}}

import "/fmt" for Fmt

import "/ioutil" for FileUtil

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

lineCount = lines.count

{{out}}

=={{header|Zig}}==

const std = @import("std");

return result;

}