The Top-Down Parser Dilemma
Top-down parsers (including LL(1) predictive parsers and hand-crafted Recursive Descent parsers) work by attempting to find a leftmost derivation for an input string.
When evaluating a non-terminal A, the parser inspects the current lookahead token and selects a production rule to expand.
However, if the grammar contains Left Recursion:
A o Alpha mid eta The parser enters an immediate, fatal infinite recursion:
- Function
A()is invoked. - To expand
A, it invokesA(). - To expand
A, it invokesA()... - Result: Zero input tokens are consumed, and the process terminates with a
StackOverflowError.
1. Eliminating Immediate Left Recursion
Notice the strings generated by A o Alpha mid eta:
etaetalphaetalphalphaetalphaⁿ
The language is simply: a string beginning with eta, followed by zero or more copies of lpha.
We can generate this identical language without left recursion by introducing a new right-recursive non-terminal A':
eginaligned A & o eta A' \ A' & o lpha A' mid ε endaligned General Multi-Production Rule:
Given:
A o Alpha₁ mid Alpha₂ mid ... mid Alpha_m mid eta₁ mid eta₂ mid ... mid eta_n Replace with:
eginaligned A & o eta₁ A' mid eta₂ A' mid ... mid eta_n A' \ A' & o lpha₁ A' mid lpha₂ A' mid ... mid lpha_m A' mid ε endaligned 2. Handling Indirect Left Recursion
Left recursion isn't always immediate. Consider:
eginaligned S & o A a mid b \ A & o S c mid d endaligned Here, S ⇒ A a ⇒ S c a, forming a cyclic left-recursive chain.
The Systematic Elimination Algorithm:
- Arbitrarily order non-terminals:
A₁, A₂, ..., A_n. - For
i = 1ton:- For
j = 1toi - 1:- Replace each production
A_i o A_jγwithA_i o delta₁γ mid ... mid delta_kγ(whereA_j o delta₁ mid ... mid delta_k).
- Replace each production
- Eliminate immediate left recursion among
A_iproductions.
- For
3. Important Caveat: Ambiguity Remains!
⚠️ Critical Insight: Eliminating left recursion does NOT resolve inherent grammar ambiguity.
If your original grammar suffered from ambiguity (e.g. the Classic Dangling-Else problem), the right-recursive grammar will still produce conflicts in your LL(1) parsing table. Ambiguity must be resolved by enforcing precedence and associativity rules first.
Explore our full interactive Compiler Design curriculum on Binary Dose.