LR Parsing

Another bottom-up path: LR can handle more grammars than LL and does not require eliminating left recursion—the cost is relying on a generator. Understanding each step of the upgrade from LR(0)→SLR→LR(1)→LALR is understanding the essence of yacc/bison.

Overview

Recursive Descent and LL is top-down: starting from the grammar, it derives the input. LR is bottom-up: starting from the input tokens, it gradually reduces (reduce) to grammar symbols until the entire input is reduced to the start symbol. LR is more powerful than LL—it can handle a strictly larger class of grammars than LL(1) and does not require eliminating left recursion. The cost of LR is that it cannot be hand-written (it is too complex); it must rely on a generator (yacc/bison/lalrpop) to automatically construct the parse table from the grammar. This article discusses each step of the upgrade of LR from LR(0) to LALR—each step addresses the "either too little or too much" problem of the previous step.

Structure of an LR Parser

An LR parser consists of three components, driven by input and stack:

Input: [id, +, id, *, id, $]         ← Token stream, $ is the end-of-input marker
Stack: [0, E, 1, +, 2, T, 5, ...]    ← Alternating state stack and grammar symbols
                  ↑ Top of stack

Each step consults the table:
  action(state, next_token) → shift s / reduce A→β / accept / error
  goto(state, nonterminal)  → next state

• shift: Push the next input token and the target state given by the action table onto the stack.
• reduce A→β: Pop 2×|β| elements from the top of the stack (where |β| is the number of grammar symbols on the right-hand side of the reduction rule; each symbol corresponds to a "symbol + state" pair on the stack), then push A onto the stack, determine the new state using the goto table, and push it onto the stack.
• accept: Successful parsing.
• error: Syntax error.

The parse table (action + goto) contains all the wisdom of LR parsing—the core work of a compiler generator is to construct this table.

Upgrading from LR(0) to LALR: Step by Step

LR(0): Basic but Impractical

An item is the core concept in LR theory: a dotted rule of the form A → α·β, where the dot indicates "α has been recognized, β has not yet been recognized."

Construction of the LR(0) parse table:

closure(I):   ← I is a set of items
    for each item A→α·Bβ in I:
        add all productions B→·γ to I (if not already in I)
    repeat until no more additions

goto(I, X):   ← X is a grammar symbol (terminal or nonterminal)
    for each item A→α·Xβ in I, add A→αX·β to J
    return closure(J)

Starting from the closure of the initial item S'→·S, repeatedly compute goto for each possible symbol X to produce new states until all states are saturated—this yields the LR(0) canonical collection.

Problem with LR(0): For A→α· (dot at the end, ready to reduce), it reduces under any input—completely ignoring the current token. This means many practical grammars (if-else with else, expressions with precedence) produce shift/reduce conflicts in LR(0). LR(0) can handle a very limited class of grammars; most practical languages require at least SLR(1) capability.

SLR(1): Reducing Unnecessary Reductions Using FOLLOW

SLR improvement: For item A→α· (ready to reduce), only reduce when the current token belongs to FOLLOW(A)—in other words, only reduce when "the grammar expects this token to appear after A."

LR(0) reduce:  Reduce A→α under all inputs
SLR reduce:    Reduce A→α only when next_token ∈ FOLLOW(A)

SLR solves most meaningless reductions in LR(0). However, FOLLOW is a global set—it is the same at all occurrences of A and does not distinguish "what the next token is when reducing A in this specific state." SLR still performs unnecessary reductions in certain contexts.

LR(1): Fully Precise, But State Explosion

LR(1) items not only record "where the dot is" but also record the lookahead—which symbol the next token should be when reducing this rule in this state.

LR(0) item:   A → α·β
LR(1) item:   [A → α·β, a]     ← a is the lookahead token

LR(1) closure is more complex than LR(0):

closure(I):
    for [A→α·Bβ, a] in I:
        for each production B→γ of B:
            for b ∈ FIRST(βa):        ← First token derivable from β, or a if β→ε
                add [B→·γ, b] to I (if not already in I)

LR(1) parse tables rarely have spurious conflicts—can handle a very wide class of grammars. The cost is state explosion: the same LR(0) state splits into several LR(1) states due to different lookaheads. For practical programming language grammars, the number of LR(1) states can be 5–10 times that of LR(0).

LALR(1): Merging States with the Same "Core", The Choice for the Real World

LALR (Look-Ahead LR) is a streamlined version of LR(1) and is the default algorithm for all practical LR generators (yacc/bison/lalrpop):

Take the set of LR(1) states, merge all states with the same LR(0) core (same items, different lookaheads)
  After merging, the lookahead for each state = union of lookaheads from the original states
  Build the parse table using the merged set of states

• LALR state count = LR(0) state count (much smaller than LR(1)), but parsing power is very close to LR(1).
• Cost: Merging may introduce new reduce/reduce conflicts—but this is very rare in practice and almost always indicates a problem with the grammar itself.

Why LALR is the industrial standard: Fewer states → smaller parse table → lower memory usage for the compiler, and acceptable time to build the parse table. Parser generators for most programming languages (on the LR path) use LALR(1).

Shift/Reduce and Reduce/Reduce Conflicts

Two types of conflicts may arise when generating LR tables:

• Shift/Reduce: A cell in the action table contains both shift and reduce. The classic case is the dangling else—when seeing if...if...else, should else shift (match the nearest if) or reduce (close the outer if)? Most generators default to preferring shift (matching the nearest if), which aligns with programming intuition.
• Reduce/Reduce: Two different reductions conflict in the same cell. This is always a signal of a grammar problem—the grammar has genuine ambiguity and must be modified or given precedence rules.

yacc/bison allows setting precedence for tokens and rules: %left '+' '-' → If expr + expr faces both shift+ and reduce in a state, precedence determines the behavior. This is more engineering-friendly than modifying the grammar to eliminate left recursion or ambiguity, but overuse can cause the grammar's semantics to subtly change based on precedence settings.

lalrpop: A Modern Alternative for LR

lalrpop is a Rust LR(1)/LALR(1) parser generator—the grammar is written directly in Rust source code, and the generated code is also Rust. The core difference from yacc/bison: lalrpop handles parameterized grammars (semantic actions with Rust types), while yacc/bison handle untyped grammars (semantic actions are C code blocks).

Example lalrpop grammar:

Expr: i32 = {
    <l:Expr> "+" <r:Term> => l + r,       ← Right operand uses Term type (automatically promoted to Expr)
    Term,
};

Term: i32 = {
    <l:Term> "*" <r:Factor> => l * r,
    Factor,
};

The generated LR table is embedded in the code generated at Rust compile time—essentially the same LALR algorithm as the C tables generated by yacc/bison. In lalrpop, Term is automatically promoted to Expr (because Expr includes the Term variant).

Error Recovery in LR Parsing

When an LR parser encounters an error token (the action table is empty for the current state), it must recover. Standard strategies:

• Panic mode: Pop states from the top of the stack until finding a state that has a valid shift for some token—skip the intermediate tokens and continue parsing. The skipped tokens are the "part consumed by the error."
• Error productions: Explicitly write Stmt → error ';' in the grammar, then the parser generator treats error as a special symbol that "matches any token"—the parser "eats garbage until encountering a synchronization marker" after an error.

This is harder to do well than LL error recovery—LR does not know which semantic structure is currently being parsed (it is "bottom-up" and does not know what the upper layer expects), so error messages are usually worse than hand-written recursive descent. This is also an important reason why industrial compilers prefer the LL path.

Choosing Between LL and LR

The industrial trend is LL hand-written (error messages + incremental) > LR generator (fewer new projects use it). The value of LR lies mainly in understanding existing systems (e.g., parsers for Bash/awk, a large amount of legacy code from the yacc era) and scenarios requiring rapid construction of DSL parsers.

References

• Dragon Book: Chapter 4, Sections 4.5–4.7 — Complete mathematical derivations of LR(0)/SLR/LR(1)/LALR
• Knuth (1965): "On the Translation of Languages from Left to Right" — The original paper on LR parsing
• lalrpop: https://github.com/lalrpop/lalrpop — Rust LALR(1) parser generator

Keywords: LR, LR(0), SLR, LR(1), LALR, shift, reduce, shift/reduce conflict, reduce/reduce conflict, item, closure, goto, parse table, yacc, bison, lalrpop, dangling else, precedence, associativity, panic mode, error productions