Flashcards — Chapter 1¶
116 cards. Review them with spaced repetition in the terminal (./course flash 1) or export them to Anki (./course flash export 1). Here, click a card to reveal its back.
regular-languages¶
What are the regular languages, in three equivalent ways?
The languages denoted by regular expressions (∅, ε, a, r|s, rs, r*), the languages accepted by DFAs, and those accepted by NFAs (Kleene's theorem, Theorem 1.1.13).
Name four closure properties of regular languages a lexer generator uses.
Union (rule lists), concatenation, star, and intersection/complement via the product construction on complete DFAs (Proposition 1.1.15).
Why are Pebble's nested block comments not regular?
The pumping lemma: pumping inside the run of opening '/*' of a comment nested p deep breaks the balance, so no finite automaton recognizes it (Corollary 1.1.17). Lexers use a depth counter.
Precondition for building the complement of L(A) by swapping final and non-final states?
A must be a complete DFA (every state has a transition on every symbol, a dead state added if needed); on an NFA or partial DFA the swap is wrong.
thompson¶
Thompson's construction: what does it produce and how big?
An ε-NFA with one start and one accept state per fragment, built by one case per regex operator; at most 2|r| states and O(|r|) edges, each state with ≤ 2 outgoing edges (Proposition 1.1.18).
Key invariant of a Thompson fragment?
Exactly one start state with no incoming edges and one accept state with no outgoing edges, so fragments compose without interference (Lemma 1.1.9).
Thompson NFA of (a|b)*abb in Dragon numbering: how many states, and E({0})?
11 states (0–10); E({0}) = {0, 1, 2, 4, 7}.
glushkov¶
What is the position (Glushkov) automaton of r?
An ε-free NFA with one state per symbol occurrence of r plus a start state (m + 1 states), with transitions given by First and Follow; final states Last (plus the start if r is nullable).
Which four functions define the position automaton?
Null(r), First(r), Last(r) and Follow(p), computed bottom-up over the regex (Definition 1.1.7); Follow of a starred subexpression adds First after each Last.
Cost of the position automaton compared with Thompson?
m + 1 states but up to O(m²) edges (Follow sets), versus Thompson's O(|r|) states and edges with ε-moves.
backtracking¶
How does a backtracking regex matcher work?
Depth-first search over the NFA's choices: at each alternation or quantifier try one branch, and on failure return and try the next (Algorithm 1.2.3).
Worst case of backtracking, and the classic example?
Exponential: (a?)ⁿaⁿ against aⁿ explores about 2ⁿ paths; std::regex takes 123 ms at n = 20 in the lab, the automaton engines under 0.5 ms.
Why do Perl/PCRE/std::regex still backtrack?
Backreferences and lookaround are not regular; backtracking supports them and gives leftmost-first submatches, at the price of the exponential worst case.
pike-vm¶
Thompson's NFA simulation: state and cost?
Keep the set of NFA states reachable after the prefix read so far; per byte, move then ε-close. O(m) per byte, O(nm) total, O(m) space (Algorithm 1.2.4).
What does a Pike VM add to plain NFA simulation?
Threads carry submatch positions, and threads are kept in priority order so the first thread to reach Match gives the leftmost-first match.
How does llvm::Regex store its state set?
As bits of one long (smatcher) when the program has at most CHAR_BIT*sizeof(long) states, else a char array (lmatcher); step() maps the set before a character to the set after it (regexec.c, regengine.inc).
subset-construction¶
Subset construction in one sentence.
Each DFA state is a set of NFA states: start from E({q0}), and for every state T and symbol class c add E(move(T, c)) until no new set appears (Rabin–Scott, Algorithm 1.2.5).
Invariant of the subset construction?
Every DFA state is Δ̂(w) for some word w, and δ_D(Δ̂(w), a) = Δ̂(wa); hence the DFA accepts exactly L(N) (Theorem 1.2.10).
Worst-case size of the subset DFA, and a family that reaches it?
2ⁿ states; (a|b)*a(a|b)^k needs 2^(k+1) states in its minimal DFA over {a, b} (one more, the dead state, over all bytes: 5, 9, 17, …), because it must remember the last k+1 symbols.
Subset DFA of (a|b)*abb (Dragon NFA): how many states before minimization?
Five: A..E, with E the only accepting state; minimization merges A and C, leaving 4.
lazy-dfa¶
What is a lazy DFA?
A subset construction done on demand during matching: states and transitions are created the first time the input reaches them and cached (Algorithm 1.2.6).
What does a lazy DFA do when its cache is full?
Flushes the cache and continues from the current state (RE2 also falls back to NFA simulation if it flushes too often); correctness is unaffected (Proposition 1.2.12).
Bound on states a lazy DFA creates on input w?
At most |w| + 1 per run, so it never pays for the exponential states the input does not visit; O(n) per byte when warm, O(nm) worst.
brzozowski-derivatives¶
Brzozowski derivative ∂_a r: definition by its language?
L(∂_a r) = { w | aw ∈ L(r) }: what is left to match after reading a (Definition 1.3.3).
Derivative of a concatenation rs?
∂_a(rs) = (∂_a r)s | ν(r)∂_a s, where ν(r) is ε if r is nullable and ∅ otherwise.
Why must derivatives be kept in similarity-normal form?
Only up to similarity (r|r = r, commutativity and associativity of |, ∅ and ε laws) are there finitely many derivatives (Theorem 1.3.12); without it the set grows (Proposition 1.3.15).
How does a derivative matcher decide w ∈ L(r)?
Take derivatives by each symbol of w in turn, then test nullability of the result: w ∈ L(r) iff ε ∈ L(∂_w r).
antimirov¶
Antimirov partial derivative: what is it?
A set of regexes whose union is the Brzozowski derivative, obtained by distributing over alternation instead of building it; the sets form an NFA (Definition 1.3.5).
Size bound of the partial-derivative automaton?
At most m + 1 states, m = number of symbol occurrences in r (Theorem 1.3.13): no exponential blow-up, unlike the derivative DFA.
Where do partial derivatives appear in production?
.NET's NonBacktracking regex engine uses them as an NFA fallback when its derivative-based lazy DFA grows too large.
derivative-lexers¶
How do Owens–Reppy–Turon build a lexer DFA with derivatives?
A state is a vector of regexes, one per rule; derive the whole vector per symbol class; a state accepts the first rule whose component is nullable (Algorithm 1.3.10).
What are derivative classes?
A partition of Σ such that symbols in the same class give the same derivative; computed from the regex without enumerating Σ, which keeps Unicode-sized alphabets tractable (Definition 1.3.6).
Which production tool is an ORT-style derivative lexer generator?
ml-ulex, SML/NJ's lexer generator (tools/ml-lpt/ml-ulex).
moore¶
Moore's algorithm in one sentence.
Start from the partition {F, Q∖F} (by accept tag for lexers) and split blocks whose states go to different blocks on some symbol, round by round until nothing changes (Algorithm 1.4.4).
What does round i of Moore's algorithm compute?
The partition into ~i classes: states indistinguishable by words of length ≤ i (Lemma 1.4.9); it stabilizes after at most n − 2 rounds.
Moore's worst-case complexity?
O(k n²): up to n rounds of O(kn) work each; in practice a few rounds (re2c uses it by default).
Myhill–Nerode theorem?
L is regular iff ≡_L has finitely many classes; the number of classes is the number of states of the minimal complete DFA, which is unique up to renaming (Theorems 1.4.7–1.4.8).
hopcroft¶
Hopcroft's minimization complexity and key trick?
O(k n log n): split blocks by splitters from a worklist, and when a block splits, only the smaller half needs to be added as a splitter (Algorithm 1.4.5).
Why is enqueueing only the smaller half correct?
If a block B was a splitter and splits into B1 and B2, splitting by B and B1 implies the split by B2 = B ∖ B1 (Lemma 1.4.11).
Why does 'smaller half' give n log n?
Each time a state is in an enqueued splitter its block at most halves, so each state is processed O(log n) times per symbol.
brzozowski-minimization¶
Brzozowski's minimization algorithm?
det(rev(det(rev(A)))): reverse, determinize, reverse, determinize; the result is the minimal DFA (Theorem 1.4.13).
Why does det∘rev minimize?
Determinizing the reverse of an automaton whose states are all reachable yields a DFA whose states are all distinguishable (co-reachability becomes distinguishability).
Pitfall when reversing for Brzozowski's method?
Start the subset construction from the SET of old final states; a fresh start state with ε-edges gives a DFA that is not minimal. Also: not tag-aware, so unsuitable for multi-rule lexers.
hand-written-lexer¶
Shape of a hand-written lexer?
A loop with a switch on the current byte; each case consumes the longest token starting with that byte using explicit lookahead, and returns one token per call (Algorithm 1.5.6).
Why do Clang, GCC, rustc, swiftc and V8 hand-write their lexers?
Context sensitivity (modes, feedback, special cases) and diagnostics/recovery, not speed: generated DFAs are nearly as fast.
Why keep a NUL sentinel after the buffer?
It removes the end-of-buffer test from inner loops; a NUL inside the file must still be diagnosed (Pebble: E0101).
table-driven¶
What does a table-driven DFA lexer store?
A class map κ from bytes to classes, a transition table T over states × classes, and an accept vector (Definition 1.5.2).
How does a comb vector look up T(q, c)?
next[base[q] + c] if check[base[q] + c] = q, else the default (or dead) state: the Dragon book's base/next/check compression.
Lab numbers: generated table lexer vs hand-written Pebble lexer?
135 states, built in about 2.5 ms; 93 MB/s vs 105 MB/s on a 6.9 MB program, with identical tokens.
direct-coded¶
What is a direct-coded DFA?
Each DFA state becomes a code label and each transition a goto (via a switch on the byte); no tables at run time (re2c; Definition 1.5.3).
Why can direct code be faster than tables?
No table load per byte, and the compiler can turn each state's switch into compares, jump tables or bit tests, keeping state in the program counter.
Which tool generates direct-coded lexers, and who uses it?
re2c (Bumbulis & Cowan 1993); PHP and Ninja lexers.
regex-combinators¶
How does a regex-combinator lexer work?
One big alternation of named regexes run by a backtracking engine at each position (Python's tokenize builds its pattern by string functions like group(), any(), maybe()).
What goes wrong with first-match alternation in combinator lexers?
The engine takes the first alternative that matches, not the longest: '=' listed before '==' lexes '==' as two tokens. Order the alternatives longest first.
Cost of a combinator lexer?
O(R n) or worse (R rules tried per position, backtracking inside each); the slowest style, but the least code.
simd-lexing¶
What does SIMD bulk classification compute?
For a 16/32/64-byte block, one bit mask per byte class via vector compares and movemask (Definition 1.5.5).
Mask formula for the starts of word runs?
starts = W & ~(W << 1) (plus a carry bit from the previous block), where W is the word-byte mask.
Where does Clang use SIMD in its lexer?
Skipping block-comment bodies (SSE2 compares against '/' in SkipBlockComment) and identifier characters (_mm_cmpistri in fastParseASCIIIdentifier).
maximal-munch¶
Maximal munch rule?
At each position take the longest prefix that is a token; with backup to the last accepting position when the DFA dies (Definition 1.6.2, Algorithm 1.6.5).
How does Clang lex a+++++b and why is it an error?
a ++ ++ + b by maximal munch; (a++)++ is not assignable, although a ++ + ++ b would parse.
Worst case of naive maximal munch?
Θ(n²) reads: rules a and a*b on aⁿ read n(n+1)/2 bytes (4 → 10, 8 → 36, 32 → 528) (Proposition 1.6.11).
rule-priority¶
Rule priority in lexer generators?
When several rules match the same longest prefix, the rule listed first wins (Definition 1.6.3): keywords before the identifier rule.
How is priority implemented in a DFA?
Each accepting DFA state is tagged with the smallest rule index among its accepting NFA states (Algorithm 1.6.6); minimization starts from a partition by tag.
How do generators detect dead rules?
A rule is unmatchable iff no reachable DFA state carries its tag (flex warns 'rule cannot be matched').
reps¶
What does Reps' algorithm memoize?
Failed (state, position) pairs: once the DFA in state q at position i is known not to reach an accepting state, later scans stop there (Algorithm 1.6.7).
Complexity of Reps' maximal munch?
O(|Q| n) time and space worst case, linear in the input for a fixed DFA (Proposition 1.6.12).
Does Reps' algorithm change the tokens?
No: same tokenization as maximal munch (Theorem 1.6.10), only fewer reads.
lexer-modes¶
What is a lexer mode?
A lexer state that changes which rules apply (flex start conditions); with a stack of modes the lexer recognizes nested structure (Definition 1.7.1).
Pebble interpolation stack: what happens at '(' and at ')'?
'(' pushes 0; '(' increments the top; ')' with top > 0 decrements it (r_paren); ')' with top 0 pops and resumes the string (string_middle or string_tail) (Algorithm 1.7.7).
Token kinds for "a(x)b(y)c"?
string_head "a(, identifier x, string_middle )b(, identifier y, string_tail )c".
regex-vs-division¶
Why can't a JavaScript lexer decide '/' alone?
Whether '/' starts a regex or is division depends on the syntactic context (ECMA-262's InputElementRegExp vs InputElementDiv goals), which the parser knows.
How does V8 handle a regex literal?
The parser, on seeing '/' where an expression can start, asks the scanner to rescan it as a regular expression literal.
Why does a 'previous token' heuristic fail for '/'?
After ')' both are possible: '(a) / b / g' is division, 'if (a) /b/g.test(s)' is a regex (Proposition 1.7.14).
template-angle-brackets¶
How does Clang handle '>>' closing two template argument lists?
The lexer produces greatergreater by maximal munch; Parser::ParseGreaterThanInTemplateList splits it (C++11); in C++98 it emits an error with a '> >' fix-it.
Which tokens does ParseGreaterThanInTemplateList accept and split?
'>', '>>', '>=', '>>=' (and '>>>' for CUDA kernel calls), splitting off one '>'.
Which C++ paper made '>>' close templates?
N1757 (Vandevoorde, 2005), adopted for C++11.
indent-dedent¶
How does Python produce INDENT/DEDENT?
A stack of indentation widths starting at 0; a deeper line pushes and emits INDENT; a shallower line pops, one DEDENT per pop, and must match an earlier width (Algorithm 1.7.10).
When does Python ignore indentation?
Inside brackets (parenthesis depth > 0) and on blank or comment-only lines.
Error when a dedent matches no enclosing level?
'unindent does not match any outer indentation level' (an IndentationError).
raw-strings¶
How does a C++ raw string end?
R"d( ... )d" ends at the first ')d"' with the same delimiter d (up to 16 characters); the lexer remembers d in a variable.
Why are delimited raw strings not regular (as a family)?
The closing delimiter must equal the opening one, an unbounded copy; for a fixed maximum length it is regular but huge. Lexers store the delimiter instead.
Rust raw strings?
r#"..."# with any number of '#'; ends at '"' followed by the same number of '#'. rustc_lexer reports RawStr { n_hashes }.
lexer-hack¶
What is the C lexer hack?
Feeding the symbol table back into the lexer so it returns TYPE_NAME for typedef names and IDENTIFIER otherwise; needed because 'T * a;' parses differently.
How does Clang avoid classic lexer feedback?
The lexer always returns identifier; the parser asks Sema (Parser::TryAnnotateTypeOrScopeToken) and replaces the token by an annot_typename token.
Constraint the lexer hack puts on the parser?
The parser must not look ahead past an identifier before the declarations preceding it are entered in the symbol table (bounded lookahead).
keyword-hash-table¶
How do Clang and rustc recognize keywords?
Keywords are pre-interned in the identifier table; lexing an identifier interns it and the entry already knows its token kind (Clang IdentifierTable, rustc symbol.rs).
How does Clang enable or disable keywords per language mode?
getKeywordStatus decides per keyword flag and LangOptions; KS_Disabled keywords are simply not added as keywords.
Why is the hash table nearly free for keywords?
The compiler hashes every identifier anyway to intern it; keyword recognition piggybacks on that one lookup.
perfect-hashing¶
What is a perfect hash for a keyword set K?
A hash function with no collisions on K; minimal if the table has exactly |K| slots (Definition 1.8.2).
Why must a perfect-hash lookup still compare strings?
A non-keyword can hash to a keyword's slot (fnord lands on float's slot); only the final strcmp makes it exact (Proposition 1.8.10).
gperf's hash shape?
len + asso_values[key[i]] for selected positions i (e.g. first and last characters), with the asso_values table found by search.
keyword-trie¶
What is a trie?
A tree whose edges are labelled by characters; each keyword is a root-to-node path with the node marked (Fredkin 1960; Definition 1.8.3).
How do flex and re2c recognize keywords?
The keyword rules become part of the lexer DFA (a trie merged with the identifier automaton); priority tags decide keyword vs identifier at no run-time cost.
Cost of a standalone trie lookup?
O(ℓ) character steps for an identifier of length ℓ, plus memory for the nodes (74 nodes for Pebble's 21 keywords including the root).
switch-on-length¶
Switch on length for keywords?
First switch on the identifier's length, then compare against the few keywords of that length (Algorithm 1.8.8); TableGen's StringMatcher generates this shape.
Pebble keyword counts by length?
2: 4 (as, fn, if, in); 3: 6; 4: 3; 5: 4; 6: 3; 8: 1. At most 6 comparisons after the switch.
Why does switch on length suit small fixed sets?
Most identifiers fail on length or first character, it needs no tables or build step, and the compiler turns it into jump tables and memcmp.
utf8¶
UTF-8 byte ranges of leading bytes?
00–7F: 1 byte; C2–DF: 2; E0–EF: 3; F0–F4: 4. C0, C1 and F5–FF never occur; continuation bytes are 80–BF.
Which second-byte restrictions does strict UTF-8 add?
E0: A0–BF (no overlongs); ED: 80–9F (no surrogates); F0: 90–BF; F4: 80–8F (≤ U+10FFFF) (Unicode Table 3-7).
Maximal subpart rule for ill-formed UTF-8?
Replace each maximal prefix of a well-formed sequence, or a single bad byte, by one U+FFFD: ED A0 80 gives three, C0 AF gives two (Definition 1.9.4).
Does llvm::getNumBytesForUTF8 validate?
No: it returns the length from the lead byte's table (0xF4 and 0xF5 both give 4); validation is isLegalUTF8Sequence / ConvertUTF's job.
xid-identifiers¶
UAX #31 default identifier syntax?
<XID_Start> <XID_Continue>*, where XID_Start ⊆ XID_Continue (letters, and marks/digits/connector punctuation in Continue) (Definition 1.9.5).
Is U+0301 COMBINING ACUTE ACCENT an identifier start?
No: it is XID_Continue but not XID_Start, so 'x\u0301' is an identifier but '\u0301x' is not.
What does Pebble do with 'café'?
One identifier token with one E0110 at 'é' (recovery via XID tables); a non-identifier character like '∑' is one unknown token with E0101.
unicode-normalization¶
NFC vs NFKC?
NFC composes canonically equivalent sequences (é = e + U+0301); NFKC also folds compatibility characters (fi → fi, superscripts, full-width letters).
Which normalization do Rust and Python apply to identifiers?
Rust: NFC. Python: NFKC (so the ligature fi in an identifier equals 'fi').
What is a confusable, and who warns about them?
A character that looks like another (Cyrillic а vs Latin a); rustc's lints mixed_script_confusables and confusable_idents use UTS #39 data.
trivia¶
What is trivia?
Whitespace and comments: bytes between tokens that the parser ignores but tools need.
Losslessness condition for a token stream with leading trivia?
Concatenating trivia bytes and spelling of every token, eof included, gives back the file exactly (Definition 1.10.1).
Roslyn's trivia rule?
Trailing trivia of a token runs up to and including the end of its line; everything after that is leading trivia of the next token.
trivia-tokens¶
Trivia as tokens: how does rustc_lexer do it?
It returns Whitespace, LineComment and BlockComment tokens like any other; the parser layer filters them.
Trade-off of trivia tokens vs attached trivia?
Trivia tokens keep the lexer uniform and give comments exact positions, but the parser needs a cursor that skips them; attached trivia hides them from the parser.
How does Clang keep comments when tools need them?
It keeps only StartOfLine/LeadingSpace flags normally; in keep-comment mode (inKeepCommentMode()) it returns comment tokens.
incremental-relexing¶
What is a token's lookahead extent?
How far past its end the lexer read to decide it; an edit inside a token or its lookahead extent can change it (Definition 1.10.4).
Where does incremental relexing start and stop?
Start at the first token whose span or lookahead reaches the edit; stop when a new token ends at an old token end shifted by Δ with the same lexer state (Algorithm 1.10.8).
Worst case of incremental relexing?
O(n): opening an unterminated comment or string changes every later token; typically d tokens are relexed with d tiny, O(d + log m) per edit.