Lesson 3.2 — Lookahead: SLR(1) and canonical LR(1)¶

Techniques: SLR(1) (DeRemer 1971); canonical LR(1) (Knuth 1965), with the theory of LR(k) grammars · Pebble implements: nothing in pebblec; the lab builds both tables (exercises E1, E2, E4) · Lab: labs/ch03-lr-toolkit (SPEC; buildAutomaton(G, Method::SLR1 | Method::LR1), buildTable; lr report --method slr|lr1) · Prerequisites: Lesson 3.1; FIRST and FOLLOW (Lesson 2.2) · Time: 4 hours

Lesson 3.1 ended with state I4 of the running example, which holds $S \to L \bullet = R$ and $R \to L \bullet$: shift = or reduce by $R \to L$? The LR(0) table does both. One token of lookahead decides it, if you know which tokens can legally follow the reduction. SLR(1) approximates that set by $\mathrm{FOLLOW}(R)$, a property of the grammar; canonical LR(1) computes it exactly per state, by carrying the lookahead inside the items. The two sit at the ends of a trade-off that Lessons 3.3–3.4 refine: SLR keeps the small LR(0) automaton and fails on the running example; LR(1) succeeds on every LR(1) grammar but may need many more states.

1. Problem and motivation¶

Input: the LR(0) automaton of $G$ (Lesson 3.1). Output: a deterministic ACTION table, i.e. for each state and lookahead token at most one action, that makes the driver of Algorithm 3.1.18 correct, for as large a class of grammars as possible.

SLR(1)¶

DeRemer introduced Simple LR(k) in 1971 [DeR71] as the cheapest way to add lookahead to the LR(0) automaton he had isolated in his thesis [DeR69]: reduce by $A \to \beta$ only on tokens in $\mathrm{FOLLOW}(A)$. It adds nothing to the automaton and needs only the FOLLOW sets of Ch 2. It handles most expression grammars, including the left-recursive $E \to E + T \mid T$ that no LL(1) parser accepts, but FOLLOW is global: a token that follows $A$ somewhere is allowed after every $A$.

Canonical LR(1)¶

Knuth's 1965 paper [Knu65] defined the LR(k) grammars ("translatable from left to right with bound $k$"), proved that exactly they have deterministic bottom-up parsers with $k$ tokens of lookahead, and gave the construction with $k$-token lookaheads carried in the items. The canonical LR(1) automaton is its $k = 1$ case. It was long considered impractical (states for a 1960s programming language did not fit in memory), which motivated SLR and LALR; today Bison (%define lr.type canonical-lr) and Menhir (--canonical) build it on request, and it is the reference against which the minimal methods of Lesson 3.4 are defined.

2. Definitions and algorithms¶

$\mathrm{FIRST}$, $\mathrm{FOLLOW}$ and nullability are those of Definition 2.2.1, computed on the augmented grammar (so $\$ \in \mathrm{FOLLOW}(S)$). For a string $x \in T^{*}$, $\mathrm{first}_1(x)$ is the first symbol of $x\,\$$ (Definition 2.3.2).

Definition 3.2.1 (SLR(1) table)

The SLR(1) table is the LR(0) table of Definition 3.1.11 with one change: a completed item $[A \to \beta \bullet] \in I$, $A \neq S'$, puts reduce $A \to \beta$ into ACTION$[I, a]$ only for $a \in \mathrm{FOLLOW}(A)$. $G$ is SLR(1) if this table has no conflict.

Definition 3.2.2 (LR(1) items and their validity)

An LR(1) item $[A \to \alpha \bullet \beta,\ a]$ is an LR(0) item plus a lookahead $a \in T \cup \{\$\}$. It is valid for $\gamma$ if there is a rightmost derivation $S' \Rightarrow_{\mathrm{rm}}^{*} \delta A w \Rightarrow_{\mathrm{rm}} \delta \alpha \beta w$ with $\gamma = \delta\alpha$ and $a = \mathrm{first}_1(w)$. $V_1(\gamma)$ is the set of LR(1) items valid for $\gamma$. We write items with the same core together: $[A \to \alpha \bullet \beta,\ \{a, b\}]$.

Definition 3.2.3 (CLOSURE₁, GOTO₁, canonical LR(1) automaton)

$\mathrm{CLOSURE}_1(I)$ is the least set $J \supseteq I$ such that $[A \to \alpha \bullet B \beta,\ a] \in J$, $B \to \eta \in P$ and $b \in \mathrm{FIRST}(\beta a)$ imply $[B \to \bullet \eta,\ b] \in J$. $\mathrm{GOTO}_1(I, X) = \mathrm{CLOSURE}_1(\{[A \to \alpha X \bullet \beta,\ a] : [A \to \alpha \bullet X \beta,\ a] \in I\})$. The canonical LR(1) automaton $\mathcal{A}_1$ is built from $q_0 = \mathrm{CLOSURE}_1(\{[S' \to \bullet S,\ \$]\})$ exactly as $\mathcal{A}_0$ is in Definition 3.1.8; two states are equal only if they have the same items with the same lookaheads. The core of a state is its set of LR(0) items.

Definition 3.2.4 (Canonical LR(1) table)

As Definition 3.1.11 on $\mathcal{A}_1$, except that $[A \to \beta \bullet,\ a] \in I$ ($A \neq S'$) puts reduce $A \to \beta$ only into ACTION$[I, a]$, and accept goes to ACTION$[I, \$]$ for $[S' \to S \bullet,\ \$]$.

Definition 3.2.5 (LR(k) grammar [Knu65])

Let $G$ be augmented ($S'$ occurs on no right side). $G$ is LR(k) if for all rightmost derivations

\[ S' \Rightarrow_{\mathrm{rm}}^{*} \alpha A w \Rightarrow_{\mathrm{rm}} \alpha \beta w \qquad\text{and}\qquad S' \Rightarrow_{\mathrm{rm}}^{*} \gamma B x \Rightarrow_{\mathrm{rm}} \gamma \delta x = \alpha \beta y \]

with $w, x, y \in T^{*}$ and $\mathrm{FIRST}_k(w\,\$) = \mathrm{FIRST}_k(y\,\$)$ (the first $k$ symbols), we have $\alpha = \gamma$, $A = B$ and $x = y$. In words: once the stack $\alpha\beta$ and $k$ tokens after it are known, the handle is determined.

SLR vs LR(1) on I4

$\mathrm{FOLLOW}(R) = \{=, \$\}$ because $R$ ends $L \to *\,R$ and $L$ is followed by $=$ in $S \to L = R$. So SLR puts reduce $R \to L$ on $=$ in I4, next to shift 8: a conflict, and the grammar is not SLR(1). But the only right-sentential forms whose stack reaches I4 from I0 have $L$ as the left side of the assignment or as the whole statement; an $R$ produced there is a whole statement ($S \to R$), which only $\$$ follows. The LR(1) item $[R \to L \bullet,\ \$]$ in the LR(1) state for the stack $L$ records exactly that.

SLR(1)¶

Algorithm 3.2.6 (SLR(1) table)

Input: the LR(0) automaton $(Q, \delta)$ of $G$ and $\mathrm{FOLLOW}$.
Output: ACTION and GOTO, with the conflicting cells.
Precondition: FOLLOW is the least fixed point of Definition 2.2.1 (Theorem 2.2.5).
Postcondition: the table of Definition 3.2.1; it contains every action the canonical LR(1) table needs, mapped to LR(0) states (Lemma 3.2.11).
Invariant: after processing states $I_0, \dots, I_j$, their rows are complete.

Reference solution: solutions/labs/ch03-lr-toolkit/src/Table.cpp (buildTable, Method::SLR1).

function SLRTable(Q, δ, FOLLOW):
    for each state I in Q:
        for each terminal a with δ(I, a) defined:  add shift δ(I, a) to ACTION[I, a]
        for each nonterminal A with δ(I, A) defined: GOTO[I, A] ← δ(I, A)
        for each completed item [A → β •] in I:
            if A = S':  add accept to ACTION[I, $]
            else for each a in FOLLOW(A):  add reduce A → β to ACTION[I, a]
    return ACTION, GOTO, { cells of ACTION with ≥ 2 actions }

Canonical LR(1)¶

Algorithm 3.2.7 (CLOSURE₁ with merged lookahead sets)

Input: a kernel $K$ as a map item $\mapsto$ lookahead set.
Output: $\mathrm{CLOSURE}_1(K)$ in the same representation.
Precondition: FIRST and nullability of the grammar.
Postcondition: the least set of Definition 3.2.3 (every lookahead of every item).
Invariant: out[i] $\subseteq$ the lookaheads of $i$ in $\mathrm{CLOSURE}_1(K)$; an item whose set grew is on the worklist, so its successors will be updated.

Reference solution: closure1 in solutions/labs/ch03-lr-toolkit/src/Automata.cpp and tools/course/lib/lr.py.

function Closure1(K):
    out ← copy of K;  work ← queue of the items of K
    while work ≠ ∅:
        [A → α • X β] ← pop work
        if X is not a nonterminal: continue
        (f, nullable) ← FirstOf(β)                     # Algorithm 2.2.6's helper
        new ← f ∪ (out[A → α • X β] if nullable else ∅)
        for each production X → η:
            i ← [X → • η]
            if i ∉ out:  out[i] ← ∅
            if new ⊄ out[i]:  out[i] ← out[i] ∪ new;  push i on work if absent
            elif i was just created:  push i on work
    return out

Algorithm 3.2.8 (Canonical LR(1) collection)

Input: the augmented grammar.
Output: the states of $\mathcal{A}_1$ in the course's canonical numbering (breadth first, successors in symbol order, exactly as Algorithm 3.1.10) and $\delta_1$.
Precondition: none.
Postcondition: Definition 3.2.3; each state is $V_1(\gamma)$ for the strings $\gamma$ leading to it (Lemma 3.2.10).
Invariant: states are identified by their kernel with lookaheads.

function LR1Collection(G):
    states ← [Closure1({[S' → • S] ↦ {$}})];  index ← {that kernel ↦ 0};  q ← 0
    while q < |states|:
        for each symbol X in symbol order:
            K ← { [A → α X • β] ↦ L : [A → α • X β] ↦ L in states[q] }     # union L per item
            if K = ∅: continue
            if K ∉ index: index[K] ← |states|; append Closure1(K)
            δ₁(q, X) ← index[K]
        q ← q + 1

3. Worked example¶

Running example (Lesson 3.1): $(1)\ S \to L = R$, $(2)\ S \to R$, $(3)\ L \to *\,R$, $(4)\ L \to \mathit{id}$, $(5)\ R \to L$; $\mathrm{FOLLOW}(S) = \{\$\}$, $\mathrm{FOLLOW}(L) = \mathrm{FOLLOW}(R) = \{=, \$\}$.

SLR(1) on the running example¶

Rows of Algorithm 3.2.6 for the states with completed items (the others only shift):

state	completed item	FOLLOW of its left side	reduce entries	shifts in the state	conflict
I2	$L \to \mathit{id} \bullet$	$\{=, \$\}$	r4 on =, $	–	no
I3	$S' \to S \bullet$	–	acc on $	–	no
I4	$R \to L \bullet$	$\{=, \$\}$	r5 on =, $	= → s8	ACTION[4, =] = {s8, r5}
I5	$S \to R \bullet$	$\{\$\}$	r2 on $	–	no
I6	$R \to L \bullet$	$\{=, \$\}$	r5 on =, $	–	no
I7	$L \to * R \bullet$	$\{=, \$\}$	r3 on =, $	–	no
I9	$S \to L = R \bullet$	$\{\$\}$	r1 on $	–	no

SLR removes the LR(0) table's spurious reductions on * and id everywhere, but the conflict in I4 survives. Compare the expression grammar tests/ch03/Inputs/expr.grammar ($E \to E + T \mid T$, …): its LR(0) table has shift/reduce conflicts in the two states holding $E \to T \bullet$ / $T \to T \bullet * F$, and $* \notin \mathrm{FOLLOW}(E) = \{), +, \$\}$ removes both. It is SLR(1).

Canonical LR(1) on the running example¶

$\mathrm{CLOSURE}_1(\{[S' \to \bullet S,\ \$]\})$, one row per lookahead propagation (oracle closure1):

step	from	adds	new lookaheads $= \mathrm{FIRST}(\beta a)$
1	$[S' \to \bullet S,\ \$]$	$S \to \bullet L = R$	$\$$ ($\beta = \varepsilon$)
2	$[S' \to \bullet S,\ \$]$	$S \to \bullet R$	$\$$
3	$[S \to \bullet L = R,\ \$]$	$L \to \bullet * R$	$=$ ($\beta = {=}\,R$)
4	$[S \to \bullet L = R,\ \$]$	$L \to \bullet \mathit{id}$	$=$
5	$[S \to \bullet R,\ \$]$	$R \to \bullet L$	$\$$
6	$[R \to \bullet L,\ \$]$	$L \to \bullet * R$	$\$$ (grows to $\{=, \$\}$)
7	$[R \to \bullet L,\ \$]$	$L \to \bullet \mathit{id}$	$\$$ (grows to $\{=, \$\}$)

The canonical collection has 14 states; the four LR(0) cores that are reached in two lookahead contexts split:

LR(0) state	LR(1) states	lookaheads of the split item
I1 ($L \to * \bullet R$)	1, 9	$\{=, \$\}$ (under the left side) vs $\{\$\}$ (under the right side)
I2 ($L \to \mathit{id} \bullet$)	2, 10	$\{=, \$\}$ vs $\{\$\}$
I6 ($R \to L \bullet$)	6, 11	$\{=, \$\}$ vs $\{\$\}$
I7 ($L \to * R \bullet$)	7, 13	$\{=, \$\}$ vs $\{\$\}$
I0, I3, I4, I5, I8, I9	0, 3, 4, 5, 8, 12	(one context each)

In LR(1) state 4, $= \{[S \to L \bullet = R,\ \$], [R \to L \bullet,\ \$]\}$: reduce $R \to L$ only on $\$$, shift on =. No conflict anywhere: the grammar is LR(1). (It is even LALR(1): merging the split pairs back creates no conflict — Lesson 3.3.)

Try it

./course drill lr0-closure --seed 5 --difficulty hard --solution computes an LR(1) closure with lookaheads; ./course drill lr-table --difficulty medium fills an SLR(1) table; lr report tests/ch03/Inputs/assign.grammar --method lr1 prints all 14 states.

4. Invariants and correctness¶

Canonical LR(1)¶

Lemma 3.2.9 (LR(1) viable-prefix witness)

Let $\alpha\beta w$ be a right-sentential form with handle $(A \to \beta, \lvert \alpha\beta \rvert)$, $\gamma$ a prefix of $\alpha\beta$ and $a = \mathrm{first}_1(w)$. If $\gamma = \alpha\beta$ then $[A \to \beta \bullet,\ a] \in V_1(\gamma)$; if $\gamma X$ is a prefix of $\alpha\beta$, some item $[C \to \mu \bullet X \nu,\ b] \in V_1(\gamma)$.

Proof

The first claim is Definition 3.2.2 applied to the derivation that creates the handle. The second is Lemma 3.1.14's construction: the item $[A_{i^{*}} \to \beta' \bullet \beta'']$ found there comes from the step $\alpha_{i^{*}} A_{i^{*}} w_{i^{*}} \Rightarrow_{\mathrm{rm}} \alpha_{i^{*}}\beta_{i^{*}} w_{i^{*}}$, so it is LR(1)-valid with lookahead $b = \mathrm{first}_1(w_{i^{*}})$.

Lemma 3.2.10 (CLOSURE₁ and GOTO₁ compute valid LR(1) items)

$V_1(\varepsilon) = \mathrm{CLOSURE}_1(\{[S' \to \bullet S,\ \$]\})$ and $V_1(\gamma X) = \mathrm{GOTO}_1(V_1(\gamma), X)$. Hence $\delta_1^{*}(q_0, \gamma) = V_1(\gamma)$ whenever $\gamma$ is viable, and the core of $V_1(\gamma)$ is $V(\gamma)$.

Proof

Follow the proof of Lemma 3.1.15, carrying the lookahead. Closure is sound: from $S' \Rightarrow_{\mathrm{rm}}^{*} \delta A w \Rightarrow_{\mathrm{rm}} \delta\alpha B \beta w$ with $a = \mathrm{first}_1(w)$ and any $b \in \mathrm{FIRST}(\beta a)$: if $b$ comes from $\beta$, derive $\beta \Rightarrow_{\mathrm{rm}}^{*} b\,y$; if $\beta$ is nullable and $b = a$, derive $\beta \Rightarrow_{\mathrm{rm}}^{*} \varepsilon$. Either way $S' \Rightarrow_{\mathrm{rm}}^{*} \delta\alpha B v w \Rightarrow_{\mathrm{rm}} \delta\alpha\eta v w$ with $\mathrm{first}_1(v w) = b$, so $[B \to \bullet\eta,\ b]$ is valid. Closure is complete: in the chain argument of Lemma 3.1.15, let $[B \to \bullet\eta,\ c] \in V_1(\gamma)$ via a derivation $S' \Rightarrow_{\mathrm{rm}}^{*} \gamma B v u \Rightarrow_{\mathrm{rm}} \gamma\eta v u$, where the occurrence of $B$ was introduced by the step $\zeta C u \Rightarrow_{\mathrm{rm}} \zeta\mu B \nu u$ and later $\nu \Rightarrow_{\mathrm{rm}}^{*} v$, so $c = \mathrm{first}_1(v u)$. Then $[C \to \mu \bullet B \nu,\ \mathrm{first}_1(u)]$ is valid for $\gamma = \zeta\mu$, and $c \in \mathrm{FIRST}(\nu\, \mathrm{first}_1(u))$, which is exactly the closure rule; the chain ends at a kernel item as before. GOTO moves the dot over $X$ without changing $w$, so it preserves lookaheads (Lemma 3.1.15(b)). The last sentence follows by induction on $\lvert\gamma\rvert$ as in Theorem 3.1.16, and by dropping lookaheads.

Lemma 3.2.11 (A table that contains the LR(1) actions and has no conflict is correct)

Let $M$ be an ACTION/GOTO table whose states are the states of $\mathcal{A}_0$ or of $\mathcal{A}_1$, such that for every viable $\gamma$ and token $a$, the cell of the state reached by $\gamma$ on $a$ contains reduce $A \to \beta$ whenever $[A \to \beta \bullet,\ a] \in V_1(\gamma)$, and shift whenever $\gamma a$ is viable. If $M$ has no conflict, the driver (Algorithm 3.1.18) with $M$ reduces only handles, accepts exactly $L(G)$ and has the correct-prefix property.

Proof

Repeat the proof of Theorem 3.1.19 with LR(1) items. On a sentence, suppose every reduction so far was a handle, so stack $\cdot$ input $= s\,x$ is a right-sentential form, and let $(B \to \eta, k)$ be its handle, $a$ the next token. If $k = \lvert s \rvert$, $[B \to \eta \bullet,\ a] \in V_1(s)$ (Lemma 3.2.9), so the cell holds that reduction; it holds nothing else (no conflict), so the parser reduces the handle. If $k > \lvert s \rvert$, $s\,a$ is a prefix of the form up to the handle's end, so $s\,a$ is viable and the cell holds a shift, and only it: the parser shifts, as it must. ($k < \lvert s \rvert$ is impossible: by induction the parser never shifted past a handle.) So the parser follows the reversed rightmost derivation and accepts; it never accepts a non-sentence by Theorem 3.1.13. The correct-prefix property holds because shifts only extend viable prefixes, as in Theorem 3.1.19.

Theorem 3.2.12 (Canonical LR(1) characterizes LR(1) [Knu65])

An augmented reduced grammar is LR(1) (Definition 3.2.5 with $k = 1$) if and only if its canonical LR(1) table has no conflict.

Proof

($\Leftarrow$) Take two derivations as in Definition 3.2.5 with $\mathrm{first}_1(w) = \mathrm{first}_1(y) = a$. By Lemma 3.2.9, $[A \to \beta \bullet,\ a] \in V_1(\alpha\beta)$. Let $(B \to \delta, k)$ with $k = \lvert\gamma\delta\rvert$ be the handle the second derivation gives to $\alpha\beta y$. If $k > \lvert\alpha\beta\rvert$, then $\alpha\beta a$ is a prefix of $\gamma\delta$ (the symbol after $\alpha\beta$ is the first token of $y$, which is $a$; it cannot be $\$$ because a handle does not extend past the end), so $V_1(\alpha\beta)$ contains an item with $a$ after its dot: shift and reduce in the same cell, a conflict. If $k < \lvert\alpha\beta\rvert$, then $\gamma\delta$ is a proper prefix of $\alpha\beta$ and the symbols of $\alpha\beta$ after position $k$ belong to $x \in T^{*}$; let $b$ be the first of them, so $b = \mathrm{first}_1(x)$ and $[B \to \delta \bullet,\ b] \in V_1(\gamma\delta)$ (Lemma 3.2.9 for the second derivation). But $\gamma\delta\, b$ is a prefix of $\alpha\beta$, so Lemma 3.2.9 for the first derivation puts an item with $b$ after its dot into $V_1(\gamma\delta)$: a shift/reduce conflict on $b$. If $k = \lvert\alpha\beta\rvert$, both $[A \to \beta \bullet,\ a]$ and $[B \to \delta \bullet,\ a]$ are in $V_1(\alpha\beta)$, so they are the same production (no reduce/reduce conflict); then $\gamma = \alpha$, $B = A$, and $\gamma\delta x = \alpha\beta y$ gives $x = y$.

($\Rightarrow$) Suppose $V_1(\gamma)$ has a conflict on $a$. Reduce/reduce: $[A \to \beta \bullet,\ a]$ and $[B \to \delta \bullet,\ a]$ with $A \to \beta \neq B \to \delta$ give derivations $S' \Rightarrow_{\mathrm{rm}}^{*} \alpha A w \Rightarrow_{\mathrm{rm}} \alpha\beta w$ and $S' \Rightarrow_{\mathrm{rm}}^{*} \alpha' B w' \Rightarrow_{\mathrm{rm}} \alpha'\delta w'$ with $\alpha\beta = \alpha'\delta = \gamma$ and $\mathrm{first}_1(w) = \mathrm{first}_1(w') = a$; Definition 3.2.5 (with $y = w'$) would force $A = B$ and $\alpha = \alpha'$, hence $\beta = \delta$, a contradiction. (Accept against a reduction is the case $A = S'$.) Shift/reduce: $[A \to \beta \bullet,\ a]$ and $[C \to \mu \bullet a \nu,\ b]$, the latter via $S' \Rightarrow_{\mathrm{rm}}^{*} \zeta C u \Rightarrow_{\mathrm{rm}} \zeta\mu a\nu u$ with $\zeta\mu = \gamma$. Continue rightmost until $\nu$ is terminal: $\zeta\mu a \nu u \Rightarrow_{\mathrm{rm}}^{*} \gamma a z$. The last step of this derivation creates a handle that ends after position $\lvert\gamma\rvert$ (it rewrites a nonterminal of $\nu$, or it is the step that created $a$). With $y = a z$, Definition 3.2.5 applied to the reduce derivation and this one would require that handle to end at $\lvert\gamma\rvert$: a contradiction.

Theorem 3.2.13 (LR(k) grammars are unambiguous [Knu65])

Every LR(k) grammar is unambiguous. In particular no ambiguous grammar has a conflict-free LR(0), SLR(1), LALR(1) or LR(1) table.

Proof

Let $D_1: S' = \gamma_0 \Rightarrow_{\mathrm{rm}} \cdots \Rightarrow_{\mathrm{rm}} \gamma_m = w$ and $D_2: S' = \eta_0 \Rightarrow_{\mathrm{rm}} \cdots \Rightarrow_{\mathrm{rm}} \eta_n = w$ be rightmost derivations of the same sentence. We show $\gamma_{m-i} = \eta_{n-i}$ and that step $m - i$ of $D_1$ equals step $n - i$ of $D_2$, by induction on $i$. For $i = 0$ both forms are $w$. If $\gamma_{m-i} = \eta_{n-i} = \varphi \neq S'$, both derivations reach $\varphi$ by a last step: $\gamma_{m-i-1} = \alpha A u \Rightarrow_{\mathrm{rm}} \alpha\beta u = \varphi$ and $\eta_{n-i-1} = \gamma' B x \Rightarrow_{\mathrm{rm}} \gamma'\delta x = \varphi = \alpha\beta u$. The LR(k) condition with $y = u$ gives $\gamma' = \alpha$, $B = A$, $x = u$, so $\delta = \beta$ and the previous forms are equal. The forms reach $S'$ at the same index because $S'$ occurs in no other form (it is on no right side), so $m = n$ and $D_1 = D_2$. A sentence with one rightmost derivation has one parse tree (Lemma 2.1.10). The second sentence follows from Theorem 3.2.12 and the inclusions of Theorem 3.2.15.

Theorem 3.2.14 (Every LL(1) grammar is LR(1))

Every reduced LL(1) grammar is LR(1). The inclusion is proper: the left-recursive expression grammar is SLR(1) and not LL(1).

Proof sketch (full proof: [Nij82]; the stronger statement for p-reduced grammars: [Bea82])

Suppose the LR(1) condition fails for two derivations as in Definition 3.2.5 with $\mathrm{first}_1(w) = \mathrm{first}_1(y) = a$. Expand the common prefix $\alpha\beta$ of both right-sentential forms identically to a terminal string $z$, obtaining two sentences $z\,w$ and $z\,y$ that agree on the first $\lvert z \rvert + 1$ tokens. In an LL(1) grammar the leftmost derivation is determined step by step by the tokens consumed so far and the next one (Definition 2.3.2), so the two parse trees coincide on every node whose yield starts at or before position $\lvert z \rvert + 1$ — Beatty calls this common part the left part of the trees. Every node involved in the two handles (the $A$-node with children $\beta$, the $B$-node with children $\delta$, and all nodes left of them) lies in the left part, so both trees contain both nodes, and the order in which a rightmost derivation (a reverse postorder) creates them is the same in both trees; the two last steps must therefore coincide ($A = B$, $\alpha = \gamma$, $x = y$). Nijholt [Nij82] makes the left-part argument precise via Beatty's LL(k) Left Part Theorem, after observing that several earlier published proofs of the inclusion are informal or flawed; the relation between the two classes goes back to Knuth's study of top-down analysis [Knu71]. The expression grammar is left-recursive, hence not LL(1) (Corollary 2.3.10), and its SLR(1) table has no conflict (§3).

Theorem 3.2.15 (The hierarchy of grammar classes)

LR(0) $\subsetneq$ SLR(1) $\subsetneq$ LALR(1) $\subsetneq$ LR(1), where each class is the set of grammars whose table (Definitions 3.1.11, 3.2.1, 3.3.2, 3.2.4) has no conflict. Every LR(1) grammar has a conflict-free canonical LR(1) table, so a correct deterministic parser.

Proof

Inclusions. The LR(0) table's reduce entries of a state $I$ include its SLR entries ($\mathrm{FOLLOW}(A) \subseteq T \cup \{\$\}$). Every LALR(1) lookahead of an item in LR(0) state $V(\gamma)$ is a canonical lookahead of that item in some $V_1(\gamma')$ with the same core (Definition 3.3.2), and every canonical lookahead $a$ of $[A \to \beta \bullet,\ a] \in V_1(\gamma')$ is in $\mathrm{FOLLOW}(A)$ (the valid derivation shows $a$ following $A$); so LALR entries $\subseteq$ SLR entries with identical shifts, and a conflict-free SLR table implies a conflict-free LALR table. Splitting a merged LALR state into its canonical LR(1) states only removes lookaheads from each copy, so a conflict-free LALR table implies a conflict-free LR(1) table. Strictness: tests/ch03/Inputs/expr.grammar is SLR(1) and not LR(0); assign.grammar is LALR(1) and not SLR(1) (§3); nonlalr.grammar is LR(1) and not LALR(1) (Lesson 3.3, §3). The last sentence is Lemma 3.2.11 applied to the canonical table, which contains exactly the needed actions (Lemma 3.2.10).

SLR(1)¶

Corollary 3.2.16 (SLR(1) parsers are correct)

If the SLR(1) table of $G$ has no conflict, the driver with it reduces only handles, accepts exactly $L(G)$ and has the correct-prefix property; it may perform extra reductions before detecting an error, but never shifts an erroneous token.

Proof

The SLR table lives on $\mathcal{A}_0$ and contains every reduction the LR(1) items require (the proof of Theorem 3.2.15: canonical lookaheads $\subseteq$ FOLLOW) and every shift; apply Lemma 3.2.11. Extra entries (tokens in FOLLOW but not in the canonical lookahead) can only fire on inputs that are already erroneous; they perform reductions but never a shift, so the error is detected before the offending token is consumed.

When it breaks. SLR fails whenever a nonterminal appears in two contexts with different followers and both contexts reach one LR(0) state (the running example); LR(1) never fails on an LR(1) grammar but pays in states (§5). Neither handles ambiguous grammars (Theorem 3.2.13): those need precedence declarations (Lesson 3.5) or GLR (Lesson 3.6).

5. Complexity¶

Variables: $\lvert Q_0 \rvert$, $\lvert Q_1 \rvert$ the numbers of LR(0) and canonical LR(1) states, $\lvert G \rvert$ the number of LR(0) items, $\lvert T \rvert$ terminals.

Technique	Time (worst)	Time (typical)	Space	Variables
SLR(1)	FOLLOW in $O(\lvert G \rvert \cdot \lvert T \rvert)$ per pass (Lesson 2.2), table $O(\lvert Q_0 \rvert \cdot (\lvert T \rvert + \lvert N \rvert))$	as LR(0)	the LR(0) table	as above
Canonical LR(1)	$O(\lvert Q_1 \rvert \cdot \lvert G \rvert \cdot \lvert T \rvert)$ with hashing, $\lvert Q_1 \rvert \le \lvert Q_0 \rvert \cdot 2^{\lvert G \rvert (\lvert T \rvert + 1)}$	1.5–2× LR(0) on small grammars; did not finish in 600 s for PostgreSQL	$O(\lvert Q_1 \rvert \cdot \lvert G \rvert \cdot \lvert T \rvert)$	as above

Proposition 3.2.17 (Bounds and a duplication family)

(a) Every canonical LR(1) state has the core of an LR(0) state, so $\lvert Q_0 \rvert \le \lvert Q_1 \rvert \le \lvert Q_0 \rvert \cdot 2^{\lvert G\rvert(\lvert T \rvert + 1)}$. (b) For $k \ge 1$ let $H_k$ have the productions $S \to a_i\, A\, b_i$ ($1 \le i \le k$), $A \to (\, A\, )$, $A \to x$. Then $\lvert Q_0 \rvert = 3k + 6$ and $\lvert Q_1 \rvert = 7k + 6$.

Proof

(a) The core of $V_1(\gamma)$ is $V(\gamma)$ (Lemma 3.2.10), and a state is determined by its core and a lookahead set per item. (b) LR(0): $I_0$ and $S' \to S \bullet$; per $i$ the states after $a_i$, $a_i A$ and $a_i A b_i$ ($3k$); the four states of the $A$-part — after (, x, ( A, ( A ) — are shared by all contexts. LR(1): the first-level $A$-states inherit the lookahead $b_i$ of their context, so each context has its own four copies ($4k$ more), while the nested ones (lookahead )) are shared (4): $2 + 3k + 4k + 4 = 7k + 6$. The oracle confirms $13, 20, 27, 34$ for $k = 1..4$; all methods between LALR and LR(1) (Lesson 3.4) stay at $3k + 6$, because nothing conflicts.

Pathological inputs are grammars in which one sub-language (here parenthesized expressions) is used in many contexts with different followers: canonical LR(1) copies the whole sub-automaton per context. At scale: Bison's canonical LR(1) construction for PostgreSQL 17's grammar did not finish within 600 s on the course container, while LALR took 2.2 s (6 458 states) and IELR 3.3 s (6 459 states) — Lesson 3.4's real-world box.

SLR(1)¶

SLR(k) [DeR71]: $\mathrm{FOLLOW}_k$ sets instead of FOLLOW — trade-off: more grammars, tables indexed by $k$-token strings.
"Extended SLR" / LR(0) with lookahead sets per state (the first step towards LALR): intersect FOLLOW with what can follow in this state — this is exactly LALR(1) (Lesson 3.3).

Canonical LR(1)¶

LR(k), $k > 1$ [Knu65]: $k$-token lookaheads in items and cells — trade-off: the number of lookahead strings grows as $\lvert T \rvert^{k}$; LR(k) languages are all LR(1) languages anyway (Knuth), so $k > 1$ only saves grammar rewriting.
Merging compatible states (LALR, Pager, IELR; Lessons 3.3–3.4) — trade-off: LR(0)-sized automata, with a risk (LALR) or a guarantee (IELR, Pager) of no new conflicts.
Menhir's canonical mode [MENHIR-Manual]: --canonical, used when an exact correspondence between states and contexts matters (precise .messages error messages).

7. In real compilers¶

SLR(1)¶

SLR survives mainly as a teaching tool and a first approximation: no parser generator among Bison, Menhir, tree-sitter or yacc derivatives uses FOLLOW-based reductions in production, because LALR costs little more and handles strictly more (the real-world box below). It lives on in textbooks as the first LR method with lookahead [ALSU07 §4.6] and in the course's lab (Method::SLR1).

Bison's lookaheads in I4 are sharper than FOLLOW

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 --report=lookaheads --report-file=assign.output -o /dev/null assign.y
sed -n '/^State 4$/,/^State 5$/p' assign.output

Output (complete):

State 4

    1 s: l . '=' r
    5 r: l .  [$end]

    '='  shift, and go to state 9

    $default  reduce using rule 5 (r)


State 5

What to notice: Bison's lookahead set for $R \to L \bullet$ in I4 is [$end], not $\mathrm{FOLLOW}(R) = \{=, \$\}$: with it the = column holds only the shift. An SLR(1) generator would report ACTION$[4, =]$ as a shift/reduce conflict (§3 table). No mainstream generator ships SLR today for exactly this reason [BISON-Manual].

Canonical LR(1)¶

Bison's canonical LR(1) automaton splits the running example's states

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
cat > nonlalr.y <<'EOF'
%%
s: 'a' a 'd' | 'b' b 'd' | 'a' b 'e' | 'b' a 'e' ;
a: 'c' ;
b: 'c' ;
EOF
for g in assign nonlalr; do
  for t in lalr canonical-lr; do
    bison -Dlr.type=$t --report=states --report-file=$g-$t.output -o /dev/null $g.y 2>/dev/null
    echo "$g.y $t: $(grep -cE '^State [0-9]+$' $g-$t.output) states"
  done
done
bison -Dlr.type=canonical-lr --report=lookaheads --report-file=c.output -o /dev/null assign.y
grep -nE "^State [0-9]+$|r: l \." c.output | grep -B1 "r: l \." | grep -v -- --

Output (complete):

assign.y lalr: 11 states
assign.y canonical-lr: 15 states
nonlalr.y lalr: 14 states
nonlalr.y canonical-lr: 15 states
76:State 4
79:    5 r: l .  [$end]
93:State 6
95:    5 r: l .  [$end, '=']
152:State 13
154:    5 r: l .  [$end]

What to notice: Bison's counts are ours plus its extra accept state: 10 + 1 and 14 + 1 for the running example, 13 + 1 and 14 + 1 for nonlalr. The item $R \to L \bullet$ appears in three canonical states with lookaheads $\{\$\}$ (our 4), $\{\$, =\}$ (our 6) and $\{\$\}$ (our 11): the split of §3.

Bison (3.8.2) src/ielr.c — lr_type_get reads lr.type, and ielr implements both ielr and canonical-lr: for the latter it skips the annotation phase and runs the state-splitting phase ielr_split_states with the canonical LR(1) compatibility test (Lesson 3.4) [BISON-src]; -Dlr.type=canonical-lr in the box above.
Menhir (20231231) src/LR1Canonical.ml — a traversal that creates one state per distinct LR(1) item set, selected by --canonical [MENHIR-src]. Lesson 3.4's real-world box compares its count with LALR and Pager.
LLVM has no LR parser. The C++ standard's grammar is ambiguous (an expression statement and a declaration can spell the same tokens), so by Theorem 3.2.13 it has no conflict-free LR(k) table; Clang resolves such cases by tentative parsing (Lesson 3.8).

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
SLR(1)	SLR(1) grammars: LR(0) ⊊ SLR(1) ⊊ LALR(1); fails on context-dependent followers	LR(0) automaton + FOLLOW · as fast as LR(0)	Correct prefix, but extra reductions before an error; spurious conflicts	Low: LR(0) + FOLLOW	Teaching; historical generators
Canonical LR(1)	Exactly the LR(1) grammars (Theorem 3.2.12); ⊋ LL(1) (Theorem 3.2.14)	$\lvert Q_1\rvert$ can be many times $\lvert Q_0\rvert$ · PostgreSQL: > 600 s	Immediate error detection (no extra reductions); one state per context helps messages	Moderate: lookahead propagation in closure	Reference semantics; Menhir `--canonical`, Bison `canonical-lr`

Choose SLR(1) when you are learning or bootstrapping a generator: it is the smallest step from LR(0), and it already accepts left-recursive expression grammars. Choose canonical LR(1) when the grammar is small, or when you need the exact LR(1) power and the most precise error behavior; for anything large, use a minimal LR(1) method (Lesson 3.4) that keeps its power without its size.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch03.yaml`)	Drill	Flashcard tag	Exercises
SLR(1)	`slr-conflict-cell`, `lr-hierarchy`	`./course drill lr-table --difficulty medium`	`slr`	E4
Canonical LR(1)	`lr1-closure-lookaheads`, `ll1-in-lr1`, `lr-hierarchy`	`./course drill lr0-closure --difficulty hard`, `./course drill lr-classify`	`lr1`	E2

FOLLOW is about the grammar, lookahead is about the state

$\mathrm{FOLLOW}(R) \ni {=}$ because some $R$ is followed by = (inside $L \to *\,R$ on the left of an assignment). The $R$ you are about to reduce in I4 is not that one. SLR's conflicts on grammars that are perfectly deterministic all come from this confusion.

References¶

See the chapter references.

step	from	adds	new lookaheads \(= \mathrm{FIRST}(\beta a)\)
1	\([S' \to \bullet S,\ \$]\)	\(S \to \bullet L = R\)	\(\$\) (\(\beta = \varepsilon\))
2	\([S' \to \bullet S,\ \$]\)	\(S \to \bullet R\)	\(\$\)
3	\([S \to \bullet L = R,\ \$]\)	\(L \to \bullet * R\)	\(=\) (\(\beta = {=}\,R\))
4	\([S \to \bullet L = R,\ \$]\)	\(L \to \bullet \mathit{id}\)	\(=\)
5	\([S \to \bullet R,\ \$]\)	\(R \to \bullet L\)	\(\$\)
6	\([R \to \bullet L,\ \$]\)	\(L \to \bullet * R\)	\(\$\) (grows to \(\{=, \$\}\))
7	\([R \to \bullet L,\ \$]\)	\(L \to \bullet \mathit{id}\)	\(\$\) (grows to \(\{=, \$\}\))

state	completed item	FOLLOW of its left side	reduce entries	shifts in the state	conflict
I2	\(L \to \mathit{id} \bullet\)	\(\{=, \$\}\)	r4 on =, $	–	no
I3	\(S' \to S \bullet\)	–	acc on $	–	no
I4	\(R \to L \bullet\)	\(\{=, \$\}\)	r5 on =, $	= → s8	ACTION[4, =] = {s8, r5}
I5	\(S \to R \bullet\)	\(\{\$\}\)	r2 on $	–	no
I6	\(R \to L \bullet\)	\(\{=, \$\}\)	r5 on =, $	–	no
I7	\(L \to * R \bullet\)	\(\{=, \$\}\)	r3 on =, $	–	no
I9	\(S \to L = R \bullet\)	\(\{\$\}\)	r1 on $	–	no

LR(0) state	LR(1) states	lookaheads of the split item
I1 (\(L \to * \bullet R\))	1, 9	\(\{=, \$\}\) (under the left side) vs \(\{\$\}\) (under the right side)
I2 (\(L \to \mathit{id} \bullet\))	2, 10	\(\{=, \$\}\) vs \(\{\$\}\)
I6 (\(R \to L \bullet\))	6, 11	\(\{=, \$\}\) vs \(\{\$\}\)
I7 (\(L \to * R \bullet\))	7, 13	\(\{=, \$\}\) vs \(\{\$\}\)
I0, I3, I4, I5, I8, I9	0, 3, 4, 5, 8, 12	(one context each)

Technique	Time (worst)	Time (typical)	Space	Variables
SLR(1)	FOLLOW in \(O(\lvert G \rvert \cdot \lvert T \rvert)\) per pass (Lesson 2.2), table \(O(\lvert Q_0 \rvert \cdot (\lvert T \rvert + \lvert N \rvert))\)	as LR(0)	the LR(0) table	as above
Canonical LR(1)	\(O(\lvert Q_1 \rvert \cdot \lvert G \rvert \cdot \lvert T \rvert)\) with hashing, \(\lvert Q_1 \rvert \le \lvert Q_0 \rvert \cdot 2^{\lvert G \rvert (\lvert T \rvert + 1)}\)	1.5–2× LR(0) on small grammars; did not finish in 600 s for PostgreSQL	\(O(\lvert Q_1 \rvert \cdot \lvert G \rvert \cdot \lvert T \rvert)\)	as above

Lesson 3.2 — Lookahead: SLR(1) and canonical LR(1)¶

1. Problem and motivation¶

SLR(1)¶

Canonical LR(1)¶

2. Definitions and algorithms¶

SLR(1)¶

Canonical LR(1)¶

3. Worked example¶

SLR(1) on the running example¶

Canonical LR(1) on the running example¶

4. Invariants and correctness¶

Canonical LR(1)¶

SLR(1)¶

5. Complexity¶

6. Variants and refinements¶

SLR(1)¶

Canonical LR(1)¶

7. In real compilers¶

SLR(1)¶

Canonical LR(1)¶

8. Comparison¶

9. Assessment¶

References¶