Flashcards — Chapter 3¶
57 cards. Review them with spaced repetition in the terminal (./course flash 3) or export them to Anki (./course flash export 3). Here, click a card to reveal its back.
shift-reduce¶
What is a handle of a right-sentential form?
A pair (A → β, k): the occurrence of β ending at position k that the last step of some rightmost derivation S' ⇒rm* αAw ⇒rm αβw produced. Reducing it gives the previous form.
What is a viable prefix?
A prefix of a right-sentential form that does not extend past the right end of its handle: exactly the possible contents of a correct shift-reduce parser's stack.
In which order does a shift-reduce parser produce the derivation?
The rightmost derivation in reverse: its reductions, read backwards, apply productions to the rightmost nonterminal from S down to w (postorder of the tree).
Why is a reducible right side on the stack not always a handle?
Because the handle is fixed by the rightmost derivation, not by matching: in the running example the stack L matches R → L, but reducing before = gives R =, which no right-sentential form contains.
lr0¶
What is an LR(0) item, and when is it valid for γ?
A production with a dot, [A → α • β]; valid for γ = δα if S' ⇒rm* δAw ⇒rm δαβw for some w.
State the key theorem about the LR(0) automaton.
δ*(q0, γ) is defined iff γ is a viable prefix, and then it equals the set of items valid for γ (Knuth 1965). So viable prefixes form a regular language.
How does CLOSURE work for LR(0) items?
Least set containing I such that [A → α • B β] in it adds [B → • η] for every production of B; a worklist over the item list computes it.
What is the course's state numbering?
State 0 = CLOSURE({S' → • S}); breadth first; each state's successors created in symbol order: terminals by first appearance, then nonterminals in grammar order (Bison's order if tokens are declared that way).
How large can the LR(0) automaton be?
Exponential: the family S → Ai, Ai → aj Ai (j ≠ i), Ai → bi has n·2^(n−1) + n² + 2 states for n² + n productions. In practice PostgreSQL's 3 408 rules give 6 458 states.
slr¶
Where does an SLR(1) parser reduce by A → β?
In every state with the completed item A → β •, on every token in FOLLOW(A).
Why is the assignment grammar S → L = R | R, L → * R | id, R → L not SLR(1)?
In the state {S → L • = R, R → L •}, = ∈ FOLLOW(R) (via L → * R on the left of =), so shift = and reduce R → L collide; LALR's lookahead there is only $.
How does SLR relate to LR(0) and LALR(1) as grammar classes?
LR(0) ⊊ SLR(1) ⊊ LALR(1): the expression grammar is SLR not LR(0); the assignment grammar is LALR not SLR.
lr1¶
What is an LR(1) item and when is it valid for γ?
[A → α • β, a]: valid if S' ⇒rm* δAw ⇒rm δαβw with γ = δα and a = first symbol of w$.
LR(1) closure rule?
[A → α • B β, a] adds [B → • η, b] for every b ∈ FIRST(β a).
When are two canonical LR(1) states equal?
Only when their kernels have the same items with the same lookahead sets; equal cores with different lookaheads are different states.
Knuth's characterization of LR(1) grammars?
A grammar is LR(1) iff its canonical LR(1) table has no conflict. LR(k) grammars are unambiguous.
Is every LL(1) grammar LR(1)? LALR(1)?
Every LL(1) grammar is LR(1) (Knuth; proof via the left-part theorem, Nijholt 1982), but not always LALR(1); every p-reduced LL(1) grammar is LALR(1) (Beatty 1982).
lalr¶
How do you get LALR(1) from canonical LR(1)?
Merge the LR(1) states that have the same core (LR(0) item set), taking the union of lookaheads per item; the states are the LR(0) states.
What kind of conflict can merging LR(1) states introduce?
Only reduce/reduce: shifts depend on the core alone, so a merged shift/reduce conflict already existed in one of the canonical states.
What is a "mysterious" reduce/reduce conflict?
A merge artifact: two contexts reach one LR(0) state with disjoint lookaheads; LALR unions them. No input is ambiguous; Bison shows two different counterexamples. IELR removes it.
Give an LR(1) grammar that is not LALR(1).
S → a A d | b B d | a B e | b A e, A → c, B → c: the states after a c and b c merge into {A → c •, B → c •} with lookaheads {d, e} for both.
deremer-pennello¶
Name DeRemer–Pennello's relations.
DR(p,A): terminals shifted after the A-transition; reads: over nullable nonterminals; includes: (p,A) includes (p',B) if B → β A γ, γ nullable, p' --β--> p; lookback: (q, A→ω) to (p,A) if p --ω--> q.
What does Digraph compute and how fast?
The least F with F(x) = F'(x) ∪ ⋃{F(y) : x R y}, via Tarjan-style DFS where SCC members share one set; linear in nodes + edges (one set union per edge).
How are LALR lookaheads obtained from the relations?
Read = Digraph(DR, reads); Follow = Digraph(Read, includes); LA(q, A → ω) = ⋃ Follow(p, A) over the transitions it looks back to.
Why must DR of the transition on S from state 0 contain $?
Its target holds S' → S •, which accepts on $; with the S' → S augmentation (no explicit $ shift), that is the only way $ enters the relations.
pgm¶
Pager's weak compatibility of isocores K, K'?
For all kernel items i ≠ j: (L_K(i) ∩ L_K'(j) = ∅ and L_K'(i) ∩ L_K(j) = ∅) or L_K(i) ∩ L_K(j) ≠ ∅ or L_K'(i) ∩ L_K'(j) ≠ ∅.
What does Pager's method guarantee?
Merging only weakly compatible states never creates a conflict that canonical LR(1) lacks: LR(1) power at close to LALR size. Menhir's default.
How does PGM compare in size on the Bison "mysterious" grammar?
Ours: LALR 19, PGM 20, canonical 21 states (Menhir: 21, 22, 23 with its EOF rule): one state split removes the conflict.
ielr¶
What is an inadequacy in IELR(1)?
A (state, token) of the LALR automaton with two or more actions before conflict resolution, including conflicts later resolved by precedence.
What do IELR annotations record?
For each inadequacy, which kernel items of which (predecessor) states contribute which actions; isocores are merged only if merging leaves every contribution set unchanged.
IELR size guarantee?
If LALR(1) has no inadequacy, IELR returns exactly the LALR automaton; otherwise it splits only what changes canonical LR(1) behavior (PostgreSQL: 6 459 vs 6 458 states).
conflicts¶
Shift/reduce vs reduce/reduce conflict?
A cell with two or more actions is shift/reduce if one is a shift, reduce/reduce if all are reductions.
What is yacc's default resolution?
Shift beats reduce; between reductions, the production listed first wins. Bison warns and %expect acknowledges a count.
Unifying vs nonunifying counterexample?
Unifying: one sentential form with two derivations (the grammar is ambiguous). Nonunifying: two different inputs sharing the conflicting stack (needs more lookahead or is a merge artifact).
precedence¶
How is a shift/reduce conflict between rule p and token t resolved by precedence?
Compare levels (rule = its last terminal with a level): reduce if the rule's is higher, shift if lower; if equal: %left reduces, %right shifts, %nonassoc makes an error entry.
When is precedence resolution safe?
When every sentence keeps a tree consistent with the choices, as for operator ambiguities (the layered grammar's trees) and the dangling else; unsafe for non-operator conflicts, where sentences can disappear.
Why do declarations beat layered expression grammars?
Fewer states (2k + 6 vs 3k + 6 for k operators) and no chains of unit reductions (1 vs up to k + 1 per operand): Aho–Johnson–Ullman 1975.
op-precedence¶
Floyd's three relations?
a ⋖ b: b starts a phrase nested in a's; a ≐ b: same phrase; a ⋗ b: a's phrase ends before b. Computed from LEADING and TRAILING sets of an operator grammar.
What is an operator grammar?
No ε right sides and no two adjacent nonterminals in any right side.
Weakness of operator-precedence parsing?
It reduces anonymous skeletons (N + N), so it cannot tell nonterminals apart and may accept non-sentences; error detection is weak.
glr¶
What is a graph-structured stack?
One node per (LR state, input position); edges point down to earlier nodes and carry the forest node of the symbol; every root path is one LR stack.
What is a shared packed parse forest?
Symbol nodes (X, i, j) unique per span, with packed nodes for alternative derivations; shared subtrees make exponentially many trees fit in polynomial space.
Tomita GLR complexity?
O(n^(p+1)) time and space for longest right side p; deterministic regions run at LR speed.
rnglr¶
What goes wrong with naive GLR on ε-rules?
With hidden left recursion (A ⇒+ β A γ, β ⇒+ ε) ε-reductions at one level can loop or be missed; Bison's GLR does not terminate on S → A S b | x, A → ε.
What is RNGLR's idea?
Right-nulled reductions: reduce A → αβ with β nullable as soon as α is on the stack, attaching a precomputed ε-forest, so reductions never traverse ε-edges created at the current level.
What does BRNGLR add?
Binarized reductions (at most two edges per step), giving O(n³) worst-case time for all context-free grammars.
yacc-error¶
How does yacc recover with the error token?
Report (if 3 tokens were shifted since the last error), pop states until one shifts error, shift it, then discard tokens until one has an action; yyerrok ends recovery early.
Why does yacc recovery terminate?
Each error either discards an input token or, after popping and shifting error, is followed by a discard on the next error; tokens are consumed once.
What does the recovery status (3) do?
After recovering, no new error is reported until three real tokens have been shifted, suppressing cascades.
burke-fisher¶
Burke–Fisher simple repair?
At the first error, try single-token insertions, deletions and substitutions within a window of k deferred tokens; keep the one that lets the parser advance furthest.
Why does Burke–Fisher defer tokens?
The error is often detected after its cause; keeping k tokens unreduced lets the repair be placed before the detection point (ML-Yacc inserts ( at token 0 for an error at token 5).
Modern successor of Burke–Fisher?
CPCT+ (Diekmann–Tratt 2020): all minimum-cost repair sequences within a time budget, in Rust's grmtools.
messages¶
What does menhir --list-errors produce?
For every state where an error can actually occur, a shortest input reaching it, with the state's items, as a .messages skeleton for hand-written messages.
Why is the shortest path in the automaton only a lower bound for error sentences?
Following a nonterminal edge needs reductions enabled by the next token; some error sites are unreachable (e.g. ( after a reduced E in an expression grammar). Pottier's LRijkstra checks this.
lr-practice¶
Where do LR generators still dominate?
SQL engines (PostgreSQL, SQLite's Lemon, MySQL), PHP, OCaml (Menhir), CompCert (validated Menhir), editor tooling (tree-sitter).
Why did GCC replace its yacc C++ parser?
C++ is not LR(k) (declaration vs expression needs arbitrary lookahead); a hand-written RD parser with tentative parsing gave control and better errors (GCC 3.4, 2004; C in 4.1).
What did Ruby do with its parser in 3.3 and 3.4?
3.3 replaced Bison with its own Lrama LALR generator; 3.4 made the hand-written Prism parser the default.