Chapter 10

LALR — The Best of Both Worlds

Merge CLR states that share the same LR(0) core. Same state count as SLR, nearly the power of CLR. The algorithm behind yacc, bison, and most real-world parser generators.

⚡ LALR — The Best of Both Worlds
Problem CLR has too many states for large grammars — state explosion makes it impractical in real tools.
Fix Merge CLR states that have the same LR(0) core (same productions + dot positions, different lookaheads). Combine their lookaheads by set union.
Result Same number of states as SLR (LR(0) collection), with nearly the conflict-resolving power of CLR.
Used by yacc, GNU bison, ANTLR (v3), CUP, and most real-world parser generators. The de-facto standard for production parsers.
Edge case Merging can introduce reduce/reduce conflicts (two reductions compete for the same lookahead after merging). Rare in practice for well-designed grammars.
Section 1

The CLR State Count Problem

CLR produces many states that have the same LR(0) core but different lookaheads. These states do the same parsing work — they only differ in when to reduce.

Consider the LR0 grammar S→CC, C→cC|d. CLR produces separate states for each unique (core, lookahead) combination. Below is a concrete example of two states that CLR distinguishes but LALR merges:

CLR State A
I4 (example)
[C → d•, c]
I7 (example)
[C → d•, $]
⟹
LALR Merged State
I4 (merged)
[C → d•, c / $]
Lookaheads: union of both states
Key Observation: Both CLR state A and state B have the same core: {C → d•}. The only difference is the lookahead. When we merge them, we combine the lookaheads: {c} ∪ {$} = {c, $}. The merged state behaves identically to CLR for all inputs that this grammar can generate — as long as no reduce/reduce conflict is introduced.

When Can Merging Introduce a Conflict?

Safe merge (most cases):
State A reduces P1 on {a, b}
State B reduces P2 on {c, d}
Disjoint lookaheads → merge is safe.
Dangerous merge (rare):
State A reduces P1 on {a}
State B reduces P2 on {a}
Same lookahead 'a' → reduce/reduce conflict after merge!
Section 2

Identifying and Grouping Mergeable States

States are mergeable when they have the same LR(0) core: the set of (production, dot) pairs, ignoring lookaheads.

Core Key: For each state, we compute a "core key" by listing all (production_id, dot_position) pairs sorted. States with the same core key are candidates for merging. Only one CLR state will survive per core key group.
Section 3

Merge Process — Step by Step

Watch how CLR states are grouped by core and their lookaheads are unioned to form LALR states.

Step 1 / …
Section 4

LALR Parse Table

Built from the merged LALR states. Compare with the CLR table — for this grammar they are identical, confirming LALR introduces no extra conflicts here.

Shift (s#) Reduce (r#) Goto (#) Accept
Productions:
Building LALR table…
Section 5

LALR State Collection

Each LALR state shows which CLR states were merged into it and the combined lookaheads. Fewer states than CLR, same structure as SLR's LR(0) collection.

Computing LALR states…
Section 6

Parsing Simulation

Simulating input id = id $ with the LALR table. Demonstrates that LALR accepts the same language as CLR for this grammar.

Input tokens: id  =  id  $
Stack (state) Remaining Input Action Note
Section 7

LALR vs CLR — Detailed Comparison

Understanding the trade-offs between the two approaches.

Property CLR (Canonical LR(1)) LALR
Lookahead source Exact per-item lookahead (computed during closure) Union of merged states' lookaheads
State count Larger — one state per unique (core, lookahead) combination Fewer — same as LR(0)/SLR (one state per core)
Memory usage Higher (more states → larger tables) Lower (fewer states → compact tables)
Expressive power Slightly more — can parse all LALR(1) grammars + a few more Slightly less — may fail on some LR(1) grammars
Shift/reduce conflicts Almost none (exact lookaheads prevent false conflicts) Almost none (union lookaheads still precise enough usually)
Reduce/reduce conflicts Almost none for unambiguous grammars Rare but possible (introduced by merging incompatible lookaheads)
Build time Longer (more states to compute) Shorter (or equivalent via merging CLR states)
Used in practice Rarely alone (too expensive for large grammars) ✓ yacc, bison, CUP, ANTLR, most production tools
State Count for This Grammar:
Section 8

The Full LR Parser Evolution Chain

From the simple but conflict-prone LR(0) to the practical powerhouse LALR — each step solves the previous approach's key weakness.

LR(0)
Foundation — no lookahead at all. Reduce on every token when a reduction is possible.
States: fewest
Problem: Shift/reduce conflicts (no lookahead to decide when to reduce)
↓
SLR (Simple LR)
Uses FOLLOW sets to restrict when to reduce. Reduces only when next token ∈ FOLLOW(LHS).
States: same as LR(0)
Problem: FOLLOW sets too coarse — global, not context-sensitive → false conflicts
↓
CLR (Canonical LR(1))
Embeds exact lookaheads inside each LR item. [A→α•β, a]: reduce only on 'a'. Eliminates false conflicts.
States: most (explodes)
Problem: State explosion — too many states for practical large grammars
↓
LALR (Look-Ahead LR)
Merges CLR states with same LR(0) core. Unions lookaheads. Same state count as SLR, nearly CLR's power.
States: same as SLR ✓
✓ LALR is the sweet spot — used by yacc, GNU bison, and most production parser generators.
For even harder grammars: GLR (generalized LR) parsing handles arbitrary context-free grammars at the cost of ambiguity handling.