You build an LL(1) prediction table before hand-writing a recursive-descent parser, and one cell holds two rules — what does that mean?

## What the table is and what a cell means Before writing a predictive parser by hand it is worth building the table the mechanical version would use, because the table makes every branch decision explicit. The table is indexed by **nonterminal** down one axis and **lookahead terminal** across the other. Cell `[A, t]` holds the alternative of `A` to take when the next unconsumed token is `t`. It is filled from the prediction sets: for each alternative, write it into the cell of every token in its prediction set. A cell that ends up holding **two** entries is a **conflict**. It is the table telling you, at a named nonterminal and a named token, that the grammar does not decide what to do. ## The two shapes a conflict takes | shape | cause | example in a job language | |---|---|---| | starting-token clash | two alternatives of one rule can begin with the same token | `directive -> 'run' STRING \| 'run' STRING 'as' USER` | | empty-alternative clash | an alternative can derive nothing and the rule's FOLLOW overlaps another alternative's starting tokens | `options -> 'retry' NUMBER \| (nothing)` in a place where `'retry'` can also follow `options` | Both produce the same symptom in the table and the same symptom in hand-written code: an `if` on the lookahead where two branches are equally justified and the one written first silently wins. ## What the conflict does and does not prove This is the part interviewers push on, because three claims are routinely confused: - **It proves this rule set is not LL(1).** That is all the table can tell you. - **It does not prove the language is ambiguous.** Ambiguity means some input has two distinct derivations. A conflict only means one token is not enough to choose; the two alternatives may accept entirely disjoint inputs beyond that token. - **It does not prove no LL(1) rule set exists for the language.** A different set of rules describing the same language may separate cleanly. Whether a language admits such a rule set at all is a separate question from whether the one on your desk does. ## The realistic responses 1. **Restate the rule set** so the alternatives no longer share a prediction token — the standard repair, and a subject of its own under grammar transformation rather than something the parser does. 2. **Look further ahead at exactly that point.** A hand-written parser is ordinary code: it can inspect two or three tokens at one troublesome branch while staying one-token everywhere else. This is the pragmatic move, and it is one advantage hand-written parsers keep over a strict single-token table — but it is a local patch, and each one is a place where the implicit grammar drifts from anything written down. 3. **Change the parser family.** Bottom-up table-driven parsing accepts a strictly larger class of grammars than one-token top-down prediction, and ordered-choice parsing removes the conflict by definition by committing to the first alternative that matches. Both are separate subjects; what matters here is knowing the conflict is a reason to consider them. 4. **Accept backtracking.** Try one alternative and rewind on failure. It removes the conflict but gives up the linear-time guarantee, and it makes error messages much worse, because the failure is reported from whichever alternative was tried last rather than the one the author intended. What is **not** a response is resolving the cell by rule order and moving on without recording it. Generators commonly resolve some conflicts by a default preference and emit a warning; a warning suppressed at build time is a grammar whose real behaviour is now defined by the order of lines in a file. ## The special case worth memorising A rule that is **left-recursive** — one whose first symbol is the nonterminal itself, directly or through a chain — always produces a conflict cell. Every token that can start the recursive alternative can also start the non-recursive one, since the recursion must eventually bottom out in it. That is the formal statement behind the practical rule of thumb: no left-recursive grammar is LL(1), and adding a second or third token of lookahead does not rescue it, because the overlap is unbounded rather than one token deep. For a hand-written parser the payoff of building the table at all is this: the conflicts are found on paper, at design time, with the nonterminal and the token named. Found later, they arrive as a bug report saying one legal input is parsed as the wrong construct, and nothing in the code points at which branch was wrong.