Lesson 3.4 — Minimal LR(1): Pager's method and IELR(1)¶

Techniques: Pager's practical general method with weak compatibility (PGM, 1977); IELR(1), "inadequacy elimination LR(1)" (Denny and Malloy, 2010); state-count comparisons across LR(0), LALR(1), PGM, IELR(1) and canonical LR(1) · Pebble implements: nothing; the Python oracle implements PGM (lr.pgm_automaton) and Bison is the reference for IELR · Lab: the comparison lab measures state counts (lr compare, tests/ch03/Inputs/corpus.compare); PGM is a stretch goal (SPEC) · Prerequisites: Lesson 3.3 · Time: 3 hours

LALR(1) is small but may add reduce/reduce conflicts (Theorem 3.3.9); canonical LR(1) never does but may be large (Proposition 3.2.17). The minimal LR(1) methods build an automaton with the full power of LR(1) — the same actions as canonical LR(1) on every LR(1) grammar — and nearly the size of LALR(1): they merge LR(1) states with the same core unless merging could change a decision. Pager's method decides this with a cheap sufficient test on lookahead sets; IELR(1) computes exactly which lookaheads can influence which conflicts. Menhir uses Pager's method by default and Bison offers IELR(1) as %define lr.type ielr.

1. Problem and motivation¶

Input: a grammar. Output: an LR automaton and table that (a) accept exactly the grammars canonical LR(1) accepts, with the same parsing actions, and (b) have as few states as possible — ideally as many as LALR(1) whenever LALR(1) already works.

Pager's practical general method¶

Pager's 1977 paper [Pag77] ("A practical general method for constructing LR(k) parsers") builds LR(1) states in the canonical way but, whenever a new state has the same core as an existing one, merges them if they are weakly compatible: no pair of kernel items would acquire a common lookahead through the merge unless they already share one. The test is local and cheap, and merging weakly compatible states never introduces a reduce/reduce conflict that canonical LR(1) does not have. Hyacc and, since its early versions, Menhir implement it; Menhir's current src/LR1Pager.ml is a 2020 re-implementation that fixed a bug of the older one which "could create artificial (unexplainable) conflicts" [MENHIR-src].

IELR(1)¶

Denny and Malloy [DM10] observed that Pager's test is only sufficient: it refuses merges that would be harmless, and — more importantly for Bison — it says nothing about grammars with resolved conflicts (precedence declarations, %expect), where canonical LR(1) and LALR(1) can differ in behavior even without reported conflicts. IELR(1) starts from LALR(1), finds every inadequacy (conflict, including resolved ones), computes which kernel lookaheads of which states contribute to it (annotations), and splits only the states whose merge changes a contribution. Its result behaves exactly like canonical LR(1) and is LALR-sized when LALR(1) is already adequate. It shipped in Bison 2.5 (2011).

2. Definitions and algorithms¶

LR(1) states are written as kernels with lookahead sets, $K = \{ i \mapsto L_K(i) \}$ for kernel items $i$ of a core $C$ (Definition 3.3.1). Two LR(1) states with the same core are isocores.

Definition 3.4.1 (Weak compatibility [Pag77])

Isocore kernels $K$ and $K'$ with core items $i_1, \dots, i_m$ are weakly compatible if for all $x \neq y$,

\[ \bigl(L_K(i_x) \cap L_{K'}(i_y) = \emptyset \ \land\ L_{K'}(i_x) \cap L_K(i_y) = \emptyset\bigr) \ \lor\ L_K(i_x) \cap L_K(i_y) \neq \emptyset \ \lor\ L_{K'}(i_x) \cap L_{K'}(i_y) \neq \emptyset . \]

Merging them yields the kernel $i \mapsto L_K(i) \cup L_{K'}(i)$.

Definition 3.4.2 (Inadequacy and contributions, after [DM10])

An inadequacy of the LALR(1) automaton is a pair $(s, t)$ of a state and a token with two or more actions before conflict resolution (so it includes conflicts later resolved by precedence). An action $a$ of $(s, t)$ is contributed by a kernel item $k$ of a state $s'$ with a path $s' \xrightarrow{\beta} s$ if the lookahead $t$ of $k$ in $s'$ propagates, through closure and GOTO along $\beta$, to the reduce item of $a$ in $s$ (shifts are contributed unconditionally). The annotation of $s'$ for $(s, t)$ maps each action to the set of kernel items of $s'$ that can contribute it. For an LR(1) state $J$ with core $s'$, its contribution set for $(s, t)$ is the set of actions some kernel item of $J$ contributes with its actual lookaheads.

Definition 3.4.3 (IELR compatibility, simplified from [DM10, §3.5])

Isocore LR(1) states $J$, $J'$ are IELR-compatible if, for every inadequacy annotated on their core, merging them does not change the contribution set of either: $J$ and $J'$ have the same contribution set, or one of them contributes no action at all for that inadequacy. (Denny and Malloy's test additionally treats actions that conflict resolution makes dominant specially; this refinement never splits more states.)

Pager's practical general method¶

Algorithm 3.4.4 (Pager's PGM with weak compatibility)

Input: the augmented grammar.
Output: an LR(1) automaton; states renumbered in the canonical breadth-first order at the end.
Precondition: FIRST/nullable; Algorithm 3.2.7 (CLOSURE₁).
Postcondition: every state is a union of weakly compatible canonical states; on an LR(1) grammar the table has no conflict (Theorem 3.4.8).
Invariant: every state's kernel lookaheads are the union of the canonical kernels merged into it so far; a state whose lookaheads grew is on the worklist, so its successors will be recomputed.

Oracle: lr.pgm_automaton (tools/course/lib/lr.py), which also records how each transition target was chosen.

function PGM(G):
    states ← [{[S' → • S] ↦ {$}}];  work ← [0];  byCore ← {core ↦ [0]}
    while work ≠ ∅:
        q ← pop front of work;  I ← Closure1(states[q])
        for each symbol X in symbol order:
            K ← GOTO₁ kernel of I on X;  if K = ∅: continue
            target ← none
            for j in byCore[core(K)]:                    # an isocore that already covers K
                if K ⊆ states[j] item-wise: target ← j; break
            if target = none:
                for j in byCore[core(K)]:
                    if WeaklyCompatible(K, states[j]):
                        states[j] ← states[j] ∪ K item-wise;  push j on work if absent
                        target ← j; break
            if target = none:
                target ← new state K;  add to byCore;  push on work
            δ(q, X) ← target                           # may redirect an earlier transition
    drop unreachable states; renumber breadth first in symbol order
    return states, δ

IELR(1)¶

Algorithm 3.4.5 (IELR(1), phases as in [DM10] and Bison's src/ielr.c)

Input: the augmented grammar (and precedence declarations, if any).
Output: an LR(1) automaton whose actions, after conflict resolution, equal canonical LR(1)'s.
Precondition: the LALR(1) automaton and lookaheads (Lesson 3.3).
Postcondition: Theorem 3.4.10; if the LALR table has no inadequacy, the result is the LALR automaton.
Invariant (phase 3): a state is merged into an isocore only if they are IELR-compatible, so no annotated contribution set ever changes.

function IELR(G):
    # Phase 0: LALR(1) automaton A and its lookaheads (DeRemer–Pennello)
    # Phase 1: auxiliary tables
    #   follow_kernel_items[(p, A)] = kernel items of p whose lookaheads flow into Follow(p, A)
    #   always_follows[(p, A)]      = tokens in Follow(p, A) independent of any kernel lookahead
    #   predecessors[s]             = states with a transition into s
    # Phase 2: annotations
    for each inadequacy (s, t) of A:
        annotate s: for each action, the kernel items of s that can contribute it
        propagate the annotation backwards along predecessors while kernel items of the
        predecessor can contribute (via follow_kernel_items); stop where nothing can
    # Phase 3: split states
    rebuild the automaton like PGM, but the merge test is IELR compatibility (Def. 3.4.3)
    for states whose core carries annotations, and "same core" (LALR merging) otherwise
    # Phase 4: recompute the lookaheads of the new automaton
    # Phase 5: build the table and resolve conflicts (precedence, %expect, default rules)
    return the table

3. Worked example¶

The non-LALR grammar of Lesson 3.3 (tests/ch03/Inputs/nonlalr.grammar): $(1)\ S \to a\,A\,d$, $(2)\ S \to b\,B\,d$, $(3)\ S \to a\,B\,e$, $(4)\ S \to b\,A\,e$, $(5)\ A \to c$, $(6)\ B \to c$. LR(0)/LALR: 13 states with two reduce/reduce conflicts in I4; canonical LR(1): 14 states.

Pager's practical general method on the example¶

One row per transition computed (oracle pgm_automaton, symbol order $a, d, b, e, c, S, A, B$):

#	from	on	kernel with lookaheads	decision	to
1	0	a	$[S \to a \bullet A\,d,\ \$]$, $[S \to a \bullet B\,e,\ \$]$	new	1
2	0	b	$[S \to b \bullet B\,d,\ \$]$, $[S \to b \bullet A\,e,\ \$]$	new	2
3	0	S	$[S' \to S \bullet,\ \$]$	new	3
4	1	c	$[A \to c \bullet,\ d]$, $[B \to c \bullet,\ e]$	new	4
5	1	A	$[S \to a\,A \bullet d,\ \$]$	new	5
6	1	B	$[S \to a\,B \bullet e,\ \$]$	new	6
7	2	c	$[A \to c \bullet,\ e]$, $[B \to c \bullet,\ d]$	isocore of 4, not weakly compatible	new 7
8	2	A	$[S \to b\,A \bullet e,\ \$]$	new	8
9	2	B	$[S \to b\,B \bullet d,\ \$]$	new	9
10–13	5, 6, 8, 9	d, e, e, d	the four completed $S$-items	new	10–13

Row 7: with $i_x = A \to c \bullet$, $i_y = B \to c \bullet$, $L_K(i_x) = \{e\}$, $L_{K'}(i_y) = \{e\}$ ($K'$ = state 4), so the first disjunct fails; $L_K(i_x) \cap L_K(i_y) = \{e\} \cap \{d\} = \emptyset$ and $L_{K'}(i_x) \cap L_{K'}(i_y) = \{d\} \cap \{e\} = \emptyset$: not weakly compatible, so the merge that LALR performs is refused. Result: 14 states, conflict-free (= canonical here). On the running example (assign.grammar), the transitions from I8 on *, id, $L$ produce kernels such as $[L \to * \bullet R,\ \$]$ whose lookaheads are contained in the existing isocore ($\{=, \$\}$): they are absorbed, and PGM ends with 10 states, the LALR size, where canonical LR(1) has 14.

IELR(1) on the example¶

Phase 0–1: LALR state I4 $= \{A \to c \bullet,\ B \to c \bullet\}$ with $\mathrm{LA} = \{d, e\}$ for both items. Inadequacies: $(I4, d)$ and $(I4, e)$, each between r5 and r6. Phase 2: in I4 itself, r5 is contributed by kernel item $A \to c \bullet$ and r6 by $B \to c \bullet$ (every lookahead of a completed kernel item is its own). Their lookaheads come from the predecessors I1 and I2 through the $c$-transitions; in I1 the items $S \to a \bullet A\,d$ and $S \to a \bullet B\,e$ determine them.

Phase 3: rebuilding, the $c$-successor of I1 has lookaheads $A{:}\{d\}$, $B{:}\{e\}$ — contribution set for $(I4, d)$: $\{$r5$\}$, for $(I4, e)$: $\{$r6$\}$. The $c$-successor of I2 has $A{:}\{e\}$, $B{:}\{d\}$ — contributions $\{$r6$\}$ and $\{$r5$\}$. The sets differ and neither is empty: not IELR-compatible, so I4 splits into two states. No other state carries an annotation, so all other isocores merge as in LALR. Phase 4: the split states get $\{d\}/\{e\}$ lookaheads; no conflict remains. Result: 14 states here (= canonical, since the only split is the necessary one). The Bison manual's mysterious grammar shows the difference: LALR 19, IELR 20, canonical 21 states (ours; Bison prints one more) — the real-world box below.

Try it

./course drill lr-classify --difficulty hard --solution compares state counts; lr compare tests/ch03/Inputs/*.grammar prints LR(0)/SLR/LALR/LR(1) counts for the whole corpus, and lr.state_counts in tools/course/lib/lr.py adds PGM.

4. Invariants and correctness¶

Pager's practical general method¶

Lemma 3.4.6 (Weak compatibility preserves a conflict-free kernel)

Let $K$, $K'$ be weakly compatible isocores whose tables have no reduce/reduce conflict between completed kernel items. Then their merge has no reduce/reduce conflict between completed kernel items.

Proof

Suppose completed kernel items $i_x \neq i_y$ of the merge both reduce on $t$: $t \in (L_K(i_x) \cup L_{K'}(i_x)) \cap (L_K(i_y) \cup L_{K'}(i_y))$. If $t \in L_K(i_x) \cap L_K(i_y)$, $K$ already conflicts; if $t \in L_{K'}(i_x) \cap L_{K'}(i_y)$, $K'$ does. Otherwise $t \in L_K(i_x) \cap L_{K'}(i_y)$ or $t \in L_{K'}(i_x) \cap L_K(i_y)$, so the first disjunct of Definition 3.4.1 fails, and weak compatibility gives $L_K(i_x) \cap L_K(i_y) \neq \emptyset$ or $L_{K'}(i_x) \cap L_{K'}(i_y) \neq \emptyset$ — a conflict between $i_x$ and $i_y$ in $K$ or $K'$ on some token, contrary to the hypothesis.

Lemma 3.4.7 (Merging never creates shift/reduce conflicts)

Merging isocores (by any criterion) cannot create a shift/reduce conflict that neither has.

Proof

As in Theorem 3.3.9: shifts depend only on the core, and a reduction on $t$ in the merge is present, with the same item, in one of the merged states, which then also has the shift.

Theorem 3.4.8 (PGM has the power of LR(1) [Pag77])

If $G$ is LR(1), the table built from Algorithm 3.4.4's automaton has no conflict.

Proof sketch (full proof: [Pag77], the theorem on weak compatibility)

Shift/reduce conflicts are excluded by Lemma 3.4.7. For reduce/reduce conflicts, Lemma 3.4.6 handles completed kernel items. The remaining cases are conflicts that appear only in successors of a merged state (and in closure items), after the merged kernel lookaheads propagate. Pager shows that lookaheads propagate from kernel items to later items along fixed paths determined by the core (the same GOTO/closure chain in both isocores), so a new conflict between two items downstream would come from two kernel items $i_x$, $i_y$ of the merged state whose propagated lookaheads meet; weak compatibility forbids a new meeting unless the lookaheads of $i_x$ and $i_y$ already met in one of the originals, in which case the corresponding canonical state already had the conflict downstream. The re-expansion of states whose lookaheads grow (the worklist invariant) makes every state's lookaheads the union of the canonical states merged into it, so the argument applies to the final automaton. Menhir's source recalls that a subtle implementation bug could violate this guarantee, which its 2020 re-implementation fixed [MENHIR-src].

IELR(1)¶

Lemma 3.4.9 (No inadequacy, no split)

If the LALR(1) table of $G$ has no inadequacy (not even a resolved conflict), IELR(1) returns the LALR(1) automaton.

Proof

Phase 2 creates annotations only for inadequacies; with none, no core carries annotations, Definition 3.4.3 holds vacuously for all isocores, phase 3 merges every isocore group (the LALR criterion), and phase 4 recomputes exactly the LALR lookaheads.

Theorem 3.4.10 (IELR(1) behaves like canonical LR(1) [DM10])

For every grammar (with or without precedence declarations), the IELR(1) parser performs, on every input, the same sequence of shifts and reductions as the canonical LR(1) parser, up to default reductions on erroneous inputs.

Proof sketch (full proof: [DM10, §3–4])

Actions of a merged state differ from those of its canonical constituents only at inadequacies: elsewhere every token has at most one action, and merging adds a reduction only where the canonical states already agree (Lemma 3.4.7 and the LALR argument). At an inadequacy $(s, t)$, the action chosen after conflict resolution depends only on which actions are present on $t$, i.e. on the contribution set. Phase 2 computes, for every state from which a lookahead can flow into $(s, t)$, which kernel items determine that set; phase 3 merges two isocores only if the merge leaves every such contribution set unchanged, so every merged state resolves each inadequacy exactly as each of its canonical constituents does. Phase 4 then recomputes lookaheads on the new automaton, and Denny and Malloy show the recomputed sets induce the same contributions (their Lemma on the stability of annotations under splitting).

When it breaks. Weak compatibility is sufficient, not necessary: PGM may keep isocores apart whose merge would be harmless (Menhir's Pager mode is one state larger than LALR on the mysterious grammar, like IELR, but can exceed IELR on others). IELR's guarantee needs the whole annotation machinery; a hand-written approximation that only looks at the conflicting state itself misses conflicts caused by lookaheads merged several states earlier (the mysterious conflicts of Lesson 3.3 are of this kind: the merge happens in I4's predecessors' successors).

5. Complexity¶

Variables: $\lvert Q_0 \rvert$ LR(0)/LALR states, $\lvert Q_P \rvert$ PGM states, $\lvert Q_I \rvert$ IELR states, $\lvert Q_1 \rvert$ canonical states; $\lvert T \rvert$ terminals; $I$ the number of inadequacies.

Technique	Time (worst)	Time (typical)	Space	Variables
PGM	$O(\lvert Q_1 \rvert^2 \cdot \lvert G \rvert \cdot \lvert T \rvert)$: each new kernel is tested against every isocore, and a state can be re-expanded once per growth of its lookaheads (at most $\lvert G \rvert \cdot \lvert T \rvert$ times)	≈ LALR size: 10 vs 14 states (running example); Menhir: 22 vs 21 LALR vs 23 canonical (`mysterious`)	$O(\lvert Q_P \rvert \cdot \lvert G \rvert \cdot \lvert T \rvert)$	as above
IELR(1)	LALR, plus annotations $O(I \cdot \lvert Q_0 \rvert \cdot \lvert G \rvert)$, plus a PGM-like phase 3	3.3 s vs 2.2 s for LALR on PostgreSQL; 6 459 vs 6 458 states	$O((\lvert Q_I \rvert + I \cdot \lvert Q_0\rvert) \cdot \lvert G \rvert)$	as above

Proposition 3.4.11 (State counts are sandwiched)

For every grammar, $\lvert Q_0 \rvert \le \lvert Q_P \rvert \le \lvert Q_1 \rvert$ and $\lvert Q_0 \rvert \le \lvert Q_I \rvert \le \lvert Q_1 \rvert$, and $\lvert Q_I \rvert = \lvert Q_0 \rvert$ when the LALR table has no inadequacy.

Proof

Every PGM or IELR state has the core of an LR(0) state, and every LR(0) core is reached (the construction explores the same transitions), so each LR(0) state has at least one isocore: $\lvert Q_0 \rvert \le$. Each PGM/IELR state is a union of canonical states (merging only unions), so there are at most $\lvert Q_1 \rvert$. The last claim is Lemma 3.4.9. The oracle test test_pgm_size_between_lalr_and_lr1 checks the PGM sandwich on 150 random grammars; on all 355 random LALR(1) grammars of a separate oracle run, PGM also equalled LALR.

Pathological input for PGM: Proposition 3.2.17's $H_k$ is not one (all isocores are compatible, so PGM stays at $3k + 6$); grammars where many isocores have crossing lookaheads on non-completed kernel items force splits that IELR would not make. At scale: PostgreSQL 17's grammar needs one extra state under IELR (6 459 vs 6 458), and Bison's canonical construction did not finish within 600 s (Lesson 3.8) — the whole point of the minimal methods.

Pager's practical general method¶

Strong compatibility [Pag77]: merge only if the merge creates no new lookahead intersection at all — trade-off: simpler, more states.
Lane-tracing (Pager's other algorithm; Chen's Hyacc, 2009 [Che09]): start from LR(0), trace "lanes" back from each conflict and split only there — trade-off: IELR-like sizes, more complex; Hyacc implements both.
Menhir's re-implementation [MENHIR-src]: a graph traversal in which the target of a transition depends on the states discovered so far, with a check that no conflict is introduced — trade-off: robust against the rare artificial conflicts of the older implementation.

IELR(1)¶

Canonical LR through the same machinery (Bison canonical-lr): skip annotations and use identical-lookahead compatibility in phase 3 — trade-off: exact canonical automaton, impractical for large grammars.
Minimal LR(1) by partition refinement / state splitting from LALR (Spector's splitting, 1988 [Spe88]): split LALR states on demand where a conflict appears — trade-off: simpler, but not guaranteed to match canonical behavior with resolved conflicts.
tree-sitter's post-hoc merging [TS-build]: build lookahead-carrying item sets, then merge_compatible_states merges isocores whose actions (including lexical conflicts between tokens) do not clash — trade-off: also accounts for the lexer, but is a table-level criterion rather than a lookahead-level one.

7. In real compilers¶

Pager's practical general method¶

Menhir (20231231) src/LR1Pager.ml — the default construction; its header describes the target-depends-on-discovery-order traversal [MENHIR-src]. Selected when no --lalr/--canonical flag is given.

Menhir: LALR, Pager and canonical state counts

Reproduce (menhir 20231231, Ubuntu 24.04 package menhir 20231231+ds-1; any OS with OCaml's menhir):

cat > assign.mly <<'EOF'
%token EQ STAR ID EOF
%start <unit> main
%type <unit> s l r
%%
main: s EOF {}
s: l EQ r {} | r {}
l: STAR r {} | ID {}
r: l {}
EOF
cat > mysterious.mly <<'EOF'
%token ID COMMA COLON EOF
%start <unit> main
%type <unit> def param_spec return_spec typ name name_list
%%
main: def EOF {}
def: param_spec return_spec COMMA {}
param_spec: typ {} | name_list COLON typ {}
return_spec: typ {} | name COLON typ {}
typ: ID {}
name: ID {}
name_list: name {} | name COMMA name_list {}
EOF
for g in assign mysterious; do
  for m in --lalr "" --canonical; do
    echo "== menhir $m $g.mly"
    menhir $m --log-automaton 1 $g.mly 2>&1 | grep -E "construction mode|LR\(1\) automaton|reduce/reduce"
  done
done

Output (complete):

== menhir --lalr assign.mly
The construction mode is lalr.
Built an LR(1) automaton with 12 states.
== menhir  assign.mly
The construction mode is pager.
Built an LR(1) automaton with 12 states.
== menhir --canonical assign.mly
The construction mode is canonical.
Built an LR(1) automaton with 16 states.
== menhir --lalr mysterious.mly
The construction mode is lalr.
Built an LR(1) automaton with 21 states.
Warning: one state has reduce/reduce conflicts.
Warning: one reduce/reduce conflict was arbitrarily resolved.
== menhir  mysterious.mly
The construction mode is pager.
Built an LR(1) automaton with 22 states.
== menhir --canonical mysterious.mly
The construction mode is canonical.
Built an LR(1) automaton with 23 states.

What to notice: Menhir's default is Pager's method. On the running example it stays at the LALR size (12 = our 10 + two states for Menhir's explicit EOF rule), while canonical needs 4 more (our 10 vs 14). On mysterious Pager splits exactly one state (21 → 22), removing the LALR conflict, one state below canonical (23); our oracle gives the same shape: LALR 19, PGM 20, LR(1) 21 [MENHIR-Manual].

IELR(1)¶

Bison (3.8.2) src/ielr.c — ielr runs the phases: ielr_compute_auxiliary_tables (phase 1: ielr_compute_follow_kernel_items, ielr_compute_always_follows, ielr_compute_predecessors), ielr_compute_annotation_lists (phase 2), ielr_split_states (phase 3), ielr_compute_lookaheads (phase 4); annotations live in src/AnnotationList.c [BISON-src].

Bison: LALR, IELR and canonical LR on the mysterious grammar

Reproduce (bison 3.8.2; any OS):

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
for t in lalr ielr canonical-lr; do
  bison -Wno-conflicts-rr -Dlr.type=$t --report=states --report-file=$t.output -o /dev/null mysterious.y
  echo "$t: $(grep -cE '^State [0-9]+$' $t.output) states"
done
bison -Dlr.type=ielr --trace=ielr -o /dev/null mysterious.y 2>&1 | grep -A3 "^Inadequacy annotations for state 1:"

Output (complete):

lalr: 20 states
ielr: 21 states
canonical-lr: 22 states
Inadequacy annotations for state 1:
  Annotation 0 (manifesting state 1):
    Contributes token 4 as lookahead, rule number 6, items: nbits = 2, set = { 0 }
    Contributes token 4 as lookahead, rule number 7, items: nbits = 2, set = { 1 }

What to notice: IELR adds exactly one state to LALR (our 19 → 20; Bison counts its accept state). The trace shows phase 2's annotation on state 1, the state after ID: token 4 (,) is contributed to rule 6 (type: ID) by kernel item 0 and to rule 7 (name: ID) by kernel item 1 — Definition 3.4.2's "which kernel items contribute which action". Isocores of state 1 with different contribution sets are split in phase 3 [BISON-Manual].

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Pager's PGM	LR(1) (Theorem 3.4.8); merges only weakly compatible isocores	Near LALR · Menhir builds OCaml-scale grammars in seconds	No mysterious conflicts; error behavior between LALR and canonical	Moderate: LR(1) closure plus a merge test and re-expansion	Menhir (default), Hyacc
IELR(1)	Same actions as canonical LR(1), including resolved conflicts (Theorem 3.4.10); LALR-sized when LALR is adequate	LALR + annotations · PostgreSQL: 3.3 s vs 2.2 s	Exactly canonical decisions; still default reductions	High: five phases, annotation lists	Bison `%define lr.type ielr`

Choose Pager's method when you write a generator and want LR(1) power with LALR-like sizes for modest effort. Choose IELR(1) when you use Bison on a grammar with LALR artifacts (mysterious reduce/reduce conflicts, or precedence declarations whose effect differs between contexts): it removes them without touching the grammar, at a small cost.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch03.yaml`)	Drill	Flashcard tag	Exercises
Pager's PGM	`weak-compatibility`, `state-count-order`	`./course drill lr-classify --difficulty hard` (state counts); PGM itself is the lab's stretch goal	`pgm`	E6 ★
IELR(1)	`ielr-lalr-grammar`, `state-count-order`	`./course drill lr-classify` (decides whether IELR would split: LR(1) but not LALR(1))	`ielr`	— (Bison is the reference implementation; the lesson explains why the lab does not re-implement its five phases)

Minimal LR(1) does not make a grammar unambiguous

Switching to IELR or Pager only removes conflicts that are artifacts of merging. A shift/reduce conflict is never an artifact (Lemma 3.4.7): the grammar is ambiguous or needs more lookahead, and you need precedence declarations or a rewrite (Lesson 3.5).

References¶

See the chapter references.

#	from	on	kernel with lookaheads	decision	to
1	0	a	\([S \to a \bullet A\,d,\ \$]\), \([S \to a \bullet B\,e,\ \$]\)	new	1
2	0	b	\([S \to b \bullet B\,d,\ \$]\), \([S \to b \bullet A\,e,\ \$]\)	new	2
3	0	S	\([S' \to S \bullet,\ \$]\)	new	3
4	1	c	\([A \to c \bullet,\ d]\), \([B \to c \bullet,\ e]\)	new	4
5	1	A	\([S \to a\,A \bullet d,\ \$]\)	new	5
6	1	B	\([S \to a\,B \bullet e,\ \$]\)	new	6
7	2	c	\([A \to c \bullet,\ e]\), \([B \to c \bullet,\ d]\)	isocore of 4, not weakly compatible	new 7
8	2	A	\([S \to b\,A \bullet e,\ \$]\)	new	8
9	2	B	\([S \to b\,B \bullet d,\ \$]\)	new	9
10–13	5, 6, 8, 9	d, e, e, d	the four completed \(S\)-items	new	10–13

Technique	Time (worst)	Time (typical)	Space	Variables
PGM	\(O(\lvert Q_1 \rvert^2 \cdot \lvert G \rvert \cdot \lvert T \rvert)\): each new kernel is tested against every isocore, and a state can be re-expanded once per growth of its lookaheads (at most \(\lvert G \rvert \cdot \lvert T \rvert\) times)	≈ LALR size: 10 vs 14 states (running example); Menhir: 22 vs 21 LALR vs 23 canonical (`mysterious`)	\(O(\lvert Q_P \rvert \cdot \lvert G \rvert \cdot \lvert T \rvert)\)	as above
IELR(1)	LALR, plus annotations \(O(I \cdot \lvert Q_0 \rvert \cdot \lvert G \rvert)\), plus a PGM-like phase 3	3.3 s vs 2.2 s for LALR on PostgreSQL; 6 459 vs 6 458 states	\(O((\lvert Q_I \rvert + I \cdot \lvert Q_0\rvert) \cdot \lvert G \rvert)\)	as above

Lesson 3.4 — Minimal LR(1): Pager's method and IELR(1)¶

1. Problem and motivation¶

Pager's practical general method¶

IELR(1)¶

2. Definitions and algorithms¶

Pager's practical general method¶

IELR(1)¶

3. Worked example¶

Pager's practical general method on the example¶

IELR(1) on the example¶

4. Invariants and correctness¶

Pager's practical general method¶

IELR(1)¶

5. Complexity¶

6. Variants and refinements¶

Pager's practical general method¶

IELR(1)¶

7. In real compilers¶

Pager's practical general method¶

IELR(1)¶

8. Comparison¶

9. Assessment¶

References¶