LR and LALR Parsing

An LR parser is a deterministic, stack-based bottom-up parser that reads input left to right (L) and produces a rightmost derivation in reverse. At each step it is in some configuration — a stack of grammar symbols interleaved with automaton states — and it consults the next input token (the lookahead) to choose one of two actions: shift the token onto the stack, or reduce the symbols at the top of the stack using some production `A → β`, replacing β with A. Parsing succeeds when the stack reduces to the start symbol and all input is consumed; it fails the moment no legal action exists, which is exactly why LR parsers, unlike general CFG parsers, can report errors at the earliest possible point. The central technical device is the LR item: a production with a dot marking a position, e.g. `A → α · β`, meaning "if we are here, we have already seen a string derivable from α and are hoping next to see one derivable from β." An LR(1) item additionally carries a lookahead symbol, `[A → α · β, a]`, meaning this configuration is only relevant if the token immediately following the eventual A is `a`. Items are grouped into sets of items (also called states) via two closure-and-transition operations — `closure` and `goto` — that mirror subset construction in NFA-to-DFA conversion. The collection of all reachable item sets, connected by goto edges, is the LR automaton; it is built once, offline, by the parser generator. Different LR variants differ only in how precisely they use lookahead to decide reduces. LR(0) ignores lookahead entirely for reduce decisions (usable only for very restricted grammars). SLR(1) ("Simple LR") reduces on `A → α·` whenever the lookahead lies in `FOLLOW(A)` — cheap to compute but sometimes too permissive, causing spurious conflicts. Canonical LR(1) carries a lookahead per item, computed contextually, giving the most precise (and most expensive) automaton. LALR(1) takes the canonical LR(1) automaton and merges states with identical cores (item sets ignoring lookaheads), recovering most of LR(1)'s power in an automaton the size of SLR(1)'s. This hierarchy — LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊆ LR(1) in grammar-class power — is the organizing fact of the whole theory.

Step 1 — Augment the grammar. Add a new start symbol `S'` with production `S' → S`, where `S` was the original start symbol. This guarantees a unique accepting state and gives the parser a clean "done" signal: when `S' → S ·` is reduced (conceptually — it is never actually reduced, it triggers `accept`).

Step 2 — Define closure. Given a set of items `I`, `closure(I)` adds, for every item `[A → α · B β, a]` in I and every production `B → γ`, the item `[B → · γ, b]` for every `b` in `FIRST(β a)` (for LR(1); for LR(0)/SLR(1), lookahead is simply dropped). This saturates the item set with everything that must also be "in progress" if `A → α · B β` is in progress, since parsing β starts by parsing some derivation of B.

Step 3 — Define goto. `goto(I, X)`, for grammar symbol X, is `closure` of the set of items `[A → α X · β, a]` for every `[A → α · X β, a]` in `I`. This is literally the subset-construction transition function: it moves the dot past X.

Step 4 — Build the canonical collection. Starting from `closure({[S' → · S, $]})`, repeatedly apply `goto` on every symbol to every existing state until no new states appear. This is exactly BFS/worklist subset construction and terminates because there are finitely many item sets over a finite grammar.

Step 5 — Fill ACTION and GOTO tables. For each state `I` and terminal `a`: if `[A → α · a β, b] ∈ I` and `goto(I, a) = J`, set `ACTION[I, a] = shift J`. If `[A → α ·, a] ∈ I` (A ≠ S'), set `ACTION[I, a] = reduce A → α`. If `[S' → S ·, $] ∈ I`, set `ACTION[I,$] = accept`. For nonterminal `X`, `GOTO[I, X] = goto(I, X)` when defined.

Step 6 — Run the shift-reduce engine. Maintain a stack of (state, symbol) pairs. Repeat: look at the top state and the current lookahead token; consult ACTION; shift, reduce, accept, or error accordingly. ``` function LR_PARSE(tokens): stack = [state0] # stack of states; symbols implied by transitions symbols = [] # parallel stack of grammar symbols (for AST building) i = 0 tokens.append('') # end marker loop: s = stack.top() a = tokens[i] action = ACTION[s][a] if action == "error": report_syntax_error(a); return FAIL else if action == shift(t): stack.push(t) symbols.push(a) i = i + 1 else if action == reduce(A -> beta): k = length(beta) pop k states from stack pop k symbols from symbols # these become children of the AST node for A s' = stack.top() stack.push(GOTO[s'][A]) symbols.push(A) # build AST node here, with popped children else if action == accept: return symbols.top() # the parse tree / AST root ``` ``` function CLOSURE(items): # LR(1) version result = items changed = true while changed: changed = false for [A -> alpha . B beta, a] in result: for each production B -> gamma: for b in FIRST(beta a): if [B -> . gamma, b] not in result: add it; changed = true return result function GOTO(items, X): moved = { [A -> alpha X . beta, a] : [A -> alpha . X beta, a] in items } return CLOSURE(moved) function BUILD_CANONICAL_COLLECTION(grammar): C = { CLOSURE({ [S' -> . S, ] }) } worklist = C while worklist not empty: I = worklist.pop() for each grammar symbol X: J = GOTO(I, X) if J not empty and J not in C: add J to C; add J to worklist return C ```

Each item set is a DFA state; each `goto` edge is a transition on a grammar symbol; states containing a "dot at the end" item generate reduce actions in ACTION. The stack in the parser always mirrors a path from the start state through this automaton, which is precisely why the algorithm is correct — see below.

Table construction. Let `n` be the grammar size (number of symbols across all productions) and `G` the number of distinct items. The number of possible item sets is bounded by `2^G` in the worst case, but in practice grammars used in compilers yield automata with a number of states linear to low-polynomial in grammar size. Constructing the canonical LR(1) collection takes `O(n · 2^n)` in the theoretical worst case (each state's closure can enumerate many lookahead-augmented items), which is why LR(1) tables can explode — this is the textbook justification for LALR. LALR(1) construction merges states sharing a core; the number of LALR states equals the number of LR(0) states, which is empirically close to linear in grammar size for real programming-language grammars. SLR(1) construction is cheapest: it reuses the LR(0) automaton and only needs `FOLLOW` sets, computable in `O(n^2)` (fixed-point iteration over a bounded lattice) in the worst case, typically much less.

Parsing time. Once tables are built, parsing itself is `O(m)` in the length `m` of the input: each input token is shifted exactly once, and each reduction pops a bounded number of stack entries corresponding to a fixed production length, so the total number of stack operations is `O(m)` amortized (a standard potential-function argument: shifts add to a budget that reduces spend, and each token contributes at most a constant number of pushes across its lifetime). Table lookups are `O(1)` with array-indexed ACTION/GOTO tables (or `O(log |Σ|)` with hashed tables for large alphabets). This linear-time guarantee, independent of grammar ambiguity subtleties, is the entire commercial argument for LR parsing over general CFG parsers (Earley/CYK, which are `O(m^3)` worst case).

Correctness argument. The key invariant is: > At every point during parsing, the sequence of states on the stack corresponds to a valid path through the LR automaton from the start state, and the grammar symbols on the stack form a viable prefix — a prefix of some right-sentential form that can still be extended to a full derivation of the augmented start symbol. This is proved by induction on parsing steps. Initially the stack holds only the start state, trivially a viable prefix (the empty string). A shift step extends the viable prefix by one terminal and moves along a `goto` edge that exists precisely because that terminal was expected by some item with the dot immediately before it — so the invariant is preserved by construction of `goto`. A reduce step replaces `α` (matching `A → α·` in the current state) with `A`; since the state before `α` was pushed has a `goto` on `A` defined (this is guaranteed because `A → α` was itself introduced via `closure` from some earlier item expecting `A`), the new top state is well defined and the new stack remains a valid path. The parser accepts exactly when the stack spells out `S` and lookahead is `$`, matching the unique item `S' → S ·`, which by the invariant means the entire input is a sentence of the augmented grammar, i.e., of the original grammar. The lookahead refinement (SLR/LALR/canonical LR(1)) only affects when reduce actions are chosen among competing options; it never allows an invalid reduce, because a reduce action is only listed in ACTION at all when the corresponding complete item (with matching lookahead, for LR(1)/LALR(1)) exists in that state. The soundness of restricting lookahead to `FOLLOW(A)` in SLR follows because any valid rightmost derivation reducing `A → α` at this point must be followed by a token in `FOLLOW(A)`; the incompleteness of SLR arises because `FOLLOW(A)` is context-insensitive — it merges lookahead information across all contexts where A appears, which can incorrectly permit a reduce that is only valid in some contexts, producing a spurious conflict that canonical LR(1) (context-sensitive lookahead) avoids.

The LALR merge and its risk. Merging LR(1) states with identical cores can only ever lose precision, never introduce a shift-reduce conflict that wasn't structurally present (a theorem due to DeRemer): merging preserves the shift actions exactly (cores are identical, so the same gotos exist) and can only take the union of lookaheads on reduce items. The one danger is a new reduce-reduce conflict: if two originally distinct LR(1) states had, say, `[A → α·, a]` in one and `[B → α·, b]` in the other with disjoint lookaheads, merging can create a state containing both items with lookaheads now overlapping in the union. This is rare in practical grammars (it does not occur for any standard programming-language grammar construct), which is why LALR(1) is the workhorse in Yacc/Bison despite this theoretical caveat.

Grammar (already augmented), a minimal expression grammar: ``` (0) S' -> E (1) E -> E + T (2) E -> T (3) T -> id ``` Input: `id + id `. Building the automaton (abbreviated, matching the figure): `I0 = closure({[S'\to \cdot E,]})` contains items for `E→·E+T`, `E→·T`, `T→·id`, all with lookahead `$` (from I0's context) — but note `E\to \cdot E+T` also needs lookahead `+` because after reducing the inner E, a `+` may follow: closure propagates `FIRST(+T$) = {+}` for the item `[E→·E+T, ]`'s own sub-items, so `T\to \cdot id` in fact gets lookaheads `{, +}`.

Every reduction step in this trace corresponds to constructing one AST node — step 2 builds a leaf `id`, step 6 builds another leaf, step 7 builds the interior node `E+T` with the two previously built subtrees as children — which is exactly the mechanism used to hand a completed Abstract Syntax Trees structure to later compiler phases. Notice that the crucial disambiguating fact is in step 2: the parser reduces `T → id` under lookahead `+` (not shift, since `id` has no outgoing shift item at that point) — this is a decision only possible because the automaton correctly tracked that `id` is complete once no further extension (`.` at the end) exists in that state.

The LR(k) concept originates with Donald Knuth's foundational 1965 analysis of deterministic bottom-up parsing, which characterized exactly which context-free languages admit a deterministic left-to-right, rightmost-derivation-in-reverse parser with bounded lookahead. Knuth's original construction was too large for practical compilers; the subsequent decade of work by Frank DeRemer produced SLR(1) and, crucially, the LALR(1) merge that made table sizes tractable enough for real machines, directly enabling tools like Yacc.

LALR(1) parser generators are the backbone of production compiler front ends: Yacc and Bison generate parsers for C, historical Unix tools, and countless domain-specific languages; many SQL and configuration-language parsers still emit LALR grammars by hand or via Bison. GCC's early C and C++ front ends used Bison-generated LALR parsers for years before hand-written recursive-descent replacements were adopted for better error messages. Java's `javacc`-adjacent and ANTLR ecosystems reference LR/LALR theory even when using LL(*) generation, because the conflict-detection vocabulary (shift-reduce, reduce-reduce) is universal. Database query parsers, protocol description languages, and many "little languages" embedded in build systems (Make-like DSLs, some templating engines) rely on LALR tooling because the theory gives a mechanically checkable guarantee: if the table builds with zero conflicts, the grammar is unambiguous under the parser's own resolution rules, a guarantee unavailable from ad hoc hand-rolled parsers. Once a program is reduced through this automaton, the popped children at each reduce step are exactly the raw material assembled into an Abstract Syntax Trees for the next compiler phase, connecting this article directly to Bottom-Up Parsing on one side and tree-based semantic analysis on the other.

Ask the tutor: Can you walk through building the full LALR(1) table for a grammar with a real dangling-else conflict, and show exactly how precedence declarations resolve it?