Lab 3 · The LR toolkit: LR(0), SLR(1), LALR(1) two ways, LR(1), and ★ GLR¶

Chapter: 3 · Bottom-Up Parsing · Lessons: 3.1, 3.2, 3.3, 3.5, 3.6 · Time: 12–18 hours (+4 for ★ G1) · Tests: ./course test 3 (label ch03)

Goal¶

You build an LR parser generator and its driver behind one small contract, include/lr/LR.h:

The toolkit (your code in src/, switch lr-toolkit): the canonical LR(0) automaton (closure and GOTO), the canonical LR(1) automaton, LALR(1) both by merging LR(1) states and by DeRemer–Pennello lookaheads (they must agree), the ACTION/GOTO table for LR(0), SLR(1), LALR(1) and LR(1) with classified conflicts and yacc-style precedence resolution, and one shift-reduce driver for all of them.
The comparison lab (no extra code): the provided lr compare tool uses your functions to count states and conflicts of the four methods over 33 grammars (Chapter 2's corpus plus eleven LR grammars) and classifies each; a test checks that your LR parser builds exactly the trees of your Chapter 2 LL(1) parser wherever both apply.
★ G1 (your code in glr/, switch glr): Tomita's GLR parser over your (conflicting) table, returning a shared packed parse forest.

You design every data structure: item sets, how you intern kernels, the relations, the stack. The provided code is infrastructure only: augmentation and the grammar-file reader with precedence lines (provided/Grammar.cpp), the printers of the golden formats (provided/Print.cpp), and the lr tool. The grammar model itself is Chapter 2's (labs/ch02-ll1-toolkit/include/ll1/Grammar.h), linked, not copied.

Requirements¶

Grammars are augmented (lr::augment): production 0 is S' -> S; production $k \ge 1$ is production $k$ of the file (1-based numbering of Grammar::numbered()); symbol ids are those of the file's grammar. Items are Item{Production, Dot} (Lesson 3.1, Definition 3.1.6).

R1 (closure and states). buildAutomaton(G, Method::LR0) returns the canonical LR(0) collection: every state's Kernel and Closure (non-kernel items) sorted by (Production, Dot), Goto holding every transition, Lookaheads empty. State 0 is CLOSURE({S' -> . S}).
R2 (numbering). States are numbered breadth first: process states in index order, and for each state create its successors in symbol order — G.terminals() (first appearance), then G.nonterminals() without S' — appending a state when its kernel is new. (This is Algorithm 3.1.10; it makes your numbers equal the golden files and Bison's, see Lesson 3.1.)
R3 (canonical LR(1)). Method::LR1 returns the canonical LR(1) automaton (Algorithm 3.2.8): states are equal only if their kernels and kernel lookaheads are equal; numbering as R2; Lookaheads holds every item of Kernel and Closure with its full lookahead set ($ is symbol 0).
R4 (LALR(1) two ways). Method::LALR1Merge returns the LR(0) automaton (same numbering) whose Lookaheads holds, for every item, the union over the canonical LR(1) states with that core (Algorithm 3.3.5). Method::LALR1 returns the LR(0) automaton whose Lookaheads holds at least every completed item (Dot == |rhs|) with its DeRemer–Pennello lookahead set (Algorithm 3.3.7; S' -> S . gets {$}). You must not build LR(1) states for Method::LALR1. Method::SLR1 returns the LR(0) automaton.
R5 (table). buildTable(G, A, M, Prec) returns Actions with exactly the non-empty cells: shift on terminal transitions; accept on $ for S' -> S .; reduce p for each completed item with $p \ne 0$ on: every terminal and $ (LR0), FOLLOW of its left side (SLR1), its lookahead set (LALR1, LALR1Merge, LR1). Each cell sorted (shift < reduce by production < accept < error), without duplicates. Gotos holds every nonterminal transition. Conflicts has one entry per cell with ≥ 2 actions (after precedence), ordered by (state, symbol id), Kind ShiftReduce iff the cell has a shift. NumStates = number of states.
R6 (precedence). With a non-empty Prec, resolve yacc-style (Definition 3.5.3): for each cell with a shift and reductions, in order (state, token name by ll1::symbolNameLess), and for each reduction in the cell, if both the rule (its last terminal that has a level) and the token have levels, compare them; log one Resolution with the exact Why strings of LR.h; a cell left without actions holds one Error action. Resolved cells are not conflicts.
R7 (driver). parseLR(G, T, Input) runs Algorithm 3.1.18 using each cell's first action. Steps has one entry per move (stack before the move; Position = index of the lookahead) with actions shift N, reduce (p) <G.productionString(p)>, accept. Reductions lists the productions reduced (augmented indices), Tree is rooted at the original start symbol with augmented production indices (the contract comment). On an error: SyntaxError{Position, Found, Expected} with Expected = terminals (and $) having a non-error action in the top state, sorted by symbol id.
R8 (performance). Every ch03 test runs in well under a second on the reference design; the automata may be built with ordered maps (no need for hashing), but closure must be a worklist (not "repeat until nothing changes" over all items of the grammar), and Method::LALR1 must be linear in the size of the relations (Digraph, Theorem 3.3.10).
R9 (★ GLR). parseGLR(G, T, Input) implements Algorithm 3.6.4 for grammars without ε-productions and cycles, over a table built by any method (conflicts kept): it returns a Forest whose Root is (S, 0, n), with (Sym, Start, End) unique, terminal nodes without packed nodes, each PackedNode consistent with its production (children symbols and adjacent spans), no duplicate packed node, and exactly the parse trees of the input (counted by the provided countTrees); on rejection, a SyntaxError whose Position is the level at which every stack died.

The contract¶

// labs/ch03-lr-toolkit/include/lr/LR.h  (provided; do not change; abridged)
namespace lr {
Grammar augment(const Grammar &G);                                   // provided
std::expected<GrammarFile, pebble::Error> readGrammarFile(const std::string &Path);  // provided
struct Item { unsigned Production, Dot; };
struct State { std::vector<Item> Kernel, Closure; std::map<Item, SymbolSet> Lookaheads;
               std::map<Symbol, unsigned> Goto; };
struct Automaton { std::vector<State> States; };
enum class Method { LR0, SLR1, LALR1, LALR1Merge, LR1 };
Automaton buildAutomaton(const Grammar &G, Method M);                             // E1-E3
ParseTable buildTable(const Grammar &G, const Automaton &A, Method M,
                      const Precedence *Prec = nullptr);                          // E4
std::expected<ParseResult, ll1::SyntaxError>
parseLR(const Grammar &G, const ParseTable &T, std::span<const Symbol> Input);    // E5
std::expected<Forest, ll1::SyntaxError>
parseGLR(const Grammar &G, const ParseTable &T, std::span<const Symbol> Input);   // G1 (optional)
}

Read the header for every field (Action, Conflict, Resolution, ParseTable, ParseStep, ParseResult, ForestNode, PackedNode, Forest). The functions own nothing and return values.

Where your code goes: any *.cpp under src/ (E1–E5) and under glr/ (G1). Both start with a Stub.cpp that defines the contract with PEBBLE_TODO; delete it as you implement. Add files and private headers freely.

Input and output formats¶

Grammar files: Chapter 2's format (tests/ch02/Inputs/*.grammar), plus optional precedence lines anywhere, lowest level first:

%left + -
%left * /
%right ^
E -> E + E | E - E | E * E | E / E | E ^ E | ( E ) | id

Golden reports (lr report <file> --method lr0|slr|lalr|lalr-merge|lr1, printed by the provided formatReport from your automaton and table; files tests/ch03/Inputs/<name>.<method>; lalr-merge must print the .lalr file):

[method] lalr
[grammar]
(0) S' -> S
(1) S -> L = R
…
[states] 10
state 0
  S' -> • S
  + S -> • L = R
  …
  on * -> 1
…
state 4
  S -> L • = R
  R -> L •  , $
  on = -> 8
…
[action]
4 =: s8
4 $: r5
…
[goto]
0 S: 3
…
[conflicts]
summary: 10 states, 0 shift/reduce, 0 reduce/reduce

For lr1 every item line ends with , <lookaheads>; for lalr only completed items do. With precedence a [resolved] section lists state token: rN vs shift -> <why>.

lr compare prints one line per grammar: name: lr0 N s/r | slr N s/r | lalr N s/r | lr1 N s/r | CLASS (golden tests/ch03/Inputs/corpus.compare; precedence lines are ignored). lr parse [--trace] [--tree] prints the trace as a Markdown table, then accept; reductions: … or the error. lr glr prints trees: N and the forest, one symbol node per line.

Provided infrastructure¶

File	What it gives you
`include/lr/LR.h`, `provided/Grammar.cpp`	the contract; `augment`, `isAugmented`, `readGrammar(File)` with precedence lines
`include/lr/Print.h`, `provided/Print.cpp`	`formatReport` (golden format), `stepsToTable`, `countTrees`, `formatForest`, `classify` (uses your functions), `methodName`/`parseMethod`, `itemString`
`tools/lr.cpp`	the `lr` command-line tool (`report`, `parse`, `classify`, `compare`, `glr`)
Chapter 2: `ll1/Grammar.h`, `ll1/Language.h`, `ll1/Print.h`	the grammar model, bounded-language enumeration, random sentences, tree printing
`tests/ch03/Inputs/`	11 LR grammars with golden reports for the four methods (produced by `tools/course/lib/lr.py`; regenerate with `tests/ch03/update_goldens.py`) and `corpus.compare`

What the tests check¶

Every test goes through the contract or the lr tool.

Test	Checks
`ch03.Provided*`	the provided code (pass in the skeleton build)
`ch03.AutomatonLR0.`, `ch03.AutomatonLR1.`	R1–R3: the closure of state 0, the running example's 10 LR(0) states with their numbers and transitions, ε-items, the 14 canonical LR(1) states and their lookaheads, Dragon-book state counts
`ch03.LalrDeRemerPennello.`, `ch03.LalrMerge.`, `ch03.Corpus/LalrAgreeCorpus.*`	R4: the running example's LALR lookaheads, the reads relation on nullable nonterminals, merged lookaheads on every item, merge-induced reduce/reduce conflicts, and both constructions agree on all 33 corpus grammars
`ch03.Table.`, `ch03.Corpus/Golden.`	R5–R6: cells, conflict kinds, precedence resolution and `%nonassoc` error entries; `formatReport` byte-for-byte equal to all 55 golden reports (11 grammars × lr0, slr, lalr, lalr-merge, lr1)
`ch03.Corpus/Classify.*`	the comparison lab: states, shift/reduce and reduce/reduce counts of the four methods and the class of every grammar equal `corpus.compare`
`ch03.Driver.`, `ch03.Corpus/DriverLanguage.`	R7: the 11-step trace of Lesson 3.1, reductions = reversed rightmost derivation, error positions and expected sets, default resolution of the dangling else, precedence trees, `%nonassoc`; acceptance = membership in the bounded language (all strings of length ≤ 4) for every conflict-free method on 16 grammars
`ch03.Random.*`	R4–R7 on 450 random grammars: both LALR constructions give identical tables, the class hierarchy holds, merging never adds shift/reduce conflicts, conflict-free tables accept exactly the language (up to length 6)
`ch03.LL1Corpus/AgreeWithLL1.*`	your `parseLR` and your Chapter 2 `parseLL1` return the same trees and verdicts on 200 inputs per LL(1) grammar (needs Chapter 2 done, or `-DPEBBLE_USE_SOLUTION=ll1-toolkit`)
`ch03.GLR.*`	★ R9: Catalan tree counts, forest structure and polynomial size, rejection positions, a non-LALR grammar with an LR(0) table, and forests = brute-force tree counts on 120 random ε-free grammars
`ch03.lit`	the `lr` tool on your code: 55 golden report diffs, `compare` against `corpus.compare`, `classify`, traces, errors, trees, usage errors, and `glr` forests

Milestones¶

LR(0) (E1): ctest --preset linux -L '^ch03$' -R 'AutomatonLR0' (macOS: --preset macos); then lr report tests/ch03/Inputs/assign.grammar --method lr0.
Tables (E4, LR(0)/SLR first): -R 'ch03.Table|Golden.*(lr0|slr)'.
Driver (E5): -R 'ch03.Driver'; lr parse tests/ch03/Inputs/assign.grammar --trace '* id = id' prints Lesson 3.1's table.
LR(1) (E2): -R 'AutomatonLR1|Golden.*lr1'.
LALR two ways (E3): -R 'Lalr|Golden.*lalr'.
Everything, and the comparison lab: ./course test 3; then the measurement below.
★ GLR (G1): -R 'ch03.GLR'; lr glr tests/ch02/Inputs/expr-ambiguous.grammar id + id '*' id.

Measurement¶

Run build/<preset>/bin/lr compare tests/ch02/Inputs/*.grammar tests/ch03/Inputs/*.grammar and fill in, for five grammars of your choice plus these three:

grammar	LR(0) states	LR(0) conflicts	SLR conflicts	LALR conflicts	LR(1) states	class
`statements` (ch02)
`assign` (ch03)
`bison-mysterious` (ch03)

Then answer: which grammars have more LR(1) than LALR states without being non-LALR? Why does no LL(1) grammar in the corpus fall in none? (Lesson 3.2, Theorem 3.2.14.) Compare with Bison's lalr/ielr/canonical-lr counts (Lesson 3.4's box) for one grammar.

Hints¶

Hint 1 — where to start

Write CLOSURE for LR(0) items first (a worklist over a vector, a set of seen items) and print state 0 of the running example; it must match Lesson 3.1 §3. Then GOTO as "advance the dot over X, sort, deduplicate": that sorted vector is the kernel, and a std::map<std::vector<Item>, unsigned> interns states. You need nullable, FIRST and FOLLOW for SLR and LR(1): compute them yourself on the augmented grammar (or call your Chapter 2 ll1::analyze if you finished it).

Hint 2 — the key ideas

LR(1): represent a kernel as std::map<Item, SymbolSet> and intern that map; closure propagates lookaheads $\mathrm{FIRST}(\beta a)$ and must re-queue an item whose set grew.
Merging: map each LR(1) state to the LR(0) state with the same kernel core (the kernel's items without lookaheads) and union per item.
DeRemer–Pennello: number the nonterminal transitions (p, A), build DR, reads, includes (walk p' --β--> p for each B -> β A γ with γ nullable) and lookback as vectors of indices, and run one Digraph function twice. Don't forget $ in DR of the transition on S from state 0.
Table: build all actions, then sort and deduplicate each cell, then resolve precedence, then collect conflicts.
Driver: keep three parallel stacks (states, symbols, trees); a reduce by A -> β pops |β| of each, which is zero for ε.

Hint 3 — a design sketch

The reference solution (one possible design): src/Internal.h (the Sets of nullable/FIRST/FOLLOW, firstOf, symbolOrder, closure0, closure1), src/Automata.cpp (the sets, both closures, the LR(0) and LR(1) collections, buildAutomaton), src/Lalr.cpp (merging; a small Digraph class; DeRemer–Pennello), src/Table.cpp (actions, precedence, conflicts), src/Driver.cpp; glr/GLR.cpp (a GSS as a vector of nodes with edge lists, a std::map<std::tuple<Symbol, size_t, size_t>, unsigned> for symbol nodes, a worklist of (node, optional edge) for the reducer).

Bugs the tests catch most often: successors not in symbol order (every golden differs from state 1 on); closure1 not re-queuing an item whose lookaheads grew (Random.LalrTwoWaysAgreeAndTheHierarchyHolds: the corpus grammars happen not to need it); forgetting $ for (0, S) in DR (RunningExampleLookaheads); reads relation missing (NullableNonterminalsUseReads); precedence taken from the first instead of the last terminal of the rule (RuleLevelIsItsLastTerminalWithALevel); GLR re-reducing only from new nodes but not through new edges (AmbiguousExpressionsGiveCatalanManyTrees).

Stretch goals ★¶

G1: the GLR parser of R9 (tests ch03.GLR.*).
E6: Pager's PGM (Algorithm 3.4.4) as a sixth method in your own code; check it is conflict-free on every LR(1) corpus grammar and compare its state counts with lr.state_counts in tools/course/lib/lr.py (the oracle implements it).
E7: yacc's error recovery (Algorithm 3.7.5) in your driver; reproduce Lesson 3.7's 22-step trace on tests/ch03/Inputs/error-stmts.grammar.