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.
diagram
We can eliminate the left-recursion by introducing new nonterminals and new productions rules.
For example, the left-recursive grammar is:
E → E + T | T
E → T * F | F
F → (E) | id.
We can redefine E and T without left-recursion as:
E → TE`
E`→ + TE` | E
T → FT`
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.
