Left Recursion

The production is left-recursive if the leftmost symbol on the right side is the same as the non terminal on the left side. For example,
            expr expr + term.

If one were to code this production in a recursive-descent parser, the parser would go in an infinite loop.


We can eliminate the left-recursion by introducing new nonterminals and new productions rules.

For example, the left-recursive grammar is:

E + T | T
T * F | F
(E) | id.

We can redefine E and T without left-recursion as:

E` + TE` | E
T * FT` | E
F (E) | id

Getting rid of such immediate left recursion is not enough. One must get rid of indirect left recursion too, where two or more nonterminals are mutually left-recursive.