Skip to content

Theory test — Chapter 3

30 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 3                                   # interactive
./course quiz template 3 -o answers/ch03.yaml  # or fill in a file ...
./course quiz grade 3                             # ... and grade it
Question 1 handle-of-form · mapping · 1 pt · 01-shift-reduce-and-lr0

Grammar (augmented): (0) S' → S, (1) S → L = R, (2) S → R, (3) L → * R, (4) L → id, (5) R → L.
The string L = * id is a right-sentential form. Give its handle.
production: the production number of the handle.
end: the position (1-based symbol index) where the handle's right side ends.

Keys: production, end
Answer format: one value per key
Question 2 sr-trace-running · sequence · 1 pt · 01-shift-reduce-and-lr0

Same grammar, with the LALR(1) table of Lesson 3.3 (states numbered as in Lesson 3.1:
I0 –* → I1, –id → I2, –S → I3, –L → I4, –R → I5; I1 –L → I6, –R → I7; I4 –= → I8;
I8 –* → I1, –id → I2, –L → I6, –R → I9). Give the actions of the driver on id = * id,
written s<state>, r<production>, acc.

Answer format: items in order, e.g. A B C
Question 3 closure-state0 · set · 1 pt · 01-shift-reduce-and-lr0

Same grammar. Give all LR(0) items of CLOSURE({S → L = • R}), written like S -> L = . R
(use . for the dot), separated by commas.

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 4 llparser-technique · single · 1 pt · 01-shift-reduce-and-lr0

Find where LLVM does it: open llvm/lib/AsmParser/LLParser.cpp (LLVM 23.1.2) and read
LLParser::parseTopLevelEntities. How does LLVM's textual IR parser choose what to parse next?

  1. It consults a Bison-generated LALR(1) ACTION table.
  2. It switches on the current token kind (Lex.getKind()) and calls one parse function per construct — hand-written recursive descent.
  3. It runs a GLR parser and resolves ambiguities with dynamic precedence.
  4. It uses Floyd's operator-precedence relations between tokens.
Answer format: one letter
Question 5 slr-conflict-cell · mapping · 1 pt · 02-slr-and-canonical-lr1

Same grammar; FOLLOW(L) = FOLLOW(R) = {=, $}, FOLLOW(S) = {$}. In the SLR(1) table, give
the actions (e.g. s8 r5, - for empty) of the cells
4/=, 4/$ (state I4 = {S → L • = R, R → L •}) and 2/* (state I2 = {L → id •}).

Keys: 4/=, 4/$, 2/*
Answer format: one value per key
Question 6 lr-hierarchy · mapping · 1 pt · 02-slr-and-canonical-lr1

Classify each grammar as LR(0), SLR(1), LALR(1), LR(1) or none (the smallest class whose
table has no conflict).
expr: E → E + T | T, T → T * F | F, F → ( E ) | id
assign: S → L = R | R, L → * R | id, R → L
nonlalr: S → a A d | b B d | a B e | b A e, A → c, B → c
cc: S → C C, C → c C | d
flat: E → E + E | id

Keys: expr, assign, nonlalr, cc, flat
Answer format: one value per key
Question 7 lr1-closure-lookaheads · mapping · 1 pt · 02-slr-and-canonical-lr1

Canonical LR(1) state 0 of the assign grammar is CLOSURE({[S' → • S, $]}). Give the
lookahead set of each item (e.g. = $).
"L -> . id", "L -> . * R", "R -> . L", "S -> . R"

Keys: L -> . id, L -> . * R, R -> . L, S -> . R
Answer format: one value per key (a set: {x, y})
Question 8 ll1-in-lr1 · multi · 1 pt · 02-slr-and-canonical-lr1

Which statements are true?

  1. Every LL(1) grammar is LR(1).
  2. Every LL(1) grammar is LALR(1).
  3. Every LR(1) grammar is unambiguous.
  4. Every unambiguous grammar is LR(1).
  5. A left-recursive grammar can be SLR(1).
Answer format: letters, e.g. a, c
Question 9 merge-conflict-kind · single · 1 pt · 03-lalr

A grammar's canonical LR(1) table has no conflict, but its LALR(1) table has one. What kind
can it be?

  1. Only shift/reduce, because merging adds shifts.
  2. Only reduce/reduce, because shifts depend only on the core.
  3. Either kind.
  4. Neither: LALR(1) and LR(1) accept the same grammars.
Answer format: one letter
Question 10 ll1-not-lalr · set · 1 pt · 03-lalr

Grammar: S → ( X | E ] | F ), X → E ) | F ], E → A, F → A, A → ε. In its LALR(1) table, on
which tokens is there a conflict in the state {E → A •, F → A •}?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 11 dp-lookaheads · mapping · 1 pt · 03-lalr

Assign grammar, LR(0) states of Lesson 3.1. DeRemer–Pennello gives Follow(0, L) = {=, $},
Follow(1, R) = Follow(1, L) = {=, $}, Follow(8, L) = Follow(8, R) = {$}, Follow(0, R) =
Follow(0, S) = {$}. Give LA for the reduce items: I2 (L → id •), I4 (R → L •),
I6 (R → L •).

Keys: I2, I4, I6
Answer format: one value per key (a set: {x, y})
Question 13 weak-compatibility · single · 1 pt · 04-minimal-lr1

Two isocore LR(1) kernels have items i = A → c • and j = B → c •, with lookaheads
K: i ↦ {d}, j ↦ {e} and K': i ↦ {e}, j ↦ {d}. Are they weakly compatible (Pager)?

  1. Yes, because neither K nor K' has a conflict.
  2. No, because L_K(i) ∩ L_K'(j) ≠ ∅ while L_K(i) ∩ L_K(j) and L_K'(i) ∩ L_K'(j) are both empty.
  3. Yes, because the cores are equal.
  4. No, because weak compatibility requires equal lookahead sets.
Answer format: one letter
Question 14 state-count-order · mapping · 1 pt · 04-minimal-lr1

For the Bison manual's "mysterious conflict" grammar (tests/ch03/Inputs/bison-mysterious.grammar),
give the number of states (without Bison's extra accept state) of LALR(1), Pager's PGM and
canonical LR(1). (Bison reports 20, 21, 22 for lalr, ielr, canonical-lr.)

Keys: lalr, pgm, lr1
Answer format: one value per key
Question 15 ielr-lalr-grammar · single · 1 pt · 04-minimal-lr1

A grammar's LALR(1) table has no inadequacy (no conflict, resolved or not). What does IELR(1) produce?

  1. The canonical LR(1) automaton.
  2. Exactly the LALR(1) automaton.
  3. An automaton between LALR(1) and canonical LR(1) in size, depending on Pager compatibility.
  4. Nothing: IELR only runs on non-LALR grammars.
Answer format: one letter
Question 16 conflict-kinds · mapping · 1 pt · 05-conflicts-and-precedence

Classify each cell (shift/reduce or reduce/reduce):
c1: {s6, r1} in E → E + E • / E → E • * E, on *
c2: {r5, r6} in {A → c •, B → c •}, on d
c3: {s3, r2, r4}

Keys: c1, c2, c3
Answer format: one value per key
Question 17 unifying-counterexample · single · 1 pt · 05-conflicts-and-precedence

Bison prints for a conflict First example: 'a' 'c' . 'd' $end and Second example: 'b' 'c' . 'd' $end.
What does this tell you?

  1. The grammar is ambiguous.
  2. The conflict is nonunifying: no single input is shown to have two parses; typical of LALR merging or of needing more lookahead.
  3. The grammar has a cycle A ⇒+ A.
  4. Precedence declarations will resolve it safely.
Answer format: one letter
Question 18 prec-resolution · mapping · 1 pt · 05-conflicts-and-precedence

E → E + E | E * E | ( E ) | id with %left + then %left * (* binds tighter). Resolve:
a: state E → E + E • with lookahead *
b: state E → E * E • with lookahead +
c: state E → E + E • with lookahead +

Keys: a, b, c
Answer format: one value per key
Question 19 prec-trace · sequence · 1 pt · 05-conflicts-and-precedence

Same grammar and declarations; productions (1) E → E + E, (2) E → E * E, (3) E → ( E ),
(4) E → id. Give the productions reduced, in order, when parsing id * id + id.

Answer format: items in order, e.g. A B C
Question 20 mc-plus-precedence · number · 1 pt · 05-conflicts-and-precedence

Find where LLVM does it: in llvm/lib/MC/MCParser/AsmParser.cpp (LLVM 23.1.2),
getGNUBinOpPrecedence returns a precedence number for each binary operator. What number
does it return for + and -?

Answer format: a number
Question 21 floyd-relation · mapping · 1 pt · 05-conflicts-and-precedence

Floyd's relations for E → E + T | T, T → T * F | F, F → ( E ) | id (stack terminal first,
input terminal second). Write <, =, > or none.
"+ ", " +", "( )", "id ("

Keys: + *, * +, ( ), id (
Answer format: one value per key
Question 22 glr-tree-count · number · 1 pt · 06-glr

A GLR parser for E → E + E | E * E | ( E ) | id (no precedence) parses
id + id * id + id * id. How many parse trees does the root node of its SPPF represent?

Answer format: a number
Question 23 rnglr-why · single · 1 pt · 06-glr

What problem of Tomita's GLR algorithm does RNGLR solve?

  1. Its exponential running time on unambiguous grammars.
  2. Incorrect behavior (missed parses or non-termination) on grammars with ε-rules, especially hidden left recursion.
  3. Its inability to use LALR tables.
  4. Its lack of a parse forest.
Answer format: one letter
Question 24 brnglr-bound · single · 1 pt · 06-glr

What is the worst-case time of BRNGLR on an input of length n, for any context-free grammar?

  1. O(n)
  2. O(n^2)
  3. O(n^3)
  4. O(n^(p+1)) with p the longest right side
Answer format: one letter
Question 25 yacc-discards · set · 1 pt · 07-lr-error-recovery

Grammar S → S L | L, L → x ; | error ; with yacc/Bison recovery (an error is reported only
after 3 real tokens have been shifted since the last error). Input tokens (0-based):
x x ; x x x ;. Give the positions of the tokens the parser discards.

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 26 clang-skipuntil · single · 1 pt · 07-lr-error-recovery

Find where LLVM does it: Parser::SkipUntil in clang/lib/Parse/Parser.cpp (LLVM 23.1.2)
skips tokens until one of a given set. What plays the role of that set in a yacc parser with
error productions?

  1. The FIRST set of the start symbol.
  2. The tokens that can follow error in the error productions of the states the parser pops back to (e.g. ; in L → error ;).
  3. The tokens in %left declarations.
  4. Nothing: yacc never skips tokens.
Answer format: one letter
Question 27 bf-repair · mapping · 1 pt · 07-lr-error-recovery

Expression grammar E → E + T | T, T → T * F | F, F → ( E ) | id, input id + * id
(tokens 0-based). With the course's Burke–Fisher oracle (window 2, prefer the position
closest to the error, then delete < insert < replace), give the chosen repair.
kind: delete, insert or replace
position: the token position

Keys: kind, position
Answer format: one value per key
Question 28 unreachable-error-site · set · 1 pt · 07-lr-error-recovery

E → E + E | ( E ) | id with %left +, LALR(1). State 3 is {E' → E •, E → E • + E}; its
empty ACTION cells are (, ) and id. Which of these error sites can never be reached
by any input?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 29 recovery-compare · multi · 1 pt · 07-lr-error-recovery

Which statements are true?

  1. Burke–Fisher repair can place an edit before the token where the error was detected.
  2. yacc's error recovery requires the grammar author to add error productions.
  3. menhir --list-errors lists one sentence for every empty ACTION cell.
  4. A Menhir .messages file maps states to hand-written messages.
Answer format: letters, e.g. a, c
Question 30 where-lr-dominates · multi · 1 pt · 08-lr-in-practice

Which statements about production parsers (as of the pinned versions) are true?

  1. PostgreSQL 17 parses SQL with a Bison-generated LALR(1) parser whose grammar declares %expect 0.
  2. GCC's C++ front end has used a hand-written recursive-descent parser since GCC 3.4.
  3. Ruby 3.4's default parser is generated by Bison.
  4. OCaml's compiler grammar is written for Menhir.
  5. Clang's C++ parser is generated by an LR generator.
Answer format: letters, e.g. a, c