Left Recursion and Left Factoring
Our tidy expression grammar has a secret that is fatal to one whole family of parsers. Look again at
E \;\to\; E + T \;\mid\; T.
A top-down parser works by prediction: to match an E, it picks
a production and tries to match its right-hand side against the input, left to right. But the very first
symbol of the first alternative is E again. So to match
E the parser must first match E, which means first
matching E, … — an infinite regress that consumes no input and never
returns. This is left recursion, and it hangs every naive
recursive-descent / LL
parser stone dead.
Bottom-up parsers actually love left recursion (it keeps their stacks shallow), so this page is
really about making a grammar safe for top-down parsing — through two mechanical, meaning-preserving
transformations: left-recursion elimination and left factoring.
Immediate left recursion, and the standard cure
A nonterminal is immediately left-recursive if it has a production whose right-hand side
begins with itself. Group all such productions:
A \;\to\; A\alpha_1 \mid A\alpha_2 \mid \dots \mid A\alpha_m \;\mid\; \beta_1 \mid \beta_2 \mid \dots \mid \beta_n,
where no \beta_i begins with A. Every string this
generates is a \beta followed by a run of \alphas —
i.e. it matches the regular pattern \beta(\alpha_1 \mid \dots \mid \alpha_m)^{*}.
Rewriting that "start with a base, then loop" as right recursion gives the classic transform:
- Replace A \to A\alpha \mid \beta with the pair
A \to \beta A' and
A' \to \alpha A' \mid \varepsilon.
- In general, A \to \beta_1 A' \mid \dots \mid \beta_n A' and
A' \to \alpha_1 A' \mid \dots \mid \alpha_m A' \mid \varepsilon, with a
fresh nonterminal A'.
- The generated language is unchanged; only the shape of the derivation (and its
trees) flips from left-leaning to right-leaning.
Applied to the whole expression grammar, the ubiquitous left recursion vanishes and a new
\varepsilon appears at the end of each helper:
| Left-recursive (bottom-up friendly) | Right-recursive (top-down ready) |
|---|
| E \to E + T \mid T | E \to T\,E', E' \to +\,T\,E' \mid \varepsilon |
| T \to T * F \mid F | T \to F\,T', T' \to *\,F\,T' \mid \varepsilon |
| F \to (\,E\,) \mid \mathbf{id} | F \to (\,E\,) \mid \mathbf{id} (already fine) |
The general algorithm: indirect left recursion too
Left recursion can also be indirect: no rule starts with itself, yet a cycle exists across
several nonterminals, e.g. A \to B\,a and
B \to A\,c \mid d — here A \Rightarrow B a \Rightarrow A c a,
so A is left-recursive through B. The Dragon Book's
algorithm removes all left recursion, direct and indirect, by imposing an ordering and
substituting earlier nonterminals forward before eliminating immediate recursion:
order the nonterminals A1, A2, …, An
for i = 1 … n:
for j = 1 … i-1:
# replace each Ai → Aj γ by Ai → δ1 γ | δ2 γ | …
# where Aj → δ1 | δ2 | … are the current Aj-productions
substitute the Aj-productions into Ai
eliminate immediate left recursion among the Ai-productions
The inner loop guarantees that by the time you reach A_i, every production
starting with a lower-numbered nonterminal has been expanded away, so any remaining left recursion in
A_i must be immediate — and the previous section handles that. The
procedure assumes the grammar has no \varepsilon-productions and no cycles
A \Rightarrow^{+} A; both can be removed first by standard cleanups.
Left factoring: postponing a decision
A different top-down disease is a common prefix. When two productions for the same
nonterminal start identically, a one-token-lookahead parser cannot tell which to choose:
S \;\to\; \mathbf{if}\ E\ \mathbf{then}\ S\ \mathbf{else}\ S \;\mid\; \mathbf{if}\ E\ \mathbf{then}\ S.
Seeing \mathbf{if}, the parser has no idea yet whether an
\mathbf{else} is coming. Left factoring factors out the shared
prefix and defers the choice until the tokens that actually differ:
- Replace A \to \alpha\beta_1 \mid \alpha\beta_2 with
A \to \alpha A' and
A' \to \beta_1 \mid \beta_2, where \alpha is the
longest common prefix.
- Now the parser commits to the shared \alpha immediately and only has to
distinguish the tails \beta_1, \beta_2 once it reaches them.
The dangling-\mathbf{else} rule becomes
S \to \mathbf{if}\ E\ \mathbf{then}\ S\ S' with
S' \to \mathbf{else}\ S \mid \varepsilon — the
\mathbf{else}-or-nothing decision is pushed to the exact spot where the input
reveals the answer. Left recursion and common prefixes are the two structural obstacles a grammar must
clear before it can be LL(1).
Elimination in code
Immediate left-recursion elimination is short enough to write out. Given one nonterminal's alternatives,
split them into the left-recursive ones (starting with A) and the rest, then
emit the two transformed rules. We use "eps" for \varepsilon.
type Alt = string[]; // one right-hand side, e.g. ["E", "+", "T"]
type Rules = Record<string, Alt[]>; // nonterminal -> its alternatives
// Eliminate IMMEDIATE left recursion for nonterminal A.
// A -> A a1 | A a2 | b1 | b2 becomes
// A -> b1 A' | b2 A' and A' -> a1 A' | a2 A' | eps
function eliminate(rules: Rules, A: string): Rules {
const alts = rules[A];
const recursive: Alt[] = []; // the a's (tail after leading A)
const base: Alt[] = []; // the b's
for (const alt of alts) {
if (alt[0] === A) recursive.push(alt.slice(1)); // drop the leading A
else base.push(alt);
}
if (recursive.length === 0) return rules; // nothing to do
const Ap = A + "'";
const out: Rules = { ...rules };
out[A] = base.map((b) => [...b, Ap]); // b_i A'
out[Ap] = [...recursive.map((a) => [...a, Ap]), ["eps"]]; // a_i A' | eps
return out;
}
const show = (rules: Rules) => {
for (const [nt, alts] of Object.entries(rules)) {
console.log(`${nt} -> ${alts.map((a) => a.join(" ")).join(" | ")}`);
}
};
// E -> E + T | T
let g: Rules = { E: [["E", "+", "T"], ["T"]] };
console.log("BEFORE:"); show(g);
console.log("AFTER:"); show(eliminate(g, "E"));
Out comes E -> T E' and E' -> + T E' | eps — the left recursion is gone,
the language identical, and a top-down parser can now proceed without looping.
This is the subtle cost. The original E \to E + T was
left-recursive precisely so that a + b + c would tree up as
(a + b) + c — left-associative, which is what subtraction and division need.
The transformed E \to T E', E' \to + T E' is
right-recursive, so its natural tree leans the other way. Does that break arithmetic? No — because
the parser no longer relies on the tree's shape to encode associativity. Instead it carries the
left operand along as it loops through E' and combines
semantically: it computes ((a + b) + c) by folding left as it scans,
via an inherited-attribute accumulator. Associativity moves from the grammar's geometry into the parser's
action code. The syntax was reshaped for the machine; the meaning is restored by hand.
The single most important thing to hold onto: left-recursion elimination and left factoring are
language-preserving. Before and after generate exactly the same set of strings
— you have refactored the description, not the thing described. What does change is (a) the set
of nonterminals (a fresh A' appears), (b) the shape of the parse trees
(right-leaning instead of left-leaning), and therefore (c) where associativity has to be enforced (in
semantic actions, not in the tree). A common exam slip is to "simplify" the transformed grammar by
deleting the \varepsilon alternative on A' — but
that \varepsilon is what lets the loop stop; drop it and you can no
longer derive the base case \beta alone, shrinking the language. Keep the
\varepsilon.