Left recursion, associativity and AST evaluation

Question

So I have been reading a bit on lexers, parser, interpreters and even compiling.

For a language I'm trying to implement I settled on a Recrusive Descent Parser. Since the original grammar of the language had left-recursion, I had to slightly rewrite it.

Here's a simplified version of the grammar I had (note that it's not any standard format grammar, but somewhat pseudo, I guess, it's how I found it in the documentation):

expr:
-----
expr + expr
expr - expr
expr * expr
expr / expr
( expr )
integer
identifier

To get rid of the left-recursion, I turned it into this (note the addition of the NOT operator):

expr:
-----
expr_term {+ expr}
expr_term {- expr}
expr_term {* expr}
expr_term {/ expr}

expr_term:
----------
! expr_term
( expr )
integer
identifier

And then go through my tokens using the following sub-routines (simplified pseudo-code-ish):

public string Expression()
{
    string term = ExpressionTerm();

    if (term != null)
    {
        while (PeekToken() == OperatorToken)
        {
            term += ReadToken() + Expression();
        }
    }

    return term;
}

public string ExpressionTerm()
{
    //PeekToken and ReadToken accordingly, otherwise return null
}

This works! The result after calling Expression is always equal to the input it was given.

This makes me wonder: If I would create AST nodes rather than a string in these subroutines, and evaluate the AST using an infix evaluator (which also keeps in mind associativity and precedence of operators, etcetera), won't I get the same result?

And if I do, then why are there so many topics covering "fixing left recursion, keeping in mind associativity and what not" when it's actually "dead simple" to solve or even a non-problem as it seems? Or is it really the structure of the resulting AST people are concerned about (rather than what it evaluates to)? Could anyone shed a light, I might be getting it all wrong as well, haha!

The purpose of a parser is to produce an interpretation (actions), or a translation (an equivalent document in the same or another language, like in optimization, annotation, or compilation). Reproducing the original input is uninteresting. — Apalala
I assumed it showed I got my recursion loop right in that if I would change the string to a node-tree instead, I'd also end up with a grammatically correct "sentence". Is this assumption incorrect? — Lennard Fonteijn
Reproducing the input proves nothing about recognizing the structure. It can be done by echoing, or by luck. A simple and revealing translation to try would be to convert the input to prefix or postfix (Polish) notation. You could even build an evaluator for postfix to know if you're interpreting the input structure correctly. In your case, you'll find that you're not, because all operators are at the same level. You would need some kind of operator precedence tho grok that a+b*3 means a+(b*3) and not (a+b)*3. — Apalala

rici rici · Accepted Answer · 2013-10-19T01:16:05

The shape of the AST is important, since a+(b*3) is not usually the same as (a+b)*3 and one might reasonably expect the parser to indicate which of those a+b*3 means.

Normally, the AST will actually delete parentheses. (A parse tree wouldn't, but an AST is expected to abstract away syntactic noise.) So the AST for a+(b*3) should look something like:

          Sum
           |
       +---+---+
       |       |
      Var     Prod
       |       |
       a   +---+---+
           |       |
          Var    Const
           |       |
           b       3

If you language obeys usual mathematical notation conventions, so will the AST for a+b*3.

An "infix evaluator" -- or what I imagine you're referring to -- is just another parser. So, yes, if you are happy to parse later, you don't have to parse now.

By the way, showing that you can put tokens back together in the order that you read them doesn't actually demonstrate much about the parser functioning. You could do that much more simply by just echoing the tokenizer's output.

Left recursion, associativity and AST evaluation

2 Answers