How do you rewrite a directly left-recursive rule such as `list -> list ',' item` so a top-down parser can use it?
answer
- nothing consumed before it recurses
- same rule, same position, forever
- split recursive from non-recursive alternatives
- fresh helper rule carries the repeat
- tail repeats, exits through empty
basics
~20 sSplit the alternatives: replace A -> A alpha | beta with A -> beta A2 and A2 -> alpha A2 | empty. The recursive part becomes a repeating tail, so the parser consumes the leading beta before re-entering and the recursion terminates.
solid answer
~50 sA rule is directly left recursive when the nonterminal is the first symbol of one of its own right-hand sides, as in `list -> list ',' item | item`. A top-down parser picks an alternative and expands it before consuming input, so expanding `list` re-enters `list` at the same input position and never makes progress. The standard fix separates the alternatives that start with the nonterminal from those that do not: `A -> A alpha | beta` becomes `A -> beta A2` plus `A2 -> alpha A2 | empty`, where `A2` is a fresh helper. Applied to the list rule that gives `list -> item list_tail` and `list_tail -> ',' item list_tail | empty`. The accepted language is unchanged, but the tree now leans right, so a left-associative operator must be folded explicitly in the semantic action rather than being read off the tree shape.
code
pseudocode · 8 linesbefore:
list -> list ',' item
| item
after:
list -> item list_tail
list_tail -> ',' item list_tail
| emptygo deeper
Recall the shape: a rule whose name is the first symbol of its own right-hand side cannot be used by a parser that works top-down, because it never consumes input before trying again.
Be able to perform the rewrite live on an expression or list rule, name the fresh helper, keep its empty alternative, and explain why the original never makes progress.
Show that you know what the rewrite costs downstream: right-leaning trees, associativity moved into the semantic action, a nullable helper interacting with what may follow, and generated names leaking into diagnostics.
Frame it as a choice about where the complexity lives — a readable canonical rule set with a transformed copy for the tool, versus one rewritten rule set that every reader has to decode.
## What direct left recursion is A **context-free grammar** is a set of **productions**. Each production has a **nonterminal** on the left (a name for a construct, like `list` or `expr`) and a sequence of terminals and nonterminals on the right (**terminals** are the tokens the input actually contains). A production is **directly left recursive** when the left-hand nonterminal is also the *first* symbol on the right: ``` list -> list ',' item | item ``` This is a natural way to write a comma-separated list, and it is exactly the shape a top-down parser generator rejects with the note *left recursive*. ## Why a top-down parser cannot use it A top-down parser works from the start symbol downwards: to match `list` it chooses one alternative and expands it, then matches the symbols of that alternative left to right. Choosing `list ',' item` means the very first thing to match is `list` again — **at the same input position, with nothing consumed**. The parser is in the identical state it was in a moment ago, so it makes the identical choice, and descends forever. A backtracking variant fares no better: the failing path has no base case to fail against, so it diverges instead of backtracking. The key point is that the loop is caused by *no input being consumed before the recursive occurrence*, not by the recursion itself. Right recursion (`list -> item ',' list`) is fine: `item` is consumed first, so each level of recursion is strictly closer to the end of the input. ## The rewrite, step by step Group the alternatives of `A` into the ones that begin with `A` (write them `A alpha_1 … A alpha_n`) and the ones that do not (`beta_1 … beta_m`). Then: 1. Invent a fresh nonterminal `A2` that appears nowhere else. 2. Replace `A`'s productions with `A -> beta_1 A2 | … | beta_m A2`. 3. Add `A2 -> alpha_1 A2 | … | alpha_n A2 | empty`. 4. Keep the `empty` (epsilon) alternative — it is the only exit, and dropping it makes the tail rule non-terminating in the other direction. For the list rule: `beta` is `item`, `alpha` is `',' item`, so you get `list -> item list_tail` and `list_tail -> ',' item list_tail | empty`. Read aloud, the original said *a list is a list followed by another item*; the rewrite says *a list is one item followed by any number of extra items*. Both describe the same strings; only the second can be read left to right without knowing the end in advance. ## What the rewrite changes and what it does not | property | original left-recursive rule | after the rewrite | |---|---|---| | set of strings accepted | L | L — unchanged | | shape of the parse tree | leans left | leans right, through the tail rule | | ambiguity of the rule set | whatever it was | unchanged; this rewrite does not remove it | | usable by a predictive top-down parser | no | yes, provided the alternatives also have disjoint first tokens | | usable by an LR-family bottom-up parser | yes | yes, but the stack grows with the list length | The last row is the reason bottom-up grammars are usually written left recursive on purpose: a left-recursive list is reduced as it goes and the stack stays shallow, while the right-recursive form must shift the whole list before the first reduction. ## Consequences worth naming in an interview - **Associativity leaves the tree.** `expr -> expr '-' term` encodes left associativity structurally; after the rewrite the structure is a flat tail and `a - b - c` must be folded left by hand, by accumulating in a loop rather than by recursing. - **The helper nonterminal is visible.** It appears in generated code, in error messages and in any diagram derived from the rule set, so give it a name a human can read rather than `A2`. - **The helper is nullable**, which pushes work onto the follow set of the original nonterminal: whatever can come after `list` must not also be able to start `list_tail`. - **It is one of two rewrites, not both.** Eliminating left recursion does nothing about two alternatives that share a leading prefix; that needs left factoring as well. - **It does not simplify the language.** Nothing is removed and nothing is disambiguated — you have changed the description, not the thing described. ## The check to run afterwards Derive two or three short sentences from the rewritten rules and confirm you get the same strings, then derive one string the original rejected and confirm the rewrite still rejects it. A rewrite that silently widens the language is the common self-inflicted bug: forgetting a `beta` alternative narrows it, and attaching `A2` to the wrong alternative widens it.
- After the rewrite the tree leans right. How do you keep a left-associative operator behaving correctly?Stop reading associativity off the tree and fold it explicitly: as the tail rule matches each `operator operand` pair, combine it into the accumulated result so far, left to right. The structure is now a flat repetition, so the semantic action carries the associativity the shape used to carry.
- Does the rewrite accept exactly the same strings as the original rule?Yes. Left-recursion elimination is language preserving — it changes the derivations and the tree shapes, not the set of accepted strings. Its common bugs are clerical: dropping one non-recursive alternative narrows the language, and attaching the helper to the wrong alternative widens it.
- Would a bottom-up parser generator have complained about the original rule at all?No. An LR-family parser defers its decision until it has seen the whole right-hand side, so left recursion is not a problem and is in fact preferred: it lets the list be reduced incrementally, keeping the stack shallow, while the right-recursive form must shift the entire list first.
It is the difference between defining a chain as 'a chain plus one more link' and as 'one link, then as many extra links as you like'. Only the second lets you start building before you know how long it is.
saying these in an interview costs you the question
- Thinks the rewrite changes which strings the rules accept.
- Claims eliminating left recursion also removes ambiguity.
- Says every parser family needs left recursion removed.
- Forgets the helper rule needs an empty alternative to terminate.
- Assumes left-associative folding still comes free from the tree.
- Believes right recursion is simply the better form everywhere.