Skip to content

Theory test — Chapter 1

56 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 1                                   # interactive
./course quiz template 1 -o answers/ch01.yaml  # or fill in a file ...
./course quiz grade 1                             # ... and grade it
Question 1 nested-comments-not-regular · multi · 1 pt · 01-regular-languages-and-thompson

You want to prove with the pumping lemma (pumping length \(p\)) that Pebble's nested block comments, \(C = \{\, (\texttt{/*})^{k}\,x\,(\texttt{*/})^{k} \mid k \ge 1 \,\}\) restricted to \(x = \varepsilon\), are not regular. Which statements are correct steps of the proof?

  1. Pick \(w = (\texttt{/*})^{p}(\texttt{*/})^{p}\), which is in \(C\) and has length \(\ge p\).
  2. Pick the decomposition \(w = xyz\) so that \(y\) is exactly one /*.
  3. For every decomposition with \(\lvert xy\rvert \le p\), \(y \ne \varepsilon\), the part \(y\) lies within the openers.
  4. Pumping \(y\) changes the openers but not the \(p\) closers, so \(xy^{2}z \notin C\).
  5. It suffices to show that one particular DFA with a depth counter needs infinitely many states.
Answer format: letters, e.g. a, c
Question 2 closure-complement · single · 1 pt · 01-regular-languages-and-thompson

A lexer generator builds \(\overline{L(A)}\) by swapping final and non-final states of an automaton \(A\). For which \(A\) is this construction correct?

  1. Any ε-NFA
  2. Any DFA, even with missing transitions
  3. A complete DFA (a transition for every state and symbol)
  4. Only a minimal DFA
Answer format: one letter
Question 3 llvm-regex-state-sets · mapping · 1 pt · 01-regular-languages-and-thompson

In llvm/lib/Support/regexec.c (LLVM 23.1.2), llvm_regexec chooses between two matchers compiled from the same regengine.inc.
small: the matcher used when the program's number of states is at most CHAR_BIT * sizeof(long).
large: the other matcher.
small-set: the C type that represents a set of NFA states in the small matcher.
large-set: that type in the large matcher.

Keys: small, large, small-set, large-set
Answer format: one value per key
Question 4 thompson-state-count · mapping · 1 pt · 01-regular-languages-and-thompson

For \(r = a(b \mid c)^{*}d\):
thompson: the number of states of Thompson's construction as in Algorithm 1.1.6 (concatenation merges the accept state of the left fragment with the start state of the right one, as in the Dragon book).
position: the number of states of the position (Glushkov) automaton.

Keys: thompson, position
Answer format: one value per key
Question 5 thompson-closure · mapping · 1 pt · 01-regular-languages-and-thompson

Thompson NFA of \((a \mid b)^{*}abb\) (Dragon numbering): 0: ε→1, ε→7; 1: ε→2, ε→4; 2: a→3; 3: ε→6; 4: b→5; 5: ε→6; 6: ε→1, ε→7; 7: a→8; 8: b→9; 9: b→10; 10 accepting.
Give the ε-closures as sets: E3 = \(E(\{3\})\), E6 = \(E(\{6\})\), E8 = \(E(\{8\})\).

Keys: E3, E6, E8
Answer format: one value per key (a set: {x, y})
Question 6 glushkov-follow · mapping · 1 pt · 01-regular-languages-and-thompson

Linearize \((a \mid b)^{*}ab\) as \((a_1 \mid b_2)^{*}a_3 b_4\). Give Follow for each position (as sets of position numbers).

Keys: 1, 2, 3, 4
Answer format: one value per key (a set: {x, y})
Question 7 backtracking-blowup · number · 1 pt · 02-nfa-simulation-and-subset-construction

A backtracking matcher runs \((a \mid a)^{*}b\) against \(a^{10}\) (no b). The star is greedy, alternatives are tried left to right, and every choice is explored before the match fails. Each time the matcher leaves the star it tries to match the final b once. How many attempts to match b does it make in total?

Answer format: a number
Question 8 engine-choice · mapping · 1 pt · 02-nfa-simulation-and-subset-construction

Pick the best engine for each job: backtracking, pike-vm, dfa (ahead-of-time subset construction) or lazy-dfa.
grep: search large files for a user-supplied pattern without backreferences, no submatches.
backrefs: a pattern with a backreference (a+)b\1.
captures: extract submatch positions with a guaranteed linear-time bound.
lexer: a lexer specification fixed at build time.

Keys: grep, backrefs, captures, lexer
Answer format: one value per key
Question 9 subset-states · mapping · 1 pt · 02-nfa-simulation-and-subset-construction

Thompson NFA of \((a|b)^{*}a(a|b)\) has states 0–13 (Dragon numbering; the start set is \(E(\{0\}) = \{0,1,2,4,7\}\)). Run the subset construction over \(\{a, b\}\) with a FIFO worklist and name DFA states A, B, C, … in order of creation.
states: the number of DFA states (no dead state is needed here).
accepting: the accepting DFA states.
A-a, A-b: the targets of A on a and on b.

Keys: states, accepting, A-a, A-b
Answer format: one value per key (a set: {x, y})
Question 10 subset-blowup · number · 1 pt · 02-nfa-simulation-and-subset-construction

How many states does the minimal complete DFA of \((a|b)^{*}a(a|b)(a|b)(a|b)\) have over the alphabet \(\{a, b\}\)?

Answer format: a number
Question 11 lazy-dfa-states · number · 1 pt · 02-nfa-simulation-and-subset-construction

A lazy DFA runs \((a|b)^{*}a(a|b)(a|b)(a|b)\) (Thompson NFA) on the input abaabb, starting with an empty cache. How many distinct DFA states does it create, including the start state?

Answer format: a number
Question 12 derivative-compute · single · 1 pt · 03-derivatives

Which expression is the Brzozowski derivative \(\partial_a\big((ab \mid a)^{*}b\big)\), simplified by similarity?

  1. \(b \mid (ab \mid a)^{*}b\)
  2. \((b \mid \varepsilon)(ab \mid a)^{*}b\)
  3. \((b \mid \varepsilon)b\)
  4. \(b(ab \mid a)^{*}b\)
  5. \(\emptyset\)
Answer format: one letter
Question 13 derivative-nullable · mapping · 1 pt · 03-derivatives

For \(r = (ab \mid a)^{*}b\) and each word \(w\), is \(\partial_w r\) nullable (yes/no)? That is, is \(w \in L(r)\)?

Keys: a, aa, aab, ab, abab
Answer format: one value per key
Question 14 antimirov-bound · number · 1 pt · 03-derivatives

The partial-derivative (Antimirov) automaton of \((a|b)^{*}abb\) has at most \(m + 1 = 6\) states (\(m\) = symbol occurrences). How many states does it actually have?

Answer format: a number
Question 15 ort-lexer-tag · single · 1 pt · 03-derivatives

In an Owens–Reppy–Turon derivative lexer with rules (1) if and (2) [a-z]+, the DFA state reached by reading if is the vector \((\varepsilon,\ [a\text{-}z]^{*})\). Which rule does this state accept?

  1. Rule 1 (if): the first nullable component wins
  2. Rule 2: the longest rule wins
  3. Both: the lexer returns two tokens
  4. Neither: a state accepts only if exactly one component is nullable
Answer format: one letter
Question 16 derivative-classes · number · 1 pt · 03-derivatives

How many derivative classes does \(r = [a\text{-}c]x \mid [b\text{-}d]y\) induce on the 256 byte values (Definition 1.3.6)? Symbols in one class must give the same derivative \(\partial_c r\).

Answer format: a number
Question 17 moore-rounds · mapping · 1 pt · 04-dfa-minimization

Complete DFA over {a, b}, start A, accepting E:

a b
A B C
B D E
C B C
D B C
E Z Z
Z Z Z

Run Moore's algorithm from {F, Q∖F}.
rounds: the number of rounds that change the partition (not counting the final confirming round).
states: the number of states of the minimal DFA.

Keys: rounds, states
Answer format: one value per key
Question 18 myhill-nerode-classes · number · 1 pt · 04-dfa-minimization

How many Nerode classes (states of the minimal complete DFA over {a, b}) does \(L = (b^{*}ab^{*}ab^{*}ab^{*})^{*}\) have?

Answer format: a number
Question 19 hopcroft-smaller-half · single · 1 pt · 04-dfa-minimization

In Hopcroft's algorithm, a block \(B\) that is on the worklist as a splitter is itself split into \(B_1\) and \(B_2\). What does the algorithm put on the worklist?

  1. Both \(B_1\) and \(B_2\) (it replaces \(B\)); if \(B\) had not been on the worklist, only the smaller of the two
  2. Always only the smaller half
  3. Always both halves
  4. Nothing: splitters are fixed at the start
Answer format: one letter
Question 20 brzozowski-reachable · single · 1 pt · 04-dfa-minimization

Why must the automaton given to each \(\det(\mathrm{rev}(\cdot))\) step of Brzozowski's minimization have all states reachable, and how do you reverse a DFA with several final states?

  1. Unreachable states make the subset construction loop; add a fresh start state with ε-edges to the old finals
  2. Reachability is irrelevant; reversal needs a unique final state, so first merge the finals
  3. Reachability of the input makes the result's states pairwise distinguishable; start the subset construction from the set of old final states
  4. Reachability makes the result complete; reversing is only possible with one final state
Answer format: one letter
Question 21 llvm-dfa-emitter · single · 1 pt · 04-dfa-minimization

llvm/utils/TableGen/DFAEmitter.cpp (LLVM 23.1.2) builds the automata of TableGen's GenAutomaton backend (VLIW packetizers). How does DfaEmitter::constructDfa deduplicate DFA states?

  1. It runs Hopcroft's algorithm after determinization
  2. It interns each sorted set of NFA states in a UniqueVector while determinizing, without minimizing afterwards
  3. It uses Brzozowski's double reversal
  4. It never deduplicates: every transition creates a new state
Answer format: one letter
Question 22 llvm-clang-less-case · multi · 1 pt · 05-lexer-implementation-styles

In clang/lib/Lex/Lexer.cpp (LLVM 23.1.2), Lexer::LexTokenInternal, case '<', compiling C++20 with digraphs enabled (not CUDA, not inside #include <…>). Which token kinds can this case produce?

  1. less
  2. lessequal
  3. lessless
  4. lesslessequal
  5. spaceship
  6. l_square
  7. l_brace
  8. lesslessless
  9. greater
Answer format: letters, e.g. a, c
Question 23 style-choice · mapping · 1 pt · 05-lexer-implementation-styles

Choose an implementation style for each lexer: switch (hand-written loop), table (flex-style), direct (re2c direct code), combinator (regex alternation), simd (bulk classification fast path).
compiler: a C++ compiler front end with context-sensitive tokens and precise recovery.
dsl: a small configuration DSL, lexer written in an afternoon, performance irrelevant, in Python.
fastgen: a generated lexer for a build tool where speed matters and rules change rarely.
classic: a teaching compiler that generates its lexer tables from a rule file.
json: skip long runs of whitespace and string bytes in a JSON parser.

Keys: compiler, dsl, fastgen, classic, json
Answer format: one value per key
Question 24 comb-vector-lookup · mapping · 1 pt · 05-lexer-implementation-styles

A comb-vector table (Definition 1.5.2) with classes 0–2: base = [0, 1, 4]; next = [1, 2, 2, 1, 0]; check = [0, 0, 1, 1, 2]. \(T(q, c) = next[base[q] + c]\) if the index is in range and \(check[base[q] + c] = q\), else dead.
Give T for the keys q1c1, q1c0, q2c0, q0c2 (qXcY means state X, class Y).

Keys: q1c1, q1c0, q2c0, q0c2
Answer format: one value per key
Question 25 direct-coded-labels · number · 1 pt · 05-lexer-implementation-styles

re2c turns each state of the minimized lexer DFA into one label (the dead state needs none). How many labels does it need for the rules =, ==, !=, [a-z]+?

Answer format: a number
Question 26 combinator-first-match · sequence · 1 pt · 05-lexer-implementation-styles

A combinator lexer tries the alternation =|==|<|<=|[a-z]+ with a backtracking engine at each position, takes the FIRST alternative that matches (not the longest), skips nothing else. Give the lexemes it produces for a<=b==c.

Answer format: items in order, e.g. A B C
Question 27 simd-starts-mask · set · 1 pt · 05-lexer-implementation-styles

The 16-byte block id = x2+foo(bar) is classified with SIMD masks; W has bit i set iff byte i is a letter or digit. Which bit positions (0-based) are set in starts = W & ~(W << 1) (no carry from a previous block)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 28 munch-tokens · sequence · 1 pt · 06-disambiguation

Rules, in priority order: kw_if if; id [a-z][a-z0-9]*; int [0-9]+; float [0-9]+\.[0-9]+; dotdot \.\.; dot \.; ws +. Give the token rule names produced by maximal munch for if1..2 iffy 3.4.5.

Answer format: items in order, e.g. A B C
Question 29 llvm-lex-pptoken-exception · single · 1 pt · 06-disambiguation

C++ [lex.pptoken]p3: std::vector<::std::string>. In clang/lib/Lex/Lexer.cpp (LLVM 23.1.2), case '<' sees <:: followed by a character that is neither : nor >. What does it return?

  1. l_square (the digraph <:) followed by colon
  2. less, leaving :: for the next token
  3. lessless
  4. An error: <:: is ill-formed
Answer format: one letter
Question 30 priority-order · single · 1 pt · 06-disambiguation

A flex specification lists the identifier rule [a-z]+ BEFORE the rule while. What happens?

  1. while is a keyword: longer rules win ties
  2. while is a keyword: the more specific rule always wins
  3. while is an identifier, and flex warns that the keyword rule cannot be matched
  4. It is a syntax error in the specification
Answer format: one letter
Question 31 reps-reads · mapping · 1 pt · 06-disambiguation

Rules a and a*b on the input \(a^{10}\) (no b). A read is one byte fed to the DFA (including the byte that kills it).
naive: reads made by naive maximal munch with backup.
reps: reads made by Reps' memoized maximal munch.

Keys: naive, reps
Answer format: one value per key
Question 32 munch-quadratic · number · 1 pt · 06-disambiguation

With the same rules (a, a*b), how many reads does naive maximal munch make on \(a^{20}\)?

Answer format: a number
Question 33 interp-kinds · sequence · 1 pt · 07-context-sensitive-lexing

Give the Pebble token kinds for the source "x\(a(b))\("c")!" (one string with two interpolations).

Answer format: items in order, e.g. A B C
Question 34 interp-depth · number · 1 pt · 07-context-sensitive-lexing

While lexing the Pebble source "\("\("\(x)")")", what is the maximum height of the InterpolationDepth stack?

Answer format: a number
Question 35 js-slash · mapping · 1 pt · 07-context-sensitive-lexing

For each JavaScript snippet, is the first / the start of a regex literal or a division (answer regex or division)?
a: x = a / b / g
b: x = /b/g
c: f(a) / 2
d: if (a) /b/.test(s)
e: return /x/

Keys: a, b, c, d, e
Answer format: one value per key
Question 36 context-feedback · mapping · 1 pt · 07-context-sensitive-lexing

Where does the information that resolves each case live? Answer lexer (state kept inside the lexer), parser (the parser decides or re-splits) or symbols (the symbol table).
interpolation: Pebble string interpolation.
slash: JavaScript regex vs division.
angle: C++ >> closing two templates.
indent: Python INDENT/DEDENT.
raw: C++ raw-string delimiters.
typedef: C typedef names.

Keys: interpolation, slash, angle, indent, raw, typedef
Answer format: one value per key
Question 37 llvm-template-greater · multi · 1 pt · 07-context-sensitive-lexing

In clang/lib/Parse/ParseTemplate.cpp (LLVM 23.1.2), Parser::ParseGreaterThanInTemplateList ends a template argument list. Which tokens does it accept there, splitting off one > when the token is longer? (Ignore CUDA.)

  1. >
  2. >>
  3. >=
  4. >>=
  5. ->
Answer format: letters, e.g. a, c
Question 38 indent-dedent-count · mapping · 1 pt · 07-context-sensitive-lexing

Python's tokenizer on this file (4-space steps):

if a:
    if b:
        x
z

indent: how many INDENT tokens? dedent: how many DEDENT tokens? before-z: how many DEDENT tokens come immediately before z?

Keys: indent, dedent, before-z
Answer format: one value per key
Question 39 raw-string-end · number · 1 pt · 07-context-sensitive-lexing

C++ source: R"ab(x)a)" )ab" y. How many bytes long is the raw string literal token (from R to its closing quote)?

Answer format: a number
Question 40 lexer-hack · single · 1 pt · 07-context-sensitive-lexing

C: typedef int T; then, inside void g(int T) { T * a; }. What must the lexer hack classify T as, and how is the statement parsed?

  1. TYPE_NAME: a is declared as T *
  2. IDENTIFIER: the statement is a multiplication
  3. TYPE_NAME, and the declaration of a conflicts with the parameter
  4. The lexer cannot decide; the statement is ambiguous in C
Answer format: one letter
Question 41 llvm-keyword-status · mapping · 1 pt · 08-keyword-recognition

In clang/lib/Basic/IdentifierTable.cpp (LLVM 23.1.2):
function: the free function that decides whether a keyword is a keyword under the given LangOptions.
disabled: the enumerator it returns when the keyword is not a keyword in this language mode.

Keys: function, disabled
Answer format: one value per key
Question 42 keyword-choice · mapping · 1 pt · 08-keyword-recognition

Pick a keyword-recognition method for each case: hash (pre-interned in the identifier table), gperf (perfect hash), dfa (keywords compiled into the lexer DFA), length (switch on length).
clang: keywords depend on the language mode, and identifiers are interned anyway.
flex: a generated lexer from a rule file.
small: a hand-written lexer with 21 fixed keywords and no interning.
fixedset: a large fixed set of names checked in a C library, with no dynamic changes.

Keys: clang, flex, small, fixedset
Answer format: one value per key
Question 43 gperf-hash-value · mapping · 1 pt · 08-keyword-recognition

gperf's hash for Pebble's keywords is \(h(w) = \lvert w \rvert + a[w_2] + a[w_1]\) with \(a[\texttt{m}] = 15\), \(a[\texttt{u}] = 10\), \(a[\texttt{x}] = 5\) (among others); mut has \(h = 28\).
h: the hash of the identifier mux.
slot: the keyword stored in that slot.
rejected-by: what rejects mux (first-char or strcmp)?

Keys: h, slot, rejected-by
Answer format: one value per key
Question 44 trie-nodes · number · 1 pt · 08-keyword-recognition

How many nodes, including the root, does the trie of the keywords {if, in, int, fn, for} have?

Answer format: a number
Question 45 switch-length-compares · mapping · 1 pt · 08-keyword-recognition

Pebble's switch-on-length keyword lookup (lengths 2: as, fn, if, in; 3: for, int, let, mut, str, var; 4: bool, else, true; 5: break, false, float, while; 6: extern, return, struct; 8: continue). How many string comparisons does it make for each non-keyword identifier?

Keys: foo, x, whilex, go
Answer format: one value per key
Question 46 utf8-invalid-count · number · 1 pt · 09-unicode

How many U+FFFD replacement characters does a strict decoder that replaces each maximal subpart (Definition 1.9.4) produce for the bytes 61 E0 80 AF 62 F4 90 80 80 63 E2 82?

Answer format: a number
Question 47 llvm-utf8-length · mapping · 1 pt · 09-unicode

In llvm/lib/Support/ConvertUTF.cpp (LLVM 23.1.2), what does getNumBytesForUTF8 return for each first byte?

Keys: 0xF4, 0xF5, 0xC0, 0xFC
Answer format: one value per key
Question 48 xid-classes · mapping · 1 pt · 09-unicode

Classify each code point as start (XID_Start, hence also XID_Continue), continue (XID_Continue only) or neither.

Keys: U+00E9, U+0301, U+0663, U+2211, U+03C0
Answer format: one value per key
Question 49 unicode-policy · mapping · 1 pt · 09-unicode

Which policy does each language apply to non-ASCII identifiers? Answer nfc (UAX #31 identifiers, compared after NFC), nfkc (compared after NFKC), or ascii (identifiers must be ASCII; non-ASCII is diagnosed).
rust: Rust.
python: Python 3.
pebble: Pebble.

Keys: rust, python, pebble
Answer format: one value per key
Question 50 nfc-nfkc · mapping · 1 pt · 09-unicode

For each pair, are the two strings equal after normalization? Answer both, nfkc-only or neither.
e-acute: U+00E9 vs e + U+0301.
fi-lig: U+FB01 (fi) vs fi.
cyr-a: Latin a vs Cyrillic U+0430.
sup2: x² vs x2.
angstrom: U+212B ANGSTROM SIGN vs U+00C5.

Keys: e-acute, fi-lig, cyr-a, sup2, angstrom
Answer format: one value per key
Question 51 trivia-count · mapping · 1 pt · 10-lossless-and-incremental-lexing

Pebble source (⏎ is one newline byte): x /* a */ = 1 // c⏎;. Give LeadingTrivia of each token: x, eq (=), one (1), semi (;), eof.

Keys: x, eq, one, semi, eof
Answer format: one value per key
Question 52 roslyn-trailing · mapping · 1 pt · 10-lossless-and-incremental-lexing

Roslyn's rule (Definition 1.10.2): a token's trailing trivia runs up to and including the first line break; the rest is the next token's leading trivia. For a; // c⏎ b (⏎ = one newline byte), how many bytes are semi-trailing (after ;) and b-leading (before b)?

Keys: semi-trailing, b-leading
Answer format: one value per key
Question 53 trivia-tokens-count · number · 1 pt · 10-lossless-and-incremental-lexing

A lexer that returns trivia as tokens (like rustc_lexer: whitespace runs, line comments without their newline, and ordinary tokens) lexes let x = 1; // c⏎ (⏎ = one newline). How many tokens does it return (no eof)?

Answer format: a number
Question 54 llvm-keep-comments · text · 1 pt · 10-lossless-and-incremental-lexing

In clang/include/clang/Lex/Lexer.h (LLVM 23.1.2), which member function of Lexer reports whether comments should be returned as tokens?

Answer format: a short answer
Question 55 incremental-first-token · text · 1 pt · 10-lossless-and-incremental-lexing

Old Pebble source let a = b<c; (bytes 0–11). The edit inserts = at byte 10 (between < and c), giving b<=c. Using Definition 1.10.4 (lookahead extent = one past the last byte examined, including the byte that ended the token), which old token is the first affected token? Give its spelling.

Answer format: a short answer
Question 56 incremental-worst-case · single · 1 pt · 10-lossless-and-incremental-lexing

Why can a single one-byte edit force an incremental relexer to relex the rest of the file?

  1. It can open a comment or string, changing the lexer state at every later boundary so resynchronization never succeeds
  2. Token positions after the edit must all be shifted by Δ, which is a relex
  3. The lookahead extents of all tokens must be recomputed
  4. Incremental relexing is only correct for edits at the end of the file
Answer format: one letter