Why a parser walks into a wall
Earlier in this rung you forced a grammar into rigid shapes: Chomsky normal form for the CYK algorithm, and Greibach normal form, whose every rule starts with a terminal so a top-down machine always commits a real letter before recursing. This last guide tackles two smaller, sharper surgeries — left recursion removal and left factoring — that real parsers depend on. They are not full normal forms; they are targeted fixes for two very specific ways a naive top-down parser gets stuck. Like Greibach, they are about controlling what happens at the LEFT edge of a rule, because a left-to-right parser reads the left edge first.
Picture the simplest top-down strategy, recursive descent: to match a nonterminal A, you look at the rules for A, pick one, and try to match its right-hand side left to right, calling a little procedure for each symbol. It is a polite reader expanding a leftmost derivation as it scans the input. Now feed it the rule E -> E + T. To match E, the procedure's very first act is... to call itself to match E, with the input pointer unmoved. That call again starts by calling itself, forever. No letter is ever consumed. This is the disease of left recursion: a nonterminal that can derive a string beginning with itself, A =>* A something.
Removing left recursion: flip the loop around
The fix is a clean piece of algebra on the rules, and it never changes the language. Look at what A -> A α | β really generates: a single β, then any number of α's stuck on the right. So the strings are β, βα, βαα, βααα, ... — a β followed by zero or more α's. That is just β (α)star, a left-edge loop wearing a recursive disguise. Once you SEE it as a loop, you can rebuild the same set of strings with the recursion moved to the RIGHT instead, where a top-down parser can handle it: consume β first, then peel off α's one at a time.
The mechanical recipe for immediate (direct) left recursion: gather every A-rule into the left-recursive ones A -> A α1 | A α2 | ... and the rest A -> β1 | β2 | .... Introduce a fresh helper nonterminal A' (read 'A-prime'). Replace them with A -> β1 A' | β2 A' | ... and A' -> α1 A' | α2 A' | ... | ε. Each non-recursive start βi now launches the parse, and A' then optionally appends the αi tails, ending with the epsilon-production A' -> ε when the loop stops. The recursion now sits on the right edge of A', so the parser always reads a real prefix before recursing.
Left-recursive (top-down parser loops forever):
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
After removing left recursion (E', T' are fresh helpers):
E -> T E'
E' -> + T E' | epsilon
T -> F T'
T' -> * F T' | epsilon
F -> ( E ) | id
Same language, e.g. id + id * id still parses --
but now every rule's left edge consumes input or ends.There is a subtler cousin: INDIRECT left recursion, where no single rule begins with A, yet a chain does, e.g. A -> B x and B -> A y, so A =>* A y x. The standard cure is to fix an ordering A1, A2, ..., An of the nonterminals and sweep through them: for each Ai, substitute the right-hand sides of every earlier Aj (j < i) wherever Aj appears at the start of an Ai-rule, which forces all of Ai's left recursion to become immediate, then apply the direct recipe above. After the full sweep, no nonterminal is left-recursive at all. This is essentially the same machinery that drives the conversion to Greibach normal form.
Left factoring: stop guessing at the fork
The second illness is different. Suppose A -> if E then S | if E then S else S. Both alternatives begin with the same long run 'if E then S'. A predictive parser wants to choose the right rule by peeking at just the next input symbol — but here both rules start identically, so one symbol of lookahead tells it nothing. The naive parser must GUESS a branch, march down it, and if it turns out wrong, backtrack and try the other — slow, and beyond the reach of a clean one-token-lookahead LL(1) parser. Left factoring removes the guess by refusing to commit until the alternatives actually diverge.
- Find the longest common prefix shared by two or more alternatives of one nonterminal: A -> γ β1 | γ β2 | ... where γ is the shared front and the βi are what differs afterward (any βi may even be empty).
- Factor γ out exactly once and defer the decision to a fresh helper A': replace those rules with A -> γ A' and A' -> β1 | β2 | ....
- Now the parser matches the common γ with no choice at all, and only THEN looks at the next symbol to pick among the βi -- by which point they genuinely differ, so a single token of lookahead suffices. Repeat if a prefix is still shared, since one pass may expose a new common prefix underneath.
On the example: A -> if E then S A', A' -> else S | ε. The parser now matches 'if E then S' unconditionally, then peeks once: if the next token is 'else' it takes that branch, otherwise it takes the empty one. The guessing is gone, and one-token lookahead decides cleanly. (This very example, the dangling-else, is also genuinely ambiguous in another sense — which 'if' an 'else' attaches to — but that is a separate problem from the lookahead problem left factoring solves; factoring fixes the parser's choice, not the tree's shape.)
The honest catch: the tree changes, and grammars can swell
Here is the price, and it is the same warning that haunts every transformation in this rung. These rewrites preserve the LANGUAGE — exactly the same set of strings is generated, no more, no less — but they do NOT preserve the parse tree. After removing left recursion, the natural left-leaning tree for 'a - b - c' (which encodes left-to-right grouping, ((a-b)-c)) is replaced by a right-leaning tree threaded through the helper A'. The grammar still accepts the same strings, but the structure it assigns them has flipped. If your tree carried meaning — say, that subtraction groups to the left — you must reconstruct that meaning afterward, because the grammar no longer hands it to you for free.
The second honest catch is size. Left factoring with repeated common prefixes, and indirect left-recursion removal where you substitute earlier nonterminals into later ones, can each cause a blowup: the number of rules can balloon, in the worst case far faster than the original grammar's size. This is the same theme as converting to CNF or GNF — the rigid, parser-friendly shape is bought with a bigger, less readable grammar. It is a transformation done once, by a tool, not something you would maintain by hand.
Stepping back: where normal forms have brought us
Look at what this rung built. You learned WHY a tidy grammar is worth the trouble; how to strip out useless symbols, epsilon-productions, and unit productions in the right order; CNF with its binary trees that power the CYK membership test and the context-free pumping lemma; GNF whose terminal-first rules mirror a pushdown automaton's moves; and now the two top-down surgeries — left-recursion removal so the parser never loops, and left factoring so it never has to guess. Together they are the bridge from the abstract idea of a context-free grammar to a grammar a machine can actually drive.
Carry one sentence out of all five guides: a normal form changes the grammar's SHAPE, never the language, and often at the cost of the parse tree and the grammar's size. That single trade — readability and structure given up for a rigid form an algorithm can chew on — is the whole reason these conversions exist, and the reason a parser generator applies them silently before it ever builds your parser. Next, the ladder leaves grammars behind and gives them a matching machine: the pushdown automaton, a finite control with a stack of plates where you may only touch the top — the exact amount of memory a context-free language needs, and not one plate more.