Chapter 2 exercises¶

You implement the LL(1) toolkit (nullable, FIRST, FOLLOW, the LL(1) table, the table-driven parser with panic-mode recovery, and the grammar transformations) and the comparison lab (recursive descent vs the table, naive vs memoized backtracking). The whole task is specified in labs/ch02-ll1-toolkit/SPEC.md: requirements R1–R12, the contract, the formats, and exactly what every test checks. This page orders the work and gives hints.

The contract is one header, labs/ch02-ll1-toolkit/include/ll1/LL1.h: nine functions and the plain result types they return. The tests call nothing else.
Your code goes anywhere under labs/ch02-ll1-toolkit/src/ (E1–E8, switch ll1-toolkit) and labs/ch02-ll1-toolkit/rd/ (L1–L4, switch rd-compare). Each starts with a Stub.cpp whose functions stop with TODO(ch02): …; replace it with your own files and design (every *.cpp there is compiled).
Provided: the grammar model and file reader, the bounded-language oracle, the printers, the lab's fixed expression grammar, the ll1 tool and the golden corpus tests/ch02/Inputs/.

./course test 2                                          # builds, then runs every test labelled ch02
ctest --preset linux -L '^ch02$' -R 'ch02.Analysis'      # one group while iterating (macOS: --preset macos)
build/linux/bin/ll1 report tests/ch02/Inputs/running.grammar   # try your code on any grammar file

Before you start, every ch02 test except the provided-code ones (ch02.GrammarFormat.*, ch02.Language.*) fails with TODO(ch02): …, and the message names the step below that fixes it. The golden files tests/ch02/Inputs/*.expected and *.transformed were produced by the course's Python oracles (tools/course/lib/grammar.py), which also produced every trace in the lessons.

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

E1–E3 · nullable, FIRST and FOLLOW¶

Contract: GrammarAnalysis analyze(const Grammar &G) · Spec: R1–R3 · Tests: ch02.AnalysisNullable.*, ch02.AnalysisFirst.*, ch02.AnalysisFollow.*, ch02.AnalysisCrossCheck.* · Lesson: 2.2, Algorithm 2.2.6

Compute the three least fixed points by round-robin iteration, in dependency order (nullable, then FIRST, then FOLLOW). Return them as vectors indexed by Symbol, with the conventions of R2 for terminals and $.

Requirements: exact least fixed points on every grammar (Theorem 2.2.11); no $\varepsilon$ pseudo-symbol in FIRST (nullability is its own vector); $ in FOLLOW of the start symbol.

Hint 1 — where to start

Write the FIRST-of-a-string helper of Lesson 2.2 first: walk the symbols, add each one's FIRST set, stop at the first symbol that is not nullable, and report whether you ran off the end (the string is nullable; the empty string included). Everything else in this chapter uses it.

Hint 2 — the key idea

Each loop is "repeat whole passes over the productions until a pass changes nothing" (Lemma 2.2.10 says why that is enough). If you index your nullable vector by symbol and leave terminals false, "is this right-hand-side symbol nullable?" needs no special case, and all_of over an empty right side handles A → ε.

Hint 3 — a design sketch

Three functions plus the helper, each returning a vector sized G.numSymbols(); analyze calls them in order. Rule W3 copies FOLLOW(A) into FOLLOW(B): when B = A (A → a A), copy the source set before inserting (SelfReferenceAtTheEnd). Stopping after one pass fails NeedsSeveralPasses; forgetting W3 fails RunningExampleOfTheLesson.

Done when: ch02.Analysis* pass.

E4 · The LL(1) table and its conflicts¶

Contract: LL1Table buildLL1Table(const Grammar &G, const GrammarAnalysis &A) · Spec: R4 · Tests: ch02.Table.*, ch02.Golden/Corpus.*, lit report.test, table.test · Lesson: 2.3, Algorithm 2.3.5

Put each production into the cells of its PREDICT set, without duplicates, then list every cell with two or more productions as a Conflict with the kind of Definition 2.3.3.

Hint 1 — where to start

One loop over the productions with the FIRST-of-a-string helper from E1–E3: the lookaheads are its FIRST set, plus FOLLOW of the left side if the right side is nullable.

Hint 2 — the key idea

Classify after the table is complete, by counting how many of the cell's productions have the lookahead in FIRST of their right side. The count decides the kind, not the order of insertion. Two nullable alternatives conflict on all of FOLLOW(A), and neither reaches the lookahead through FIRST: FIRST/FOLLOW (two-nullable.grammar).

Hint 3 — a design sketch

A small add(M, A, t, p) that skips duplicates keeps Cells clean. When a golden report differs, ll1 report tests/ch02/Inputs/<name>.grammar | diff - tests/ch02/Inputs/<name>.expected shows the first wrong line.

Done when: all 22 ch02.Golden/Corpus.ReportMatchesGolden/* tests pass.

E5 · The table-driven predictive parser¶

Contract: parseLL1(G, M, Input) · Spec: R5 and "Formats" · Tests: ch02.PredictiveParser.*, lit parse.test · Lesson: 2.5, Algorithm 2.5.4

Run the stack machine, recording every step (stack before the move, position, action text), the leftmost derivation, and the concrete tree; stop at the first error with its expected set.

Hint 1 — where to start

Reproduce Lesson 2.5 §3's 17-step table for id + id * id first (ll1 parse tests/ch02/Inputs/expr-ll1.grammar --trace id + id '*' id); build the tree once the steps are right.

Hint 2 — the key idea

Keep on the stack, next to each symbol, a pointer to the tree node it will fill. When you expand a node, size its children vector once and push pointers to the children in reverse order; since that vector never grows again, the pointers stay valid.

Hint 3 — a design sketch

A Driver class that owns the stack and a run(ParseResult &) loop with one branch per move of Definition 2.5.1. The expected set depends on the top: the terminal itself, {$}, or the non-empty cells of the nonterminal's row, sorted by id. Anticipate E6 by giving the driver an optional pointer to the analysis (null means "stop at the first error").

Done when: ch02.PredictiveParser.* pass.

E6 · Panic-mode recovery¶

Contract: parseWithRecovery(G, A, M, Input) · Spec: R6 · Tests: ch02.PanicMode.*, lit parse.test · Lesson: 2.7, Algorithm 2.7.3

The same driver, but at an error record it and recover (pop, or skip, per R6) instead of stopping; the parse always reaches the end of the input.

Hint 1 — where to start

Reuse the E5 driver: the four recovery branches replace its four return error sites.

Hint 2 — the key idea

Recovery must never push (Lemma 2.7.8): every action pops or consumes, which is why the loop terminates (Theorem 2.7.9).

Hint 3 — a design sketch

AgreesWithTheStrictParserOnSentences compares with E5 on 800 random inputs: on a sentence no recovery happens and the tree is identical; otherwise the first recorded error equals E5's error. A popped nonterminal stays in the tree as a node without a production.

Done when: ch02.PanicMode.* pass.

E7 · Left-recursion elimination (SCC-restricted Paull)¶

Contract: eliminateLeftRecursion(G) · Spec: R7 and "Output conventions" · Tests: ch02.TransformLeftRecursion.*, ch02.TransformProperties.*, ch02.Corpus/TransformGolden.*, lit transform.test · Lesson: 2.4, Algorithms 2.4.4–2.4.5

Substitute earlier nonterminals of the same left-corner SCC, then remove direct left recursion, nonterminal by nonterminal in grammar order; check the result and fail with the documented messages.

Hint 1 — where to start

Compute the left-corner graph (Definition 2.4.2: an edge A → B when B can be the first symbol after a nullable prefix) and its reachability closure once, on the input grammar. Aᵢ and Aⱼ share an SCC iff each reaches the other. The same closure answers "is the result still left-recursive?" at the end.

Hint 2 — the key idea

Work on a copy that is easy to rewrite (alternatives per nonterminal plus an output order), create fresh nonterminals in a copy of the grammar with freshName, and build the result Grammar at the end, mapping symbols by name.

Hint 3 — a design sketch

Per Aᵢ: substitute only if some alternative actually starts with Aⱼ; remove duplicates after each substitution (keep the first); drop Aᵢ → Aᵢ; split into tails and bases; bases get Aᵢ′, and Aᵢ′ gets each tail followed by Aᵢ′, then ε. Without the SCC test, OnlySubstitutesInsideLeftCornerCycles fails on json.grammar (18 productions become 24).

Done when: ch02.TransformLeftRecursion.* pass.

E8 · Left factoring¶

Contract: leftFactor(G) · Spec: R8 and "Output conventions" · Tests: ch02.TransformLeftFactor.*, ch02.TransformProperties.*, ch02.Corpus/TransformGolden.* · Lesson: 2.4, Algorithm 2.4.6

Repeatedly factor the first group's longest common prefix into a fresh nonterminal until no nonterminal has two alternatives with the same first symbol.

Hint 1 — where to start

Reuse E7's working representation. Restart the scan from the first nonterminal after every rewrite: the new A′ may need factoring itself (NestedPrefixesNeedSeveralRounds).

Hint 2 — the key idea

The rewritten alternative A → α A′ takes the position of the group's first member, the other members disappear, and A′ goes into the order right after A and after the primes of A already there. Theorem 2.4.11's potential shows why the loop terminates.

Hint 3 — a design sketch

ll1 transform tests/ch02/Inputs/if-unfactored.grammar --no-left-recursion must print S' -> ε | e S (remainders in group order, ε included). Then run TransformProperties.RandomGrammars: every result must keep its bounded language.

Done when: all ch02.Transform* and ch02.Corpus/TransformGolden.* tests pass.

Lab · Recursive descent vs the table; backtracking vs memoization¶

Directory: labs/ch02-ll1-toolkit/rd/ (switch rd-compare) · Spec: R9–R11 and "Measurement" · Tests: ch02.RDCompare.*, ch02.Backtracking.*, lit rd.test, backtrack.test

The RDCompare tests compare with your parseLL1: finish E1–E5 first, or configure with -DPEBBLE_USE_SOLUTION=ll1-toolkit to compare against the reference toolkit.

L1 · A predictive recursive-descent parser¶

Contract: rd::parseTree(G, Input) · Lesson: Algorithm 2.5.5, Proposition 2.5.10

Hand-write a parser for rd::exprGrammar() that returns exactly what the table-driven parser returns: the same trees (same production indices) and the same errors (position, found token, expected set).

Hint 1 — where to start

Print the table first (ll1 table on a file containing rd::ExprGrammarText). One function per nonterminal; each function's cases are exactly its row.

Hint 2 — the key idea

Take the ε-alternatives of E′ and T′ only on their FOLLOW tokens, and report an error otherwise with the row's terminals as the expected set. A default: ε case moves the error to the caller.

Hint 3 — a design sketch

A small internal class holding the grammar, the input span, the position and the looked-up symbols, with peek, advance, expect(t) and error(expected) helpers. AgreesOnRandomInputs prints both errors on the first disagreement; a typical bug is checking FIRST(E) in parseT but not in parseE.

L2 · A left-associative AST from a right-recursive grammar¶

Contract: rd::parseAst(G, Input)

Parse sums and products with loops and fold to the left, so id - id - num gives ((id-id)-num).

Hint 1 — where to start

A sum is a product followed by any number of (+ or -, product); a product likewise with * and /.

Hint 2 — the key idea

An accumulator: after each operator, the new node's left child is everything parsed so far. That is the whole difference between the right-nested CST and the left-nested AST (Lesson 2.4's pitfall).

Hint 3 — a design sketch

A tiny AST struct (operator or leaf, two children) and a printer that parenthesizes every binary node. Require $ after the top-level sum so errors are found at the same token as the table-driven parser (AstParserDetectsErrorsAtTheSameToken).

L3–L4 · Backtracking, naive and memoized¶

Contract: backtrackRecognize(G, Input, Memoize) · Lesson: Algorithms 2.5.6–2.5.7, Proposition 2.5.14

Recognize any non-left-recursive grammar by computing, for a symbol and a position, every end position; count calls; with Memoize, cache results per (nonterminal, position).

Hint 1 — where to start

A terminal yields one end position or none. A nonterminal unions its alternatives; an alternative threads a set of positions through its symbols and stops early when the set is empty.

Hint 2 — the key idea

Count a call only when a nonterminal runs its alternatives (not for terminals, not for memo hits); the result of (symbol, position) does not depend on how you got there, so the cache is always valid for this recognizer (Lemma 2.5.13). The depth guard of R11 turns left recursion into an error instead of a stack overflow (Lemma 2.5.12).

Hint 3 — a design sketch

An internal class with the call counter and a std::map from (symbol, position) to a sorted vector of positions. ll1 backtrack must print 3, 9, 21, 45, 93, … naive calls (3·2^(d+1) − 3) and 2d + 2 memoized: more means you count terminals; fewer means you stop after the first successful alternative (that is ordered choice, not backtracking).

Measure¶

Fill in the table of SPEC.md "Measurement" with build/<preset>/bin/ll1 backtrack --max-depth 12 and compare with Lesson 2.5 §3.

★ Optional: the stretch goals of the spec (worklist/digraph sets, phrase-level or single-token repair, packrat with ordered choice).