Theory test — Chapter 4¶

57 questions; you pass at 80 %. This page shows the questions only: take the test in the terminal, where every answer is graded and explained.

./course quiz 4                                   # interactive
./course quiz template 4 -o answers/ch04.yaml  # or fill in a file ...
./course quiz grade 4                             # ... and grade it

Question 1 layered-calls · number · 1 pt · 01-expression-parsing

Operator table: level 1 + - (left), level 2 * / (left), level 3 ^ (right), no prefix
operators. The layered parser has one function Level(p) per level, and Level(4) reads an
operand (as in Lesson 4.1 §3). How many calls to Level (all levels, including Level(4))
does it make on a * b + c?

Answer format: a number

Question 2 root-rule · single · 1 pt · 01-expression-parsing

Table: + - level 1 left, * / level 2 left, ^ level 3 right. By the root rule
(Lemma 4.1.4), which operator of a * b ^ c ^ d * e is the root of its tree?

the first *
the first ^
the second ^
the second *

Answer format: one letter

Question 3 climb-min-level · sequence · 1 pt · 01-expression-parsing

Same table. Precedence climbing (Algorithm 4.1.6) starts with Climb(1) and calls Climb(q)
for each right operand, with q = level + 1 for left-associative and q = level for
right-associative operators. Give the arguments of all Climb calls, in call order, on
a * b - c ^ d.

Answer format: items in order, e.g. A B C

Question 4 find-clang-right-assoc · set · 1 pt · 01-expression-parsing

In clang/lib/Parse/ParseExpr.cpp (LLVM 23.1.2), Parser::ParseRHSOfBinaryExpression
computes isRightAssoc from the precedence level of the operator. Which prec::Level values
(as spelled in clang/include/clang/Basic/OperatorPrecedence.h) make an operator
right-associative? Give the enumerator names.

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 5 pratt-calls · sequence · 1 pt · 01-expression-parsing

Binding powers: + - (2, 3), * / (4, 5), ^ (7, 6). Pratt's expr_bp(min_bp) (Algorithm
4.1.8) is called with 0 at the top and with the operator's right power for each right operand.
Give the min_bp of every call, in call order, on a - b * c ^ d.

Answer format: items in order, e.g. A B C

Question 6 pratt-bp-right · mapping · 1 pt · 01-expression-parsing

Table: level 1 = (right), level 2 + (left), level 3 ^ (right). Using the convention of
Definition 4.1.7 — (2p, 2p+1) for left and non-associative levels, (2p+1, 2p) for right — give
the right binding power of each operator.

Keys: =, +, ^

Answer format: one value per key

Question 7 sy-stack · sequence · 1 pt · 01-expression-parsing

Shunting-yard (Algorithm 4.1.9) with + - level 1 left, * / level 2 left, ^ level 3
right, on a + b * c ^ d - e. Give the operator stack (bottom first) just before the token
- is processed.

Answer format: items in order, e.g. A B C

Question 8 sy-rpn · sequence · 1 pt · 01-expression-parsing

Same table. Give the reverse Polish output of shunting-yard on a - b * c ^ d ^ e - f.

Answer format: items in order, e.g. A B C

Question 9 gcc-shunting · text · 1 pt · 01-expression-parsing

Which function in GCC 15's C front end (gcc/c/c-parser.cc) parses binary expressions with
an explicit stack of operands and operators instead of one function per precedence level?

Answer format: a short answer

Question 10 peg-prefix-capture · number · 1 pt · 02-peg-and-packrat

PEG: S <- 'a' / 'a' 'b'. What is match(S, 0) on the input ab (the end position, as in
Definition 4.2.2)?

Answer format: a number

Question 11 peg-anbncn · set · 1 pt · 02-peg-and-packrat

PEG of Theorem 4.2.5:
S <- &(A 'c') 'a'+ B !., A <- 'a' A? 'b', B <- 'b' B? 'c'.
Which of these inputs does S accept: abc, aabbcc, aabbc, aabcc, abbcc?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 12 packrat-table · number · 1 pt · 02-peg-and-packrat

PEG: E <- T '+' E / T, T <- 'n' '*' T / 'n', input n*n+n (each character a terminal).
Run the packrat parser (Algorithm 4.2.7), memoizing every (nonterminal, position) result.
How many memo entries are there at the end?

Answer format: a number

Question 13 packrat-hits · number · 1 pt · 02-peg-and-packrat

Same PEG and input. How many memo hits occur (a call of a nonterminal at a position whose
result is already in the table)?

Answer format: a number

Question 14 seed-rounds · sequence · 1 pt · 02-peg-and-packrat

Left-recursive PEG E <- E '+' 'n' / 'n' on n+n+n, evaluated by seed growing (Algorithm
4.2.8). Give the end positions of E at 0 after each round that grows the match (the seed round
included).

Answer format: items in order, e.g. A B C

Question 15 seed-tree · single · 1 pt · 02-peg-and-packrat

With the same grammar and input, which tree does seed growing build (Theorem 4.2.9)?

(+ n (+ n n)): right-nested, as a right-recursive PEG would
(+ (+ n n) n): left-nested
no tree — the parser loops forever
a flat list n, n, n with no associativity

Answer format: one letter

Question 16 earley-set-size · number · 1 pt · 03-earley

Grammar E -> E + T | T, T -> T * n | n, augmented with E' -> E. Input n + n * n.
How many items does the Earley set S₁ contain (Algorithm 4.3.3)?

Answer format: a number

Question 17 earley-items-s2 · set · 1 pt · 03-earley

Same grammar and input. Give the items of S₂ (after n +), written A -> α . β, origin.

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 18 earley-accept · single · 1 pt · 03-earley

When does the Earley recognizer accept a₁ … aₙ?

when Sₙ is non-empty
when [S' → S •, 0] ∈ Sₙ
when some completed item [A → γ •, 0] ∈ Sₙ
when [S' → • S, 0] ∈ S₀ and no set is empty

Answer format: one letter

Question 19 leo-count · number · 1 pt · 03-earley

Grammar S -> a S | a, input aⁿ with n = 10. How many items does Earley's algorithm without
Leo's optimization add in total (Proposition 4.3.10)?

Answer format: a number

Question 20 leo-lark · single · 1 pt · 03-earley

Lesson 4.3 times Lark 1.3.1's Earley parser on a right-recursive and a left-recursive list
grammar: 0.61 / 2.67 / 16.63 s versus 0.02 / 0.06 / 0.07 s as the input grows. What explains
the difference?

Lark's lexer is quadratic on right-recursive grammars
Lark 1.3.1's Earley parser does not apply Leo's optimization, so right recursion leaves quadratically many completed items
left recursion makes Earley exponential
Lark switches to CYK for right-recursive grammars

Answer format: one letter

Question 21 sppf-catalan · number · 1 pt · 03-earley

Ambiguous grammar E -> E + E | a. How many parse trees does a + a + a + a + a (five
operands) have, i.e. how many trees does its SPPF pack?

Answer format: a number

Question 22 sppf-size · single · 1 pt · 03-earley

For a sentence of length n and a fixed grammar, how large is a binarized SPPF (Definition
4.3.7) in the worst case, although the number of trees can be exponential?

O(n)
O(n³)
O(2ⁿ)
O(Cₙ), the Catalan number

Answer format: one letter

Question 23 cyk-cell · set · 1 pt · 04-cyk-and-gll

CNF grammar (Hopcroft–Ullman's example): S -> A B | B C, A -> B A | a, B -> C C | b,
C -> A B | a. Input baaba. Give V[3, 2]: the nonterminals that derive the substring of
length 2 starting at position 3 (1-based).

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 24 cyk-top · set · 1 pt · 04-cyk-and-gll

Same grammar and input. Give the top cell V[1, 5]. Is baaba in the language?
(Answer with the set only.)

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 25 cyk-cnf-count · number · 1 pt · 04-cyk-and-gll

Convert E -> E + T | T, T -> ( E ) | n to Chomsky normal form with Algorithm 4.4.2 (new
start symbol with a copy of E's productions, one unit nonterminal per terminal in long rules,
binarization with fresh nonterminals, unit-rule elimination). How many productions (counting
each alternative) does the result have?

Answer format: a number

Question 26 gll-descriptors · number · 1 pt · 04-cyk-and-gll

GLL recognition (Algorithm 4.4.5, first-in first-out, no FIRST-set tests), grammar
S -> S a | a, input a a a. Lesson 4.4 §3 processes 8 descriptors on a a. How many
descriptors are processed on a a a?

Answer format: a number

Question 27 gll-leftrec · single · 1 pt · 04-cyk-and-gll

Why does GLL terminate on the left-recursive S -> S a | a while plain recursive descent
loops?

GLL rewrites the grammar to remove left recursion first
a second call of S at the same position finds the GSS node ⟨slot, position⟩ already created and only adds an edge; 𝒰ᵢ forbids repeating a descriptor
GLL uses a lookahead of two tokens
GLL bounds the recursion depth by the input length

Answer format: one letter

Question 28 nom-leftover · single · 1 pt · 05-parser-combinators

With nom 8, sum := num (('+'|'-') num)* written with many0(pair(op, num)), parsing
"10 - 3 -" returns Ok(("-", 7)). What happened?

nom reported an error at column 8
many0 tried a third element, consumed -, failed on the number, backtracked, and stopped; the parse succeeds with - left over
nom evaluated 10 - 3 - 0
nom skipped the invalid token as error recovery

Answer format: one letter

Question 29 los-count · number · 1 pt · 05-parser-combinators

List-of-successes parsers (Definition 4.5.1): many p = (p >>= λa. many p >>= λas. return (a:as)) ++ return [], with p = the character a. How many (result, rest) pairs does
many p return on the input aaa?

Answer format: a number

Question 30 parsec-commit · number · 1 pt · 05-parser-combinators

Parsec: sum = num >> many (op >> spaces >> num) without try, on "10 - 3 -". At which
column does Parsec report the error (the Parsec box of Lesson 4.5)?

Answer format: a number

Question 31 parsec-try-cost · single · 1 pt · 05-parser-combinators

Why does Parsec make backtracking opt-in with try instead of trying every alternative after
a failure?

try is needed only for left-recursive rules
without backtracking, choice is predictive: linear time, the input before the committed point can be released, and the error points at the first token no alternative consumes
Haskell cannot express backtracking without try
try makes Parsec an LR parser

Answer format: one letter

Question 32 furthest-failure · number · 1 pt · 05-parser-combinators

chumsky 0.10 on "10 - x" (0-based byte spans) reports error at 5..6: found Some('x').
Under the furthest-failure rule (Definition 4.5.6), what is the start offset of the reported
error, and why is it not the - at offset 3?
(Give the offset.)

Answer format: a number

Question 33 recovery-placeholders · single · 1 pt · 05-parser-combinators

chumsky with recover_with on "[1, x, 3, y y, 5]" outputs
Some([Some(1), None, Some(3), None, Some(5)]) and two errors. What are the None entries?

integers that overflowed
placeholders produced by recovery where the item parser failed and tokens were skipped, so the rest of the list is still parsed
empty list elements in the input
the parser's backtracking points

Answer format: one letter

Question 34 recovery-count · number · 1 pt · 06-resilient-and-incremental-parsing

pebblec's parser (pebble-spec §13.1) on tests/ch04/Inputs/err-statements.pbl (the
worked example of Lesson 4.6 §3). How many syntax errors does it report?

Answer format: a number

Question 35 recovery-location · text · 1 pt · 06-resilient-and-incremental-parsing

Same file: return x without ; is followed by the closing } of the function on line 10,
column 1. Where is "expected ';'" reported? Answer line:column.

Answer format: a short answer

Question 36 error-prod-vs-node · single · 1 pt · 06-resilient-and-incremental-parsing

What is the main difference between yacc's error productions and rust-analyzer's error nodes?

error productions are faster
error productions put recovery in the grammar and reduce to an ordinary nonterminal; error nodes put the skipped tokens into the tree under an ERROR node, keeping the grammar clean
error nodes only work for LR parsers
there is no difference; both are panic mode

Answer format: one letter

Question 37 bison-error · sequence · 1 pt · 06-resilient-and-incremental-parsing

The Bison grammar of Lesson 4.6 (stmt : NUM '+' NUM ';' | error ';') on 1+2; 3 4; 5+6;.
Give the kinds of the three lines about statements it prints, in order: stmt for a
normal statement, error for the error production.

Answer format: items in order, e.g. A B C

Question 38 ts-reuse · single · 1 pt · 06-resilient-and-incremental-parsing

In tree-sitter's incremental reparse, when can a subtree of the old tree be reused (shifted
as a whole)?

whenever its text is unchanged
when it does not touch the edited range (including lexer lookahead), and the parse state lets the parser shift a node of its kind at that point
only if it is a leaf token
only at the top level of the file

Answer format: one letter

Question 39 wg-condition · multi · 1 pt · 06-resilient-and-incremental-parsing

Which conditions does the exactness argument of Theorem 4.6.11 (Wagner–Graham) need for
shifting an old subtree X whole?

GOTO(q, X) is defined in the current state q
the lookahead after X is unchanged
X is at most 3 levels deep
X's yield is unchanged by the edit

Answer format: letters, e.g. a, c

Question 40 ra-shared · set · 1 pt · 06-resilient-and-incremental-parsing

In the rust-analyzer box of Lesson 4.6, fn a() { let x = 1; } has its 1 replaced by
10 + 20. Which children of the old FN node for a are shared by the new tree? Give
their kinds (ignore duplicates).

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 41 incr-reparsed · mapping · 1 pt · 06-resilient-and-incremental-parsing

The lab's ★ item-level reparser (Algorithm 4.6.7 at item granularity) holds a module with five
items (fib, Point, putchar, sum, main). A statement is inserted inside fib. Give
ItemsReparsed and ItemsReused.

Keys: ItemsReparsed, ItemsReused

Answer format: one value per key

Question 42 rtti-interval · mapping · 1 pt · 07-syntax-tree-design

Hierarchy: Stmt ← {Expr, ReturnStmt}; Expr ← {Lit, BinExpr}; Lit ← {IntLit,
FloatLit}, children in the order listed. Number the concrete (leaf) classes in preorder from
0 (Definition 4.7.1). Give first(Expr) and last(Expr), the interval that Expr::classof tests.

Keys: first, last

Answer format: one value per key

Question 43 find-clang-stmt-new · text · 1 pt · 07-syntax-tree-design

In clang/include/clang/AST/Stmt.h (LLVM 23.1.2), the plain operator new(size_t) of Stmt
is protected and unreachable. Which class must be passed (by reference or pointer) to the
public operator new that allocates statements?

Answer format: a short answer

Question 44 variant-size · number · 1 pt · 07-syntax-tree-design

x86-64, libstdc++: struct A { long v; } (8 bytes), struct B { void *p, *q, *r; }
(24 bytes), struct C { int i; } (4 bytes). What is sizeof(std::variant<A, B, C>)?

Answer format: a number

Question 45 expression-problem · single · 1 pt · 07-syntax-tree-design

The expression problem (Wadler 1998): which statement is right?

sum types make adding a new operation easy and adding a new node kind hard; class hierarchies with virtual methods make it the other way round
class hierarchies make both easy
sum types make both easy
it is about operator precedence

Answer format: one letter

Question 46 arena-slabs · number · 1 pt · 07-syntax-tree-design

A bump allocator with fixed 4096-byte slabs (Algorithm 4.7.6) serves 100 requests of 100 bytes
each (alignment already included). How many slabs does it allocate?

Answer format: a number

Question 47 index-postorder · sequence · 1 pt · 07-syntax-tree-design

The lab's index-based tree (Tree.h) appends a node when it is built. Pratt parsing a * b + c
builds the nodes in which order? Give the heads (a, b, c, *, +) by index 0, 1, 2, ….

Answer format: items in order, e.g. A B C

Question 48 red-offset · number · 1 pt · 07-syntax-tree-design

A lossless green tree for the text x * (y + 3) (spaces are whitespace tokens). What is the
absolute offset of the red node of the literal 3, computed by summing relative offsets along
its path (Algorithm 4.7.8)?

Answer format: a number

Question 50 for-desugar-continue · single · 1 pt · 07-syntax-tree-design

pebble-spec §7 desugars for i in a..b { B } into
{ let start = a; let end = b; var k = start; while k < end { let i = k; B; k = k &+ 1; } }.
What goes wrong if a continue in B is lowered to a jump to the while test?

nothing
the increment is skipped, so the next iteration repeats the same i — possibly forever
the loop runs one iteration fewer
a and b are evaluated again

Answer format: one letter

Question 51 hir-for · set · 1 pt · 07-syntax-tree-design

In rustc 1.94.1's -Zunpretty=hir output for for x in v { … }, which two functions (as
printed) does the lowered loop call to drive the iteration?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 52 cpp-double · number · 1 pt · 08-syntax-extension

#define SQ(x) x * x. What does printf("%d\n", SQ(1 + 2)) print?

Answer format: a number

Question 53 cpp-self-ref · text · 1 pt · 08-syntax-extension

Clang marks a macro-name token that must never be expanded again ("painted blue", because its
macro was disabled when the token was produced). What is the name of the Token flag it sets
(in clang/lib/Lex/PPMacroExpansion.cpp)?

Answer format: a short answer

Question 54 mbe-expr-vs-tt · mapping · 1 pt · 08-syntax-extension

Rust: macro_rules! double { ($e:expr) => { $e * 2 }; } and
macro_rules! double_tt { ($($t:tt)*) => { $($t)* * 2 }; }. Give the values of
double!(3 - 1) (key expr) and double_tt!(3 - 1) (key tt).

Keys: expr, tt

Answer format: one value per key

Question 55 mbe-fragment-subtree · single · 1 pt · 08-syntax-extension

How does rustc 1.94.1 make sure that an $e:expr fragment stays one subtree after
transcription (Theorem 4.8.9)?

it inserts real parentheses into the source text
it wraps the fragment's tokens in a group with invisible delimiters tagged with the fragment kind, which the parser can only consume as a whole
it re-lexes the fragment as a string literal
it forbids operators after $e

Answer format: one letter

Question 56 hygiene-swap · mapping · 1 pt · 08-syntax-extension

SWAP(tmp, other) with #define SWAP(a, b) { int tmp = a; a = b; b = tmp; } in C, and the
same macro as macro_rules! swap in Rust, starting from tmp = 1, other = 2. Give the final
values: keys c_tmp, c_other, rust_tmp, rust_other.

Keys: c_tmp, c_other, rust_tmp, rust_other

Answer format: one value per key

Question 57 hygiene-contexts · single · 1 pt · 08-syntax-extension

rustc's -Zunpretty=expanded,hygiene prints let tmp /* 2535#4 */ = tmp /* 2535#0 */;.
What do 2535 and #4/#0 mean?

line and column numbers
2535 is the interned symbol tmp (the same for both); #4 and #0 are syntax contexts — the macro expansion's mark versus none — so the two are different identifiers for local-variable resolution
two different symbols that happen to print the same
memory addresses of AST nodes

Answer format: one letter