LR Parsing

LR is Left-to-right scan, Rightmost derivation — in reverse. That last clause is the whole idea and it is worth taking slowly.

A rightmost derivation of 1 + 2 * 3 expands the rightmost nonterminal at each step. Run it backwards — from the tokens to the start symbol — and each step becomes a *reduction*: a substring on the stack matching some production's right-hand side is replaced by its left-hand side. The parser never derives; it un-derives. And because it works from the input inward, it never has to guess which production it is in. It accumulates tokens until the answer is unambiguous, and only then commits.

That is the source of every advantage LR has. An LL parser must pick a production for expr before it has seen anything of the expression; an LR parser can shift 1, +, 2, *, 3 and decide afterwards. Left recursion, which prevents a top-down parser from making progress at all, is for an LR parser simply the most natural way to write a repeated construct — it keeps the stack shallow, because each reduction consumes the accumulated left side immediately.

An item is a production with a dot marking how far the parser has got: T -> T • '*' F means "I have seen a T, and if the next token is * I can continue in this production". A state of the LR automaton is a *set* of items — all the productions the parser might simultaneously be in the middle of, given everything on the stack so far.

Two operations build the automaton. Closure: if a state contains E -> E '+' • T, then the parser is about to start a T, so every production of T is added with the dot at the front — T -> • T '*' F and T -> • F — and transitively their own. Goto: from a state, moving the dot past a symbol X gives the state you reach after that symbol is on the stack. Do this from the start item until no new sets appear and you have the automaton. The parse table is a direct transcription of it.

The consequence worth holding onto: a state is a statement of *ambient possibility*. When the parser is in a state containing four items, it is genuinely tracking four hypotheses at once, and it has not committed to any of them. That is why it can handle grammars LL cannot, and also why its error messages are poor — when something goes wrong, the parser can say which state it was in and which tokens that state permits, but it cannot say "you were in the middle of an argument list", because it was in the middle of four things.

LR is a family, not an algorithm, and the members differ only in how much lookahead information the states carry — which trades table size against the grammars accepted.

LR(0) uses no lookahead: it reduces whenever a state contains a completed item, which conflicts almost immediately on real grammars. SLR(1) reduces by A -> α only when the lookahead is in FOLLOW(A), which is cheap and resolves many conflicts. LR(1) carries an explicit lookahead set on every item, which is maximally precise and produces enormous tables. LALR(1) merges LR(1) states that have the same item cores, keeping LR(0)-sized tables with most of LR(1)'s power — this is what Yacc and Bison generate by default, and it is the reason LALR is the LR variant that actually shipped. The merge is not free: it can introduce reduce/reduce conflicts that pure LR(1) would not have, though never shift/reduce conflicts.

GLR abandons determinism entirely: when a state has a conflict, it forks and pursues every interpretation in parallel, discarding branches that die. That accepts *any* context-free grammar, including ambiguous ones — at the cost of potentially returning several parses, and of worst-case cubic time. Bison has a GLR mode; tree-sitter is built on a GLR-family algorithm precisely because real source code under edit is frequently ambiguous or broken.

A state contains a completed item A -> α • (so the parser *could* reduce) and also an item B -> β • t γ with the lookahead t after the dot (so the parser *could* shift t). Both are consistent with everything seen so far. The automaton has no basis to choose. That is a shift/reduce conflict, and it means the grammar is genuinely ambiguous at this point, or requires more lookahead than this variant carries.

The canonical instance is the dangling else. With stmt -> 'if' expr 'then' stmt | 'if' expr 'then' stmt 'else' stmt, parsing if a then if b then c else d reaches a state holding a stack of if expr then stmt with else as the lookahead. Reducing gives the else to the *outer* if; shifting gives it to the inner one. Both are valid derivations of the same input under this grammar — the grammar is ambiguous, and the conflict is the tool correctly reporting that.

Generators resolve it by default rather than refusing: Yacc and Bison prefer shift, which attaches the else to the nearest if — which happens to be what C, Java and almost every language specify, so the default is right and the warning is noise. That is a trap worth naming: because the default is usually correct, teams learn to ignore conflict warnings, and then a genuine ambiguity in a new construct is resolved arbitrarily and nobody notices. The disciplined practice is %expect N — declare the number of conflicts you have accepted, and let the build fail when the count changes.

A reduce/reduce conflict is worse: two completed items in the same state, so the parser has two different productions it could reduce by and no way to choose. There is no sensible default (Bison picks the production listed first), and it almost always means the grammar is genuinely ambiguous or that LALR state merging has lost information that LR(1) would have kept.

There is a third route, and it is the one most real Yacc grammars take. Write the expression grammar in its ambiguous one-line form — E -> E '+' E | E '*' E | NUMBER — which conflicts everywhere, and then declare precedence and associativity *outside* the productions with %left '+' and %left '*'. The generator uses those declarations to resolve every shift/reduce conflict in the expression states: on a conflict, compare the precedence of the production being reduced against the precedence of the lookahead token, and shift if the token binds tighter.

This is the same computation [[pratt-parsing]] performs with binding powers, done at table-construction time rather than at parse time. It is genuinely good engineering — a fifteen-level C expression grammar becomes a handful of productions plus fifteen declaration lines instead of fifteen stratified nonterminals — and it has one specific cost: the grammar in the file no longer describes the language on its own. Read the productions alone and 1 + 2 * 3 is ambiguous. The declarations are load-bearing, and a reader who skips them draws the wrong tree.