Two alternatives of a directive rule both begin with the keyword `import`; why does that defeat a one-token-lookahead parser?
answer
- the choice happens before the evidence
- overlapping first sets on one nonterminal
- hoist the longest common prefix
- helper rule holds the differing tails
- may need more than one round
basics
~20 sA predictive parser chooses an alternative from the next token alone, and both alternatives start with the same one, so the choice is undecidable at that point. Left factoring pulls the shared prefix out and defers the decision until the rules differ.
solid answer
~50 sA predictive top-down parser commits to one alternative of a rule using a bounded lookahead — classically one token. If `directive -> 'import' name ';' | 'import' name 'as' name ';'`, the first token is `import` in both cases, so the sets of tokens that can begin each alternative overlap and no decision can be made. **Left factoring** rewrites `A -> alpha beta1 | alpha beta2` as `A -> alpha A2` with `A2 -> beta1 | beta2`, so the parser matches the common prefix unconditionally and only chooses once it reaches the point where the alternatives genuinely diverge. Here the shared prefix is `'import' name`, and the tails are `';'` and `'as' name ';'` — which now start with different tokens. Factoring is a separate rewrite from left-recursion elimination; a rule set aimed at a predictive parser usually needs both.
go deeper
Recall that a parser choosing from one token cannot pick between two alternatives that start with the same token, and that the fix is to hoist the shared part.
Perform the rewrite on a two-alternative rule, name the helper, and explain that the decision has been postponed to the point where the alternatives first differ.
Show where it stops working: unbounded shared prefixes, nullable tails interacting with what may follow, and tree-shape changes that break consumers walking the tree by position.
Weigh repeated factoring against a parser family that defers decisions — a heavily factored rule set is correct but becomes unreadable as a published specification.
## The problem: a choice made too early A predictive top-down parser expands one nonterminal at a time and must decide, **before** matching anything, which alternative of that nonterminal to use. It makes the decision from a bounded window of upcoming tokens — one token in the classic LL(1) case. That works only if the alternatives can be told apart by that window. The set of tokens that can begin a given alternative is its **first set**; if two alternatives of the same nonterminal have overlapping first sets, the parser has no basis for choosing. A shared leading *keyword* is the everyday version of this. Consider an interface-definition rule set with two forms of import directive: ``` directive -> 'import' name ';' | 'import' name 'as' name ';' ``` Both alternatives begin with `import`, and after the name, both can continue. The generator reports a conflict on this nonterminal, and it is right to: the distinguishing token (`;` versus `as`) sits three tokens in. ## The rewrite: left factoring Left factoring takes the **longest common prefix** of a group of alternatives and hoists it: 1. Find the longest sequence of symbols `alpha` that starts two or more alternatives of `A`. 2. Introduce a fresh nonterminal `A2`. 3. Replace those alternatives with one: `A -> alpha A2`, keeping any alternative that does not begin with `alpha` untouched. 4. Give `A2` the leftover tails: `A2 -> beta1 | beta2 | …`, using the empty alternative for a tail that is nothing. 5. Repeat — the tails may themselves share a shorter prefix, so factoring can need several rounds. Applied above: ``` directive -> 'import' name directive_tail directive_tail -> ';' | 'as' name ';' ``` Now the parser matches `import` and the name without deciding anything, and at `directive_tail` the two alternatives begin with different tokens. The decision was not made smarter; it was **postponed until the information exists**. ## Why postponing is legitimate Factoring is language preserving: every string derivable before is derivable after, with the same terminals in the same order. What changes is the derivation, and therefore the tree — an extra node for the helper nonterminal appears where the branch used to be. Nothing about the meaning of the input has moved. ## What factoring does not fix - **Left recursion.** `A -> A alpha | beta` has no shared prefix to hoist; it needs the tail rewrite instead. A rule set headed for a predictive parser typically needs both rewrites, in either order. - **A genuinely ambiguous rule set.** If one string has two distinct trees, factoring re-arranges the rules without collapsing the two readings. - **Conflicts that need more context than any fixed window.** If the two alternatives stay identical for an unbounded distance — a list of unknown length before the distinguishing token — no finite amount of factoring separates them, and the answer is a different parser family or a semantic decision made after the parse. - **A nullable tail's interaction with what follows.** If one factored tail can derive nothing, the parser must also check what may legally follow the whole construct, not just what can start the tail. ## Which parser families care | family | needs left factoring? | why | |---|---|---| | predictive top-down with fixed lookahead | yes | must choose the alternative before matching it | | backtracking top-down | no, for correctness | tries alternatives in turn, but re-scans the shared prefix each time | | ordered-choice top-down | no, for correctness | the first matching alternative wins, so overlap is resolved by order, not by lookahead | | LR-family bottom-up | no | the decision is deferred until the whole right-hand side has been seen | | general cubic parsers | no | all alternatives are pursued at once | The second and third rows carry a cost rather than an error: without factoring, the shared prefix is matched repeatedly, and with ordered choice a longer alternative placed after a shorter one that also matches can be masked entirely. ## The interview signal The answer that lands is the one that names the mechanism rather than the fix: *the parser must commit before it has the evidence, so move the commitment point to where the evidence is*. That framing explains why factoring works, why it sometimes has to be applied twice, and why some conflicts survive it.
- The factored tails still share a shorter prefix. What do you do?Factor again. Left factoring is applied repeatedly until no nonterminal has two alternatives with a common leading symbol. Each round hoists the longest current prefix and pushes the remainder into a further helper rule, so a deeply shared structure produces a short chain of helpers rather than one large rewrite.
- When can no amount of factoring make a rule set usable by a fixed-lookahead parser?When the alternatives stay identical for an unbounded distance — for example a list of arbitrary length before the token that distinguishes them. Factoring only moves the decision point a bounded number of symbols; if the evidence is arbitrarily far away, the answer is a parser family that defers or explores, not another rewrite.
- Does left factoring change the parse tree?Yes, in shape but not in content. The same terminals appear in the same order, but an extra node for the helper nonterminal sits where the branch used to be. Anything that walks the tree by position rather than by name must be updated, which is a common source of breakage after the rewrite.
saying these in an interview costs you the question
- Says factoring removes ambiguity from the rule set.
- Thinks one factoring round always suffices.
- Confuses left factoring with left-recursion elimination.
- Claims a bottom-up parser also needs the shared prefix factored.
- Believes factoring changes which strings are accepted.