How to build parse tree?

Question

Have found C++ BNF and there next lines

selection-statement:
    if ( condition ) statement
    if ( condition ) statement else statement

Now trying to write parser. Need to build parse tree. On input i have BNF and source file. But i'm stucked in how i can point my parser what if condition evaluated to true, then it need to execute first statement otherwise else block? Thanks.

Solution 1

Conditional statements have a simple recursive structure. The corresponding recursive descent parser has a similarly simple recursive structure. Abstractly, the interior conditionals are parsed as follows:

<cond> -> if <expression> then <statement> [else <statement>]

cond :
  a = parse expression
  b = parse statement
  if is_else(token)
    then c = parse statement
         return conditional(a,b,c)
    else return conditional(a,b)

In your example, conditional statements contain blocks of conditionals the last of which contains an else clause. Assuming that the tokenized input sequence has this form and syntactic errors were detected during lexical analysis, the outer conditional is parsed as follows:

<conditional> -> selection_statement: {<cond>} <cond>

conditional :
  b = new block
  while (iscond(next))
    s = parse cond
    b = insert(s,b)
  return b

Of course, the actual implementation will be significantly more detailed and tedious. However, the preceding describes in outline the construction of a parse tree of a conditional statement having the required form from a tokenized input sequence.

I just realized you were talking about evaluating the abstract syntax tree. The structure of the function that evaluations a conditional statement is similar to the function that parses a conditional statement. Abstractly,

cond(input) :
  a = evaluate(if_part(input))
  if is_true(a)
    then evaluate(then_part(input))
    else if(is_else(input))
           then evaluate(else_part(input))
           else return

In order to determine which portion of the conditional to evaluate, you must first evalute the "if" part of the conditional to a Boolean value. If the Boolean value is "true," the "then" part of the conditional is evaluated. If the Boolean value is "false," then the "else" part of the conditional is evaluated. If there is no "else" part, there is nothing to evaluate. Of course, the implementation will be more detailed than the above.

Solution 2

First of all, you need to distinguish between the usual passes of a compiler:

1. The lexing, that is recognizing words and removing comments,
2. the parsing, that is structuring of the linear input stream into an abstract syntax tree, and
3. the evaluation or code generation.

Do the first things first, then you'll understand the rest. Look at boost::spirit for the first two steps.

Comments

[Yola]

its - AST with if clause. It looks like compiler must to now something about if-else except info from BNF.

[Yola]

And i can build AST, think its not hard, but i dont understand how in code-gen part it will figure out what if condition is true then jmp to first statement, and to else block otherwise.

[thiton]

@Yola: This depends fully on what you are trying to do with the AST, which is outside the scope of parsing, CFG and BNF. You'd have to reformulate your question stating what you are trying to do (interpretation? compilation? expression simplification?) and what your exact problem is.

[Yola]

i need to interpret and evaluate expression. Do you know calculator, that can evaluate expression like next: c=1;c*2; resulted to 2 or yet one if (1 > 2) then 1; else 2; resulted to 2 too.

[MSalters]

That's a step you do after parsing. Typically, a compiler transforms the AST into code. For an if statement, you could get the following pseudo-code. CMP 1,2; JLE #ELSE; MOV R1, 1; JMP #END; #ELSE: MOV R1, 2 #END: (JLE would be "jump if less")

[Yola]

thanks man. now i know that i need module to implement semantics, bnf give me only grammar.

[emi]

Yes - as thiton pointed out, there are three things you need to do. First, you need to tokenize the input stream. Second, you need to parse the tokenzed input stream. Third, you need to evaluate the parsed abstract syntax tree.