skip to content

What does a bottom-up LR parser know at the moment it commits to a rule that a top-down LL parser does not?

level: middleimportance: should knowfreq 50%

answer

  1. same input, different moment of choice
  2. left edge versus right edge of a rule
  3. how much of the rule has been seen
  4. the whole right-hand side, plus lookahead
  5. superset of evidence, superset of grammars

basics

~20 s

An LR parser commits only after the whole right-hand side is already on its stack, plus the lookahead beyond it. An LL parser must choose the rule before reading any of it, from lookahead alone. More evidence, later decision.

solid answer

~50 s

The difference is **when the decision happens**. A top-down LL(k) parser stands at the start of a nonterminal and must pick which production to expand using only the left context and `k` lookahead tokens — it decides before consuming a single symbol of the rule. A bottom-up LR(k) parser postpones that choice until the entire right-hand side has been shifted onto the stack, and only then reduces, with `k` tokens of lookahead still available beyond it. Strictly more information is on hand at the commit point, which is why every LL(k) grammar is also an LR(k) grammar and not the other way round; the LR(1) grammars cover every deterministic context-free language. The price is that the decision procedure lives in a generated table rather than in readable code, and an error is reported where the reduction fails rather than where the writer's intent diverged.

go deeper

for a junior

Remember the one-line contrast: top-down picks the rule before reading it, bottom-up picks it after the whole rule has been read. Everything else follows from that.

for a middle

Explain why the later commit means strictly more evidence, and state the containment in the right direction: every LL(k) grammar is LR(k), not the reverse.

for a senior

Argue the engineering consequence: better grammar coverage against weaker error locality and a generated artefact, and be able to say which one a given language project should pay for.

for a principal

Own the choice for a language that will outlive the team: how often the grammar changes, who writes the error messages, and whether the deferred commit is buying coverage you will actually use.

## Two parsers, two commit points Both families read input left to right and both are deterministic — no backtracking, no guessing. They differ in **where in a rule the decision is made**. - A **top-down LL(k)** parser is positioned at a nonterminal and must choose one of its productions using the left context plus `k` unread tokens. It commits at the *left edge* of the rule and then has to make the rest come true. - A **bottom-up LR(k)** parser shifts symbols without committing to anything, and chooses a rule only when that rule's entire right-hand side is sitting on the stack, with `k` tokens of lookahead still ahead of it. It commits at the *right edge*. ## Why the later commit is strictly more informed When an LR parser reduces `A -> beta`, it has already seen all of `beta` **and** the lookahead. When an LL parser picks `A -> beta`, it has seen only the lookahead. Anything the LL parser could distinguish, the LR parser could distinguish too — it has a superset of the evidence. That containment is not a rule of thumb; it is why the grammar classes nest: | | Decision made | Evidence at commit | Class relation | |---|---|---|---| | LL(k) | before the right-hand side | `k` lookahead tokens | every LL(k) grammar is LR(k) | | LR(k) | after the right-hand side | the whole right-hand side plus `k` tokens | some LR(k) grammars are not LL(k) | The language-level statement is the sharper one: the LR(1) grammars generate exactly the **deterministic context-free languages**, while the languages with an LL(k) grammar are a proper subset of those. ## What the deferral concretely rescues 1. **Rules that share a long prefix.** Two rules that look identical for several symbols are a crisis for a parser that must choose at the left edge, and a non-event for one that chooses at the right edge — it shifts the shared symbols and decides afterwards. 2. **Rules whose left end recurses into the same nonterminal.** A top-down parser has to restructure the rule set before it can proceed at all; a bottom-up parser builds the recursive part on the stack and reduces it iteratively. 3. **Constructs distinguished by their ending.** When two forms differ only in a trailing element, the deferred commit sees that element before choosing. (The mechanics of restructuring a rule set, and of prediction tables and their conflicts, belong to the grammar-transformation and recursive-descent neighbours; here the point is only that the deferral removes the need.) ## What the deferral does not buy - **Ambiguity is still fatal.** If one string has two trees, no amount of deferral picks one; the generator reports a conflict instead. The extra power is over *how a rule set is written*, not over rule sets that mean two things. - **More lookahead is not free.** Going from one token to more explodes the table, which is why practical constructions stay at one. - **Diagnostics get harder.** A top-down parser can say "I was expecting a type here" because a function frame names the construct it is inside. A table-driven parser knows only a state number, so useful messages must be reconstructed from the state's expected-token set. - **Readability moves.** The grammar becomes the source of truth and the parser becomes generated output — good for a language that changes often, awkward when you want to step through the parse. ## The interview-shaped summary If asked to compare the families in one breath: LL decides early from little evidence and produces code you can read; LR decides late from more evidence and accepts more grammars, at the cost of a generated table and weaker error locality. If someone claims LR is "more powerful" without saying **why**, the missing sentence is the one about the commit point. - The evidence available to LR at commit time is a superset of LL's. - Superset evidence means every LL(k) grammar is handled, plus more. - The extra grammars are exactly the ones whose identity is only clear at or after the right edge.

  • Does the later commit point let a bottom-up parser handle an ambiguous rule set?
    No. Ambiguity means one input has two valid trees, and a deterministic parser must pick one action per state and lookahead. The generator reports a conflict instead, and resolving it by default silently selects one of the readings rather than supporting both.
  • If LR accepts strictly more grammars, why is a hand-written top-down parser still a common choice?
    Because parser code you can read and step through is worth a lot: error messages can name the construct being parsed, recovery can be tailored per rule, and there is no generation step. The grammar restriction is usually acceptable for a language you control.
  • What does 'deterministic context-free' mean in this comparison?
    It names the languages a pushdown recognizer can accept without guessing — one move per configuration. The LR(1) grammars generate exactly those, so a language outside that set cannot be parsed deterministically at all, however the rules are rewritten.

saying these in an interview costs you the question

  • Says LR is more powerful without naming the commit point
  • Claims a bottom-up parser can handle ambiguous rule sets
  • Believes every LR(1) grammar is also LL(1)
  • Thinks the difference is scanning direction rather than decision timing
  • Assumes more lookahead is a free upgrade for either family