Skip to content

Chapter 3 exercises

You implement an LR parser generator and driver: the canonical LR(0) and LR(1) automata, LALR(1) both by merging and by DeRemer–Pennello, the ACTION/GOTO tables of LR(0), SLR(1), LALR(1) and LR(1) with precedence, and one shift-reduce driver; optionally a GLR parser with a shared packed parse forest. The whole task is specified in labs/ch03-lr-toolkit/SPEC.md: requirements R1–R9, the contract, the formats and exactly what every test checks. This page orders the work and gives hints.

  • The contract is one header, labs/ch03-lr-toolkit/include/lr/LR.h: three functions (plus parseGLR for the optional lab) and the plain result types they return.
  • Your code goes anywhere under labs/ch03-lr-toolkit/src/ (E1–E5, switch lr-toolkit) and labs/ch03-lr-toolkit/glr/ (G1, switch glr). Each starts with a Stub.cpp whose functions stop with TODO(ch03): …; replace it with your own files.
  • Provided: augmentation and the grammar reader with precedence lines, the printers of the golden formats, the lr tool, the corpus tests/ch03/Inputs/ (and Chapter 2's), and Chapter 2's grammar model.
./course test 3                                            # builds, then runs every test labelled ch03
ctest --preset linux -L '^ch03$' -R 'AutomatonLR0'         # one group while iterating (macOS: --preset macos)
build/linux/bin/lr report tests/ch03/Inputs/assign.grammar --method lr0   # your code on any grammar

Before you start, every ch03 test except ch03.Provided* fails with TODO(ch03): …, naming the step below. The golden files were produced by the course's Python oracle (tools/course/lib/lr.py), which also produced every trace in the lessons. ch03.LL1Corpus/AgreeWithLL1.* also calls your Chapter 2 LL(1) parser: finish Chapter 2 first or configure with -DPEBBLE_USE_SOLUTION=ll1-toolkit.

Stuck? Work through the hints in order. The reference solution is in solutions/labs/ch03-lr-toolkit/ (one possible design); look at it only after you pass the tests, or after an honest hour.

E1 · LR(0) items, closure, GOTO and the canonical collection

Contract: buildAutomaton(G, Method::LR0) and Method::SLR1 · Spec: R1–R2 · Tests: ch03.AutomatonLR0.*, ch03.Corpus/Golden.*_lr0 · Lesson: 3.1, Algorithms 3.1.9–3.1.10

Build the LR(0) automaton of the augmented grammar with the course's numbering: breadth first, successors in symbol order.

Hint 1 — where to start

CLOSURE is a worklist over a vector: scan items in order, and for an item with a nonterminal after the dot append that nonterminal's productions with the dot at 0 if not seen. Print state 0 of assign.grammar and compare with Lesson 3.1 §3.

Hint 2 — the key idea

A state is identified by its kernel; with kernels as sorted vectors of items, a std::map<std::vector<Item>, unsigned> interns them. The symbol order is G.terminals() followed by G.nonterminals() without G.start() (which is S').

Hint 3 — a design sketch

closure0(G, kernel) -> vector<Item>, advance(G, items, X) -> sorted kernel, and a loop for (q = 0; q < States.size(); ++q) for (X : order) …. Split the closure into Kernel and Closure at the end, both sorted. The golden assign.lr0 shows the exact expected output.

Done when: ch03.AutomatonLR0.* pass and lr report … --method lr0 equals tests/ch03/Inputs/assign.lr0.

E2 · Canonical LR(1)

Contract: buildAutomaton(G, Method::LR1) · Spec: R3 · Tests: ch03.AutomatonLR1.*, Golden.*_lr1 · Lesson: 3.2, Algorithms 3.2.7–3.2.8

Items carry lookahead sets; states are equal only with equal kernel lookaheads.

Hint 1 — where to start

You need nullable and FIRST on the augmented grammar (Chapter 2's fixed points). Then closure with lookaheads: \([A \to \alpha \bullet B \beta, a]\) adds \([B \to \bullet \eta, b]\) for \(b \in \mathrm{FIRST}(\beta a)\).

Hint 2 — the key idea

Store an item set as std::map<Item, SymbolSet>. When an item's set grows, put it back on the worklist: its successors' lookaheads must grow too (RunningExampleSplitsStates fails otherwise). GOTO unions the lookaheads of the items it advances.

Hint 3 — a design sketch

Intern kernels as std::map<std::map<Item, SymbolSet>, unsigned>; reuse E1's loop. The running example must give 14 states.

Done when: ch03.AutomatonLR1.* and the lr1 goldens pass.

E3 · LALR(1) two ways

Contract: Method::LALR1Merge and Method::LALR1 · Spec: R4 · Tests: ch03.LalrDeRemerPennello.*, ch03.LalrMerge.*, ch03.Corpus/LalrAgreeCorpus.*, ch03.Random.* · Lesson: 3.3, Algorithms 3.3.5–3.3.7

Merge LR(1) states by core; separately, compute DeRemer–Pennello lookaheads on the LR(0) automaton without building LR(1). The tests compare the two.

Hint 1 — where to start

Merging is ten lines on top of E1 and E2: find the LR(0) state with the same kernel core and union lookaheads per item. Do it first; it is your oracle for the second construction.

Hint 2 — the key idea

Number the nonterminal transitions. DR comes from the terminal transitions of the target state (plus $ for the transition on S from state 0); reads follows nullable nonterminal transitions from the target; includes walks each production B -> β A γ with nullable γ from p' along β; lookback walks each A -> ω from p. One Digraph function, called twice.

Hint 3 — a design sketch

A Digraph class holding the relation as vector<vector<unsigned>>, the sets as vector<SymbolSet>, N as vector<unsigned> and a stack; the SCC pop loop copies the root's set to every member. Compare with lr.deremer_pennello in tools/course/lib/lr.py or ./course drill lalr-lookaheads --solution when a set is wrong.

Done when: all Lalr* tests and the lalr goldens pass for both --method lalr and --method lalr-merge.

E4 · ACTION/GOTO, conflicts and precedence

Contract: buildTable · Spec: R5–R6 · Tests: ch03.Table.*, ch03.Corpus/Golden.*, ch03.Corpus/Classify.* · Lessons: 3.1 Definition 3.1.11, 3.2 Algorithm 3.2.6, 3.5 Algorithm 3.5.6

Hint 1 — where to start

Shifts and GOTOs come straight from Goto. For each completed item, decide the reduce lookaheads by method: every terminal and $, FOLLOW, or the item's lookahead set.

Hint 2 — the key idea

Collect all actions first, then sort and deduplicate each cell (the Action type's operator<=> gives the required order), then resolve precedence, then list conflicts. A rule's level is that of its last terminal with a level.

Hint 3 — a design sketch

Process resolution cells in (state, token name) order with ll1::symbolNameLess, and log one Resolution per (cell, reduction) with the exact strings of LR.h. expr-prec.lalr shows the expected [resolved] section.

Done when: ch03.Table.*, all 55 goldens and ch03.Corpus/Classify.* pass.

E5 · The shift-reduce driver

Contract: parseLR · Spec: R7 · Tests: ch03.Driver.*, ch03.Corpus/DriverLanguage.*, ch03.Random.*, ch03.LL1Corpus/AgreeWithLL1.* · Lesson: 3.1, Algorithm 3.1.18

Hint 1 — where to start

Make lr parse tests/ch03/Inputs/assign.grammar --trace '* id = id' print Lesson 3.1's 11-step table before worrying about trees.

Hint 2 — the key idea

Three parallel stacks (states, symbols, trees). Reduce by A -> β: pop |β| from each (zero for ε), push GOTO[top, A], A, and a tree node whose children are the popped trees in order. Use the first action of a cell: that is yacc's default resolution.

Hint 3 — a design sketch

Record the step before performing it. On an empty cell (or an Error action) build the SyntaxError from the top state's non-error cells, sorted by symbol id. The LL(1) agreement test compares trees after subtracting 1 from every production index.

Done when: ./course test 3 passes except the optional ch03.GLR.*.

G1 ★ · GLR with a shared packed parse forest

Contract: parseGLR · Spec: R9 · Tests: ch03.GLR.*, lit glr.test · Lesson: 3.6, Algorithm 3.6.4

Hint 1 — where to start

Reproduce Lesson 3.6 §3's level table on id + id * id with a GSS of (state, level) nodes and labelled edges; count trees with the provided countTrees.

Hint 2 — the key idea

Per level: saturate reductions with a worklist of (node, optional new edge); when a reduction reaches an existing node with a new edge, reduce again only through that edge (in ε-free grammars such paths start at the edge's source). Symbol nodes are unique per (symbol, start, end); a second derivation adds a packed node.

Hint 3 — a design sketch

struct Node { unsigned State; size_t Level; vector<Edge> Edges; }, a map from state to node for the current frontier, a map from (Symbol, start, end) to forest node index, and a set of performed (node, production, path) to avoid duplicates. Enumerate paths of length \(m\) recursively.

E6 ★, E7 ★

See the stretch goals in the SPEC: Pager's PGM as an extra method (Lesson 3.4, Algorithm 3.4.4) and yacc's error recovery in your driver (Lesson 3.7, Algorithm 3.7.5). No tests; compare with the Python oracle (lr.pgm_automaton, lr.yacc_recover_parse).