Left Recursion Problem
You'll learn why some grammar rules cause recursive descent parsers to spin forever, and how to spot them before they break your parser.
The Core Issue
Remember recursive descent parsing? Each grammar rule becomes a function that calls other functions. Left recursion happens when a grammar rule's first symbol refers back to itself—directly or indirectly. This creates an infinite loop because the parser immediately calls itself again without consuming any input tokens.
Why It Causes Infinite Loops
Consider this grammar rule:
Expr → Expr + Term | Term
When the recursive descent function for Expr starts, it sees the first alternative begins with Expr, so it immediately calls itself. That recursive call also sees Expr first, so it calls itself again. This continues forever—the parser never reads a single token or makes any progress.
Think of it like looking up a word in the dictionary, only to find: "See: this word." You're stuck in a circle.
Detecting Left Recursion
Direct left recursion is easy to spot: a rule like A → A α | β where the rule name A appears as its own first symbol.
Indirect left recursion is trickier:
A → B α
B → A β
Here A calls B, which immediately calls A back—still an infinite loop, just hidden across two rules.
Detection Strategy
Scan each grammar rule's alternatives. If any alternative starts with the rule's own non-terminal (directly or through a chain of nullable symbols), you've found left recursion.
Key Takeaway: Left-recursive grammars cause recursive descent parsers to loop infinitely because the parser calls itself without consuming input; detect left recursion by checking if any rule can derive itself as its first symbol.