Eliminating Left Recursion
What You'll Learn
You'll learn how to transform left-recursive grammar rules into equivalent forms that work with top-down parsers.
The Problem Recap
In the previous lesson, you saw that left recursion causes infinite loops in recursive descent parsers. A rule like A → A α | β makes the parser call itself immediately, never consuming input.
The Transformation
The fix is to rewrite left-recursive rules using right recursion or iteration.
For a simple left-recursive rule:
A → A α | β
Transform it into two rules:
A → β A'
A' → α A' | ε
Here, A' is a new non-terminal (read as "A-prime"). Instead of recursing before processing α, we now process β first, then let A' handle zero or more repetitions of α after.
How It Works
Think of it like building a train: left recursion tries to attach cars before the engine (impossible in a single pass), but right recursion attaches the engine first, then adds cars after one by one.
Example:
expr → expr + term | term
Becomes:
expr → term expr'
expr' → + term expr' | ε
Now the parser reads term first, then repeatedly checks for + term sequences.
Why This Works
The transformed grammar generates the same language but parses left-to-right without immediate self-recursion. The parser consumes input before making recursive calls, preventing infinite loops.
Key Takeaway:
Eliminating left recursion transforms grammar rules so the parser processes input before recursing, enabling top-down parsing while preserving the language accepted.