Theory test — Chapter 2¶
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 2 # interactive
./course quiz template 2 -o answers/ch02.yaml # or fill in a file ...
./course quiz grade 2 # ... and grade it
leftmost-derivation-order · sequence · 1 pt · 01-grammars-and-ambiguityGrammar: (1) E → E + T (2) E → T (3) T → T * F (4) T → F (5) F → ( E ) (6) F → id.
Give the leftmost derivation of id + id * id as the sequence of production numbers.
chomsky-classes · multi · 1 pt · 01-grammars-and-ambiguityWhich statements are true?
- {aⁿbⁿ : n ≥ 0} is context-free but not regular.
- Every context-free language is regular.
- {aⁿbⁿcⁿ : n ≥ 0} is context-free.
- A grammar whose productions all have the shape A → t B, A → t or A → ε is regular (type 3).
- A type-2 (context-free) grammar may generate a regular language.
catalan-trees · number · 1 pt · 01-grammars-and-ambiguityHow many parse trees does the grammar E → E + E | x give for x + x + x + x + x (four operators)?
layering-parenthesize · mapping · 1 pt · 01-grammars-and-ambiguityOperators, lowest precedence first: + - (left-associative), * / (left-associative),
^ (right-associative). The layered grammar built from this table parses
id - id * id ^ id.
grouping: the fully parenthesized form, every binary operation in parentheses, no spaces (e.g. ((id-id)-id)).
flat-trees: how many parse trees the flat grammar E → E + E | E - E | E * E | E / E | E ^ E | ( E ) | id gives for the same sentence.
grouping, flat-treesclang-prec-level · text · 1 pt · 01-grammars-and-ambiguityIn LLVM 23, open clang/include/clang/Basic/OperatorPrecedence.h. Which enumerator of prec::Level do the binary + and - operators get?
first-sets-running · mapping · 1 pt · 02-first-follow-fixed-pointsGrammar: (1) S → i E t S S' (2) S → a (3) S' → e S (4) S' → ε (5) E → T E'
(6) E' → + T E' (7) E' → ε (8) T → ( E ) (9) T → x.
Give FIRST of every nonterminal (include ε for nullable nonterminals).
S, S', E, E', Tfollow-sets-running · mapping · 1 pt · 02-first-follow-fixed-pointsSame grammar as the previous question. Give FOLLOW of every nonterminal ($ marks the end).
S, S', E, E', Tclang-first-set · single · 1 pt · 02-first-follow-fixed-pointsIn LLVM 23, clang/lib/Parse/ParseDecl.cpp defines Parser::isTypeSpecifierQualifier(const Token &Tok)
as a switch over token kinds. In the terms of lesson 2.2, what does it encode by hand?
- FOLLOW(type-specifier-qualifier)
- FIRST(type-specifier-qualifier) — the tokens that can begin one
- The nullable set of the declaration grammar
- An LL(2) lookahead DFA
table-cells-running · mapping · 1 pt · 03-ll1-tables-and-conflictsSame grammar as first-sets-running. Give the production number in each LL(1) table cell
(write the cell as A/t): S/i, E'/t, T/(, S'/$, E/x, E'/+.
S/i, E'/t, T/(, S'/$, E/x, E'/+conflict-kinds · mapping · 1 pt · 03-ll1-tables-and-conflictsClassify the LL(1) conflict of each grammar as FIRST/FIRST or FIRST/FOLLOW.
g1: S → a b | a c
g2: S → A a; A → a | ε
g3: S → A | B; A → a | ε; B → b | ε
g4: E → E + T | T; T → id
g1, g2, g3, g4clang-dangling-else · text · 1 pt · 03-ll1-tables-and-conflictsIn LLVM 23, Parser::ParseIfStatement in clang/lib/Parse/ParseStmt.cpp binds an else to the nearest if. Which diagnostic ID (the diag:: enumerator) does it emit when an inner if without braces took the else?
paull-indirect · set · 1 pt · 04-grammar-transformationsRemove the left recursion from S → A a | b; A → A c | S d | ε with Paull's algorithm
(order S, A; the new nonterminal is A'). Give A's alternatives in the result
(comma-separated, e.g. x A', A').
paull-blowup · number · 1 pt · 04-grammar-transformationsRun Paull's algorithm on N1 → N5 c | d and Ni → N(i−1) a | N(i−1) b for i = 2 … 5
(order N1 … N5). How many productions does the result have?
left-factor-result · set · 1 pt · 04-grammar-transformationsLeft-factor S → i E t S | i E t S e S | a (the new nonterminal is S'). Give the alternatives
of S' (comma-separated; write ε for the empty one).
transform-properties · multi · 1 pt · 04-grammar-transformationsWhich statements about left-recursion removal and left factoring are true?
- They preserve the language of the grammar.
- The result is always LL(1).
- They may change the shape of parse trees, e.g. turn left-nested sums into right-nested chains.
- Left factoring removes FIRST/FOLLOW conflicts.
- Paull's algorithm always succeeds on cycle-free grammars without ε-productions.
clang-right-assoc · text · 1 pt · 04-grammar-transformationsIn LLVM 23, Parser::ParseRHSOfBinaryExpression in clang/lib/Parse/ParseExpr.cpp parses binary operators with a loop. What is the name of the local bool that makes ?: and assignment group to the right?
predict-derivation · sequence · 1 pt · 05-recursive-descentGrammar: (1) E → T E' (2) E' → + T E' (3) E' → ε (4) T → F T' (5) T' → * F T'
(6) T' → ε (7) F → ( E ) (8) F → id.
Give the productions the table-driven LL(1) parser outputs on id * ( id + id ).
predictive-error-position · number · 1 pt · 05-recursive-descentSame grammar. At which token (numbered from 1) does the predictive parser detect the error in ( id + ) * id?
clang-stmt-dispatch · text · 1 pt · 05-recursive-descentIn LLVM 23, Parser::ParseStatementOrDeclarationAfterAttributes (clang/lib/Parse/ParseStmt.cpp) switches on the current token kind. Which case label dispatches to ParseWhileStatement?
backtrack-calls · mapping · 1 pt · 05-recursive-descentGrammar E → T + E | T; T → ( E ) | id. A list-of-successes backtracking parser counts one
call per nonterminal invocation that runs its alternatives. Input: ( ( ( ( ( id ) ) ) ) )
(5 levels). Give the number of calls without memoization (naive) and with memoization (memo).
naive, memoordered-choice · single · 1 pt · 05-recursive-descentGrammar S → a | a b, input a b. What do a full (list-of-successes) backtracking parser and a PEG parser with ordered choice (packrat) do?
- Both accept
- Backtracking accepts; PEG rejects
- Backtracking rejects; PEG accepts
- Both reject
llk-min-k · mapping · 1 pt · 06-llk-and-all-starGrammar: S → c A b a | a A a b; A → b | ε. Give the smallest k for which it is strong LL(k)
(strong) and the smallest k for which it is LL(k) (full).
strong, fullfull-llk-contexts · set · 1 pt · 06-llk-and-all-starSame grammar, k = 2. Give every local follow set L of A (each written as its k-strings, e.g. aa).
llstar-dfa · number · 1 pt · 06-llk-and-all-starGrammar S → X c | X d | e; X → a X | b. How many states does the LL(*) lookahead DFA for the
decision S have (count accept states too)?
sll-vs-ll · mapping · 1 pt · 06-llk-and-all-starGrammar S → x B a | y B b a; B → b | ε. The parser has consumed y (so it is inside
S → y B b a and the stack below B is b a $) and must choose B's alternative
(1: B → b, 2: B → ε). The remaining input is b a $.
Give sll (the SLL outcome: an alternative number or conflict) and ll (the full-LL alternative).
sll, llclang-tentative-result · text · 1 pt · 06-llk-and-all-starIn LLVM 23, clang/lib/Parse/ParseTentative.cpp decides declaration vs expression with helpers such as TryParseSimpleDeclaration. What is the name of the enumeration type they return (with enumerators True, False, Ambiguous and Error)?
panic-mode-trace · mapping · 1 pt · 07-error-recoveryGrammar of predict-derivation, panic-mode recovery with FOLLOW sets (lesson 2.7):
a mismatched terminal is popped; for an empty M[A, a], pop A if a ∈ FOLLOW(A) or a = $, else skip a;
with $ on top, skip the rest. Input: id * * id ) id (tokens numbered from 1).
Give error-at (the first error's token), popped (the symbols popped by recovery) and skipped
(the skipped tokens' numbers).
error-at, popped, skippedphrase-level-effective · sequence · 1 pt · 07-error-recoverySame grammar, phrase-level routines: E, T or F facing an operator, ) or $ → "missing operand",
insert id; E' or T' facing id or ( → "missing operator", insert +; ) expected at $ →
insert ); $ on top facing ) → delete it. Give the token sequence the parser effectively parses
for the input ( id id.
repair-distance · mapping · 1 pt · 07-error-recoverySame grammar and phrase-level routines as the previous question. Input: ( id * ) id.
distance: the minimum number of single-token insertions and deletions that turn the input into a sentence.
edits: how many edits the phrase-level routines make (each insertion or deletion counts one).
distance, editsclang-skipuntil · text · 1 pt · 07-error-recoveryIn LLVM 23, clang/include/clang/Parse/Parser.h declares enum SkipUntilFlags for Parser::SkipUntil. Which flag makes skipping also stop at a ;?