Flashcards — Chapter 2¶
81 cards. Review them with spaced repetition in the terminal (./course flash 2) or export them to Anki (./course flash export 2). Here, click a card to reveal its back.
derivations¶
What is a leftmost derivation, and what does it correspond to in a parse tree?
A derivation that always rewrites the leftmost nonterminal. Its production sequence is the tree's preorder; top-down parsers build it.
How do leftmost derivations, rightmost derivations and parse trees relate?
One-to-one: each tree has exactly one leftmost and one rightmost derivation, so ambiguity can be defined with any of the three.
CST vs AST?
A CST keeps every token and every nonterminal step (lossless; IDE tools). An AST keeps operators and operands only (no punctuation, no unit chains); Clang builds an AST directly.
Give a language that is context-free but not regular, and one that is context-sensitive but not context-free.
{aⁿbⁿ} (balanced counting, also balanced parentheses) and {aⁿbⁿcⁿ}.
Chomsky type of a grammar whose every production is A → t B, A → t or A → ε?
Type 3 (regular, right-linear). Type 2 = one nonterminal on every left side.
ambiguity¶
When is a grammar ambiguous?
When some sentence has two distinct parse trees (equivalently two leftmost derivations).
Is ambiguity of context-free grammars decidable? Why?
No (Cantor, Floyd, Chomsky–Schützenberger 1962–63): reduction from Post's correspondence problem via S → A | B with index-recording terminals.
How many parse trees does E → E + E | x give for x + x + x + x (3 operators)?
Catalan(3) = 5. In general Catalan(k) for k operators.
Cost of counting the parse trees of one sentence?
O(|P|·r·n³) with a memoized span DP (CYK-like); requires no cycles A ⇒+ A (otherwise infinitely many trees).
Name two sufficient conditions for unambiguity.
The grammar is LL(1) (conflict-free table) or LR(1). Neither is necessary.
layering¶
How does layering encode precedence and associativity?
One nonterminal per precedence level; left-assoc level Ei → Ei op Ei+1 | Ei+1, right-assoc Ei → Ei+1 op Ei | Ei+1; operands P → ( E1 ) | id.
In a left-associative level, which operator is at the root of Ei's subtree?
The last level-i operator outside parentheses (the right operand Ei+1 cannot contain a level-i operator).
Main costs of a layered expression grammar?
Grammar size O(levels); CST depth: a lone operand derives through a chain of m unit steps (C: 17 levels); left recursion must then be removed for LL.
round-robin¶
Rules defining FIRST (for A → X1…Xk)?
FIRST(Xi) − {ε} ⊆ FIRST(A) whenever X1…Xi−1 are all nullable; FIRST(t) = {t}; ε ∈ FIRST(A) iff A is nullable.
Rules defining FOLLOW?
$ ∈ FOLLOW(S); for A → α B β: FIRST(β) − {ε} ⊆ FOLLOW(B), and if β is nullable FOLLOW(A) ⊆ FOLLOW(B). FOLLOW never contains ε.
Why does round-robin iteration of FIRST/FOLLOW terminate, and why is the result the least solution?
Sets only grow and are bounded (finite lattice); iterating monotone rules from ∅ reaches the least fixed point (Kleene), the same argument as dataflow in Ch 14.
Pathological input for round-robin FIRST?
The chain A1 → A2 a1, …, An → b listed top-down: n + 1 passes, Θ(n²) work; bottom-up order needs 2 passes.
Why do the round-robin loops for nullable, FIRST and FOLLOW compute the least solution (Theorem 2.2.4)?
The rule operators are monotone on finite lattices (P(N), P(T)^N, P(T∪{$})^N). Kleene iteration from ⊥ increases, stabilizes within the lattice height h, and every pre-fixed point lies above it, so the first pass that changes nothing ends at lfp.
Why is CPython pegen's FirstSetCalculator not a fixed-point computation, and what does it miss?
It is one memoized DFS that returns ∅ for a rule still "in process". On a: b | ['x'], b: a it reports FIRST(b) = ∅ although b ⇒ a gives {x, ε}; round-robin iteration cannot miss such elements.
worklist¶
How does the counting (Horn-clause) nullable algorithm work?
count(p) = symbols of p not yet known nullable (productions with terminals are dead); when a nonterminal becomes nullable, decrement counts of productions containing it; count 0 ⇒ lhs nullable. Linear time; Bison's nullable_compute.
What is the inclusion graph behind FIRST?
An edge B → A whenever A → α B β with α nullable: FIRST(B) flows into FIRST(A); plus direct terminals.
Worklist invariant for FIRST/FOLLOW propagation?
Every node whose set grew since it was last popped is in the queue; when it is empty, every edge x → y satisfies S(x) ⊆ S(y).
digraph¶
What does the DeRemer–Pennello Digraph algorithm compute?
F(x) = direct(x) ∪ ⋃ F(y) over edges y → x, in one DFS using Tarjan's SCC algorithm; every SCC gets one shared set.
Complexity of the digraph method?
O(|N| + e) visits and set unions (one DFS), versus repeated passes for round-robin.
Where is the digraph algorithm used in practice?
LALR(1) lookahead computation: Bison src/relation.c relation_digraph / traverse (DeRemer & Pennello 1982).
ll1-table¶
Which cells does production A → α enter in the LL(1) table?
M[A, t] for every t ∈ FIRST(α); if α is nullable, also M[A, t] for every t ∈ FOLLOW(A) ($ included).
FIRST/FIRST vs FIRST/FOLLOW conflict?
FIRST/FIRST: ≥ 2 productions of the cell have the lookahead in FIRST of their right side. FIRST/FOLLOW: otherwise — a nullable alternative is there via FOLLOW(A).
Knuth's characterization of LL(1)?
For all alternatives A → α | β: FIRST(α) ∩ FIRST(β) = ∅, at most one is nullable, and if β is nullable FIRST(α) ∩ FOLLOW(A) = ∅. Equivalently: no conflicting table cell.
Why is a left-recursive grammar never LL(1)?
A → A α and its base alternative A → β share FIRST(β) (a FIRST/FIRST conflict); if β derives only ε, α's first token is in FOLLOW(A) instead (FIRST/FOLLOW).
How full are LL(1) tables in practice, and how are they stored?
Sparse (~25 % on the course corpus); stored with row displacement (Tarjan & Yao 1979) or as switch statements.
State Theorem 2.3.8: when is a (reduced) grammar LL(1)?
Iff its LL(1) table has no conflicting cell, iff for all distinct alternatives A → α | β: FIRST(α) ∩ FIRST(β) = ∅, not both nullable, and β nullable ⇒ FIRST(α) ∩ FOLLOW(A) = ∅.
priority¶
How is the dangling-else conflict resolved?
By priority: M[S', e] keeps S' → e S, so each else binds to the nearest unmatched if (Clang ParseIfStatement; warns -Wdangling-else).
When is priority resolution unsafe?
When the dropped production was the only way to derive some sentence: S → A a, A → a | ε resolved to A → a rejects the sentence a. It always yields a subset of L(G).
What does ANTLR 4 do with a true ambiguity at a decision?
Picks the minimum (first) alternative and reports the ambiguity (PredictionMode.resolvesToJustOneViableAlt).
direct-lr¶
Rewrite A → A α | β without left recursion.
A → β A′, A′ → α A′ | ε. Language β α* is preserved; the tree becomes right-nested.
Why does removing left recursion endanger associativity?
x − x − x now parses as a right-nested chain; build the AST with a loop (EBNF) or re-associate, or you compute x − (x − x).
What if every alternative of A is left-recursive?
A derives no terminal string; the transformation reports it instead of producing A with no productions.
paull¶
Paull's algorithm in one sentence.
Order A1…An; for each Ai substitute every Aj (j < i) that starts an Ai-alternative, then remove Ai's direct left recursion.
Invariant of Paull's algorithm?
After processing Ai, every alternative of Ak (k ≤ i) starts with a terminal, ε, a primed nonterminal, or Aj with j > k.
Preconditions of Paull's algorithm, and what breaks without them?
Cycle-free and ε-free; with ε-productions hidden left recursion (A → B A γ, B nullable) can survive — detect and report it.
Why restrict Paull's substitutions to left-corner SCCs?
Only nonterminals on a common left-corner cycle can close left recursion; substituting others only blows the grammar up (json: 18 vs 24 productions).
Worst-case output size of Paull's algorithm?
Exponential: N1 → Nn c | d, Ni → Ni−1 a | Ni−1 b gives 2^(n+1) − 1 productions (511 at n = 8).
left-factoring¶
Left-factor A → α β1 | α β2 | γ.
A → α A′ | γ, A′ → β1 | β2 (α = longest common prefix; βi may be ε).
Which conflicts can left factoring not fix?
Common prefixes hidden behind nonterminals (S → A x | B y, A → a, B → a) and FIRST/FOLLOW conflicts (dangling else).
Why does left factoring terminate?
The total length Ψ of all alternatives that belong to some group drops by at least 2 per step: the group is replaced by A → α A′ (in no group) and A′ gets only the suffixes.
table-driven¶
Invariant of the table-driven predictive parser?
Matched input · stack (top to bottom, without $) is a left-sentential form; the output so far is its leftmost derivation.
What is the correct-prefix property?
An LL(1) parser reports an error at token i only if t1…ti−1 is a prefix of a sentence and t1…ti is not.
Cost of table-driven LL(1) parsing?
Θ(n) for a fixed grammar, but the per-token constant can be exponential in |N| (whole ε-subtrees are expanded, Proposition 2.5.15); e.g. 17 steps for id + id * id.
recursive-descent¶
How does a recursive-descent function relate to the LL(1) table?
parseX() is X's table row as a switch on the lookahead; the call stack plays the parse stack.
Where must a predictive RD parser take an ε-alternative to agree with the table?
Only on FOLLOW tokens; taking ε as default: moves error detection to the caller.
Name four production compilers with hand-written recursive-descent parsers.
Clang, GCC (C++ since 3.4, C since 4.1), rustc, swiftc — also Go, V8, javac.
backtracking¶
What does list-of-successes backtracking return for Parse(X, i)?
Every j with X ⇒* t(i+1)…tj; it tries all alternatives and recognizes every non-left-recursive CFG.
Naive backtracking cost on E → T + E | T, T → ( E ) | id with d nested parens?
3·2^(d+1) − 3 rule invocations: every E parses T twice.
Why is ordered choice (PEG) not the same as backtracking over a CFG?
It commits to the first alternative that succeeds: S → a | a b rejects a b.
memoization¶
What does memoizing a backtracking parser cache?
Parse(X, i) per (nonterminal, position); each pair computed once — 2d + 2 calls on the nesting example.
When is memoizing a parser wrong?
When parsing has side effects or context (C typedef names): (X, i) no longer determines the result.
Worst-case cost of memoized list-of-successes recognition?
O(|N|·(n+1)) entries, O(|G|·n²) set work each: O(|N|·|G|·n³).
strong-llk¶
Strong LL(k) prediction set of A → α?
FIRST_k(α) ⊕k FOLLOW_k(A); strong LL(k) iff these sets are disjoint for A's alternatives.
Why is strong LL(k) weaker than LL(k) for k ≥ 2?
FOLLOW_k(A) merges all contexts: S → a A a a | b A b a, A → b | ε is LL(2) but only strong LL(3).
Is strong LL(1) weaker than LL(1)?
No: strong LL(1) = LL(1).
full-llk¶
What does a canonical LL(k) parser stack instead of bare nonterminals?
(A, L) pairs, L = the local follow set (k-strings) of that occurrence; one table T_{A,L} per pair.
How are the local follow sets of LL(k) computed?
From (S, {$}): for (A, L) and A → α B β add (B, FIRST_k(β) ⊕k L), to a fixed point.
Why is full LL(k) rarely implemented?
The number of (A, L) tables can be exponential; predicates, LL() or ALL() give the power more cheaply. LL(k) ⊊ LL(k+1) (Kurki-Suonio).
Give a family of grammars that are LL(k) but not strong LL(k), for each k ≥ 2.
G_k: S → a A a^k | b A b a^(k−1), A → b | ε. It is LL(2) (local follows {aa} and {ba} separate the alternatives) but FOLLOW_k(A) merges both contexts, so b a^(k−1) is in the strong lookahead of both A-alternatives.
llstar¶
What is an LL(*) lookahead DFA?
A per-decision DFA built by subset construction over grammar configurations; accept states predict alternatives; cycles allow unbounded (regular) lookahead. ANTLR 3.
Which decision is LL(*) but not LL(k) for any k?
S → X c | X d, X → a X | b: the DFA loops on a, then decides on c/d.
When does LL(*) static analysis fail, and what does ANTLR 3 do then?
When the lookahead is not regular (recursion in the lookahead, e.g. S → a S | a S b | ε); it falls back to predicates/backtracking.
Why does ANTLR 3 reject S → X c | X d, X → a X | b as "non-LL(*)" although a 4-state lookahead DFA exists?
Its configurations carry return-address stacks, so each recursive call of X pushes a frame and the configuration sets never repeat; with symbol-string stacks the tail call leaves nothing behind and the subset construction closes. Written as X → a* b, ANTLR 3 builds the cyclic DFA.
all-star¶
ALL(*)'s two stages?
SLL simulation without the caller's context first; only on an SLL conflict, full-LL simulation with the real parser stack (execATN → execATNWithFullContext).
Is an SLL conflict an ambiguity?
No: SLL forgets the caller and can merge alternatives the real context separates. Only a conflict under full LL context is a true ambiguity.
Complexity of ALL(*)?
O(n⁴) worst case; linear in practice thanks to the per-decision DFA cache (Parr, Harwell & Fisher 2014).
panic-mode¶
Panic-mode rules for an LL(1) parser?
Mismatched terminal: pop it. Nonterminal A, empty cell: pop A if the lookahead ∈ FOLLOW(A) or is $, else skip the token. $ on top: skip the rest.
Why does panic-mode recovery terminate?
Recovery actions only pop or consume, never push; normal steps between errors are bounded.
Clang's panic-mode primitive?
Parser::SkipUntil with StopAtSemi / StopBeforeMatch, balancing (), [], {} while skipping.
Why can a symbol pushed at lookahead a never cause an error before a is consumed (immediate error detection, Lemma 2.7.7)?
The expansion that pushed it was chosen because a ∈ PREDICT; the symbols before it that vanished were nullable without a in their FIRST, so a is in FIRST of the symbol or in its FOLLOW with the symbol nullable: its cell for a is non-empty. Hence panic-mode errors at a position only pop older symbols, which bounds recovery.
phrase-level¶
What is phrase-level recovery?
A hand-written routine per error cell that makes a local edit (insert ')', delete a stray token, insert an operand) with a precise message.
How do phrase-level routines avoid infinite loops?
At most one insertion per input position before a token is consumed; otherwise delete.
Clang example of phrase-level recovery?
Parser::ExpectAndConsumeSemi: report "expected ';'" with a fix-it and continue as if it were there.
repair¶
What is the repair distance of an input?
The minimum number of token insertions/deletions that turn it into a sentence (Aho & Peterson 1972: O(n³) for any CFG).
ANTLR 4's single-token repair?
recoverInline: singleTokenDeletion if the next token is the expected one; singleTokenInsertion if the current token can follow the missing one; else sync (panic).
Why isn't global minimum-distance repair used in compilers?
Cubic cost over the whole input, and the cheapest edit is not always the intended one; bounded windows (Burke & Fisher 1987) are the practical compromise.