Left Recursion and Its Problems
What you'll learn: You'll understand what left recursion is in context-free grammars and why it causes serious headaches for certain types of parsers.
What Is Left Recursion?
A production in a context-free grammar is left-recursive if a nonterminal can derive a string that starts with itself. The simplest form is immediate left recursion, where a production looks like this:
A → A α | β
Here, nonterminal A appears as the very first symbol on the right-hand side of its own production.
For example, consider this grammar for arithmetic expressions:
E → E + T | T
T → number
The production E → E + T is immediately left-recursive because E starts with itself.
Why Is This a Problem?
Left recursion creates infinite loops for top-down parsers (the kind that start from the start symbol and try to predict which production to use). Here's the issue:
When a top-down parser tries to expand E, it sees E → E + T. To parse the first E on the right, it must expand E again, which leads to E → E + T again... and again... forever! The parser gets stuck in an endless expansion loop before even looking at the input.
The analogy: Imagine defining a recipe that starts with "First, follow this recipe." You'd never get to the actual cooking steps—you'd be trapped in an infinite instruction loop.
The Impact
Top-down parsers (like recursive descent parsers, which are popular because they're easy to write by hand) simply cannot handle left-recursive grammars directly. The parser spins forever without consuming any input tokens.
Key Takeaway: Left recursion occurs when a nonterminal derives strings starting with itself, causing top-down parsers to enter infinite loops; such grammars must be rewritten to eliminate left recursion before top-down parsing can succeed.