Chapter 4 exercises

You implement pebblec's parser: recursive descent for items, types and statements, a Pratt loop for expressions, and panic-mode recovery with synchronizing sets, error nodes, an error cap and a nesting limit. Then, in the comparison lab, you build the same expression grammar four ways — Pratt, shunting-yard, packrat PEG, Earley — check them against each other and measure them; the ★ milestone keeps a parsed module up to date under edits.

• The contract is pebble/include/pebble/Parse/Parser.h: parseModule(Lexer&, ASTContext&, DiagnosticEngine&) and parseExpression(…). The grammar is §4 of the Pebble specification, the recovery rules §13.1, the AST dump format §14.2. The AST classes (pebble/include/pebble/AST/) are provided; you build them with Ctx.create<…>(…).
• Your code goes anywhere under pebble/lib/Parse/src/ (switch parser). It starts with a Parser.cpp whose two functions stop with TODO(ch04): …; replace it and add files as you like.
• Provided: the lexer (Chapter 1), the AST and its dumper, the diagnostics engine and codes E0201–E0212, the tools ch04-parsedump and pebblec --emit=ast, and the corpus tests/ch04/Inputs/ with golden .ast files.
• The lab is specified in labs/ch04-paradigms/SPEC.md (requirements R1–R9, contract include/exprlab/ExprParsers.h, milestones L1–L6); this page only orders it.

./course test 4                                                # builds, then runs every test labelled ch04
ctest --preset linux -L '^ch04$' -R 'PebbleParser.E2'          # one group while iterating (macOS: --preset macos)
build/linux/bin/ch04-parsedump tests/ch04/Inputs/fib.pbl       # your AST (and diagnostics) on any file
build/linux/bin/ch04-parsedump --expr 'a + b * c as float'     # one expression
build/linux/bin/ch04-parsedump --unparse tests/ch04/Inputs/items.pbl   # print the AST back as Pebble

Before you start, every ch04 test except ch04.Paradigms.Provided_* fails with TODO(ch04): …. The golden ASTs were produced by the reference parser and cross-checked against an independent Python parser that follows the layered grammar of pebble-spec §4.1 literally (tools/course/lib/pebble_parse.py, run by tests/ch04/update_goldens.py): two different algorithms, one tree (Theorem 4.1.14).

Stuck? Work through the hints in order. The reference solution is in solutions/pebble/lib/Parse/src/ (one possible design); look at it only after you pass the tests, or after an honest hour.

---

E1 · Tokens, items and types

Contract: parseModule · Spec: pebble-spec §4.1 (items, types), §14.2 (dump) · Tests: ch04.PebbleParser.E1_*, lit items.test, fib.test, fib-locations.test · Lesson: 2.5 (recursive descent), 4.7 (the AST design you are filling)

Parse a module: a sequence of fn, struct and extern fn items with parameters (including & reference parameters), result types, fields and the types of §4.1: int, float, bool, str, struct names, arrays [T; N] and references &T/&mut T (there is no () or slice type in source). Function bodies may be {} for now. Every node's range starts at its first token and ends at its last.

Hint 1 — where to start

Wrap the lexer in a small token buffer with peek(k), consume(), at(kind) and expect(kind, what). Skip unknown tokens inside the buffer (rule 2 of §13.1), so no parsing function ever sees one. Then write parseItem, parseParams, parseType as one function per nonterminal of §4.1.

Hint 2 — the key idea

Ranges: remember the first token's location when a function starts and the previous token's end when it finishes; a prevEnd() accessor in the token buffer makes every range one line of code. [T; N] requires N to be an integer literal token (E0210 otherwise, in E5).

Hint 3 — a design sketch

A class Parser { TokenBuffer Toks; ASTContext &Ctx; DiagnosticEngine &Diags; … } with parseModule, parseFunction(bool IsExtern), parseStruct, parseType. Collect children in llvm::SmallVector and copy them into the arena with Ctx.copyArray(…) when the node is built.

Done when: ch04.PebbleParser.E1_* pass and ch04-parsedump tests/ch04/Inputs/items.pbl equals items.ast (the lit test diffs it).

---

E2 · Expressions: the Pratt loop

Contract: parseExpression, and expressions inside parseModule · Spec: pebble-spec §4.1–4.2 (precedence table: || 1, && 2, comparisons 3 non-associative, | 4, ^ 5, & 6, shifts 7, + - 8, * / % 9, as 10, prefix 11, postfix 12) · Tests: E2_* (every precedence pair, associativity at every level, non-associative comparisons, 1500 random expressions round-tripped) · Lesson: 4.1, Algorithm 4.1.8

Parse binary, prefix and cast expressions with one loop driven by binding powers, not one function per level. a < b < c is error E0206 at the second operator (column 7 in a < b < c).

Hint 1 — where to start

Turn the table into binding powers (Definition 4.1.7): level \(p\) left-associative → \((2p, 2p+1)\). Write parseExprBP(unsigned MinBP): parse a prefix expression, then loop while the next token is a binary operator with left power \(\ge\) MinBP. Do the drill ./course drill pratt-trace first.

Hint 2 — the key idea

Non-associativity: after absorbing a comparison, remember its level; if the next operator in the same loop has the same level, report E0206 there (and keep parsing, treating it as left-associative, so the tree is still complete). as is a postfix operator of level 10 whose right side is a type, not an expression.

Hint 3 — a design sketch

std::optional<std::pair<unsigned, BinaryOp>> infixBP(TokenKind); the loop: while (auto BP = infixBP(peek())) { if (BP->first < MinBP) break; … RHS = parseExprBP(BP->first + 1) … }. The random test prints your tree back with minimal parentheses and reparses it; if it fails, run ch04-parsedump --expr on the printed counterexample.

Done when: E2_* pass, in particular E2_RandomExpressionsRoundTripThroughMinimalParentheses.

---

E3 · Statements and blocks

Contract: parseModule · Spec: pebble-spec §4.1 (statements), §4.3 rule 3 (assignment targets) · Tests: E3_*, lit statements.test · Lesson: 2.5

let, var (with optional type and initializer), assignment and compound assignment, expression statements, if/else if/else, while, for i in a..b, return, break, continue, nested blocks.

Hint 1 — where to start

A statement starts either with a keyword (dispatch on it) or with an expression. For the latter, parse the expression first, then look at the next token: = or op= makes it an assignment (check the left side is a place: E0207), ; an expression statement.

Hint 2 — the key idea

else if is an if statement as the else branch; do not add a node kind for it. The for header is for NAME in Expr .. Expr: .. is not an expression operator, so parse the two bounds with parseExprBP(1).

Hint 3 — a design sketch

parseBlock() loops while (!at(RBrace) && !at(Eof)) Stmts.push_back(parseStmt()); — E6 will add the recovery exits to this loop (Algorithm 4.6.3).

Done when: E3_* pass and statements.test matches.

---

E4 · Primaries, postfix chains and the §4.3 disambiguation rules

Contract: both functions · Spec: pebble-spec §3.3–3.5 (literals, interpolation), §4.1 (primaries), §4.3 rules 1–4 · Tests: E4_*, lit expressions.test, spec-examples.test · Lesson: 4.1 (postfix operators as the highest level)

Literals (integers up to \(2^{63}\) as the operand of unary minus, floats, true/false, strings with interpolation), names, calls, indexing, member access, array literals [a, b], repeats [e; N], struct literals S { f: e }, parentheses (kept as paren nodes). Rule 1: no struct literal directly in an if/while/for condition; rule 4: & only as a call argument. parseExpression must reject trailing tokens.

Hint 1 — where to start

Postfix (, [, . are infix operators of power 12 in the Pratt loop whose "right side" is an argument list, an index or a field name. Interpolated strings arrive from the lexer as a sequence of pieces (§3.5).

Hint 2 — the key idea

Rule 1 is a context flag, not a grammar change: parse conditions with a "no struct literal" flag set and clear it inside parentheses, brackets and blocks. An RAII guard that saves and restores the flag keeps this correct on every return path.

Hint 3 — a design sketch

struct NoStructScope { Parser &P; bool Old; … }. At NAME {, build a struct literal only if the flag is clear; otherwise the { starts the body. If a struct literal was clearly intended (NAME { ident :), report E0208 at the name.

Done when: E4_* pass and expressions.test, spec-examples.test match.

---

E5 · Diagnostics

Contract: diagnostics through DiagnosticEngine · Spec: pebble-spec §13.1 (the E0201–E0212 table and where each points) · Tests: E5_*, lit err-expressions.test, err-items.test · Lesson: 2.7, 4.6 §2

Report each syntax error with the right code at the right location: the lookahead token, with the exceptions listed in §13.1. A missing closer adds the note "to match this '('" at the opener.

Hint 1 — where to start

Put all reporting in one function error(Code, Loc, Args…); expect(kind, what) calls it with E0201 and returns false instead of throwing, so the caller decides how to continue.

Hint 2 — the key idea

"Expected expression" (E0203) is reported by the prefix position of the Pratt loop when the lookahead cannot start an expression; return an ErrorExpr covering nothing (do not consume), so the caller can continue with the token.

Hint 3 — a design sketch

bool expectCloser(TokenKind K, SourceLocation Opener) reports E0201 plus the note. Test one error at a time with ch04-parsedump --expr '(1 + 2'.

Done when: E5_* pass and the two lit tests match.

---

E6 · Recovery, error nodes and limits

Spec: pebble-spec §13.1 rules 1–7 · Tests: E6_* (one error per location, statement and item synchronization, braces counted while skipping, error nodes, error cap, nesting limit, lexer errors, 3000 random token soups, every prefix of the corpus, corpus round trip), lit err-statements.test, err-conditions.test, err-unclosed.test, err-limits.test · Lesson: 4.6, Algorithm 4.6.3 and Theorem 4.6.9

After an error, synchronize so that independent errors are all reported once and nothing cascades; keep everything recognized in the AST; stop cleanly after 20 errors (E0211) or above 256 levels of nesting (E0212).

Hint 1 — where to start

Rule 1 is a filter in error(): remember the location of the last reported error and drop a second report at the same location. Rule 3 is a counter in the same function; after the 21^st, report E0211 and set a "stop" flag that every loop checks.

Hint 2 — the key idea

The statement sync set of §13.1 rule 5: skip to just after ;, or to }, a statement keyword or an item keyword at brace depth 0. Count {/} while skipping, or an unclosed block will swallow the rest of the file. Every loop must consume a token or exit (Theorem 4.6.9): the random token-soup test finds any loop that does not.

Hint 3 — a design sketch

void syncStatement(), void syncItem(), void skipToCloser(TokenKind). A DepthGuard RAII object incremented in parseBlock, the prefix-operator path, every bracketed construct (parentheses, calls, indices, arrays, struct literals, interpolations, array types) and each else if reports E0212 once when the depth passes 256 and sets the stop flag. Do not count every parseExprBP call: 100 parentheses around chains through all nine binary levels must still parse (E6_NestingLimit).

Done when: all ch04.PebbleParser.* and all lit tests pass: ./course test 4 shows only the lab left.

---

The comparison lab: labs/ch04-paradigms

Specified in SPEC.md; contract include/exprlab/ExprParsers.h; your code in labs/ch04-paradigms/src/ (switch paradigms), ★ in labs/ch04-paradigms/incr/ (switch incremental).

Milestone	What	Tests	Lesson
L1	Pratt, printing the SPEC's S-expression trees	ch04.Paradigms.L1to4_CorpusTrees	4.1, Algorithm 4.1.8
L2	shunting-yard with the two-state automaton	same, plus L1to4_InvalidInputsAreRejected, L1to4_RandomExpressionsGiveTheGeneratedTree	4.1, Algorithm 4.1.9
L3	packrat PEG (ordered choice, memo table)	same	4.2, Algorithm 4.2.7
L4	Earley recognizer + tree extraction	same	4.3, Algorithm 4.3.3
L5	agreement on random token sequences; linear work; measurements with ch04-parsebench	L5_*	4.1–4.3 §5
L6 ★	item-level incremental reparsing of Pebble modules	ch04.Incremental.L6_*	4.6, Algorithm 4.6.7

Done when: ./course test 4 passes completely and your measurement table in SPEC §6 is filled in.