title: Converting a parse tree to AST
body: <p>Let me put the question first: Can I convert a parse tree implementing this particular grammar to an AST trivially.</p>
  
  <p>I was given this grammar to build a parse tree:</p>
  
  <pre><code>literal := INTEGER | FLOAT | TRUE | FALSE .
  
  designator := IDENTIFIER { "[" expression0 "]" } .
  
  op0 := "&gt;=" | "&lt;=" | "!=" | "==" | "&gt;" | "&lt;" .
  op1 := "+" | "-" | "or" .
  op2 := "*" | "/" | "and" .
  
  expression0 := expression1 [ op0 expression1 ] .
  expression1 := expression2 { op1  expression2 } .
  expression2 := expression3 { op2 expression3 } .
  expression3 := "not" expression3
         | "(" expression0 ")"
         | designator
         | call-expression
         | literal .
  </code></pre>
  
  <p>For this particular example:</p>
  
  <pre><code>func main() : void {
      let a = 1 + 2 + 3 + 4;
  }
  </code></pre>
  
  <p>My parser will generate (part of) the parse tree as such</p>
  
  <pre><code>            EXPRESSION1
                  EXPRESSION2
                    EXPRESSION3
                      LITERAL
                        INTEGER(1)(lineNum:2, charPos:10)
                  OP1
                    ADD(lineNum:2, charPos:12)
                  EXPRESSION2
                    EXPRESSION3
                      LITERAL
                        INTEGER(2)(lineNum:2, charPos:14)
                  OP1
                    ADD(lineNum:2, charPos:16)
                  EXPRESSION2
                    EXPRESSION3
                      LITERAL
                        INTEGER(3)(lineNum:2, charPos:18)
                  OP1
                    ADD(lineNum:2, charPos:20)
                  EXPRESSION2
                    EXPRESSION3
                      LITERAL
                        INTEGER(4)(lineNum:2, charPos:22)
  </code></pre>
  
  <p>Just notice how these tree branches under EXPRESSION1 go:</p>
  
  <pre><code>EXPRESSION2 + EXPRESSION2 + EXPRESSION2 + EXPRESSION2
  </code></pre>
  
  <p>which the operator + doesn't correspond to its two operands. So it seems to me that, in the AST conversion, I can't get an AST that aids 3-address IR code generation by simply pulling up the operator to replace the non-terminal EXPRESSION1.</p>
  
  <p>To achieve this goal, the grammar I would have written for this language will be like this instead</p>
  
  <pre><code>expression1 := expression2 | expression1 + expression2  (1)
  expression2 := expression3 | expression2 * expression3  (2)
  expression3 := literal                                  (3)
  </code></pre>
  
  <p>which the branches under EXPRESSION1 are only </p>
  
  <pre><code>EXPRESSION1 + EXPRESSION2
  </code></pre>
  
  <p>However, this grammar is not LL(1) since |FIRST(expression2)| = |{literal, +}| > 1. </p>
  
  <p>It begs the question that (1) what would be the most elegant and trivial way to convert this parse tree? (2) is my construction of the parse tree a complete waste of time for this grammar that I should have started out coding an AST instead?</p>