Skip to content

References — Chapter 1 · Lexical Analysis

Every source this chapter cites, grouped by kind. Lessons cite entries inline as [KEY]; each entry says why and when to read it. Core reading marks the entries the chapter assumes you will open.

Foundational and research papers

  • [Ant96] Valentin Antimirov. Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science 155(2), pp. 291–319, 1996. doi:10.1016/0304-3975(95)00182-4
    Why and when: Partial derivatives and the partial-derivative automaton with at most (positions + 1) states (Theorem 1.3.13). Read §2–3 after Lesson 1.3; the rest treats proofs of regular-expression inequalities.
    Cited in: overview, 03-derivatives

  • [BC93] Peter Bumbulis and Donald D. Cowan. RE2C: a more versatile scanner generator. ACM Letters on Programming Languages and Systems 2(1–4), pp. 70–84, 1993. doi:10.1145/176454.176487
    Why and when: The origin of re2c and of generating DFAs as direct code instead of tables (Algorithm 1.5.8), with measurements against flex. Read after Lesson 1.5 §2.
    Note: ACM journal article.
    Cited in: overview, 05-lexer-implementation-styles

  • [Brz62] Janusz A. Brzozowski. Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata, Polytechnic Institute of Brooklyn Symposia Series 12, pp. 529–561, 1962.
    Why and when: The origin of minimization by double reversal (Algorithm 1.4.6, Theorem 1.4.13). Hard to obtain; the proof in Lesson 1.4 §4 is complete, so read this only for the history.
    Note: Symposium proceedings (Polytechnic Press); no DOI. The double-reversal theorem is usually cited from here.
    Cited in: overview, 04-dfa-minimization

  • [Brz64] Janusz A. Brzozowski. Derivatives of regular expressions. Journal of the ACM 11(4), pp. 481–494, 1964. doi:10.1145/321239.321249
    Why and when: Core reading. Defines the derivative of a regular expression and proves that dissimilar derivatives are finitely many (Theorem 1.3.12, his Theorem 5.2). Read §2–5 alongside Lesson 1.3 §2 and §4.
    Cited in: overview, 03-derivatives

  • [BS86] Gérard Berry and Ravi Sethi. From regular expressions to deterministic automata. Theoretical Computer Science 48, pp. 117–126, 1986. doi:10.1016/0304-3975(86)90088-5
    Why and when: Derives the position automaton (Glushkov/McNaughton–Yamada) from derivatives of linearized expressions and proves the local-language characterization of Lemma 1.1.11. Short; read after Lesson 1.3.
    Cited in: overview, 01-regular-languages-and-thompson

  • [Cic80] Richard J. Cichelli. Minimal perfect hash functions made simple. Communications of the ACM 23(1), pp. 17–19, 1980. doi:10.1145/358808.358813
    Why and when: Minimal perfect hashing of Pascal's reserved words from length, first and last letter, by backtracking search: the ancestor of gperf (Algorithm 1.8.6). Three pages; read after Lesson 1.8 §2.
    Cited in: overview, 08-keyword-recognition

  • [CZ02] Jean-Marc Champarnaud and Djelloul Ziadi. Canonical derivatives, partial derivatives and finite automaton constructions. Theoretical Computer Science 289(1), pp. 137–163, 2002.
    Why and when: Shows that the partial-derivative automaton is a quotient of the position automaton, the relation stated in Lesson 1.3 §6. Optional, for readers who want the connection proved.
    Note: Elsevier journal article.

  • [FKS84] Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with O(1) worst case access time. Journal of the ACM 31(3), pp. 538–544, 1984. doi:10.1145/828.1884
    Why and when: Two-level perfect hashing with O(1) worst-case lookups for arbitrary static sets: the theoretical counterpart of gperf, mentioned in Lesson 1.8 §6. Optional.
    Cited in: overview, 08-keyword-recognition

  • [Fre60] Edward Fredkin. Trie memory. Communications of the ACM 3(9), pp. 490–499, 1960. doi:10.1145/367390.367400
    Why and when: Names and introduces the trie (Definition 1.8.3). Historical; Lesson 1.8 §2 is all you need to implement keyword tries.
    Cited in: overview, 08-keyword-recognition

  • [Glu61] Victor M. Glushkov. The abstract theory of automata. Russian Mathematical Surveys 16(5), pp. 1–53, 1961.
    Why and when: The other origin of the position ("Glushkov") automaton of Lesson 1.1: states are the symbol occurrences of the expression, no ε-edges. Only the construction section is needed; the paper is a broad survey of automata theory as of 1961.
    Note: English translation of the 1961 Uspekhi Mat. Nauk article.
    Cited in: overview, 01-regular-languages-and-thompson

  • [Gri73] David Gries. Describing an algorithm by Hopcroft. Acta Informatica 2(2), pp. 97–109, 1973. doi:10.1007/BF00264025
    Why and when: A structured re-derivation of Hopcroft's algorithm with a careful correctness proof; the best companion to Lesson 1.4 §4 (Lemma 1.4.11) if the proof sketch there feels too quick.
    Note: Springer journal article.
    Cited in: overview, 04-dfa-minimization

  • [Hop71] John E. Hopcroft. An n log n algorithm for minimizing states in a finite automaton. Theory of Machines and Computations (Z. Kohavi, A. Paz, eds.), Academic Press, pp. 189–196, 1971.
    Why and when: Core reading. The O(kn log n) minimization algorithm (Algorithm 1.4.5). The original is terse; read [Knu01] or [Gri73] for the proof and come back here for the "smaller half" idea.
    Note: Conference proceedings chapter; also Stanford report STAN-CS-71-190.
    Cited in: overview, 04-dfa-minimization

  • [KL21] John Keiser and Daniel Lemire. Validating UTF-8 in less than one instruction per byte. Software—Practice and Experience 51(5), pp. 950–964, 2021. doi:10.1002/spe.2920
    Why and when: SIMD UTF-8 validation with nibble lookups, the fast version of Algorithm 1.9.8. Read after Lesson 1.9 if you want to vectorize the decoder.
    Note: Wiley journal article; preprint arXiv:2010.03090.
    Cited in: overview, 09-unicode

  • [Kle56] Stephen C. Kleene. Representation of events in nerve nets and finite automata. Automata Studies (C. E. Shannon, J. McCarthy, eds.), Annals of Mathematics Studies 34, Princeton University Press, pp. 3–41, 1956.
    Why and when: Core reading. The origin of regular expressions ("regular events") and of the theorem that they describe exactly what finite automata recognize (Theorem 1.1.13). Historical reading after Lesson 1.1; the modern proof in [HMU07 §3.2] is easier to follow than the original notation.
    Note: Based on RAND memorandum RM-704 (1951). Reprinted in the De Gruyter edition of Automata Studies.
    Cited in: overview, 01-regular-languages-and-thompson

  • [Knu01] Timo Knuutila. Re-describing an algorithm by Hopcroft. Theoretical Computer Science 250(1–2), pp. 333–363, 2001. doi:10.1016/S0304-3975(99)00150-4
    Why and when: Modern invariants and the complete O(kn log n) accounting for Hopcroft's algorithm (Theorem 1.4.12 and Proposition 1.4.15 cite it). Read §4–5 after Lesson 1.4.
    Note: Elsevier journal article.
    Cited in: overview, 04-dfa-minimization

  • [LL19] Geoff Langdale and Daniel Lemire. Parsing gigabytes of JSON per second. The VLDB Journal 28(6), pp. 941–960, 2019. doi:10.1007/s00778-019-00578-5
    Why and when: simdjson's two-stage design: SIMD classification of structural characters and string regions (Algorithm 1.5.10's approach), then a scalar walk. Read §3–4 after Lesson 1.5 for the bit-manipulation tricks.
    Cited in: overview, 05-lexer-implementation-styles

  • [Moo56] Edward F. Moore. Gedanken-experiments on sequential machines. Automata Studies (C. E. Shannon, J. McCarthy, eds.), Annals of Mathematics Studies 34, Princeton University Press, pp. 129–153, 1956.
    Why and when: The origin of state equivalence by experiments, and of the partition refinement now called Moore's algorithm (Algorithm 1.4.4). Read the sections on distinguishable states after Lesson 1.4 §2.
    Note: Same volume as [Kle56].
    Cited in: overview, 04-dfa-minimization

  • [MY60] Robert McNaughton and Hisao Yamada. Regular expressions and state graphs for automata. IRE Transactions on Electronic Computers EC-9(1), pp. 39–47, 1960. doi:10.1109/TEC.1960.5221603
    Why and when: Constructs automata from regular expressions via marked positions: one origin of the position automaton (Algorithm 1.1.8) and the "M-Y" in the Dragon book's McNaughton–Yamada–Thompson construction. Read after Lesson 1.1 §2.
    Cited in: overview, 01-regular-languages-and-thompson

  • [ORT09] Scott Owens, John Reppy, and Aaron Turon. Regular-expression derivatives re-examined. Journal of Functional Programming 19(2), pp. 173–190, 2009. doi:10.1017/S0956796808007090
    Why and when: Core reading. Revives Brzozowski derivatives for practice: similarity and smart constructors (Definition 1.3.4), derivative classes for large alphabets (Definition 1.3.6), regular vectors for lexer specifications (Algorithm 1.3.10), and an evaluation in ml-ulex. The paper behind Lesson 1.3; read it all.
    Cited in: overview, 01-regular-languages-and-thompson, 03-derivatives

  • [Pik87] Rob Pike. The text editor sam. Software—Practice and Experience 17(11), pp. 813–845, 1987.
    Why and when: The editor whose regular-expression engine tracked submatches per NFA thread: the origin of the "Pike VM" of Lesson 1.2. Only the regular-expression section matters here; [Cox09] explains the engine in detail.
    Note: Wiley journal article.
    Cited in: overview, 02-nfa-simulation-and-subset-construction

  • [Rep98] Thomas Reps. "Maximal-munch" tokenization in linear time. ACM Transactions on Programming Languages and Systems 20(2), pp. 259–273, 1998. doi:10.1145/276393.276394
    Why and when: Core reading. Shows that naive maximal munch is quadratic in the worst case and gives the memoized linear-time algorithm (Algorithm 1.6.7, Theorem 1.6.10). Short and readable; read §2–3 after Lesson 1.6.
    Cited in: overview, 06-disambiguation

  • [RS59] Michael O. Rabin and Dana Scott. Finite automata and their decision problems. IBM Journal of Research and Development 3(2), pp. 114–125, 1959. doi:10.1147/rd.32.0114
    Why and when: Core reading. Introduces nondeterministic automata and the subset construction (Algorithm 1.2.5, Theorem 1.2.10). Read §4–5 after Lesson 1.2 §2; the rest (decision problems, two-way automata) is optional.
    Cited in: overview, 02-nfa-simulation-and-subset-construction

  • [Sch90] Douglas C. Schmidt. GPERF: A Perfect Hash Function Generator. Proceedings of the 2nd C++ Conference (USENIX), San Francisco, pp. 87–102, 1990. pdf
    Why and when: Core reading. The design of gperf: key positions, associated values, the search, and the generated lookup code (Definition 1.8.2, Algorithm 1.8.6). Read §2–4 while looking at the gperf output in Lesson 1.8's real-world box.
    Cited in: overview, 08-keyword-recognition

  • [SL14] Martin Sulzmann and Kenny Zhuo Ming Lu. POSIX regular expression parsing with derivatives. Functional and Logic Programming (FLOPS 2014), LNCS 8475, Springer, pp. 203–220, 2014.
    Why and when: Uses derivatives to compute POSIX (longest-leftmost) parse trees: the connection between maximal munch (Lesson 1.6) and regular-expression parsing. Further reading after Lessons 1.3 and 1.6.
    Note: Springer LNCS conference paper.
    Cited in: 06-disambiguation

  • [Tho68] Ken Thompson. Programming Techniques: Regular expression search algorithm. Communications of the ACM 11(6), pp. 419–422, 1968. doi:10.1145/363347.363387
    Why and when: Core reading. Four pages that introduce both Thompson's construction (Algorithm 1.1.6) and the simulation of all NFA states at once (Algorithm 1.2.4), compiled to IBM 7094 code for the QED editor. Read after Lesson 1.2 §2; the code is dated, the idea is not.
    Cited in: overview, 01-regular-languages-and-thompson, 02-nfa-simulation-and-subset-construction

  • [WG98] Tim A. Wagner and Susan L. Graham. Efficient and flexible incremental parsing. ACM Transactions on Programming Languages and Systems 20(5), pp. 980–1013, 1998. doi:10.1145/293677.293678
    Why and when: Core reading. Incremental lexing and parsing with lookahead-based invalidation (Algorithm 1.10.8), the design tree-sitter follows. Read the lexing sections after Lesson 1.10.
    Cited in: overview, 10-lossless-and-incremental-lexing

Textbooks and monographs

  • [CLRS4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 4th ed.. MIT Press, 2022. Read: Ch. 11 (Hash Tables), §11.3 (hash functions, universal hashing) and §11.4 (open addressing).
    Why and when: Expected-time analysis of hash tables with universal hashing and open addressing, behind the interning table of Lesson 1.8 (Algorithm 1.8.5). Read §11.3–11.4 if the expected O(1) probe bound is unfamiliar.
    Cited in: 08-keyword-recognition

  • [Dragon2] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed.. Addison-Wesley, 2006. Read: Ch. 3 (Lexical Analysis), §3.1–3.9; §3.7 (NFA simulation, subset construction, MYT construction), §3.9 (followpos DFAs, minimization, table compression).
    Why and when: Core reading. The standard textbook treatment; the running example (a|b)abb and its NFA (Fig. 3.34) and DFA (Fig. 3.35) are exactly Lessons 1.1–1.2's. Read §3.7 with Lessons 1.1–1.2 and §3.9 with Lessons 1.4–1.5.
    Cited in:* overview, 01-regular-languages-and-thompson, 02-nfa-simulation-and-subset-construction, 05-lexer-implementation-styles, 08-keyword-recognition

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: Ch. 2 (Scanners), §2.1–2.5: regular expressions, Thompson/subset/Hopcroft, and implementing scanners (table-driven, direct-coded, hand-coded).
    Why and when: The most practical textbook chapter on scanner implementation styles and their trade-offs; read §2.5 alongside Lesson 1.5.
    Cited in: overview, 05-lexer-implementation-styles

  • [HMU07] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd ed.. Pearson / Addison-Wesley, 2007. Read: Ch. 2 (§2.3–2.5 NFA, ε-NFA, subset construction), Ch. 3 (§3.2 Kleene's theorem, state elimination), Ch. 4 (§4.1 pumping lemma, §4.2 closure incl. inverse homomorphisms, §4.4 table-filling minimization).
    Why and when: The full proofs behind Lessons 1.1 and 1.4: Kleene's theorem (Theorem 1.1.13), closure under inverse homomorphism (Corollary 1.1.17), and the table-filling algorithm. Read when a proof sketch in the lessons needs more detail.
    Cited in: overview, 01-regular-languages-and-thompson, 04-dfa-minimization

Surveys and tutorials

  • [Aho90] Alfred V. Aho. Algorithms for finding patterns in strings. Handbook of Theoretical Computer Science, Vol. A (J. van Leeuwen, ed.), Elsevier, pp. 255–300, 1990.
    Why and when: A survey of regular-expression matching as used in Unix tools, including egrep's construction of DFA states on demand (the lazy DFA of Lesson 1.2). Read §3 for the history of automata-based search tools.
    Note: Handbook chapter.
    Cited in: overview, 02-nfa-simulation-and-subset-construction

Source code (pinned versions)

  • [BRICS-Min] dk.brics.automaton's three minimizers — src/dk/brics/automaton/MinimizationOperations.java in cs-au-dk/dk.brics.automaton at 582d8f3502b71185749c691aac91206619d36baf. Symbols: MinimizationOperations.minimizeBrzozowski, MinimizationOperations.minimizeHopcroft, MinimizationOperations.minimizeHuffman.
    Why and when: Brzozowski's double reversal in two lines, next to Hopcroft and table filling (Huffman): compare all three after Lesson 1.4.
    Cited in: 04-dfa-minimization

  • [CLANG-IdentifierTable] Clang's identifier table, seeded with keywords per language mode — clang/lib/Basic/IdentifierTable.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: IdentifierTable::AddKeywords, AddKeyword, getKeywordStatus.
    Why and when: Lesson 1.8's interning-table technique: how TokenKinds.def becomes identifier entries with a token kind, and how getKeywordStatus enables keywords per language.
    Cited in: overview, 08-keyword-recognition

  • [CLANG-Lexer] Clang's hand-written lexer — clang/lib/Lex/Lexer.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Lexer::LexTokenInternal, Lexer::SkipBlockComment, Lexer::LexRawStringLiteral, fastParseASCIIIdentifier, Lexer::tryConsumeIdentifierUTF8Char.
    Why and when: Core reading. The production example for Lessons 1.5–1.7 and 1.9: the switch in LexTokenInternal, the SIMD fast paths, raw strings, and UTF-8 identifiers. Start at LexTokenInternal and follow one case ('<') to the end.
    Cited in: overview, 05-lexer-implementation-styles, 06-disambiguation, 07-context-sensitive-lexing

  • [CLANG-Parser] Clang's parser-side replacement for the C lexer hack — clang/lib/Parse/Parser.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Parser::TryAnnotateTypeOrScopeToken.
    Why and when: How Clang asks Sema whether an identifier names a type and annotates the token in place (Algorithm 1.7.12). Read after Lesson 1.7.
    Cited in: overview, 07-context-sensitive-lexing

  • [CLANG-ParseTemplate] Clang splits >> when it closes a template argument list — clang/lib/Parse/ParseTemplate.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Parser::ParseGreaterThanInTemplateList.
    Why and when: Algorithm 1.7.9 in production, including >=, >>= and the C++98 fix-it. Read after Lesson 1.7.
    Cited in: 07-context-sensitive-lexing

  • [CLANG-Unicode] Clang's Unicode identifier range tables — clang/lib/Lex/UnicodeCharSets.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: XIDStartRanges, XIDContinueRanges, C11AllowedIDCharRanges, C99AllowedIDCharRanges.
    Why and when: The same range-table representation as Pebble's generated XIDTables.inc, plus the frozen C99/C11 lists (Lesson 1.9 §6).
    Cited in: 09-unicode

  • [CPYTHON-Lexer] CPython's C tokenizer (INDENT/DEDENT) — Parser/lexer/lexer.c in python/cpython at v3.13.0. Symbols: tok_get_normal_mode.
    Why and when: The indentation stack of Algorithm 1.7.10 in the tokenizer the Python compiler actually uses. Search for INDENT and DEDENT after Lesson 1.7.
    Cited in: 07-context-sensitive-lexing

  • [CPYTHON-Tokenize] Python's pure-Python tokenizer built from regex combinators — Lib/tokenize.py in python/cpython at v3.13.0. Symbols: group, any, maybe, PseudoToken.
    Why and when: Lesson 1.5's regex-combinator style: token patterns assembled by small helper functions and run by Python's backtracking engine.
    Cited in: overview, 05-lexer-implementation-styles

  • [DOTNET-SRM] .NET's derivative-based non-backtracking regex engine — src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexNode.cs in dotnet/runtime at v8.0.0. Symbols: SymbolicRegexNode.CreateDerivativeWrapper, SymbolicRegexNode.CreateNfaDerivativeWithEffects.
    Why and when: Brzozowski derivatives over minterms (derivative classes) with a DFA cache and an NFA mode built from partial derivatives (Lesson 1.3).
    Cited in: 03-derivatives

  • [FLEX-DFA] flex's subset construction ("NFA to DFA") — src/dfa.c in westes/flex at v2.6.4. Symbols: ntod.
    Why and when: The build-time subset construction over equivalence classes behind every flex scanner; no minimization pass follows (Lesson 1.2 §2).
    Cited in: 02-nfa-simulation-and-subset-construction, 05-lexer-implementation-styles

  • [GCC-Lex] GCC's C/C++ lexer (libcpp) — libcpp/lex.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: _cpp_lex_direct, search_line_sse2, init_vectorized_lexer.
    Why and when: The hand-written lexer of GCC with SIMD line scanning chosen at startup (Lesson 1.5).
    Cited in: overview, 05-lexer-implementation-styles

  • [GNULIB-DFA] GNU grep's DFA matcher (positions and lazily built states) — lib/dfa.c in coreutils/gnulib at v1.0. Symbols: dfaanalyze, build_state, dfaexec.
    Why and when: The position construction of Lesson 1.1 (nullable/firstpos/lastpos/follows) and the lazy DFA of Lesson 1.2 in one file.
    Cited in: 01-regular-languages-and-thompson, 02-nfa-simulation-and-subset-construction

  • [GO-Regexp] Go's Thompson compiler for regular expressions — src/regexp/syntax/compile.go in golang/go at go1.24.7. Symbols: Compile, compiler.compile.
    Why and when: Algorithm 1.1.6 as an instruction list; its Pike VM is machine.step in src/regexp/exec.go. Read after Lesson 1.1's Go box.
    Cited in: 01-regular-languages-and-thompson, 02-nfa-simulation-and-subset-construction

  • [LLVM-ConvertUTF] LLVM's UTF-8 validation and conversion routines — llvm/lib/Support/ConvertUTF.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: isLegalUTF8Sequence, getNumBytesForUTF8, ConvertUTF8toUTF32.
    Why and when: Table-driven UTF-8 validation (compare with Algorithm 1.9.8): the trailing-bytes table and the range checks of isLegalUTF8. Read after Lesson 1.9.
    Cited in: 09-unicode

  • [LLVM-DFAEmitter] A subset construction inside TableGen (VLIW packetizer automata) — llvm/utils/TableGen/DFAEmitter.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DfaEmitter::constructDfa, DfaEmitter::visitDfaState.
    Why and when: Determinization with states interned in a UniqueVector, the pattern of Algorithm 1.2.5, used by LLVM's DFA packetizer backends. Read after Lesson 1.2 §7.
    Cited in: 02-nfa-simulation-and-subset-construction

  • [LLVM-Regex] LLVM's POSIX regex matcher (Henry Spencer's engine), used by FileCheck — llvm/lib/Support/regexec.c in llvm/llvm-project at llvmorg-23.1.2. Symbols: llvm_regexec, smatcher, lmatcher.
    Why and when: NFA simulation with state sets as bit masks (Lesson 1.2), backtracking only for backreferences (backref in regengine.inc). The "find where LLVM does it" task of Lessons 1.1–1.2.
    Cited in: 01-regular-languages-and-thompson, 02-nfa-simulation-and-subset-construction

  • [LLVM-StringMatcher] TableGen's generated string matchers (switch on length, then on characters) — llvm/lib/TableGen/StringMatcher.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: StringMatcher::Emit, StringMatcher::EmitStringMatcherForChar.
    Why and when: The switch-on-length technique of Lesson 1.8 as a code generator; used for assembler mnemonics and register names in every LLVM backend.
    Cited in: overview, 08-keyword-recognition

  • [ML-ULEX] ml-ulex, the derivative-based lexer generator of SML/NJ — tools/ml-lpt/ml-ulex/lex-gen.sml in smlnj/smlnj at v2026.2-rc3. Symbols: LexGen.mkDFA.
    Why and when: Algorithm 1.3.10 (regular vectors, derivative classes) by two of the authors of [ORT09].
    Cited in: 03-derivatives

  • [RA-LexedStr] rust-analyzer's conversion of rustc_lexer tokens (trivia included) — crates/parser/src/lexed_str.rs in rust-lang/rust-analyzer at 2026-09-21. Symbols: LexedStr::new.
    Why and when: How rust-analyzer keeps whitespace and comments as WHITESPACE/COMMENT tokens for its lossless green trees (Lesson 1.10).
    Cited in: overview, 10-lossless-and-incremental-lexing

  • [RE2-DFA] RE2's lazy DFA — re2/dfa.cc in google/re2 at 2024-07-02. Symbols: DFA::RunStateOnByte, DFA::RunWorkqOnByte, DFA::ResetCache.
    Why and when: Core reading. The production lazy DFA of Lesson 1.2 (Algorithm 1.2.6): state cache, memory budget, cache reset and fallback. Read the comments at the top of the file first.
    Cited in: 01-regular-languages-and-thompson, 02-nfa-simulation-and-subset-construction

  • [RE2C-Min] re2c's DFA minimization (Moore, table filling) — src/dfa/minimization.cc in skvadrik/re2c at 3.1. Symbols: minimization_moore, minimization_table.
    Why and when: Moore's algorithm in a lexer generator, with rule- and tag-aware initial partitions (Lesson 1.4).
    Cited in: 02-nfa-simulation-and-subset-construction, 04-dfa-minimization

  • [REGEX-AUTOMATA-Min] Hopcroft's algorithm in Rust's regex-automata — regex-automata/src/dfa/minimize.rs in rust-lang/regex at regex-automata-0.4.9. Symbols: Minimizer::run.
    Why and when: A readable production Hopcroft implementation with the worklist and state-set partitions of Algorithm 1.4.5.
    Cited in: 04-dfa-minimization

  • [ROSLYN-Lexer] The C# compiler's lexer with leading and trailing trivia — src/Compilers/CSharp/Portable/Parser/Lexer.cs in dotnet/roslyn at Visual-Studio-2022-Version-17.12. Symbols: Lexer.LexSyntaxLeadingTrivia, Lexer.LexSyntaxTrailingTrivia, Lexer.LexSyntaxTrivia.
    Why and when: Definition 1.10.2 in production: how Roslyn decides which trivia is trailing (same line) and which is leading.
    Cited in: overview, 10-lossless-and-incremental-lexing

  • [RUSTC-Lexer] rustc's standalone lexer crate — compiler/rustc_lexer/src/lib.rs in rust-lang/rust at 1.94.1. Symbols: tokenize, Cursor::advance_token, is_id_start, is_id_continue, Cursor::raw_double_quoted_string.
    Why and when: Core reading. A hand-written lexer that returns trivia as tokens (Lesson 1.10), handles raw strings with hashes (Lesson 1.7) and nested block comments, and uses Unicode XID tables (Lesson 1.9). Short enough to read in one sitting after Lesson 1.5.
    Cited in: overview, 05-lexer-implementation-styles, 07-context-sensitive-lexing, 09-unicode, 10-lossless-and-incremental-lexing

  • [RUSTC-Symbol] rustc's pre-interned keywords and symbols — compiler/rustc_span/src/symbol.rs in rust-lang/rust at 1.94.1. Symbols: symbols!, Symbol::intern.
    Why and when: Keywords as the first interned symbols (kw::As, kw::Break, …): Lesson 1.8's interning technique in Rust's compiler.
    Cited in: overview, 08-keyword-recognition

  • [SIMDJSON-Src] simdjson's stage-1 scanner (bulk character classification) — src/generic/stage1/json_scanner.h in simdjson/simdjson at v3.10.1. Symbols: json_scanner::next, json_character_block::classify.
    Why and when: The block-at-a-time classification of Lesson 1.5 in the library that made it famous; read with [LL19].
    Cited in: 05-lexer-implementation-styles

  • [SWIFT-Lexer] The Swift compiler's lexer — lib/Parse/Lexer.cpp in swiftlang/swift at swift-6.1-RELEASE. Symbols: Lexer::lexImpl, Lexer::lexStringLiteral, skipToEndOfInterpolatedExpression.
    Why and when: A hand-written lexer with string interpolation \(…) like Pebble's; compare its bracket skipping with Pebble's mode stack after Lesson 1.7.
    Cited in: overview, 05-lexer-implementation-styles, 07-context-sensitive-lexing

  • [SWIFTSYNTAX-Trivia] SwiftSyntax's trivia representation — Sources/SwiftSyntax/Trivia.swift in swiftlang/swift-syntax at 600.0.1. Symbols: Trivia, TriviaPiece.
    Why and when: Structured trivia pieces (spaces, newlines, comments) attached to tokens (Lesson 1.10 §6).
    Cited in: overview, 10-lossless-and-incremental-lexing

  • [TS-Parser] tree-sitter's incremental parser and lexer driver — lib/src/parser.c in tree-sitter/tree-sitter at v0.25.3. Symbols: ts_parser__lex, ts_parser__can_reuse_first_leaf, ts_parser__reuse_node.
    Why and when: Core reading. Incremental relexing in production (Lesson 1.10): which leaves are reused after an edit and when the lexer must run again. Read ts_parser__can_reuse_first_leaf after the tree-sitter box.
    Cited in: overview, 10-lossless-and-incremental-lexing

  • [V8-Scanner] V8's scanner (parser-directed regex rescanning) — src/parsing/scanner.cc in v8/v8 at 12.9.1. Symbols: Scanner::ScanRegExpPattern.
    Why and when: How V8 lexes / as division by default and rescans as a regex when the parser expects an expression (Algorithm 1.7.8).
    Cited in: 07-context-sensitive-lexing

Official documentation and specifications

  • [ECMA262] ECMAScript 2024 Language Specification (ECMA-262, 15th edition). ECMA-262 2024. link
    Why and when: §12 (ECMAScript Language: Lexical Grammar) defines the goal symbols InputElementDiv and InputElementRegExp (Definition 1.7.3). Read the introduction of §12 after Lesson 1.7.
    Cited in: overview, 07-context-sensitive-lexing

  • [FLEX-Manual] Lexical Analysis With Flex (the flex manual). flex 2.6.4. link
    Why and when: Core reading. Rules, priority and longest match, start conditions and their stack (Lesson 1.7), -b backing-up reports (Lesson 1.6), and table compression options -Cf/-Cem (Lesson 1.5). Keep it open while doing the flex boxes.
    Cited in: overview, 01-regular-languages-and-thompson, 02-nfa-simulation-and-subset-construction, 05-lexer-implementation-styles, 06-disambiguation, 07-context-sensitive-lexing

  • [GPERF-Manual] GNU gperf: a perfect hash function generator. gperf 3.1. link
    Why and when: Input format, key-position selection and the generated in_word_set function used in Lesson 1.8's real-world box.
    Cited in: 08-keyword-recognition

  • [N1757] N1757: Right Angle Brackets (Revision 2). WG21 N1757 (2005). link
    Why and when: Daveed Vandevoorde's C++11 proposal that makes the first non-nested >> in a template argument list two > tokens (Algorithm 1.7.9); the wording is now [temp.names]. Read after Lesson 1.7.
    Cited in: overview, 07-context-sensitive-lexing

  • [P1949] P1949R7: C++ Identifier Syntax using Unicode Standard Annex 31. WG21 P1949R7 (2021). link
    Why and when: Why C++23 adopted XID_Start/XID_Continue and requires identifiers in NFC (Lesson 1.9 §1 and §6). Read the motivation section.
    Cited in: overview, 09-unicode

  • [PY-Lexical] The Python Language Reference: 2. Lexical analysis. Python 3.13. link
    Why and when: §2.1.8 defines INDENT/DEDENT with an indentation stack (Algorithm 1.7.10) and §2.3 NFKC identifiers (Lesson 1.9). Read those two sections after Lesson 1.7.
    Cited in: overview, 07-context-sensitive-lexing, 09-unicode

  • [RE2C-Manual] re2c user manual (C back end). re2c 3.1. link
    Why and when: re2c's syntax, conditions, direct-code generation options (--case-ranges), and the --dfa-minimization option shown in Lesson 1.4. Read with Lessons 1.4–1.5.
    Cited in: 01-regular-languages-and-thompson, 05-lexer-implementation-styles, 08-keyword-recognition

  • [RFC3629] RFC 3629: UTF-8, a transformation format of ISO 10646. November 2003. link
    Why and when: The IETF definition of UTF-8 restricted to U+10FFFF, with the security considerations (overlong forms) behind Lesson 1.9's strict decoder. Short; read §3–4 and §10.
    Cited in: overview, 09-unicode

  • [UAX15] Unicode Standard Annex #15: Unicode Normalization Forms. Unicode 16.0. link
    Why and when: NFC, NFD, NFKC, NFKD and the stream-safe text format (Definition 1.9.6, Lesson 1.9 §5). Read §1–3; the rest covers implementation details.
    Cited in: overview, 09-unicode

  • [UAX31] Unicode Standard Annex #31: Unicode Identifiers and Syntax. Unicode 16.0. link
    Why and when: Core reading. Default identifier syntax (XID_Start / XID_Continue), profiles, stability and NFKC closure (Definition 1.9.5, Proposition 1.9.13). Read §2 and §5 after Lesson 1.9.
    Cited in: overview, 09-unicode

  • [Unicode16] The Unicode Standard, Version 16.0: Core Specification. Unicode 16.0. link
    Why and when: §3.9 defines well-formed UTF-8 (Table 3-7, Definition 1.9.3) and the U+FFFD substitution of maximal subparts (Definition 1.9.4) that Pebble's lexer follows. Read §3.9 only.
    Cited in: overview, 09-unicode

Blog posts and articles

  • [Cox07] Russ Cox. Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...). 2007. link
    Why and when: The article that popularized the difference between backtracking and Thompson's simulation, with graphs of (a?)^n a^n. Read after Lesson 1.2 §5; not an origin (that is [Tho68]).
    Cited in: overview, 02-nfa-simulation-and-subset-construction

  • [Cox09] Russ Cox. Regular Expression Matching: the Virtual Machine Approach. 2009. link
    Why and when: The Pike VM with submatch threads, the instruction-list form of Thompson's construction used by the lab (Program.cpp). Read before implementing Lab L2.
    Cited in: overview, 01-regular-languages-and-thompson, 02-nfa-simulation-and-subset-construction

  • [Cox10] Russ Cox. Regular Expression Matching in the Wild. 2010. link
    Why and when: How RE2 combines the lazy DFA, the Pike VM, one-pass NFAs and bit-state backtracking. Read after Lesson 1.2 §7 for the engineering behind the lazy DFA.
    Cited in: overview, 02-nfa-simulation-and-subset-construction

  • [Hoe10] Björn Höhrmann. Flexible and Economical UTF-8 Decoder. 2010. link
    Why and when: A table-driven DFA for UTF-8 validation and decoding (Lesson 1.9 §6): Table 3-7 compiled into a 9-state automaton over byte classes. A good exercise in applying Lesson 1.2 to bytes.
    Cited in: overview, 09-unicode