title: Recursive Descent Parser
body: <p>The book 'Modern Compiler Design' is the nice book about compilers. In its source code something that is annoying me is AST or Abstract Syntax Tree. Suppose we want to write a parenthesized expression parser which parses something like: <code>((2+3)*4) * 2</code>! The book says that we have an AST like:</p>
  
  <pre><code>        ((2+3)*4) * 2
            /   |     \
         (2+3)  *4    * 2
          /     | \
       (2+3)    *  4
       / | \
      2  + 3
  </code></pre>
  
  <p>So should I save a tree in memory or just use recursive calls; Note: if I don't store it in memory, how can I convert it to machine code ?</p>
  
  <p>Parser code:</p>
  
  <pre><code>int parse(Expression &amp;expr)
  {
    if(token.class=='D')
    { 
      expr.type='D';
      expr.value=token.val-'0';
      get_next_token();
      return 1;
    }
    if(token.class=='(') 
    {
      expr.type='P';
      get_next_token();
      parse(&amp;expr-&gt;left);
      parse_operator(&amp;expr-&gt;op);
      parse(&amp;expr-&gt;right);
      if(token.class!=')')
        Error("missing )");
      get_next_token();
      return 1;
    }
    return 0;
  }
  </code></pre>
  
  <p>Grammar is:</p>
  
  <pre><code>expr -&gt; expr | (expr op expr)
  digit   -&gt; 0|1|2....|9
  op  -&gt; +|*
  </code></pre>