Skip to content

Chapter 1 · Lexical Analysis

Part 1 · Front End · about 2–3 weeks · Previous: Ch 0 · Next: Ch 2

The problem

Given a source file as a sequence of bytes \(b_0 \cdots b_{N-1}\) and a lexical specification (a list of token classes, each a regular expression, plus the language's non-regular rules for comments, strings and layout), produce the sequence of tokens \(t_1 \cdots t_n\), each a kind, a source range and a decoded value, such that the tokens and the whitespace and comments between them cover the file exactly, and report every lexical error with a location while continuing to the end. The lexer is the first phase of every compiler pipeline (Ch 0); the parser (Ch 2–Ch 4) sees only its tokens, so the tokens decide what the grammar has to handle, and the locations decide the quality of every later diagnostic. This chapter covers the theory the specification rests on (regular languages, automata, derivatives, minimization), the ways to run it (NFA simulation, DFAs built ahead of time or lazily, generated tables or direct code, hand-written loops, combinators, SIMD), the disambiguation rules, the parts no regular expression can express (modes, feedback from the parser, indentation, raw strings), keyword recognition, Unicode, and the lossless and incremental lexing that IDEs need. pebblec's lexer is hand-written, on demand, lossless, with a mode stack for string interpolation.

What you will be able to do

  • Prove that a construct is not regular (nested comments, balanced interpolation) with the pumping lemma, and use the closure properties to build lexer automata by product and complement.
  • Trace Thompson's construction, ε-closure, the Pike VM and the subset construction by hand on a 10-state NFA, and compute Brzozowski derivatives until the derivative DFA closes.
  • Minimize a DFA with Moore's, Hopcroft's and Brzozowski's algorithms, and prove with the Myhill–Nerode theorem that the result is minimal and unique.
  • Choose between a hand-written loop, flex-style tables, re2c-style direct code, combinators and SIMD classification for a given language, and justify the choice with measured numbers.
  • Apply maximal munch and rule priority to any input, explain why naive munch is quadratic in the worst case, and trace Reps' linear-time fix.
  • Design the lexer state for string interpolation, JavaScript's /, C++'s >>, Python's INDENT/DEDENT, raw strings and C's typedef names.
  • Implement the Pebble lexer (keywords, maximal munch, literals with values, nested comments, interpolation, UTF-8 and UAX #31 diagnostics, lossless trivia) and pass ./course test 1; build four regex engines and a generated lexer in the comparison lab.
  • Find where Clang, LLVM, GCC, rustc and RE2 implement each technique and read the code.

Prerequisites: none from earlier chapters beyond Ch 0's tour of the toolchain. You need sets and induction, and comfortable C++ (for the lab, C++23 std::expected). The regular languages and automata of this chapter reappear as LL(*) lookahead DFAs in Ch 2, as LR automata in Ch 3, and least fixed points (ε-closure, nullability) are generalized in Ch 14.

Notation

Shared notation follows the house notation (§1 sets and functions, §5 grammars and parsing, §8 complexity, §9 numbered statements). In this chapter:

Symbol Meaning
\(\Sigma\), \(\Sigma^{*}\), \(\varepsilon\), \(w\), \(\lvert w \rvert\) the alphabet (bytes, or a small alphabet like \(\{a, b\}\) in examples), all words, the empty word, a word and its length (Definition 1.1.1)
\(r, s\); \(L(r)\); \(\emptyset\), \(a\), \(r \mid s\), \(rs\), \(r^{*}\) regular expressions, their languages, and the constructors (Definition 1.1.2); r+, r?, r{m,n}, [...] are abbreviations
\(\lvert r \rvert\), \(m\) the size of \(r\) (constructor nodes); the number of symbol occurrences (positions) of \(r\) (Definition 1.1.7)
\(A = (Q, \Sigma, \delta, q_0, F)\), \(\hat\delta\) a DFA, its transition function extended to words (Definition 1.1.3)
\(N = (Q, \Sigma, \Delta, q_0, F)\), \(E(S)\), \(\mathrm{move}(S, a)\), \(\hat\Delta(w)\) an ε-NFA, the ε-closure of \(S \subseteq Q\), the symbol step, and the set of states reached on \(w\) (Definition 1.1.4)
\(\mathrm{Null}\), \(\mathrm{First}\), \(\mathrm{Last}\), \(\mathrm{Follow}\) the position-automaton functions (Definition 1.1.7)
\(\nu(r)\), \(\partial_a r\), \(\partial_w r\) nullability (\(\varepsilon\) or \(\emptyset\)) and the Brzozowski derivative by a symbol and by a word (Definitions 1.3.2–1.3.3)
\(\approx\), \(\mathrm{pd}_a(r)\) similarity of regular expressions (Definition 1.3.4); Antimirov's partial derivatives, a set (Definition 1.3.5)
\(\equiv_L\), \(\sim\), \(\sim_k\) the Nerode equivalence of a language; state equivalence and \(k\)-equivalence of a DFA (Definitions 1.4.1–1.4.2)
\(P\), \(\mathrm{pre}_a(S)\), \(\mathrm{rev}(A)\) a partition of \(Q\) into blocks; the states with an \(a\)-edge into \(S\); the reversed automaton (Definition 1.4.3, Algorithm 1.4.6)
\(n\), \(k\) the number of DFA states and of symbol classes when minimizing (Lesson 1.4); elsewhere \(n\) is the input length in bytes, as stated in each lesson
\(\kappa\), \(T\), \(\mathit{acc}\); \(\mathit{base}, \mathit{next}, \mathit{check}\) the class map, transition table and accept vector of a table-driven DFA; the comb-vector arrays (Definition 1.5.2)
\(M_C\) the bit mask of the bytes of a block in class \(C\) (Definition 1.5.5)
\(\mathrm{MM}(w)\), \(\mathrm{kind}\) the maximal-munch tokenization of \(w\) and the token kind chosen by rule priority (Definitions 1.6.2–1.6.3)
\(h\) the depth of the lexer's mode stack (open interpolations, indentation levels) (Lesson 1.7)
\(\mathrm{kw}(s)\) the keyword kind of a spelling \(s\), or "identifier" (Definition 1.8.1)
U+XXXX, \(\mathrm{enc}(c)\) a Unicode scalar value; its UTF-8 encoding (Definitions 1.9.1–1.9.2)
trivia, \(\mathrm{LT}(t)\) whitespace and comment bytes; the leading-trivia count of token \(t\) (Definition 1.10.1)

Numbered statements are Definition/Theorem/Lemma/Algorithm 1.k.m: chapter 1, lesson \(k\), one counter per lesson.

Technique map

Family Techniques (origin) Lesson
Regular languages and regex → NFA regular expressions and Kleene's theorem (Kleene 1956 [Kle56]), closure properties and the pumping lemma (Rabin & Scott 1959 [RS59]; [HMU07 §4]), Thompson's construction (McNaughton & Yamada 1960; Thompson 1968 [MY60, Tho68]), the position automaton (Glushkov 1961; McNaughton & Yamada 1960; Berry & Sethi 1986 [Glu61, MY60, BS86]) 1.1
Running automata backtracking search (Spencer's and Perl-style engines; worst case analysed by Cox 2007 [Cox07]), Thompson's NFA simulation (Thompson 1968 [Tho68]) and the Pike VM (Pike 1987; Cox 2009 [Pik87, Cox09]), the subset construction (Rabin & Scott 1959 [RS59]), the lazy DFA (Thompson 1968; Aho 1990; RE2, Cox 2010 [Tho68, Aho90, Cox10]) 1.2
Derivatives Brzozowski derivatives (Brzozowski 1964 [Brz64]), Antimirov partial derivatives (Antimirov 1996 [Ant96]), derivative-based lexer generators with derivative classes (Owens, Reppy & Turon 2009 [ORT09]) 1.3
DFA minimization the Myhill–Nerode theorem (Myhill 1957; Nerode 1958 [HMU07 §4.4]), Moore's partition refinement (Moore 1956 [Moo56]), Hopcroft's \(O(kn \log n)\) algorithm (Hopcroft 1971; Gries 1973; Knuutila 2001 [Hop71, Gri73, Knu01]), Brzozowski's double reversal (Brzozowski 1962 [Brz62]) 1.4
Lexer implementation styles the hand-written switch loop (Clang, GCC, rustc, swiftc [CLANG-Lexer, GCC-Lex, RUSTC-Lexer, SWIFT-Lexer]), the table-driven DFA with comb-vector compression (lex 1975, flex [FLEX-Manual]; [Dragon2 §3.9.8]), the direct-coded DFA (re2c, Bumbulis & Cowan 1993 [BC93]), regex combinators (Python's tokenize [CPYTHON-Tokenize]), SIMD bulk classification (Langdale & Lemire 2019 [LL19]) 1.5
Disambiguation maximal munch (longest match; [Dragon2 §3.3]), rule priority (first rule wins; lex/flex [FLEX-Manual]), Reps' linear-time memoized munch (Reps 1998 [Rep98]) 1.6
Context-sensitive lexing lexer modes and start conditions with a stack (flex %x, yy_push_state [FLEX-Manual]; interpolation in Swift, Kotlin, Pebble), JavaScript's / as regex or division by lexical goal (ECMA-262 [ECMA262]), C++ >> split in the parser (Vandevoorde, N1757, 2005 [N1757]), Python's INDENT/DEDENT (Python reference [PY-Lexical]), delimited raw strings (C++11, Rust), the C typedef "lexer hack" (feedback from the symbol table; Clang's parser-side annotation [CLANG-Parser]) 1.7
Keyword recognition hash table with pre-interned keywords (Clang, rustc [CLANG-IdentifierTable, RUSTC-Symbol]), perfect hashing (Cichelli 1980; Fredman, Komlós & Szemerédi 1984; gperf, Schmidt 1990 [Cic80, FKS84, Sch90]), tries and keywords in the DFA (Fredkin 1960 [Fre60]), switch on length (TableGen's StringMatcher [LLVM-StringMatcher]) 1.8
Unicode strict UTF-8 decoding with maximal-subpart recovery (Pike & Thompson 1992; RFC 3629; Unicode §3.9 [RFC3629, Unicode16]; Höhrmann 2010; Keiser & Lemire 2021 [Hoe10, KL21]), identifier syntax by UAX #31 (XID_Start/XID_Continue [UAX31]; C++23 via P1949 [P1949]), normalization NFC/NFKC and confusables (UAX #15 [UAX15]) 1.9
Lossless and incremental lexing tokens with attached trivia (Roslyn, SwiftSyntax [ROSLYN-Lexer, SWIFTSYNTAX-Trivia]), trivia as tokens (rustc_lexer, rust-analyzer [RUSTC-Lexer, RA-LexedStr]), incremental relexing with lookahead extents (Wagner & Graham 1998; tree-sitter [WG98, TS-Parser]) 1.10 
flowchart LR
  RE["Regular expressions<br/>Kleene 1956"] -->|syntax-directed| TH["Thompson NFA<br/>MY 1960, Thompson 1968"]
  RE -->|one state per position| GL["Position automaton<br/>Glushkov 1961"]
  RE -->|residual languages| BD["Brzozowski derivatives<br/>1964"]
  BD -->|sets of summands| AN["Antimirov partial derivatives<br/>1996"]
  BD -->|vectors + classes| ORT["ORT lexer generators<br/>2009"]
  TH -->|breadth-first| PV["NFA simulation / Pike VM<br/>O(nm)"]
  TH -->|depth-first| BT["Backtracking<br/>exponential"]
  TH -->|all subsets ahead of time| SC["Subset construction<br/>Rabin-Scott 1959"]
  SC -->|only reached states, cached| LZ["Lazy DFA<br/>RE2, grep"]
  SC --> MIN["Minimization:<br/>Moore 1956, Hopcroft 1971,<br/>Brzozowski 1962"]
  MN["Myhill-Nerode"] -.proves.-> MIN
  MIN --> TAB["Table-driven lexer<br/>lex/flex"]
  MIN --> DC["Direct-coded lexer<br/>re2c"]
  TAB --- MM["Maximal munch + priority;<br/>Reps 1998 linear"]
  DC --- MM
  HW["Hand-written switch loop<br/>Clang, rustc, Pebble"] --- MM
  HW -->|stack in the lexer| MODES["Modes, interpolation,<br/>INDENT/DEDENT, raw strings"]
  HW -->|parser feedback| FB["JS regex vs /, C++ >>,<br/>lexer hack"]
  HW --> KW["Keywords: hash, gperf,<br/>trie, switch on length"]
  HW --> UNI["UTF-8, UAX #31,<br/>normalization"]
  HW --> LOSS["Trivia: lossless tokens"]
  LOSS -->|resynchronize| INC["Incremental relexing<br/>Wagner-Graham, tree-sitter"]
  SIMD["SIMD classification<br/>simdjson 2019"] -->|fast paths| HW

Who uses what

System Technique Notes
Clang / LLVM 23.1.2 hand-written switch loop with explicit lookahead; keywords pre-interned in IdentifierTable with per-language status; SIMD fast paths for comments and identifiers; >> split in the parser; typedef names by parser annotation; flags instead of trivia; llvm::Regex is an NFA simulation with a backtracking fallback; TableGen matches strings by switch on length and builds DFAs by subset construction 1.2, 1.4, 1.5, 1.7, 1.8, 1.9, 1.10
GCC 15.1 (libcpp, C++ front end) hand-written lexer (_cpp_lex_direct); keywords pre-entered in the identifier hash table (init_reswords); gperf tables for fixed name sets (cfns.gperf); SSE2/SSSE3 line scanning 1.5, 1.8
rustc 1.94 rustc_lexer: hand-written, trivia as tokens, raw strings with # counts; pre-interned keyword symbols; NFC identifiers and confusable lints 1.7, 1.8, 1.9, 1.10
swiftc 6.1 / SwiftSyntax hand-written lexer with interpolation modes; lossless trivia pieces 1.7, 1.10
V8 12.9 hand-written scanner; the parser asks for a regex rescan after / in expression position 1.7
CPython 3.13 C tokenizer with an indentation stack (INDENT/DEDENT); Lib/tokenize.py built from regex combinators; NFKC identifiers 1.5, 1.7, 1.9
Roslyn (C#) leading and trailing trivia attached to tokens 1.10
tree-sitter 0.25 generated lexers; incremental relexing with lookahead extents 1.10
flex 2.6.4 subset construction, table compression (comb vectors), start conditions with a stack 1.2, 1.5, 1.7
re2c 3.1 direct-coded DFAs; Moore/table-filling minimization; keywords compiled into the DFA 1.4, 1.5, 1.8
RE2, Go regexp, Rust regex Thompson compilation, Pike VM for submatches, lazy DFA for search; Hopcroft minimization in regex-automata 1.1, 1.2, 1.4
GNU grep (gnulib dfa.c) position automaton and a lazily built DFA 1.1, 1.2
.NET 8 RegexOptions.NonBacktracking Brzozowski derivatives (lazy DFA) with an Antimirov NFA fallback 1.3
ml-ulex (SML/NJ) derivative-based lexer generator with derivative classes 1.3
simdjson 3.10 SIMD bulk classification of structural characters 1.5
pebblec hand-written switch loop, switch-on-length keywords, maximal munch, interpolation mode stack, nested comments, strict UTF-8 with UAX #31 diagnostics, leading-trivia counts all; exercises E1–E5

Comparison

Technique Power / precision Speed Output / error quality Implementation effort Typical use
Regular expressions (+ closure constructions) exactly the regular languages; no nesting, no counting product: \(O(\lvert Q_1\rvert\lvert Q_2\rvert\lvert\Sigma\rvert)\) declarative; errors are "no match" a parser for the syntax specifying tokens; RE2/Go/grep patterns
Thompson (MYT) any regex → ε-NFA \(\Theta(\lvert r\rvert)\) build; ≤ \(2\lvert r\rvert\) states keeps the regex's structure (good for submatches) small (one case per operator) front end of NFA simulators, lazy DFAs, lexer generators
Position (Glushkov) any regex → ε-free NFA with \(m+1\) states \(O(m^{2})\) build and edges states = symbol occurrences (easy to relate to the pattern) moderate (Null/First/Last/Follow) direct DFA construction (grep, Dragon §3.9), bit-parallel matchers
Backtracking regular + backreferences, lookaround \(O(n)\) typical, \(\Omega(2^{n})\) worst leftmost-first submatches; no "how far did it get" small Perl, PCRE, Python re, std::regex
Thompson simulation / Pike VM any regex; submatches with threads \(O(nm)\) always submatches, leftmost-first or -longest small–moderate RE2/Go/Rust fallback, LLVM Regex, submatch extraction
Subset construction (+ DFA run) any regex; no submatches without tags \(O(n)\), one lookup per byte accept/reject and longest match only moderate (+ minimization, tables) lexer generators (flex, re2c), ahead-of-time DFAs
Lazy DFA any regex; no submatches \(O(n)\) when warm, \(O(nm)\) worst as DFA moderate (+ cache management) grep, RE2, Rust regex for search
Brzozowski derivatives any regex, plus \(\&\) and \(\neg\) for free \(O(n)\) memoized; DFA as small or smaller than subset construction states are readable expressions ("what is left to match") small: one function per operator + smart constructors lazy matching (.NET NonBacktracking), teaching, extended regexes
Antimirov partial derivatives any regex NFA simulation, \(\le m + 1\) states states are expression suffixes small NFA fallback (.NET), submatching research
ORT derivative lexer generators lexer specifications with priority \(O(n)\) DFA; build proportional to states × classes DFA states map back to rule suffixes moderate (vectors, classes, codegen) ml-ulex (SML/NJ)
Moore exact minimum (Theorem 1.4.10); tag-aware \(O(kn^{2})\) worst, few rounds in practice partition per round (easy to debug) small re2c default, quick tools
Hopcroft exact minimum; tag-aware \(O(kn\log n)\) worst – moderate (worklist, block lists) automata libraries, regex-automata, the lab's default
Brzozowski exact minimum; works on NFAs; not tag-aware \(O(k\,2^{n})\) worst intermediate – tiny if you have a subset construction libraries (dk.brics), teaching, NFA inputs
Hand-written switch loop anything (counters, modes, context) fastest in practice; 104 MB/s in the lab best: custom diagnostics and recovery high, and the code must be kept in sync with the spec Clang, GCC, rustc, swiftc, V8, Pebble
Table-driven DFA (flex) regular rules + start conditions + actions one table lookup per byte; 90 MB/s in the lab generic ("unexpected character") unless actions add more low (write rules) tools, DSLs, older compilers, teaching
Direct-coded DFA (re2c) regular rules + conditions as fast as hand-written as flex low PHP, Ninja, performance-sensitive DSLs
Regex combinators regular (+ backreferences with backtracking engines) slowest; \(O(Rn)\) or worse poor positions unless the library tracks them lowest scripts, prototypes, Python's tokenize
SIMD / bulk classification classification only; needs a second stage 16–64 bytes per instruction none by itself high, platform-specific fast paths in Clang/GCC, JSON/CSV parsers
Maximal munch deterministic; may miss a valid tokenization \(O(n)\) with bounded backup, \(\Theta(n^{2})\) worst predictable for programmers; errors surface in the parser (a+++++b) trivial on a DFA every lexer
Rule priority resolves equal-length ties free at run time generators can warn about dead rules trivial keywords vs identifiers
Reps' memoized munch same tokens as maximal munch \(O(\lvert Q \rvert n)\) worst same small (a failure table) theory; tools that accept arbitrary rule sets
Lexer modes and start conditions nested structure via a stack (pushdown) \(O(n)\), \(O(h)\) space good: the lexer knows where an interpolation started small–moderate string interpolation, heredocs, nested comments
JavaScript regex vs division exact with parser direction \(O(n)\) exact; heuristics mis-lex rare cases lexer–parser coupling JavaScript, Ruby (/), Perl
C++ >> in templates exact \(O(1)\) per split fix-its possible (Clang's C++98 message) small, in the parser C++, Java, C# generics
Python INDENT/DEDENT layout as tokens \(O(n)\), \(O(h)\) precise "unindent does not match" errors small Python, F# light syntax, YAML
Raw strings delimiter memory in a variable \(O(n)\) (\(O(nD)\) naive) "unterminated raw string" with the delimiter small C++, Rust, Python
C typedef lexer hack exact with feedback \(O(n)\) lookups depends on parser lookahead discipline coupling to the symbol table C (and C++ via parser annotation)
Hash table with pre-interned keywords exact; any set, changeable at run time (language modes) one hash per identifier, shared with interning – small (the table exists anyway) Clang, rustc, most compilers
Perfect hashing (gperf) exact for a fixed set one hash + one strcmp – a build step GCC, interpreters, protocol parsers
Tries and keywords in the DFA exact free inside a generated lexer; \(O(\ell)\) standalone – none with a generator flex, re2c, ml-ulex lexers
Switch on length exact for a fixed set very fast for small sets – trivial Pebble, TableGen-generated matchers
UTF-8 decoding (strict) rejects every ill-formed sequence \(O(1)\) per character; ASCII fast path can name the offending byte and recover per maximal subpart small (Table 3-7) every lexer that reads UTF-8
Identifier syntax (UAX #31) standard, stable identifier sets \(O(\log R)\) per non-ASCII char "character X not allowed in an identifier" table generation from the UCD C++23, Rust, Swift, Python, Pebble diagnostics
Normalization and confusables identifies equivalent spellings; flags look-alikes normalization only when needed (quick check) lints with code points (rustc) large tables; use a library Rust (NFC), Python (NFKC), rustc lints
Tokens with attached trivia lossless; trivia owned by tokens no overhead in lexing tools see comments next to their tokens small (count) to moderate (structured pieces) Roslyn, SwiftSyntax, Pebble
Trivia as tokens lossless; uniform token stream slightly more tokens; parser skips them exact positions of every comment small in the lexer, a skipping cursor in the parser rustc_lexer, rust-analyzer, the lab's table lexer
Incremental relexing exact (Theorem 1.10.10) \(O(d + \log m)\) per edit, \(d\) usually tiny same tokens as a full relex high (states, extents, resync) tree-sitter, IDEs, editors

Comparison-lab results on the course's CI container (reproduce with build/<preset>/bin/ch01-regexbench; the numbers vary by a factor of about 1.5 between runs and machines): matching [a-z_][a-z0-9_]* against 200 000 lines (1.8 MB) takes 4.1 ms with the minimized DFA, 7.4 ms with the lazy DFA, 13 ms with derivatives, 105 ms with the Pike VM and 32 ms with std::regex; on (a?){20}a{20} against \(a^{20}\), std::regex needs 123 ms per match and every automaton engine under 0.5 ms; the minimal DFA of (a|b)*a(a|b){12} has 8193 states (Hopcroft 25 ms, Moore 36 ms, Brzozowski 30 ms); and on a 6.9 MB Pebble program the generated 135-state table lexer runs at 93 MB/s against 105 MB/s for the hand-written lexer, with identical tokens (ch01.TableLexer.AgreesWithTheHandWrittenPebbleLexer).

Route through this chapter

Step What Techniques How it is exercised
1 Lesson 1.1 regular languages, closure, pumping; Thompson; position automaton drill epsilon-closure; quiz; lab L1
2 Lesson 1.2 backtracking, Pike VM, subset construction, lazy DFA drills epsilon-closure, subset-construction; lab L2, L3, L6 ★
3 Lesson 1.3 Brzozowski, Antimirov, ORT drill brzozowski-derivative; lab L4
4 Lesson 1.4 Myhill–Nerode; Moore, Hopcroft, Brzozowski drill dfa-minimize; lab L5
5 Lesson 1.5 switch loop, tables, direct code, combinators, SIMD Pebble uses the switch loop: E1; lab L7 ★ (tables); direct code, combinators, SIMD are theory + real-world boxes
6 Lesson 1.6 maximal munch, priority, Reps drill maximal-munch; E2; lab L7 ★
7 Lesson 1.7 modes, JS /, C++ >>, INDENT/DEDENT, raw strings, lexer hack drill lexer-modes; E4 (Pebble's interpolation stack and nested comments); the rest theory + quiz
8 Lesson 1.8 hash table, gperf, trie, switch on length E1 (any method; the reference switches on length); quiz computations
9 Lesson 1.9 UTF-8, UAX #31, normalization drill utf8; E5
10 Lesson 1.10 attached trivia, trivia tokens, incremental relexing E5 (trivia counts, CorpusIsLossless); lab L7 ★ returns trivia tokens; incremental relexing is theory + quiz
11 Exercises E1–E5 and the lab spec labs/ch01-regex/SPEC.md the Pebble lexer (pebble/lib/Lex/src/, switch lexer); four regex back ends, three minimizers and a generated lexer behind include/regexlab/Regex.h (labs/ch01-regex/src/, switch regex) ./course test 1; ch01-regexbench
12 Theory test all ./course quiz 1 (≥ 80 % to finish)

Practice and check

./course drill epsilon-closure --difficulty easy   # warm up; --solution shows the construction
./course drill subset-construction                 # DFA states A, B, C, ... as sets
./course drill brzozowski-derivative               # derivatives in similarity-normal form
./course drill dfa-minimize --difficulty medium    # Moore rounds; --solution traces Hopcroft
./course drill maximal-munch --difficulty hard     # tokens, priority, naive read counts
./course drill lexer-modes                         # Pebble interpolation stack and nested comments
./course drill utf8                                # encode, decode, count maximal subparts
./course flash 1                                   # daily, a few minutes
./course quiz 1                                    # after the lessons
./course test 1                                    # after the exercises and the lab
build/linux/bin/ch01-lexdump --trivia tests/ch01/Inputs/fib.pbl   # your lexer on any file
build/linux/bin/ch01-regex --min-dfa '(a|b)*abb'                  # your lab on any pattern

References

The chapter's annotated bibliography (papers, textbook sections, pinned source files and docs) is in references.md. Start with: [Dragon2 §3] (the classical presentation of lexing, Thompson, subset construction and table compression that Lessons 1.1–1.5 follow), [HMU07 §2–4] (regular languages, the pumping lemma and Myhill–Nerode with full proofs), [Cox07] and [Cox09] (the clearest account of why automaton engines beat backtracking, and of the Pike VM), [ORT09] (derivatives made practical for lexer generators), and [EaC3 ch. 2] (an engineering-first alternative with hand-coded and table-driven scanners side by side).