Lesson 3.3 — LALR(1): merging LR(1) states, and DeRemer–Pennello lookaheads¶
Techniques: LALR(1) by merging canonical LR(1) states with equal cores (DeRemer 1969; LaLonde, Lee and Horning 1971; Anderson, Eve and Horning 1973); LALR(1) lookaheads by DeRemer and Pennello's relations and the Digraph algorithm (1982) · Pebble implements: nothing in
pebblec; the lab builds both and checks that they agree (exercise E3) · Lab:labs/ch03-lr-toolkit(SPEC;Method::LALR1Merge,Method::LALR1;lr report --method lalr-merge|lalr) · Prerequisites: Lesson 3.2; the Digraph algorithm in Lesson 2.2 · Time: 5 hours
Canonical LR(1) splits a state whenever two contexts disagree on lookaheads, even when the disagreement never matters. LALR(1) ("look-ahead LR") keeps the LR(0) automaton and gives each reduce item the union of its canonical lookaheads: sharper than FOLLOW, as small as LR(0). This is what yacc, Bison (by default), Menhir's --lalr, lemon and tree-sitter build. You can compute it two ways — build LR(1) and merge, or never build LR(1) and solve a system of set equations over the LR(0) automaton — and the two give the same sets (Theorem 3.3.12). The price of merging is a new kind of conflict that exists in no canonical state: the "mysterious" reduce/reduce conflict.
1. Problem and motivation¶
Input: the LR(0) automaton. Output: for every reduce item \([A \to \omega \bullet]\) in every state \(q\), the set \(\mathrm{LA}(q, A \to \omega)\) of tokens on which to reduce, as precise as canonical LR(1) allows without splitting states.
LALR(1) by merging LR(1) states¶
DeRemer defined LALR(k) in his 1969 thesis [DeR69] as the LR(k) automaton with states of equal core merged. The first efficient LALR generators avoided building LR(1) first: LaLonde, Lee and Horning's generator [LLH71] computed the lookaheads on the LR(0) automaton, Anderson, Eve and Horning [AEH73] showed how to make the resulting LR tables small (compact encodings and space optimizations), and Johnson's yacc (1975) [Joh75] made the method ubiquitous: its channel/propagation algorithm is the one in the Dragon book [ALSU07 §4.7.5]. Merging is still the clearest definition, and the easiest to test: this lesson's lab builds it by brute force and checks the efficient method against it.
DeRemer–Pennello lookaheads¶
DeRemer and Pennello [DP82] reduced the lookahead computation to two instances of one problem, "each set is its own direct part plus the union of the sets it is related to", solved in linear time by a depth-first search that treats strongly connected components as units (Digraph, the same algorithm you used for FOLLOW in Lesson 2.2). The relations — reads, includes, lookback — live on the nonterminal transitions of the LR(0) automaton. Bison's src/lalr.c implements exactly this (the real-world box in §3).
2. Definitions and algorithms¶
\(\mathcal{A}_0 = (Q, \delta)\) is the LR(0) automaton, \(\mathcal{A}_1\) the canonical LR(1) automaton (Definition 3.2.3). For a state \(q\) and a string \(\beta\), \(q \xrightarrow{\beta} r\) means \(\delta^{*}(q, \beta) = r\).
Definition 3.3.1 (Merging by core)
For an LR(1) state \(J\), \(\mathrm{core}(J)\) is its set of LR(0) items (Definition 3.2.3). Merging replaces every group of LR(1) states with the same core by one state: its items are the core, and the lookahead set of each item is the union of that item's lookaheads over the group.
Definition 3.3.2 (LALR(1) lookaheads and table)
For an LR(0) state \(q\) and a completed item \([A \to \omega \bullet] \in q\),
The LALR(1) table is Definition 3.2.1 with \(\mathrm{LA}(q, A \to \omega)\) in place of \(\mathrm{FOLLOW}(A)\). \(G\) is LALR(1) if it has no conflict.
Definition 3.3.3 (DeRemer–Pennello relations [DP82])
Let \(\mathcal{N} = \{\, (p, A) \mid A \in N,\ \delta(p, A) \text{ defined} \,\}\) be the nonterminal transitions of \(\mathcal{A}_0\). For \((p, A), (p', B) \in \mathcal{N}\):
- \(\mathrm{DR}(p, A) = \{\, t \in T \mid \delta(\delta(p, A), t) \text{ defined} \,\}\), plus \(\$\) for the transition \((q_0, S)\) (its target holds \(S' \to S \bullet\), which "reads" \(\$\));
- \((p, A)\) reads \((r, C)\) iff \(r = \delta(p, A)\), \((r, C) \in \mathcal{N}\) and \(C\) is nullable;
- \((p, A)\) includes \((p', B)\) iff there is a production \(B \to \beta A \gamma\) with \(\gamma\) nullable and \(p' \xrightarrow{\beta} p\);
- \((q, A \to \omega)\) lookback \((p, A)\) iff \(p \xrightarrow{\omega} q\).
The sets are the least solutions of
Definition 3.3.4 (The Digraph problem)
Given a finite set \(X\), a relation \(R \subseteq X \times X\) and sets \(F'(x)\), find the least sets \(F(x)\) with \(F(x) = F'(x) \cup \bigcup_{x R y} F(y)\). Equivalently \(F(x) = \bigcup \{\, F'(y) \mid x R^{*} y \,\}\).
LALR(1) by merging LR(1) states¶
Algorithm 3.3.5 (LALR(1) by merging)
- Input: the LR(0) automaton and the canonical LR(1) automaton.
- Output: the LR(0) automaton whose items carry lookahead sets.
- Precondition: both automata built by Algorithms 3.1.10 and 3.2.8.
- Postcondition: every item of LR(0) state \(q\) carries the union of its lookaheads over the LR(1) states with core \(q\); on completed items this is \(\mathrm{LA}(q, \cdot)\) of Definition 3.3.2. States keep their LR(0) numbers.
- Invariant: after processing LR(1) states \(J_1..J_m\), each merged set is the union over those of them with that core.
Reference solution: solutions/labs/ch03-lr-toolkit/src/Lalr.cpp (lalrByMerging); oracle lr.lalr_by_merging.
DeRemer–Pennello lookaheads¶
Algorithm 3.3.6 (Digraph [DP82])
- Input: \(X\), \(R\), \(F'\) as in Definition 3.3.4.
- Output: \(F\).
- Precondition: none (\(R\) may have cycles).
- Postcondition: \(F(x) = \bigcup \{ F'(y) : x R^{*} y \}\) for all \(x\) (Theorem 3.3.10).
- Invariant: when
Traverse(x)returns, \(F(x)\) is final unless \(x\) lies in an SCC whose root is still on the stack; \(N[x] = \infty\) marks finished nodes.
function Digraph(X, R, F'):
S ← empty stack; N[x] ← 0 for all x
for x in X: if N[x] = 0: Traverse(x)
function Traverse(x):
push x on S; d ← |S|; N[x] ← d; F(x) ← F'(x)
for each y with x R y:
if N[y] = 0: Traverse(y)
N[x] ← min(N[x], N[y]); F(x) ← F(x) ∪ F(y)
if N[x] = d: # x is the root of an SCC
repeat: top ← pop S; N[top] ← ∞; F(top) ← F(x)
until top = x
Algorithm 3.3.7 (LALR(1) lookaheads by DeRemer–Pennello)
- Input: the LR(0) automaton; nullable.
- Output: \(\mathrm{LA}(q, A \to \omega)\) for every completed item.
- Precondition: \(G\) augmented and reduced.
- Postcondition: the sets of Definition 3.3.3, equal to Definition 3.3.2 (Theorem 3.3.12).
- Invariant: as in Digraph.
Reference solution: lalrByDeRemerPennello in solutions/labs/ch03-lr-toolkit/src/Lalr.cpp; oracle lr.deremer_pennello, which also returns every relation (used by ./course drill lalr-lookaheads).
function DeRemerPennello(A0):
𝒩 ← nonterminal transitions (p, A) in state order, then symbol order
for (p, A) in 𝒩:
r ← δ(p, A)
DR(p, A) ← { t ∈ T : δ(r, t) defined } ∪ ({$} if (p, A) = (q0, S) else ∅)
reads(p, A) ← { (r, C) ∈ 𝒩 : C nullable }
Read ← Digraph(𝒩, reads, DR)
for (p', B) in 𝒩, for each production B → X1 … Xn, for each k with Xk ∈ N:
if X(k+1) … Xn all nullable:
p ← δ*(p', X1 … X(k−1)); if (p, Xk) ∈ 𝒩: add (p', B) to includes(p, Xk)
Follow ← Digraph(𝒩, includes, Read)
for (p, A) in 𝒩, for each production A → ω:
q ← δ*(p, ω); LA(q, A → ω) ← LA(q, A → ω) ∪ Follow(p, A) # lookback
return LA
3. Worked example¶
Running example: \((1)\ S \to L = R\), \((2)\ S \to R\), \((3)\ L \to *\,R\), \((4)\ L \to \mathit{id}\), \((5)\ R \to L\), with the LR(0) states I0–I9 of Lesson 3.1 and the 14 canonical states of Lesson 3.2.
LALR(1) by merging LR(1) states on the running example¶
The canonical states group by core (Lesson 3.2 §3): I1 ← {1, 9}, I2 ← {2, 10}, I6 ← {6, 11}, I7 ← {7, 13}; every other LR(0) state has one LR(1) state. Merged lookaheads of the completed items:
| LR(0) state | item | from LR(1) states | merged \(\mathrm{LA}\) | SLR (FOLLOW) |
|---|---|---|---|---|
| I2 | \(L \to \mathit{id} \bullet\) | 2: \(\{=, \$\}\); 10: \(\{\$\}\) | \(\{=, \$\}\) | \(\{=, \$\}\) |
| I3 | \(S' \to S \bullet\) | 3: \(\{\$\}\) | \(\{\$\}\) (accept) | – |
| I4 | \(R \to L \bullet\) | 4: \(\{\$\}\) | \(\{\$\}\) | \(\{=, \$\}\) |
| I5 | \(S \to R \bullet\) | 5: \(\{\$\}\) | \(\{\$\}\) | \(\{\$\}\) |
| I6 | \(R \to L \bullet\) | 6: \(\{=, \$\}\); 11: \(\{\$\}\) | \(\{=, \$\}\) | \(\{=, \$\}\) |
| I7 | \(L \to * R \bullet\) | 7: \(\{=, \$\}\); 13: \(\{\$\}\) | \(\{=, \$\}\) | \(\{=, \$\}\) |
| I9 | \(S \to L = R \bullet\) | 12: \(\{\$\}\) | \(\{\$\}\) | \(\{\$\}\) |
I4 was never merged, so it keeps the sharp set \(\{\$\}\): the running example is LALR(1). Now tests/ch03/Inputs/nonlalr.grammar, \(S \to a\,A\,d \mid b\,B\,d \mid a\,B\,e \mid b\,A\,e\), \(A \to c\), \(B \to c\) [ALSU07, Ex. 4.58]: the canonical states after \(a\,c\) and \(b\,c\) are
| LR(1) state | items |
|---|---|
| 4 (after \(a\,c\)) | \([A \to c \bullet,\ d]\), \([B \to c \bullet,\ e]\) |
| 7 (after \(b\,c\)) | \([A \to c \bullet,\ e]\), \([B \to c \bullet,\ d]\) |
Both have the core \(\{A \to c \bullet, B \to c \bullet\}\) (LR(0) state I4). Merged: \(\mathrm{LA} = \{d, e\}\) for both items, so ACTION\([4, d]\) and ACTION\([4, e]\) each hold r5 and r6: two reduce/reduce conflicts that neither canonical state has. The grammar is LR(1) but not LALR(1).
DeRemer–Pennello lookaheads on the running example¶
The seven nonterminal transitions and their relations (oracle deremer_pennello; no nonterminal is nullable, so reads is empty and Read = DR):
| \((p, A)\) | DR = Read | includes | Follow |
|---|---|---|---|
| (0, S) | \(\{\$\}\) | – | \(\{\$\}\) |
| (0, L) | \(\{=\}\) | (0, R) | \(\{=, \$\}\) |
| (0, R) | \(\{\}\) | (0, S) | \(\{\$\}\) |
| (1, L) | \(\{\}\) | (1, R) | \(\{=, \$\}\) |
| (1, R) | \(\{\}\) | (0, L), (1, L), (8, L) | \(\{=, \$\}\) |
| (8, L) | \(\{\}\) | (8, R) | \(\{\$\}\) |
| (8, R) | \(\{\}\) | (0, S) | \(\{\$\}\) |
Why these edges: \(R \to L\) ends in \(L\), so \((p, L)\) includes \((p, R)\); \(L \to *\,R\) ends in \(R\) and I0 → I1, I1 → I1, I8 → I1 on *, so \((1, R)\) includes \((0, L)\), \((1, L)\), \((8, L)\); \(S \to R\) and \(S \to L = R\) end in \(R\), so \((0, R)\) includes \((0, S)\) and \((8, R)\) includes \((0, S)\) (I0 → I4 → I8 spells \(L\,=\)). \((0, L)\) has \(\{=\}\) directly because I4 shifts =.
Digraph on includes (Algorithm 3.3.6, nodes in the order of the table; the stack is bottom first):
| step | event | node | \(N\) | stack | \(F\) |
|---|---|---|---|---|---|
| 1 | enter | (0, S) | 1 | (0,S) | \(\{\$\}\) |
| 2 | SCC done | (0, S) | ∞ | – | \(\{\$\}\) |
| 3 | enter | (0, L) | 1 | (0,L) | \(\{=\}\) |
| 4 | enter | (0, R) | 2 | (0,L) (0,R) | \(\{\}\) |
| 5 | edge to (0, S) | (0, R) | 2 | \(\{\$\}\) | |
| 6 | SCC done | (0, R) | ∞ | (0,L) | \(\{\$\}\) |
| 7 | edge to (0, R) | (0, L) | 1 | \(\{=, \$\}\) | |
| 8 | SCC done | (0, L) | ∞ | – | \(\{=, \$\}\) |
| 9 | enter | (1, L) | 1 | (1,L) | \(\{\}\) |
| 10 | enter | (1, R) | 2 | (1,L) (1,R) | \(\{\}\) |
| 11 | edge to (0, L) | (1, R) | 2 | \(\{=, \$\}\) | |
| 12 | edge to (1, L) (on stack) | (1, R) | 1 | \(\{=, \$\}\) | |
| 13 | enter | (8, L) | 3 | (1,L) (1,R) (8,L) | \(\{\}\) |
| 14 | enter | (8, R) | 4 | … (8,L) (8,R) | \(\{\}\) |
| 15 | edge to (0, S) | (8, R) | 4 | \(\{\$\}\) | |
| 16 | SCC done | (8, R) | ∞ | … (8,L) | \(\{\$\}\) |
| 17 | edge to (8, R) | (8, L) | 3 | \(\{\$\}\) | |
| 18 | SCC done | (8, L) | ∞ | (1,L) (1,R) | \(\{\$\}\) |
| 19 | edge to (8, L) | (1, R) | 1 | \(\{=, \$\}\) | |
| 20 | edge to (1, R) | (1, L) | 1 | \(\{=, \$\}\) | |
| 21 | SCC done: \(\{(1, R), (1, L)\}\) | (1, L) | ∞ | – | \(\{=, \$\}\) |
Step 12 finds the cycle \((1, L)\) includes \((1, R)\) includes \((1, L)\) (from \(R \to L\) and \(L \to *\,R\) inside I1): the two transitions form one SCC and get one set. lookback then gives \(\mathrm{LA}\):
| reduce item | looks back to | LA |
|---|---|---|
| (I2, \(L \to \mathit{id}\)) | (0, L), (1, L), (8, L) | \(\{=, \$\}\) |
| (I4, \(R \to L\)) | (0, R) | \(\{\$\}\) |
| (I5, \(S \to R\)) | (0, S) | \(\{\$\}\) |
| (I6, \(R \to L\)) | (1, R), (8, R) | \(\{=, \$\}\) |
| (I7, \(L \to * R\)) | (0, L), (1, L), (8, L) | \(\{=, \$\}\) |
| (I9, \(S \to L = R\)) | (0, S) | \(\{\$\}\) |
exactly the merged sets of the previous table. A nullable example is ll1-not-slr.grammar (\(S \to A\,a\,A\,b \mid B\,b\,B\,a\), \(A \to \varepsilon\), \(B \to \varepsilon\)): the reduce items \(A \to \bullet\) and \(B \to \bullet\) in I0 look back to \((0, A)\) and \((0, B)\), with DR \(\{a\}\) and \(\{b\}\): LALR gives the disjoint sets \(\{a\}\), \(\{b\}\) where SLR has \(\mathrm{FOLLOW}(A) = \mathrm{FOLLOW}(B) = \{a, b\}\).
Try it
./course drill lalr-lookaheads --seed 2 --difficulty hard --solution shows DR, reads, includes, Follow, lookback and the merged LR(1) states side by side.
Bison's lalr.c prints these relations
Reproduce (bison 3.8.2; any OS):
export LC_ALL=C # plain '.' and '`->' in Bison's output; UTF-8 locales print '•' and '↳'
cat > assign.y <<'EOF'
%token '=' '*' ID
%%
s: l '=' r | r ;
l: '*' r | ID ;
r: l ;
EOF
bison --trace=all -o /dev/null assign.y 2>&1 | sed -n '/^lalr: begin/,/^lalr: done/p'
Output (abridged: the "follows after read" dump, the edge lists and the transposed relation dumps between reads: and includes: are elided as …):
lalr: begin
nnterms: 4
goto_map[0 ($accept)] = 0 .. -1
goto_map[1 (s)] = 0 .. 0
goto_map[2 (l)] = 1 .. 3
goto_map[3 (r)] = 4 .. 6
goto[0] = (0, s, 3)
goto[1] = (0, l, 4)
goto[2] = (1, l, 6)
goto[3] = (9, l, 6)
goto[4] = (0, r, 5)
goto[5] = (1, r, 7)
goto[6] = (9, r, 10)
follows after shifts:
FOLLOWS[goto[0] = (0, s, 3)] = $end
FOLLOWS[goto[1] = (0, l, 4)] = '='
FOLLOWS[goto[2] = (1, l, 6)] =
FOLLOWS[goto[3] = (9, l, 6)] =
FOLLOWS[goto[4] = (0, r, 5)] =
FOLLOWS[goto[5] = (1, r, 7)] =
FOLLOWS[goto[6] = (9, r, 10)] =
reads:
…
includes:
goto[1] = (0, l, 4): goto[4] = (0, r, 5)
goto[2] = (1, l, 6): goto[5] = (1, r, 7)
goto[3] = (9, l, 6): goto[6] = (9, r, 10)
goto[4] = (0, r, 5): goto[0] = (0, s, 3)
goto[5] = (1, r, 7): goto[1] = (0, l, 4) goto[2] = (1, l, 6) goto[3] = (9, l, 6)
goto[6] = (9, r, 10): goto[0] = (0, s, 3)
follows after includes:
FOLLOWS[goto[0] = (0, s, 3)] = $end
FOLLOWS[goto[1] = (0, l, 4)] = $end '='
FOLLOWS[goto[2] = (1, l, 6)] = $end '='
FOLLOWS[goto[3] = (9, l, 6)] = $end
FOLLOWS[goto[4] = (0, r, 5)] = $end
FOLLOWS[goto[5] = (1, r, 7)] = $end '='
FOLLOWS[goto[6] = (9, r, 10)] = $end
lookback:
0 = ( 4, 5 r: l) -> goto[4] = (0, r, 5)
Lookaheads:
State 2:
rule 4:
State 4:
rule 5: $end
State 5:
rule 2:
State 6:
rule 5:
State 7:
rule 3:
State 8:
rule 0:
State 10:
rule 1:
lalr: done
What to notice: Bison's seven goto[i] are our \(\mathcal{N}\) (its state 9 is our I8); "follows after shifts" is DR, "includes" is our table's edges one for one, and "follows after includes" is our Follow column. Bison computes lookbacks, and so lookaheads, only for the one state that needs them (I4, which has a shift and a reduction): every other reduce state gets a default reduction [BISON-src].
4. Invariants and correctness¶
LALR(1) by merging LR(1) states¶
Lemma 3.3.8 (Merging is well defined)
If \(\mathrm{core}(J) = \mathrm{core}(J')\) then \(\mathrm{core}(\mathrm{GOTO}_1(J, X)) = \mathrm{core}(\mathrm{GOTO}_1(J', X))\) for every \(X\). Hence the merged states with the merged transitions form exactly the LR(0) automaton, with lookahead sets attached.
Proof
The kernel of \(\mathrm{GOTO}_1(J, X)\) is obtained from the items of \(J\) with \(X\) after the dot by moving the dot; lookaheads play no role in which items those are, so equal cores give equal GOTO kernel cores, and closure cores depend only on kernel cores (CLOSURE\(_1\) adds \([B \to \bullet\eta, b]\) for the same \(B \to \eta\) as CLOSURE does). By Lemma 3.2.10 the core of the state of \(\gamma\) is \(V(\gamma)\), the LR(0) state of \(\gamma\).
Theorem 3.3.9 (Merging introduces only reduce/reduce conflicts)
If the canonical LR(1) table of \(G\) has no conflict, the LALR(1) table has no shift/reduce conflict. Every LALR(1) conflict of an LR(1) grammar is a reduce/reduce conflict.
Proof
Suppose LALR state \(q\) has a shift/reduce conflict on \(a\): \(q\) shifts \(a\) and some \([A \to \omega \bullet] \in q\) has \(a \in \mathrm{LA}(q, A \to \omega)\). By Definition 3.3.2, \([A \to \omega \bullet,\ a] \in J\) for some LR(1) state \(J\) with core \(q\). The shift comes from an item \([C \to \mu \bullet a \nu] \in q\); since \(J\) has the same core, \(J\) contains \([C \to \mu \bullet a \nu,\ b]\) for some \(b\), so \(J\) shifts \(a\) too. \(J\) also reduces by \(A \to \omega\) on \(a\): a shift/reduce conflict in the canonical table, contradicting the hypothesis. Shifts do not depend on lookaheads, so merging can only add reductions to cells; a new conflict therefore involves two reductions.
The Bison manual's “mysterious” conflict
tests/ch03/Inputs/bison-mysterious.grammar is the Bison manual's example [BISON-Manual]: in def: param_spec return_spec ',', the token id followed by , is a type when it ends the parameter spec and starts no name list, but a name in name_list. Canonically these are two LR(1) states with core \(\{\mathit{type} \to \mathit{id} \bullet,\ \mathit{name} \to \mathit{id} \bullet\}\) and disjoint lookaheads; merged, , selects both reductions. Nothing in the grammar is ambiguous, which is why these conflicts look mysterious; Bison's counterexample generator shows two different example inputs, the signature of a merge-induced conflict (real-world box below).
DeRemer–Pennello lookaheads¶
Theorem 3.3.10 (Digraph is correct and linear [DP82])
Algorithm 3.3.6 computes \(F(x) = \bigcup\{ F'(y) : x R^{*} y \}\) for every \(x\), visiting each node once and each edge once, with \(O(\lvert X \rvert + \lvert R \rvert)\) set unions.
Proof
Traverse is Tarjan's SCC algorithm [Tar72] with \(N\) playing the role of the low-link: \(N[x] = d\) at the end of the loop iff \(x\) is the root of its SCC, and the SCC's members are exactly the nodes above and including \(x\) on \(S\). By induction on the order in which SCCs complete (reverse topological order of the condensation), when the SCC of \(x\) completes, every \(y\) with \(x R y\) outside the SCC is finished with its final set, and every \(y\) inside it has contributed \(F'(y)\) and its outgoing finished sets to the union accumulated along the DFS tree towards the root \(x\). So \(F(x)\) at the root equals \(\bigcup\) of \(F'\) over the SCC and over everything reachable from it — which is \(\bigcup\{F'(y) : x R^{*} y\}\), the same for all members, and the pop loop assigns it to all of them. Each node is entered once (\(N[y] = 0\) test) and each edge examined once, with one union per edge.
Lemma 3.3.11 (What Read and Follow mean)
For \((p, A) \in \mathcal{N}\) with \(r = \delta(p, A)\): (a) \(t \in \mathrm{Read}(p, A)\) iff there are nullable \(C_1, \dots, C_n\) (\(n \ge 0\)) such that \(\delta^{*}(r, C_1 \cdots C_n\, t)\) is defined (or \(t = \$\), \(n = 0\) and \((p, A) = (q_0, S)\)). (b) \(t \in \mathrm{Follow}(p, A)\) iff there are a string \(\gamma\) with \(\delta^{*}(q_0, \gamma) = p\) and a rightmost derivation \(S' \Rightarrow_{\mathrm{rm}}^{*} \gamma A w\) with \(\mathrm{first}_1(w) = t\).
Proof sketch (full proof: [DP82, §3–4])
(a) is Definition 3.3.4 unrolled: \(\mathrm{Read}(p, A) = \bigcup \mathrm{DR}\) over the transitions reachable by reads, and a reads chain walks over nullable nonterminals \(C_1 \cdots C_n\) from \(r\). (b) (\(\Leftarrow\)) Given \(S' \Rightarrow_{\mathrm{rm}}^{*} \gamma A w\) with \(q_0 \xrightarrow{\gamma} p\), look at the production \(B \to \beta A \eta\) that introduced this \(A\). If \(\eta\) derives a string starting with \(t\), the nonterminals of \(\eta\) before the first symbol producing \(t\) are nullable, so \(t \in \mathrm{Read}(p, A)\) by (a). Otherwise \(\eta\) is nullable and \(t\) comes from after \(B\): \((p, A)\) includes \((p', B)\) where \(p'\) is the state before \(\beta\), and induction on the derivation length gives \(t \in \mathrm{Follow}(p', B)\). (\(\Rightarrow\)) Reverse the construction: each includes edge extends a derivation by one enclosing production, each reads edge by one nullable symbol. DeRemer and Pennello prove both directions as their Theorems on Read and Follow.
Theorem 3.3.12 (The two LALR(1) constructions agree [DP82])
For every LR(0) state \(q\) and completed item \([A \to \omega \bullet] \in q\): \(\mathrm{LA}_{\mathrm{DP}}(q, A \to \omega) = \mathrm{LA}(q, A \to \omega)\).
Proof
(\(\subseteq\)) Let \(t \in \mathrm{Follow}(p, A)\) with \(p \xrightarrow{\omega} q\). By Lemma 3.3.11(b) there is \(S' \Rightarrow_{\mathrm{rm}}^{*} \gamma A w \Rightarrow_{\mathrm{rm}} \gamma \omega w\) with \(q_0 \xrightarrow{\gamma} p\) and \(\mathrm{first}_1(w) = t\). Then \([A \to \omega \bullet,\ t]\) is LR(1)-valid for \(\gamma\omega\) (Definition 3.2.2), so it belongs to the canonical state \(V_1(\gamma\omega)\), whose core is \(V(\gamma\omega) = q\) (Lemma 3.2.10). So \(t \in \mathrm{LA}(q, A \to \omega)\).
(\(\supseteq\)) Let \([A \to \omega \bullet,\ t] \in J\) with \(\mathrm{core}(J) = q\). \(J = V_1(\gamma')\) for some viable \(\gamma'\), and validity gives \(S' \Rightarrow_{\mathrm{rm}}^{*} \gamma A w \Rightarrow_{\mathrm{rm}} \gamma\omega w\) with \(\gamma' = \gamma\omega\) and \(\mathrm{first}_1(w) = t\). Let \(p = \delta^{*}(q_0, \gamma)\); it is defined since \(\gamma\) is viable, \((p, A) \in \mathcal{N}\) because \(\gamma A\) is viable, \(p \xrightarrow{\omega} q\), so \((q, A \to \omega)\) lookback \((p, A)\); and \(t \in \mathrm{Follow}(p, A)\) by Lemma 3.3.11(b).
Corollary 3.3.13 (Both constructions give the same table)
Algorithms 3.3.5 and 3.3.7 produce the same LALR(1) ACTION and GOTO tables. (Checked by the lab tests ch03.Random.LalrTwoWaysAgreeAndTheHierarchyHolds on 300 random grammars and ch03.Corpus/LalrAgreeCorpus.* on the 33 corpus grammars.)
Proof
Both use the LR(0) automaton's shifts and GOTOs (Lemma 3.3.8), and their reduce entries are the sets of Theorem 3.3.12.
Proposition 3.3.14 (An LL(1) grammar that is not LALR(1))
tests/ch03/Inputs/ll1-not-lalr.grammar, \(S \to (\ X \mid E\ ] \mid F\ )\), \(X \to E\ ) \mid F\ ]\), \(E \to A\), \(F \to A\), \(A \to \varepsilon\), is LL(1) and LR(1) but not LALR(1). This does not contradict Beatty's theorem that every p-reduced LL(1) grammar (every nonterminal derives a non-empty terminal string) is LALR(1) [Bea82]: here \(E\), \(F\) and \(A\) derive only \(\varepsilon\).
Proof
LL(1): the PREDICT sets of \(S\)'s alternatives are \(\{(\}\), \(\{]\}\) (as \(E\) is nullable) and \(\{)\}\), of \(X\)'s \(\{)\}\) and \(\{]\}\); \(E\), \(F\), \(A\) have one alternative each (Theorem 2.3.8). Canonical LR(1): from I0, closure gives \([E \to \bullet A,\ ]]\), \([F \to \bullet A,\ )]\) and then \([A \to \bullet,\ ]]\), \([A \to \bullet,\ )]\); GOTO on \(A\) yields the state \(\{[E \to A \bullet,\ ]],\ [F \to A \bullet,\ )]\}\). After (, closure of \(X \to \bullet E\,)\) and \(X \to \bullet F\,]\) gives \(\{[E \to A \bullet,\ )],\ [F \to A \bullet,\ ]]\}\) on \(A\). Neither state conflicts, and the oracle finds none in the 14 canonical states. LALR: the two states have the same core; merged, \(E \to A \bullet\) and \(F \to A \bullet\) both carry \(\{), ]\}\): reduce/reduce conflicts on ) and ]. The oracle and the lab both classify it LR(1), and is_ll1 confirms LL(1).
When it breaks. LALR's only failure mode on LR(1) grammars is the merge-induced reduce/reduce conflict (Theorem 3.3.9), which is hard to understand because no single input shows both reductions valid. Error detection is also weaker than canonical LR(1): merged lookaheads can trigger reductions on tokens that are illegal in the actual context before the error is reported (never a wrong shift, by the correct-prefix argument of Corollary 3.2.16).
5. Complexity¶
Variables: \(\lvert Q_0 \rvert\) LR(0) states, \(\lvert \mathcal{N} \rvert\) nonterminal transitions, \(\lvert\mathit{includes}\rvert\), \(\lvert\mathit{reads}\rvert\) relation sizes, \(\lvert T \rvert\) terminals (so a set union costs \(O(\lvert T \rvert / w)\) with \(w\)-bit words), \(\lvert Q_1 \rvert\) canonical states.
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| LALR by merging | building \(\mathcal{A}_1\): \(O(\lvert Q_1 \rvert \cdot \lvert G \rvert \cdot \lvert T \rvert)\), then linear merging | as canonical LR(1): impractical for large grammars | \(O(\lvert Q_1 \rvert \cdot \lvert G \rvert)\) | as above |
| DeRemer–Pennello | \(O((\lvert \mathcal{N} \rvert + \lvert\mathit{reads}\rvert + \lvert\mathit{includes}\rvert + \lvert\mathit{lookback}\rvert) \cdot \lvert T \rvert / w)\) | 2.2 s for PostgreSQL's 6 458 states, including LR(0) | \(O(\lvert \mathcal{N} \rvert \cdot \lvert T \rvert)\) bits | as above |
Proposition 3.3.15 (DeRemer–Pennello is linear in the relations)
Algorithm 3.3.7 runs in time \(O((\lvert\mathcal{N}\rvert + \lvert\mathit{reads}\rvert + \lvert\mathit{includes}\rvert + \lvert\mathit{lookback}\rvert) \cdot \lvert T \rvert)\) plus the time to build the relations, which is \(O(\lvert \mathcal{N} \rvert \cdot \lvert G \rvert)\) walks of \(\delta\).
Proof
Two Digraph runs, each linear in nodes plus edges with one union of \(O(\lvert T\rvert)\) bits per edge (Theorem 3.3.10). Building includes walks, for each transition \((p', B)\) and each production of \(B\), the path \(p' \xrightarrow{\beta}\) once: \(O(\lvert G \rvert)\) steps per transition. The final lookback pass performs one union per lookback edge.
Pathological input for merging: any grammar that makes \(\lvert Q_1 \rvert\) large (Proposition 3.2.17's \(H_k\)); DeRemer–Pennello never builds those states. At scale: Bison builds PostgreSQL 17's LALR table (6 458 states) in about two seconds on the course container (Lesson 3.8).
6. Variants and refinements¶
LALR(1) by merging LR(1) states¶
- Lookahead propagation (yacc, Dragon book) [Joh75, ALSU07 §4.7.5]: compute spontaneous lookaheads and propagation links between kernel items with the dummy lookahead
#, then iterate — trade-off: no LR(1) automaton, but repeated passes until nothing changes (quadratic in bad cases). - Merging on the fly (LaLonde's and Pager's approaches): merge as states are created instead of after — trade-off: saves memory; with Pager's compatibility test instead of "same core" this becomes a minimal LR(1) method (Lesson 3.4).
DeRemer–Pennello lookaheads¶
- Bermudez–Logothetis [BL89]: LALR(1) lookaheads as FOLLOW sets of a transformed grammar — trade-off: reuses a FOLLOW implementation, same result and complexity.
- Park, Choe and Chang [PCC85]: a different relational formulation, computing lookaheads per item — trade-off: sometimes fewer relation edges.
- Lookaheads only where needed (Bison): compute LA only for states with a conflict potential and use default reductions elsewhere — trade-off: less work and smaller tables; errors detected slightly later.
7. In real compilers¶
LALR(1) by merging LR(1) states¶
- Menhir (20231231)
src/LALR.ml— "In LALR mode, two LR(1) states are merged as soon as they have the same LR(0) core" (its header comment); the states are numbered like the LR(0) automaton, exactly our convention [MENHIR-src]. - Bison (3.8.2) conflicts reported as merge artifacts: the
-Wcounterexamples"First example … Second example" format ([BISON-Manual], box below), produced bysrc/counterexample.c.
A merge-induced reduce/reduce conflict, and how Bison explains it
Reproduce (bison 3.8.2; any OS):
export LC_ALL=C # plain '.' and '`->' in Bison's output; UTF-8 locales print '•' and '↳'
cat > nonlalr.y <<'EOF'
%%
s: 'a' a 'd' | 'b' b 'd' | 'a' b 'e' | 'b' a 'e' ;
a: 'c' ;
b: 'c' ;
EOF
bison -Wcounterexamples -o /dev/null nonlalr.y
bison -Wall -Dlr.type=canonical-lr -o /dev/null nonlalr.y && echo "canonical-lr: no conflicts"
Output (complete):
nonlalr.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
nonlalr.y: warning: reduce/reduce conflict on tokens 'd', 'e' [-Wcounterexamples]
First example: 'a' 'c' . 'd' $end
First reduce derivation
$accept
`-> 0: s $end
`-> 1: 'a' a 'd'
`-> 5: 'c' .
Second example: 'b' 'c' . 'd' $end
Second reduce derivation
$accept
`-> 0: s $end
`-> 2: 'b' b 'd'
`-> 6: 'c' .
nonlalr.y:4.4-6: warning: rule useless in parser due to conflicts [-Wother]
4 | b: 'c' ;
| ^~~
canonical-lr: no conflicts
What to notice: the two examples differ in their prefix ('a' 'c' vs 'b' 'c'): no single input makes both reductions valid, so this is not ambiguity but the merge of LR(1) states 4 and 7 of §3 (Theorem 3.3.9: reduce/reduce only). Bison then resolves by rule order and warns that b: 'c' can never be reduced. The canonical construction has no conflict [BISON-Manual].
DeRemer–Pennello lookaheads¶
- Bison (3.8.2)
src/lalr.c—initialize_goto_followscomputes DR and runsrelation_digraphover reads;build_relationsbuilds includes and lookback (add_lookback_edge);compute_followsruns the second Digraph andcompute_lookaheadsunions Follow over lookback [BISON-src];src/relation.c—traverseandrelation_digraphare Algorithm 3.3.6 line for line. The box in §3 prints their data. - tree-sitter (0.27.0) does not use DeRemer–Pennello:
crates/generate/src/build_tables/build_parse_table.rsbuilds item sets that carry lookahead sets (as in canonical LR(1)), andminimize_parse_table.rs(merge_compatible_states) afterwards groups states by core and merges those whose actions do not conflict — an approach closer to the minimal LR(1) methods of Lesson 3.4 [TS-build].
The Bison manual's mysterious conflict, and IELR
Reproduce (bison 3.8.2; any OS):
export LC_ALL=C # plain '.' and '`->' in Bison's output; UTF-8 locales print '•' and '↳'
cat > mysterious.y <<'EOF'
%token ID
%%
def: param_spec return_spec ',' ;
param_spec: type | name_list ':' type ;
return_spec: type | name ':' type ;
type: ID ;
name: ID ;
name_list: name | name ',' name_list ;
EOF
bison -Wcounterexamples -o /dev/null mysterious.y
bison -Dlr.type=ielr -o /dev/null mysterious.y && echo "ielr: no conflicts"
Output (complete):
mysterious.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
mysterious.y: warning: reduce/reduce conflict on token ',' [-Wcounterexamples]
First example: param_spec ID . ',' $end
First reduce derivation
$accept
`-> 0: def $end
`-> 1: param_spec return_spec ','
`-> 4: type
`-> 6: ID .
Second example: ID . ',' name_list ':' type return_spec ',' $end
Second reduce derivation
$accept
`-> 0: def $end
`-> 1: param_spec return_spec ','
`-> 3: name_list ':' type
`-> 9: name ',' name_list
`-> 7: ID .
ielr: no conflicts
What to notice: ID followed by , is a type after a param_spec but a name at the start: two contexts, one LR(0) state, merged lookaheads. The example of §4 and our oracle agree (lr classify prints LR(1) for bison-mysterious.grammar). IELR(1) (Lesson 3.4) splits exactly the state that needs it.
Find where LLVM does it. LLVM has no LALR generator, but it has the Digraph pattern: open llvm/include/llvm/ADT/SCCIterator.h (LLVM 23.1.2) and find scc_iterator::DFSVisitChildren [LLVM-SCCIterator]. Which field of StackElement records the minimum visit number reachable from a node's subtree, the role \(N[x]\) plays in Algorithm 3.3.6? (quiz scc-iterator-lowlink)
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| LALR(1) by merging LR(1) states | LALR(1) = LR(0) states with the union of canonical lookaheads; can add reduce/reduce conflicts (Theorem 3.3.9) | Needs \(\mathcal{A}_1\) first · impractical for large grammars | Same table as DeRemer–Pennello | Low once LR(1) exists | Definition, testing, teaching |
| DeRemer–Pennello lookaheads | Identical sets (Theorem 3.3.12) | Linear in the relations · 2.2 s for PostgreSQL | Same table; lookaheads can be computed only where needed | Moderate: four relations and Digraph | Bison's default, most LALR generators |
Choose merging when you need an oracle or a teaching implementation: it is obviously right given canonical LR(1). Choose DeRemer–Pennello when you generate parsers for real grammars: LALR(1) power at LR(0) cost, linear time, and the relations double as documentation of where each lookahead came from.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch03.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| LALR by merging | merge-conflict-kind, ll1-not-lalr, lr-hierarchy |
./course drill lalr-lookaheads (merge view), ./course drill lr-classify |
lalr |
E3 |
| DeRemer–Pennello | dp-lookaheads, scc-iterator-lowlink, sr-trace-running |
./course drill lalr-lookaheads --difficulty hard |
deremer-pennello |
E3 |
A reduce/reduce conflict in an LR(1) grammar is not ambiguity
When Bison's two counterexamples start differently, look for two contexts sharing an LR(0) state before rewriting the grammar: switching to %define lr.type ielr removes the conflict without changing the language or the parse trees.
References¶
See the chapter references.