Flashcards — Chapter 4¶
82 cards. Review them with spaced repetition in the terminal (./course flash 4) or export them to Anki (./course flash export 4). Here, click a card to reveal its back.
layered¶
What does the precedence-layered grammar look like for k infix levels?
One nonterminal per level: E_p → E_{p+1} (op_p E_{p+1})* for left-associative levels, E_p → E_{p+1} [op_p E_p] for right, E_p → E_{p+1} [op_p E_{p+1}] for non-associative; E_{k+1} is the operand level (prefix operators, atoms, parentheses).
State the root rule of the layered grammar (Lemma 4.1.4).
The root of an expression's tree is a depth-0 operator of the loosest level present: the last one if that level is left-associative, the first one if right-associative (non-associative: exactly one allowed).
Why does a layered recursive-descent parser cost Θ(k·n)?
Every operand is reached through a chain of calls, one per level from the current level down to the operand level: up to k+1 calls per operand (16 calls for 6 operands on the running example).
climbing¶
What does precedence climbing replace, and with what?
The k functions of the layered grammar by one function Climb(p) that loops over operators of level ≥ p and parses each right operand with Climb(level+1) (left assoc) or Climb(level) (right assoc).
How many calls does precedence climbing make on an expression with m operands?
Exactly m calls to Climb (one per operand), so Θ(n) time regardless of the number of levels.
Which Clang function implements precedence climbing, and which levels are right-associative there?
Parser::ParseRHSOfBinaryExpression in clang/lib/Parse/ParseExpr.cpp; prec::Conditional and prec::Assignment are right-associative (right operand parsed at ThisPrec + !isRightAssoc).
pratt¶
What are Pratt binding powers for level p?
(lbp, rbp) = (2p, 2p+1) for left-associative and non-associative levels, (2p+1, 2p) for right-associative ones; a prefix operator has only a right power.
What is the core loop of Pratt's expr_bp(min_bp)?
Read a prefix/operand (nud); then while the next operator has lbp ≥ min_bp: consume it and parse the right operand with expr_bp(rbp) (led). Stop at the first operator binding more loosely.
How does Pratt parsing handle postfix operators, calls and indexing?
As operators with only a left binding power in the same loop: (, [, . and casts are "infix" handlers whose right side is an argument list, an index, a field or a type.
shunting-yard¶
What two stacks does Dijkstra's shunting-yard use, and when does an operator pop the stack?
An output (operand/RPN) queue and an operator stack; an incoming operator pops every stacked operator of higher level, or of equal level if the incoming one is left-associative, then is pushed.
How does shunting-yard tell prefix - from infix -?
With a two-state automaton: in the "expecting an operand" state a - is prefix; in the "expecting an operator" state it is infix.
Which production compiler uses a shunting-yard-style operator stack for binary expressions?
GCC: c_parser_binary_expression (gcc/c/c-parser.cc) and cp_parser_binary_expression (gcc/cp/parser.cc) keep an explicit stack inside recursive descent.
peg¶
What is ordered choice in a PEG?
e1 / e2 tries e1 first; if it succeeds the choice commits to it and e2 is never tried at that position, even if the rest of the parse then fails.
What is prefix capture?
With S <- 'a' / 'a' 'b', the first alternative always wins, so ab is never matched as a whole: ordered choice can silently shrink the language of the corresponding CFG.
Name a language a PEG can recognize that no CFG can.
{aⁿbⁿcⁿ | n ≥ 1}: S <- &(A 'c') 'a'+ B !., A <- 'a' A? 'b', B <- 'b' B? 'c' (and-predicates check two counts at once).
packrat¶
What does a packrat parser memoize?
The result (end position or failure) of every (nonterminal, input position) pair, so each is evaluated at most once.
Why is packrat parsing linear, and what does it cost?
At most |N|·(n+1) memo entries, each computed once with work bounded by the rule size: O(|G|·n) time — but also O(|G|·n) memory, which is why CPython memoizes selectively and cut operators exist.
How bad can a PEG without memoization get?
Exponential: nested alternatives that share a long prefix re-parse it on every backtrack (Proposition 4.2.11 builds a grammar with 2·3^(d+1)−2 calls).
left-recursion-peg¶
What is seed growing (Warth et al.)?
For a left-recursive rule at position i: first let the recursive call fail (the seed), parse, store the result in the memo, then re-evaluate the rule body using it as long as the match grows.
What tree does seed growing produce for E <- E '+' n / n on n+n+n?
The left-nested tree ((n+n)+n): each round wraps the previous match as the left operand.
Which production parser generator uses seed growing, and how does it handle indirect left recursion?
CPython's pegen (memoize_left_rec); compute_left_recursives picks a "leader" per left-recursive cycle, and only leaders grow seeds.
earley¶
What is an Earley item?
[A → α • β, j]: a production with a dot and an origin j, meaning α derives the input between positions j and the current set's position.
Name Earley's three operations.
Predictor (dot before a nonterminal B: add B's productions with the current origin), scanner (dot before the next token: advance into the next set), completer (completed [B → γ •, j]: advance items in S_j waiting for B).
What are Earley's complexity bounds?
O(n³) for every CFG, O(n²) for unambiguous grammars, linear for most deterministic (bounded-state) grammars; left recursion is cheap.
What is the Aycock–Horspool fix?
When predicting a nullable nonterminal B, also advance the dot over B immediately, so ε-completions are never missed.
leo¶
What problem does Leo's optimization solve?
Right recursion: without it, S → a S on aⁿ keeps completed items for every earlier origin — n²/2 + 9n/2 + 3 items; with Leo's topmost items it is 5n + 3.
What is a deterministic reduction path?
A chain of unique penultimate items: completing B completes A, which completes the next, … Leo memoizes the topmost item so the whole chain is completed in one step.
Does Lark 1.3.1's Earley parser use Leo items?
No: they were removed, and the lesson measures the quadratic right-recursion slowdown (0.61/2.67/16.63 s vs 0.02/0.06/0.07 s for left recursion).
sppf¶
What is an SPPF?
A shared packed parse forest: a DAG of symbol nodes (X, i, j) and intermediate nodes, with packed nodes for alternative splits, representing all parse trees of a sentence.
How large is a binarized SPPF?
O(n³) nodes for a fixed grammar, although the number of trees it represents can be exponential (Catalan numbers for E → E + E).
Why binarize an SPPF?
So every packed node has at most two children (prefix of the rule, last symbol); otherwise rules with long right sides make the forest O(n^(k+1)).
cyk¶
What is Chomsky normal form?
Every production is A → B C or A → a (plus S → ε if needed, with S not on any right side).
What does CYK's table cell V[i, j] hold?
The set of nonterminals that derive the substring of length j starting at position i; V[i, j] is filled from all splits into V[i, k] and V[i+k, j−k].
What is CYK's cost and what does Valiant's result add?
Θ(n³·|P|) on every input; Valiant (1975) reduces CFL recognition to Boolean matrix multiplication, so sub-cubic time is possible in theory.
gll¶
What is a GLL descriptor?
A triple (L, u, i): continue at grammar slot L with GSS node u at input position i. Each descriptor is processed once (the set 𝒰ᵢ).
What is a GSS node in GLL?
⟨L, j⟩: the return slot L after a call of a nonterminal, and the position j where the call started; a repeated call at the same position reuses the node.
Why does GLL handle left recursion?
The left-recursive call at the same position finds its GSS node already there and only adds an edge; with finitely many descriptors, recognition terminates in O(n³).
combinators¶
What is a list-of-successes parser (Wadler 1985)?
A function from input to the list of all (result, remaining input) pairs; failure is [] and choice is list concatenation, so every parse is found.
Why does nom's many0 return Ok with leftover input on "10 - 3 -"?
Single-result backtracking: the failing third element is undone, the repetition stops successfully, and "-" is left unconsumed; the caller must check for end of input.
What is the relation between backtracking combinators and PEGs?
Single-result backtracking combinators with ordered choice have exactly PEG semantics (Proposition 4.5.9).
parsec¶
What are Parsec's four replies?
Consumed-ok, consumed-error, empty-ok, empty-error; choice tries the second alternative only after an empty error from the first.
What does Parsec's try do?
Turns a consumed error into an empty error, re-enabling backtracking locally.
Why is committed choice good for errors and performance?
No backtracking after consumption: predictive, O(k·n), input before the commit point can be released, and the error points at the first token no alternative could consume.
error-recovery¶
What is the furthest-failure rule?
When all alternatives fail, report the rightmost position where any terminal test failed, with the union of what was expected there.
How does chumsky recover from errors?
Strategies like skip_then_retry_until and nested_delimiters skip to a synchronizing token and produce a placeholder output, so parsing continues and several errors are reported.
What does chumsky output for "[1, x, 3, y y, 5]" with recovery?
Some([Some(1), None, Some(3), None, Some(5)]) plus two errors: None marks the recovered items.
resilient¶
What makes a parser resilient?
It returns a tree containing every token for any input, with erroneous regions under error nodes and well-formed constructs intact, plus errors without cascades.
What is a recovery set of a list loop?
Tokens an enclosing construct can use (closers of enclosing brackets, keywords starting enclosing constructs): the loop stops there instead of skipping them.
What must every iteration of a resilient list loop do?
Consume at least one token (an element or a bumped error token) or exit at the closer, a recovery-set token or eof — which gives termination in O(n·D).
error-nodes¶
What is an error production?
A grammar rule with yacc's error token (stmt : error ';'): the LR parser pops states until one shifts error, then discards input until it can continue.
What is an error node?
A tree node (ERROR in rust-analyzer and tree-sitter, ErrorExpr in pebblec) that holds skipped tokens or marks a missing piece, keeping the grammar clean.
Why do IDE parsers prefer error nodes over error productions?
Error nodes record exactly which tokens were skipped and where, keep all other structure, and need no grammar changes; error productions reduce to an ordinary nonterminal and lose the detail.
incremental¶
What does an incremental LR parser reuse?
Clean subtrees of the old tree (outside the edit and its lookahead) that the current parse state can shift as a whole; others are broken down into children.
Why is incremental LR reuse exact?
For LR(1), the reductions that build a subtree depend only on its yield, the state at its left end and the lookahead at its right end; if all match, shifting it whole equals reparsing its yield.
How much faster was tree-sitter's incremental reparse in Lesson 4.6?
62 ms after an edit vs 374 ms for a full parse of 20 000 JavaScript functions.
block-reparse¶
How does rust-analyzer's block-level reparse work?
Relex a single token if the edit stays inside one of the same kind; otherwise reparse the smallest enclosing {…} block whose new text is balanced and splice it in; fall back to a full parse.
What does path copying cost when a block is replaced?
O(d) new nodes for the ancestors of the replaced subtree; all other nodes are shared with the old tree.
What granularity does the lab's ★ incremental reparser use?
Top-level items: an edit inside one function reparses that item and reuses the other ASTs (ItemsReparsed 1, ItemsReused 4 in the test program).
ast-hierarchy¶
What is LLVM-style RTTI?
A kind field in the base class plus a static classof per class; isa/cast/dyn_cast test the kind with integer comparisons instead of C++ dynamic_cast.
Why does preorder numbering make classof an interval test?
The concrete classes below any class D are consecutive in a depth-first preorder, so classof is first(D) ≤ kind ≤ last(D).
How does Clang force AST nodes into its arena?
Stmt's plain operator new is protected and unreachable; the public operator new takes an ASTContext& and allocates from its BumpPtrAllocator.
sum-types¶
What is a sum type?
A type whose values are tagged tuples of one of several constructors (Rust enum, ML datatype, std::variant); case analysis can be checked for exhaustiveness.
What does std::visit do when a visitor misses an alternative?
The code does not compile: std::visit requires the visitor to be callable with every alternative (clang reports an invoke_result error from the library).
What is the expression problem?
Sum types make adding operations easy and adding cases hard; class hierarchies with virtual methods make adding cases easy and operations hard (Wadler 1998).
arena¶
What is a bump (arena) allocator?
Allocation rounds a pointer up to the alignment and advances it within a large slab; a new slab is opened when the object does not fit; everything is freed at once.
What slab size does LLVM's BumpPtrAllocator use by default?
4096 bytes, doubling every 128 slabs; oversized requests get their own slab.
What is a HirId in rustc?
(owner item, local index): an index-based node id, stable when other items change, used as a key into side tables for incremental compilation.
red-green¶
What is a green node?
An immutable, position-free node storing kind, width and children with relative offsets; equal green nodes can be shared (hash-consed).
What is a red node?
A lightweight view created on demand: a green node plus parent pointer and absolute offset (parent offset + the child's relative offset).
Which green nodes does rowan 0.15.18 intern?
Tokens and nodes with at most three children: 1+1 is shared between occurrences, 1 + 1 (five children with whitespace) is not.
lowering¶
What is desugaring?
Lowering surface constructs into combinations of core ones (for → loop + match, ? → match) so later phases handle fewer cases.
How does rustc lower for x in v { B }?
match into_iter(v) { mut iter => loop { match next(&mut iter) { None => break, Some(x) => B } } } (lower_expr_for).
Why must a desugared Pebble for send continue to the increment?
Otherwise k is not incremented and the next iteration repeats the same i; pebblec keeps ForStmt in the AST to lower continue correctly.
token-macros¶
Why does #define DOUBLE(e) e * 2 give 5 for DOUBLE(1 + 2)?
Token substitution produces 1 + 2 * 2; the argument's grouping is lost. Fully parenthesize: ((e) * 2).
Why does #define foo (4 + foo) terminate?
While foo's replacement is rescanned, foo is disabled; the inner foo is painted blue (Clang: Token::DisableExpand) and never expanded.
When does the C preprocessor run relative to parsing?
Before parsing, on tokens: the parser only sees the expanded token stream (clang -E shows it).
ast-macros¶
What does a fragment specifier like $e:expr do in macro_rules?
Runs the real expression parser on the argument and binds the parsed fragment; it is transcribed as one unit (invisible delimiters), so grouping is kept.
double!(3 - 1) with $e:expr vs $($t:tt)*: what are the values for $e * 2?
4 with expr (the fragment is (3 - 1)), 1 with tt (raw tokens 3 - 1 * 2).
How do Swift macros differ from macro_rules?
They are separate programs that receive a SwiftSyntax tree and return a new one; arguments are type-checked first; they are not hygienic (makeUniqueName instead).
hygiene¶
What is the hygiene condition (Kohlbecker et al. 1986)?
Bindings introduced by a macro expansion bind only references introduced by the same expansion step, and user bindings bind only user references.
How do marks implement hygiene?
Each expansion step applies a fresh mark to the identifiers its template introduces; resolution of locals compares name and marks, so the two groups cannot capture each other.
What does rustc print for the two tmps of a swap! macro?
tmp /* 2535#4 / (the macro's, context #4) and tmp / 2535#0 */ (the user's): same symbol, different syntax context — so the swap works.