There is a small formal C-like language.

Code example:

int x = 10; int i = 0; while (i < x) { i = i + 1; }

How to build a parse tree here? I don’t understand how to connect all this, because the program provides several instructions, and how to present them in the tree, since in order to execute the last instruction, you need to execute the penultimate and so on.

  • one
    book dragon or something in this style read? If so, until the end? - KoVadim

2 answers 2

The easiest way is to use a parser generator, for example, a lex / yacc pair (flex / bison).

The parse tree will turn out automatically:

 program: statements { $$ = new Program($1); } statements: /* empty */ { $$ = new StatementList(); } | statements statement { $1->push_back($2); $$ = $1; } inner_statement: compound_statement | assignment | loop statement: inner_statement | vardef compound_statement: '{' statements '}' { $$ = new CompoundStatement($2); } assignment: IDENT '=' expression ';' { $$ = new AssignmentStatement($1, $3); } loop: while_loop | for_loop vardef: TYPE IDENT maybe_initializer ';' { $$ = new VarDefinition($1, $2, $3); } maybe_initializer: /* empty */ { $$ = null; } | '=' expression { $$ = $2; } while_loop: WHILE '(' expression ')' inner_statement { $$ = new WhileLoop($3, $5); }

and so on.

See how the tree is built recursively?

  • Thank. I'll try to figure it out. - nullptr

For a simple language, you can not bother with parser generators and parse manually, for example, as described in here and here , but instead of direct calculations, parsing procedures should produce parts of the parse tree. See also JSON parser as an example.

  • Thank. This will also come in handy for me) - nullptr
  • LL-parsers (recursive descent) are easily written by hand. If the language is left-recursive, writing LR-parser manually is not so easy. For example, the standard grammar for parsing an arithmetic expression, EMNIP, not LL. --- And even for LL-languages ​​I would write not manually, but on some ANTLR. - VladD
  • Grammar of arithmetic expressions - LL (1): http://en.wikipedia.org/wiki/Recursive_descent_parser - rfq
  • @rfq: Hmm, really. However, it is not so easy to write the correct LL (1) grammar for arithmetic expressions. Here is an example (section “Creating an LL (1) Grammar”). - VladD
  • one
    But why write it (grammar) if the link contains a ready-made handheld parser for a small language, including the analysis of arithmetic expressions. - rfq