Eliminating Left Recursion
You'll learn: How to systematically transform a left-recursive grammar into an equivalent one that avoids left recursion—essential for top-down parsers.
Why This Matters
Recall from the previous lesson that left recursion causes top-down parsers to loop infinitely. A production like A → A α | β makes the parser immediately call itself on A without consuming any input, creating an endless cycle. We need a mechanical procedure to fix this.
The Core Algorithm
The transformation works by replacing left recursion with right recursion and introducing a new helper nonterminal.
Immediate Left Recursion
For a rule of the form:
A → A α₁ | A α₂ | ... | A αₙ | β₁ | β₂ | ... | βₘ
Where each β does not start with A, we replace it with:
A → β₁ A' | β₂ A' | ... | βₘ A'
A' → α₁ A' | α₂ A' | ... | αₙ A' | ε
Example
Original (left-recursive):
E → E + T | T
Transformed:
E → T E'
E' → + T E' | ε
Now E starts with T (consuming input immediately), and E' handles the repeating + T parts using right recursion.
Think of It Like...
Instead of saying "a number is itself plus more stuff" (which creates a circular dependency), we say "a number is a base value followed by zero-or-more additions." The new nonterminal A' captures "what comes after" the base case.
Key Takeaway: Eliminating left recursion systematically rewrites grammar rules to replace left-recursive patterns with right recursion and a helper nonterminal, making the grammar parsable by top-down methods without changing the language it generates.