Left Recursion - Pitfalls

Pitfalls

The above transformations remove left-recursion by creating a right-recursive grammar; but this changes the associativity of our rules. Left recursion makes left associativity; right recursion makes right associativity. Example: We start with a grammar:

After having applied standard transformations to remove left-recursion, we have the following grammar:

Parsing the string 'a + a + a' with the first grammar in an LALR parser (which can recognize left-recursive grammars) would have resulted in the parse tree:

Expr / | \ Expr + Term / | \ \ Expr + Term Factor | | | Term Factor Int | | Factor Int | Int

This parse tree grows to the left, indicating that the '+' operator is left associative, representing (a + a) + a.

But now that we've changed the grammar, our parse tree looks like this:

Expr --- / \ Term Expr' -- | / | \ Factor + Term Expr' ------ | | | \ \ Int Factor + Term Expr' | | | Int Factor | Int

We can see that the tree grows to the right, representing a + (a + a). We have changed the associativity of our operator '+', it is now right-associative. While this isn't a problem for the associativity of integer addition, it would have a significantly different value if this were subtraction.

The problem is that normal arithmetic requires left associativity. Several solutions are: (a) rewrite the grammar to be left recursive, or (b) rewrite the grammar with more nonterminals to force the correct precedence/associativity, or (c) if using YACC or Bison, there are operator declarations, %left, %right and %nonassoc, which tell the parser generator which associativity to force.