Lesson 1.5 — Implementing a lexer: switch loops, tables, direct code, combinators, SIMD¶

Techniques: the hand-written switch loop (Clang, rustc, swiftc, GCC, Pebble), the table-driven DFA (flex), the direct-coded DFA (re2c), regex combinators (Python's tokenize, parser-combinator libraries), SIMD and bulk character classification (simdjson, Clang and GCC's fast paths) · Pebble implements: the hand-written loop (exercises E1–E5) and, as the ★ lab, a generated table-driven lexer benchmarked against it · Prerequisites: Lessons 1.1–1.4 · Time: 4–6 hours

Lessons 1.1–1.4 produced a minimal DFA. This lesson is about turning that DFA, or the token specification directly, into fast code. The choices trade speed, table size, error messages and who maintains the code: a grammar file that a generator reads, or a C++ function that a compiler engineer edits. Every production compiler of C-family languages (Clang, GCC, rustc, swiftc, V8, javac) lexes with a hand-written loop; lexer generators dominate in tools, DSLs and teaching. The running example is a five-rule lexer and the input a<=b1 c:

id  [a-z][a-z0-9]*      le  <=      lt  <      eq  =      ws  " "+

1. Problem and motivation¶

Given the token rules and a byte buffer, produce the token stream with maximal munch and rule priority (Lesson 1.6 makes these precise), as fast as possible, with good diagnostics. On large C++ translation units, lexing and preprocessing are a visible share of front-end time, which is why Clang's lexer has SIMD fast paths.

Hand-written switch loop¶

Dispatch on the first byte of the token with a switch, then write a small loop per token class: identifiers, numbers, strings, punctuators with one or two bytes of lookahead. The code is a DFA whose states are program points. It is the oldest style (FORTRAN and Algol compilers) and still the choice of every major compiler, because it makes error recovery, context-sensitive rules and diagnostics easy to express [EaC3 §2.5].

Table-driven DFA (flex)¶

Lesk and Schmidt's lex (1975) and its rewrite flex generate a transition table and a small interpreter loop from a rule file [FLEX-Manual]. The table is data, so it can be compressed; the loop is identical for every lexer.

Direct-coded DFA (re2c)¶

re2c [BC93] emits the DFA as C code: one label per state and a switch on the next byte, with goto between states. There is no table lookup and no interpreter loop, so the C compiler can optimize the branches; generated lexers match or beat hand-written ones [RE2C-Manual].

Regex combinators¶

Build the token recognizer from host-language functions (seq, alt, many) or from strings glued together by helper functions, and let a regex engine or a backtracking parser run it. Python's own tokenize module builds its patterns with group, any and maybe helpers; parser-combinator libraries (Parsec, nom) do the same with functions. Quick to write, easy to change, slower and with fewer guarantees.

SIMD and bulk classification¶

Process 16–64 bytes per instruction: compare a whole vector against a character class, turn the result into a bit mask, and find token boundaries with bit operations. simdjson [LL19] made the approach famous for JSON; Clang skips block comments and identifier characters with SSE2/SSE4.2, and GCC's preprocessor searches for line ends with SSE2.

2. Definitions and algorithms¶

Definition 1.5.1 (Scanner)

A scanner for rules \(r_1, \dots, r_k\) is a function \(\mathrm{scan}(w, i) = (t, j)\) that, at position \(i\) of input \(w\), returns the token kind \(t\) and end \(j > i\) of the longest match (earliest rule among ties), or an error token of length 1 if no rule matches a nonempty prefix. A lexer iterates \(\mathrm{scan}\) from \(i = 0\) to \(\lvert w \rvert\) (skipping trivia rules). All five styles implement the same function; they differ in representation.

Definition 1.5.2 (Tables: class map, transition table, comb vector)

A table-driven DFA stores a class map \(\kappa : \mathrm{Byte} \to \{0, \dots, k-1\}\), a transition table \(T : Q \times \{0..k-1\} \to Q \cup \{\bot\}\) and an accept vector \(\mathit{acc} : Q \to \{\text{rules}\} \cup \{\bot\}\). A comb vector (the "base/next/check" compression of Aho, Sethi and Ullman [Dragon2 §3.9.8]) stores \(T\) as arrays \(\mathit{base}[q]\), \(\mathit{next}[\cdot]\), \(\mathit{check}[\cdot]\) with \(T(q, c) = \mathit{next}[\mathit{base}[q] + c]\) if \(\mathit{check}[\mathit{base}[q] + c] = q\), and \(\bot\) (or a default) otherwise.

Definition 1.5.3 (Direct-coded DFA)

A direct-coded DFA is a program with one labelled block per state. The block for \(q\) reads the next byte \(c\) and jumps to the block of \(T(q, \kappa(c))\); accepting blocks record the rule and position before reading. The program counter is the state.

Definition 1.5.4 (Regex combinators)

A recognizer is a function \(p : (w, i) \mapsto\) set of end positions \(j \ge i\) such that \(w_{i..j}\) matches. Combinators build recognizers: \(\mathrm{lit}(s)\), \(\mathrm{alt}(p, q) = p \cup q\), \(\mathrm{seq}(p, q)(w, i) = \bigcup_{j \in p(w,i)} q(w, j)\), \(\mathrm{many}(p)\) = the least set containing \(i\) and closed under \(p\). A combinator scanner picks the largest end position over all rules, earliest rule first.

Definition 1.5.5 (Block masks)

For a block \(b_0 \cdots b_{L-1}\) of \(L\) bytes (\(L = 16\) for SSE2, 32 for AVX2, 64 for AVX-512) and a byte class \(C\), the mask \(M_C\) is the \(L\)-bit integer with bit \(i\) set iff \(b_i \in C\). For a class \(W\) ("word" bytes), \(\mathit{starts} = M_W \land \lnot(M_W \ll 1)\) marks the first byte of every run of \(W\) bytes that starts inside the block (with a carry bit from the previous block for runs that cross a boundary).

Hand-written switch loop¶

Algorithm 1.5.6 (Hand-written dispatch loop)

Input: buffer \(w\) terminated by a sentinel byte; position \(i\).
Output: the next token and the new position.
Precondition: \(w[\lvert w\rvert]\) is a sentinel (NUL) so one byte of lookahead past the end is safe; the end is tested by comparing with \(\lvert w \rvert\), because NUL may also occur inside the file.
Postcondition: the token is the longest match at \(i\) with the language's priorities (keywords over identifiers).
Invariant: each case consumes only bytes of the current token; at the end of a case, \(i\) is the token's end.

function Lex(w, i):
    i ← SkipTrivia(w, i);  start ← i
    if i = |w|: return (eof, i)
    c ← w[i]
    if IsIdentStart(c):
        while IsIdentChar(w[i+1]): i ← i + 1
        text ← w[start..i];  return (KeywordOrIdent(text), i + 1)
    if IsDigit(c): return LexNumber(w, start)
    switch c:
        case '<': if w[i+1] = '=': return (le, i + 2)     # two-byte lookahead decides
                  return (lt, i + 1)
        case '=': return (eq, i + 1)
        case ' ': while w[i+1] = ' ': i ← i + 1
                  return (ws, i + 1)
        default:  report "invalid character"; return (unknown, i + 1)

function SkipTrivia, LexNumber, KeywordOrIdent: one loop / lookup per token class
# (Pebble: solutions/pebble/lib/Lex/src/Lexer.cpp; keyword lookup: Lesson 1.8)

Clang's lexer is a big switch with explicit lookahead

Reproduce (clang 23.1.2; source at llvmorg-23.1.2; any OS):

printf 'int f(int a) { return a<=0x1F; }\n' > lexdemo.c
clang-23 -fsyntax-only -Xclang -dump-tokens lexdemo.c 2>&1 | sed -n '9,14p'
curl -sSfL https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/clang/lib/Lex/Lexer.cpp -o Lexer.cpp
grep -n 'bool Lexer::LexTokenInternal' Lexer.cpp
sed -n '4335,4344p' Lexer.cpp

Output (complete):

identifier       'a'                             Loc=<lexdemo.c:1:23>    [LeadingSpace]
lessequal        '<='                            Loc=<lexdemo.c:1:24>   
numeric_constant '0x1F'                          Loc=<lexdemo.c:1:26>   
semi             ';'                             Loc=<lexdemo.c:1:30>   
r_brace          '}'                             Loc=<lexdemo.c:1:32>    [LeadingSpace]
eof              ''                              Loc=<lexdemo.c:1:33>   
3836:bool Lexer::LexTokenInternal(Token &Result) {
  case '<':
    Char = getCharAndSize(CurPtr, SizeTmp);
    if (ParsingFilename) {
      return LexAngledStringLiteral(Result, CurPtr);
    } else if (Char == '<') {
      char After = getCharAndSize(CurPtr+SizeTmp, SizeTmp2);
      if (After == '=') {
        Kind = tok::lesslessequal;
        CurPtr = ConsumeChar(ConsumeChar(CurPtr, SizeTmp, Result),
                             SizeTmp2, Result);

What to notice: LexTokenInternal switches on the first character; the '<' case peeks one and two characters ahead to choose among <, <=, <<, <<= (and <::, <=>, conflict markers, #include <…>): Algorithm 1.5.6's cases, with context (ParsingFilename) that a pure DFA would not have. getCharAndSize hides trigraphs and backslash-newlines, which is why Clang cannot simply index CurPtr[1].

Table-driven DFA (flex)¶

Algorithm 1.5.7 (Table-driven scanning with backup)

Input: tables \(\kappa, T, \mathit{acc}\) (Definition 1.5.2); buffer \(w\); start position \(i\).
Output: \((t, j)\) as in Definition 1.5.1.
Precondition: the tables come from the (minimized) lexer DFA; \(T(q, c) = \bot\) means dead.
Postcondition: \((t, j)\) is the longest match with priority (Proposition 1.5.12).
Invariant: \((\mathit{lastRule}, \mathit{lastEnd})\) is the longest accepted prefix of \(w_{i..p}\) seen so far, where \(p\) is the scan position.

function TableScan(w, i):
    q ← q0;  p ← i;  lastRule ← ⊥;  lastEnd ← i
    while p < |w|:
        q ← T[q][κ[w[p]]]
        if q = ⊥: break                          # dead: stop
        p ← p + 1
        if acc[q] ≠ ⊥: (lastRule, lastEnd) ← (acc[q], p)
    if lastRule = ⊥: return (error, i + 1)
    return (lastRule, lastEnd)                   # back up to the last accept

function CombLookup(q, c):                       # Definition 1.5.2, comb vector
    k ← base[q] + c
    return next[k] if check[k] = q else ⊥

function PackComb(T):                            # first-fit row packing
    for q in Q:
        b ← 0
        while some c with T[q][c] ≠ ⊥ has next[b + c] already used: b ← b + 1
        base[q] ← b
        for c with T[q][c] ≠ ⊥: next[b + c] ← T[q][c]; check[b + c] ← q

flex adds "meta-equivalence classes" and a per-state default row (def) so that similar rows share storage; -Cf turns compression off for speed.

flex: statistics and the inner loop of a full-table scanner

Reproduce (flex 2.6.4; any OS):

cat > kwid.l <<'EOF'
%option noyywrap nodefault
%%
"if"       { return 1; }
"int"      { return 2; }
[a-z]+     { return 3; }
[ \t\n]+   { }
.          { return 4; }
%%
EOF
flex -Cf -v -o kwid.c kwid.l 2>&1 | sed -n '1,8p'
grep -n 'yy_current_state = yy_nxt\[yy_current_state\]\[' kwid.c

Output (abridged: 7 more statistics lines cut):

flex version 2.6.4 usage statistics:
  scanner options: -svB7 -Cf -okwid.c
  26/2000 NFA states
  13/1000 DFA states (46 words)
  5 rules
  No backing up
  1/40 start conditions
  17 epsilon states, 7 double epsilon states
872:        while ( (yy_current_state = yy_nxt[yy_current_state][ YY_SC_TO_UI(*yy_cp) ]) > 0 )
1207:           yy_current_state = yy_nxt[yy_current_state][YY_SC_TO_UI(*yy_cp)];

What to notice: 26 NFA states become 13 DFA states; with -Cf the table yy_nxt is a full [state][byte] array (7-bit bytes, so 128 columns), and the scanning loop at line 872 is Algorithm 1.5.7's while in one line: look up, test for the dead state (flex encodes "stop" as a negative state), advance. "No backing up" means no rule forces the scanner past an accepting state and back (Lesson 1.6).

Direct-coded DFA (re2c)¶

Algorithm 1.5.8 (Generating a direct-coded DFA)

Input: the lexer DFA (\(Q\), classes, \(T\), \(\mathit{acc}\)).
Output: a C function whose control flow is the DFA.
Precondition: \(T\) minimized (fewer labels).
Postcondition: the function computes \(\mathrm{scan}\) (Proposition 1.5.13).
Invariant: control is at label \(L_q\) exactly when the DFA is in state \(q\) with the cursor on the next unread byte.

function EmitDirect(DFA):
    emit "scan(p): mark ← none"
    for q in Q (start state first):
        emit label L_q
        if acc[q] ≠ ⊥: emit "mark ← (acc[q], p)"
        if q has no transitions: emit "goto Done"; continue
        emit "switch (*p++) {"
        for each target t: emit the case labels of every class c with T[q][c] = t, then "goto L_t;"
        emit "default: goto Done; }"
    emit label Done: "if mark = none: error, 1 byte; else p ← mark.end; return mark.rule"

re2c emits the switch as range checks, jump tables or bit tests depending on density, and folds mark into its YYMARKER pointer, which it keeps only when backing up is possible.

re2c: the same rules as direct code

Reproduce (re2c 3.1; any OS):

cat > kwid.re <<'EOF'
// re2c: keywords + identifiers, direct-coded
int lex(const char *YYCURSOR) {
    const char *YYMARKER;
    /*!re2c
        re2c:define:YYCTYPE = char;
        re2c:yyfill:enable = 0;
        "if"      { return 1; }
        "int"     { return 2; }
        [a-z]+    { return 3; }
        *         { return 4; }
    */
}
EOF
re2c -W -i --case-ranges -o kwid.re.c kwid.re
sed -n '/^int lex/,$p' kwid.re.c | sed -n '1,32p'

Output (abridged: the states for in and int, yy8–yy10, are cut):

int lex(const char *YYCURSOR) {
    const char *YYMARKER;

{
    char yych;
    yych = *YYCURSOR;
    switch (yych) {
        case 'a' ... 'h':
        case 'j' ... 'z': goto yy2;
        case 'i': goto yy5;
        default: goto yy1;
    }
yy1:
    ++YYCURSOR;
    { return 4; }
yy2:
    yych = *++YYCURSOR;
yy3:
    switch (yych) {
        case 'a' ... 'z': goto yy2;
        default: goto yy4;
    }
yy4:
    { return 3; }
yy5:
    yych = *++YYCURSOR;
    switch (yych) {
        case 'f': goto yy6;
        case 'n': goto yy8;
        default: goto yy3;
    }
yy6:

What to notice: every label is a DFA state and every goto a transition (Definition 1.5.3). There is no table and no state variable: the C compiler turns each switch into compares and jumps. The keyword trie i→f, i→n→t is embedded in the identifier DFA (yy5, yy6, yy8), which is Lesson 1.8's "keywords in the DFA" technique.

Regex combinators¶

Algorithm 1.5.9 (Combinator scanner)

Input: recognizers \(p_1, \dots, p_k\) built with the combinators of Definition 1.5.4; buffer \(w\); position \(i\).
Output: \((t, j)\) of Definition 1.5.1.
Precondition: each \(p_t\) returns the set of end positions (or, in a backtracking library, enumerates them).
Postcondition: longest match, earliest rule on ties (Proposition 1.5.14).
Invariant: best is the longest end found so far and the earliest rule achieving it.

function CombScan(w, i):
    best ← (error, i + 1, length 0)
    for t from 1 to k:
        for j in p_t(w, i):
            if j > i and j − i > best.length: best ← (t, j, j − i)
    return (best.rule, best.end)

lit(s)(w, i)     = { i + |s| } if w[i .. i+|s|) = s else {}
alt(p, q)(w, i)  = p(w, i) ∪ q(w, i)
seq(p, q)(w, i)  = ⋃ { q(w, j) | j ∈ p(w, i) }
many(p)(w, i)    = least S with i ∈ S and p(w, j) ⊆ S for every j ∈ S

Python's tokenize joins the rule strings into one regex, group(r1, …, rk), and runs Python's backtracking re engine, which returns the first alternative that matches, not the longest; the rules are ordered so that this works (longer operators before shorter ones).

Python's tokenize builds its token regexes with combinator functions

Reproduce (Python 3.11.15; CPython source tag v3.13.0; any OS):

curl -sSfL https://raw.githubusercontent.com/python/cpython/v3.13.0/Lib/tokenize.py | sed -n '60,62p'
python3 -c "import tokenize; print(tokenize.Number)"

Output (complete):

def group(*choices): return '(' + '|'.join(choices) + ')'
def any(*choices): return group(*choices) + '*'
def maybe(*choices): return group(*choices) + '?'
(([0-9](?:_?[0-9])*[jJ]|(([0-9](?:_?[0-9])*\.(?:[0-9](?:_?[0-9])*)?|\.[0-9](?:_?[0-9])*)([eE][-+]?[0-9](?:_?[0-9])*)?|[0-9](?:_?[0-9])*[eE][-+]?[0-9](?:_?[0-9])*)[jJ])|(([0-9](?:_?[0-9])*\.(?:[0-9](?:_?[0-9])*)?|\.[0-9](?:_?[0-9])*)([eE][-+]?[0-9](?:_?[0-9])*)?|[0-9](?:_?[0-9])*[eE][-+]?[0-9](?:_?[0-9])*)|(0[xX](?:_?[0-9a-fA-F])+|0[bB](?:_?[01])+|0[oO](?:_?[0-7])+|(?:0(?:_?0)*|[1-9](?:_?[0-9])*)))

What to notice: group, any and maybe are the \(\mathrm{alt}\), \(\mathrm{many}\) and option combinators of Definition 1.5.4 as string builders; Number is group(Imagnumber, Floatnumber, Intnumber), ordered so that the first-match semantics of Python's backtracking engine finds 1.5j as an imaginary number, not 1 then .5j. The combinator is a regex; the engine is Lesson 1.2's backtracker. (CPython's compiler uses the hand-written C tokenizer in Parser/lexer/lexer.c; tokenize.py serves tools.)

SIMD and bulk classification¶

Algorithm 1.5.10 (Bulk classification with masks)

Input: buffer \(w\); byte classes \(C_1, \dots, C_m\) given by ranges; block size \(L\).
Output: per block, the masks \(M_{C_j}\) and the token-start mask of Definition 1.5.5.
Precondition: classes are unions of a few byte ranges (so each needs a couple of vector compares) or a nibble-lookup table (simdjson's pshufb trick).
Postcondition: bit \(i\) of \(M_C\) is set iff \(b_i \in C\); \(\mathit{starts}\) marks the first byte of each run (Proposition 1.5.15).
Invariant: carry is 1 iff the last byte of the previous block was in \(W\).

function Classify(w, L):
    carry ← 0
    for each block B of L bytes:
        v ← VectorLoad(B)
        for each class C = [lo, hi]:
            M_C ← MoveMask(CmpGt(v, lo − 1) AND CmpLt(v, hi + 1))    # one bit per byte
        W ← M_alpha OR M_digit
        starts ← W AND NOT ((W << 1) OR carry)
        carry ← bit L−1 of W
        emit (B, masks, starts)       # then: token boundaries by count-trailing-zeros on starts

Classifying 16 bytes with SSE2

Reproduce (clang 23.1.2, x86-64 with SSE2):

cat > classify.c <<'EOF'
#include <emmintrin.h>
#include <stdio.h>

/* Classify 16 bytes at once: one SSE2 compare per class, one movemask per result. */
static void show(const char *name, int mask) {
  printf("%-10s", name);
  for (int i = 0; i < 16; ++i) putchar(mask >> i & 1 ? '1' : '.');
  putchar('\n');
}

int main(void) {
  const char text[17] = "let x1 = 42; //y";
  __m128i v = _mm_loadu_si128((const __m128i *)text);
  __m128i lo = _mm_set1_epi8('0' - 1), hi = _mm_set1_epi8('9' + 1);
  int space = _mm_movemask_epi8(_mm_cmpeq_epi8(v, _mm_set1_epi8(' ')));
  int digit = _mm_movemask_epi8(_mm_and_si128(_mm_cmpgt_epi8(v, lo), _mm_cmplt_epi8(v, hi)));
  __m128i lower = _mm_or_si128(v, _mm_set1_epi8(0x20));       /* fold ASCII case */
  int alpha = _mm_movemask_epi8(_mm_and_si128(_mm_cmpgt_epi8(lower, _mm_set1_epi8('a' - 1)),
                                              _mm_cmplt_epi8(lower, _mm_set1_epi8('z' + 1))));
  int slash = _mm_movemask_epi8(_mm_cmpeq_epi8(v, _mm_set1_epi8('/')));
  printf("%-10s%s\n", "input", text);
  show("space", space);
  show("digit", digit);
  show("alpha", alpha);
  show("slash", slash);
  /* token starts: an identifier/number byte whose predecessor is not one */
  int word = alpha | digit;
  show("starts", word & ~(word << 1));
  return 0;
}
EOF
clang-23 -O2 -msse2 classify.c -o classify && ./classify

Output (complete):

input     let x1 = 42; //y
space     ...1..1.1...1...
digit     .....1...11.....
alpha     111.1..........1
slash     .............11.
starts    1...1....1.....1

What to notice: each mask is one compare and one movemask for all 16 bytes (Algorithm 1.5.10). starts marks l, x, 4 and y: the beginnings of the words let, x1, 42 and y, found without a loop over bytes. (The y after // is inside a comment: bulk classification finds candidates; a second stage applies the lexer's modes.) Clang uses the same instructions to skip comment bodies (_mm_cmpeq_epi8 against '/' in SkipBlockComment) and identifier characters (_mm_cmpistri in fastParseASCIIIdentifier), see §7.

3. Worked example¶

All five styles on the example lexer (id, le, lt, eq, ws) and the input a<=b1 c. The DFA was built and minimized with the course oracle (lexer_dfa, hopcroft): the subset construction gives seven live states, and minimization merges the two identifier states.

Hand-written switch loop¶

call	start	first byte → case	lookahead	token	new position
1	0	`a` → identifier loop	`<` is not an ident char	`id:a`	1
2	1	`<` → case '<'	next is `=`	`le:<=`	3
3	3	`b` → identifier loop	`1` continues, stops	`id:b1`	5
4	5	→ whitespace loop	`c` stops	`ws:`	6
5	6	`c` → identifier loop	end of input	`id:c`	7
6	7	end of input	–	`eof`	7

Table-driven DFA (flex)¶

Classes: 0 = other, 1 = space, 2 = digit, 3 = <, 4 = =, 5 = letter. Minimized table (– = dead):

state	other	space	digit	`<`	`=`	letter	accepts
→ A	–	B	–	C	D	E
B	–	B	–	–	–	–	ws
C	–	–	–	–	F	–	lt
D	–	–	–	–	–	–	eq
E	–	–	E	–	–	E	id
F	–	–	–	–	–	–	le

Scan from position 1: A \(\xrightarrow{<}\) C (accept lt, lastEnd 2) \(\xrightarrow{=}\) F (accept le, lastEnd 3) \(\xrightarrow{b}\) dead: return le, end 3. From position 3: A \(\xrightarrow{b}\) E \(\xrightarrow{1}\) E \(\xrightarrow{\text{space}}\) dead: id, end 5. The whole input costs 11 table reads for 7 bytes: each token's scan also reads the byte that kills it.

Comb-vector packing (first fit, rows in the order A–F) stores the 36-entry table in arrays of length 11:

state	nonempty columns	base	slots used (`next` = target, `check` = state)
A	1, 3, 4, 5	0	1→B, 3→C, 4→D, 5→E
B	1	1	2→B
C	4	2	6→F
D	none	0	–
E	2, 5	5	7→E, 10→E
F	none	0	–

Lookup \(T(C, \text{=}) = \mathit{next}[2 + 4] = F\) because \(\mathit{check}[6] = C\); lookup \(T(C, \text{letter})\): slot \(2 + 5 = 7\) has \(\mathit{check}[7] = E \neq C\), so the answer is "dead".

Direct-coded DFA (re2c)¶

The same table as code: L_A: switch(*p++) { case ' ': goto L_B; case '<': goto L_C; case '=': goto L_D; case 'a'…'z': goto L_E; default: goto Done; }, L_C: mark = (lt, p); switch(*p++) { case '=': goto L_F; default: goto Done; }, and so on. On <=b control goes L_A → L_C → L_F → Done with mark = (le, 3).

Regex combinators¶

scan(w, 1) tries each rule at position 1: id gives \(\{\}\), le = lit("<=") gives \(\{3\}\), lt gives \(\{2\}\), eq and ws give \(\{\}\). The largest end is 3, from le. With first-match semantics (Python's re on group(le, lt, …)), order matters: group(lt, le) would return lt at position 1 and then an eq token: wrong.

SIMD and bulk classification¶

On a<=b1 c padded to 16 bytes, \(M_{\text{letter}}\) = 1..1..1........., \(M_{\text{digit}}\) = ....1..........., so \(W\) = 1..11.1......... and \(\mathit{starts}\) = 1..1..1.........: the three identifiers start at 0, 3 and 6. The punctuator run <= at 1–2 and the space at 5 are found from the complement masks.

4. Invariants and correctness¶

Hand-written switch loop¶

Proposition 1.5.11 (A hand-written loop is a DFA)

If every case of Algorithm 1.5.6 reads bytes only forward, with bounded lookahead, and its decisions depend only on the bytes read, then the scanner computes the same function as some DFA scanner with backup of at most the lookahead. Conversely, every DFA scanner can be written in this style.

Proof

Program to DFA: a program point plus the (bounded) values of its local variables that influence control flow is a finite state; each byte read moves it to another; accepting points are the returns. Lookahead of \(\ell\) bytes that is not consumed corresponds to a DFA that consumes them and backs up at most \(\ell\) bytes (Lesson 1.6). DFA to program: Definition 1.5.3 is a program of this shape. \(\square\)

The hypothesis fails exactly where compilers use hand-written lexers: nested comment depth and the interpolation stack are unbounded counters, so the Pebble lexer is not a DFA (Corollary 1.1.17; Lesson 1.7).

Table-driven DFA (flex)¶

Proposition 1.5.12 (Table-driven scanning is correct)

Algorithm 1.5.7 returns the longest nonempty prefix of \(w_{i..}\) accepted by the DFA, with the accept tag of the DFA state it ends in, and CombLookup returns \(T(q, c)\) for the packed tables.

Proof

The loop is the DFA run of Definition 1.1.3 from \(i\), stopped at the dead state (no longer prefix can be accepted from it) or at the end. The invariant holds initially (no accepting prefix of length \(\ge 1\) seen) and after every step (update when the new state accepts). At exit, every longer prefix was either rejected (the run died) or does not exist (end of input), so lastEnd is the longest accepted prefix. For the comb vector: PackComb writes \(\mathit{next}[\mathit{base}[q] + c] = T(q, c)\) and \(\mathit{check} = q\) for every defined entry and never overwrites (first fit skips used slots), so CombLookup returns \(T(q, c)\) when defined; when \(T(q, c) = \bot\), slot \(\mathit{base}[q] + c\) is either unused (check is unset) or owned by another state (check \(\neq q\)). \(\square\)

Direct-coded DFA (re2c)¶

Proposition 1.5.13 (Direct code computes the same scan)

The program emitted by Algorithm 1.5.8 returns the same \((t, j)\) as Algorithm 1.5.7 on the same DFA.

Proof

By induction on the number of bytes read, control is at \(L_q\) exactly when the table loop would be in state \(q\) (the invariant): the start label is \(L_{q_0}\), and each switch jumps to \(L_{T(q, \kappa(c))}\) or to Done when \(T = \bot\). mark is updated at accepting labels exactly when the table loop updates lastRule, lastEnd. Done performs the same backup. \(\square\)

Regex combinators¶

Proposition 1.5.14 (Combinator semantics)

For recognizers built from Definition 1.5.4, \(j \in p(w, i)\) iff \(w_{i..j} \in L(r_p)\), where \(r_p\) is the corresponding regular expression; hence Algorithm 1.5.9 computes the longest-match scan. A first-match backtracking implementation computes it only if, for every position, the first alternative that succeeds is also the longest (a property of the rule order, not of the combinators).

Proof

Structural induction mirroring Definition 1.1.2: lit matches its string; alt is union; seq concatenates (an end \(j\) of \(q\) started at an end of \(p\)); many is the least fixed point of "include \(i\), close under \(p\)", which is \(L(r)^{*}\) read from \(i\). The scanner maximizes over rules and ends. The counterexample for first-match: group("<", "<=") on <= stops after <. \(\square\)

SIMD and bulk classification¶

Proposition 1.5.15 (Mask arithmetic finds run starts)

With the carry of Algorithm 1.5.10, bit \(i\) of \(\mathit{starts}\) is set iff \(b_i \in W\) and (\(i = 0\) and the previous block did not end in \(W\), or \(i > 0\) and \(b_{i-1} \notin W\)).

Proof

Bit \(i\) of \(W \ll 1\) is bit \(i - 1\) of \(W\) (bit 0 becomes 0); OR-ing the carry into bit 0 supplies "the byte before \(b_0\) is in \(W\)". So bit \(i\) of \(\lnot((W \ll 1) \lor \mathit{carry})\) is 1 iff the byte before \(b_i\) is not in \(W\); AND with \(W\) requires \(b_i \in W\). \(\square\)

5. Complexity¶

Variables: \(n\) = input bytes; \(\lvert Q \rvert\) = DFA states; \(k\) = byte classes; \(L\) = SIMD block size; \(R\) = number of rules.

Technique	Time per byte	Table / code size	Notes
Hand-written switch	\(O(1)\), branchy; best constant in practice	code only	predictable branches on common tokens
Table-driven (full tables)	\(O(1)\): class lookup + table lookup	\(\lvert Q \rvert \times k\) entries	one indirect load per byte
Table-driven (comb vector)	\(O(1)\) + check compare	\(\ll \lvert Q \rvert k\)	first-fit packing \(O(\lvert Q \rvert k \cdot \mathrm{len})\) build
Direct-coded	\(O(1)\), branches	code grows with \(\lvert Q \rvert k\)	no data loads; I-cache pressure for huge DFAs
Regex combinators (sets)	\(O(R \cdot n)\) per token start, \(O(n^{2})\) worst for a line	–	with backtracking engines: exponential worst case (Lesson 1.2)
SIMD classification	\(O(1/L)\) per byte for the classification stage	a few constants	plus a scalar stage per token

Pathological input. Table-driven and direct-coded scanners with backup can read \(\Theta(n^{2})\) bytes on rule sets such as {a, a*b} and input \(a^{n}\) (Lesson 1.6, Proposition 1.6.11). Combinator scanners that try every rule at every position are \(\Theta(R n)\) even without backup, and a backtracking engine under them inherits Proposition 1.2.13.

At scale (lab benchmark ch01-regexbench, section 4, course container): on a generated 6.9 MB Pebble file with 1.94 M tokens, the hand-written Pebble lexer (streaming, no token vector) runs at 104 MB/s and the generated table-driven lexer (135 states × byte classes, built in 2.6 ms) at 90 MB/s. The table lexer also returns trivia tokens; the hand-written one builds full Token objects with source locations. Collecting the hand-written lexer's 80-byte Tokens into a std::vector drops it to 21 MB/s: the allocator, not the automaton, dominates.

Hand-written switch loop¶

Sentinel-terminated buffers (Clang, GCC, Pebble): the NUL after the buffer removes an end-of-buffer test from every loop; a NUL inside the file must still be diagnosed.
Lookup-table classification: isIdentChar as a 256-entry table (Clang's CharInfo.h) instead of range compares.
Fast paths: SIMD skipping of identifier bodies and comments inside the hand-written loop (Clang, §7).

Table-driven DFA (flex)¶

Compression levels (flex -Cf full, -Cem equivalence and meta-equivalence classes with comb vectors [FLEX-Manual]): 10–100× smaller tables for a few extra instructions per byte.
Row displacement with defaults (flex's def array, [Dragon2 §3.9.8]): a missing entry falls back to a default state's row, compressing near-duplicate rows.

Direct-coded DFA (re2c)¶

Switch lowering choices (re2c): nested if binary search, jump tables, or bitmaps depending on case density; --case-ranges emits GNU case ranges (box in §2).
Tunnel automata (re2c's --dfa-minimization and tunneling [RE2C-Manual]): share code between states whose outgoing structure is similar, reducing code size.

Regex combinators¶

Parser-combinator libraries (Parsec, nom, chumsky) lex with the same combinators they parse with; convenient, with backtracking costs unless the library commits (Parsec's try).
Compile combinators to automata (Rust's logos derives a DFA from token attributes at compile time): combinator-style specification, table-free generated code.

SIMD and bulk classification¶

Nibble lookup (simdjson [LL19]): classify all 256 byte values into up to 8 classes with two pshufb table lookups on the high and low nibbles.
Two-stage architectures (simdjson): stage 1 finds structural characters and quote regions for the whole buffer with SIMD and carry-less multiplication; stage 2 walks the index. A lexer can do the same for identifiers and whitespace, then run a scalar DFA only at token starts.

7. In real compilers¶

Hand-written switch loop¶

LLVM / Clang

clang/lib/Lex/Lexer.cpp — Lexer::LexTokenInternal is the switch on the first character; LexIdentifierContinue, LexNumericConstant, LexStringLiteral are the per-class loops (LLVM 23.1.2) [CLANG-Lexer]; box in §2.

rustc compiler/rustc_lexer/src/lib.rs — Cursor::advance_token matches on the first char (Rust 1.94.1) [RUSTC-Lexer].
Swift lib/Parse/Lexer.cpp — Lexer::lexImpl (swift-6.1-RELEASE) [SWIFT-Lexer].
GCC libcpp/lex.cc — _cpp_lex_direct (GCC 15.1) [GCC-Lex].
Pebble solutions/pebble/lib/Lex/src/Lexer.cpp — Lexer::lex.

Find where LLVM does it. In clang/lib/Lex/Lexer.cpp at llvmorg-23.1.2, find the case in LexTokenInternal that handles '<'. Question: which four multi-character tokens starting with < (besides < itself) can it return in C++20 mode? (Quiz llvm-clang-less-case.)

Table-driven DFA (flex)¶

flex src/gen.c emits the tables and the scanning loop (gen_next_match), src/tblcmp.c compresses them (flex 2.6.4) [FLEX-DFA]; box in §2.
The course ★ lab solutions/labs/ch01-regex/src/TableLexer.cpp — Table::lex with a uint16_t transition table.

Direct-coded DFA (re2c)¶

re2c generates the lexers of PHP (the Zend engine's Zend/zend_language_scanner.l) and Ninja (src/lexer.in.cc) [RE2C-Manual]; box in §2.

Regex combinators¶

CPython Lib/tokenize.py — group, any, maybe, PseudoToken (v3.13.0) [CPYTHON-Tokenize]; box in §2.

SIMD and bulk classification¶

Clang clang/lib/Lex/Lexer.cpp — fastParseASCIIIdentifier (_mm_cmpistri under __SSE4_2__) and the __SSE2__ loop in Lexer::SkipBlockComment [CLANG-Lexer].
GCC libcpp/lex.cc — search_line_sse2 and search_line_ssse3; init_vectorized_lexer picks the fastest line scanner at startup [GCC-Lex].
simdjson src/generic/stage1/json_scanner.h — json_character_block::classify (v3.10.1) [SIMDJSON-Src, LL19].

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
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

Choose a hand-written loop when the language has context-sensitive tokens or you care about diagnostics (a compiler). Choose flex or re2c when the token set is regular and changes often, and generic errors are acceptable; prefer re2c's direct code for speed. Choose combinators when writing a quick tool. Add SIMD to whichever style you use, for the hottest loops (comments, identifiers, whitespace).

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Hand-written switch loop	`llvm-clang-less-case`, `style-choice`	`./course drill lexer-modes`	`hand-written-lexer`	E1–E5
Table-driven DFA (flex)	`comb-vector-lookup`, `style-choice`	`./course drill maximal-munch`	`table-driven`	Lab L7 ★
Direct-coded DFA (re2c)	`direct-coded-labels`, `style-choice`	`./course drill subset-construction` (each state becomes a label)	`direct-coded`	—
Regex combinators	`combinator-first-match`, `style-choice`	`./course drill maximal-munch` (compare longest vs first match)	`regex-combinators`	—
SIMD and bulk classification	`simd-starts-mask`, `style-choice`	justification below	`simd-lexing`	—

SIMD classification has no drill: the computation is a few bit operations (the quiz asks one, simd-starts-mask), and practicing it means writing intrinsics, which the real-world box does.

Pitfall

"Generated lexers are slow" was true of lex's 1975 tables; it is not true of re2c's direct code or of flex's full tables. The lab's table lexer runs within 15 % of the hand-written Pebble lexer. The real reasons compilers hand-write lexers are context sensitivity and diagnostics.

References¶

See the chapter references.

Lesson 1.5 — Implementing a lexer: switch loops, tables, direct code, combinators, SIMD¶

1. Problem and motivation¶

Hand-written switch loop¶

Table-driven DFA (flex)¶

Direct-coded DFA (re2c)¶

Regex combinators¶

SIMD and bulk classification¶

2. Definitions and algorithms¶

Hand-written switch loop¶

Table-driven DFA (flex)¶

Direct-coded DFA (re2c)¶

Regex combinators¶

SIMD and bulk classification¶

3. Worked example¶

Hand-written switch loop¶

Table-driven DFA (flex)¶

Direct-coded DFA (re2c)¶

Regex combinators¶

SIMD and bulk classification¶

4. Invariants and correctness¶

Hand-written switch loop¶

Table-driven DFA (flex)¶

Direct-coded DFA (re2c)¶

Regex combinators¶

SIMD and bulk classification¶

5. Complexity¶

6. Variants and refinements¶

Hand-written switch loop¶

Table-driven DFA (flex)¶

Direct-coded DFA (re2c)¶

Regex combinators¶

SIMD and bulk classification¶

7. In real compilers¶

Hand-written switch loop¶

Table-driven DFA (flex)¶

Direct-coded DFA (re2c)¶

Regex combinators¶

SIMD and bulk classification¶

8. Comparison¶

9. Assessment¶

References¶