Building Scanners with Finite Automata

A token class is a regular language — the set of strings that count as, say, an identifier or an integer literal. A lexical specification pairs each token class's regex with an action (usually: "emit a token of this kind"). The scanner-generation problem is: given such a specification, build a program that, reading input left to right, repeatedly strips off the next token. The key theoretical fact making this tractable is the equivalence of three formalisms: regular expressions, nondeterministic finite automata (NFAs, which may have multiple candidate transitions or ε-moves that consume no input), and deterministic finite automata (DFAs, which have exactly one transition per state per symbol). Kleene's theorem states these define the same class of languages. Regexes are convenient to write; DFAs are efficient to run. NFAs are the algorithmic bridge between them — every regex compiles directly to an NFA via Thompson's construction, and every NFA can be mechanically converted to an equivalent DFA via the subset construction. A DFA is formally a 5-tuple $(Q, \Sigma, \delta, q_0, F)$: a finite set of states $Q$, an alphabet $\Sigma$, a total transition function $\delta: Q \times \Sigma \to Q$, a start state $q_0$, and accepting states $F \subseteq Q$. Determinism means $\delta$ is a function, not a relation — from any state, on any symbol, there is exactly one next state (possibly a dead/trap state). This is precisely what allows execution without backtracking: the automaton never needs to guess or retry. For a scanner built from several token regexes at once, each accepting state must remember which token class it accepts, and — crucially — the scanning discipline must resolve two ambiguities that a single-regex recognizer never faces: (1) length ambiguity, resolved by maximal munch — always prefer the longest match; and (2) class ambiguity, when several rules match the same longest prefix (e.g., `if` matches both the keyword rule and the general-identifier rule) — resolved by rule priority, typically "earlier-declared rule wins," which is exactly how keyword-vs-identifier conflicts are handled in real lexer generators.

The pipeline has four stages: (1) build one NFA per token regex, (2) combine them under a common start state, (3) determinize via the subset construction, tagging each DFA state with the highest-priority accepting NFA state it contains, and (4) drive the DFA with the maximal-munch loop.

Stage 1 — Thompson's construction. Each regex operator has a fixed NFA fragment with a single start state and single accept state, and ε-transitions glue fragments together:

• A symbol $a$: two states linked by an edge labeled $a$.
• Concatenation $rs$: accept state of $r$'s fragment gets an ε-edge to start state of $s$'s fragment.
• Union $r \mid s$: a new start state ε-branches to both fragments' starts; both accepts ε-converge to a new accept state.
• Kleene star $r^*$: a new start/accept pair with ε-edges allowing zero passes (start→accept directly) or looping through $r$ arbitrarily many times.

Each construction step adds at most 2 new states and a constant number of edges, so a regex of length $n$ (counting operators and symbols) yields an NFA with $O(n)$ states and $O(n)$ edges.

Stage 2 — merge into one NFA. Introduce a fresh super-start state $q_0$ with an ε-edge to the start of every token regex's NFA. Tag each token's accept state with that token's name and priority (rule order).

Stage 3 — subset construction (determinize). A DFA state is a set of NFA states — specifically, the set of NFA states reachable from the current DFA state's underlying set by reading one symbol, then closing under ε-transitions. The DFA start state is the ε-closure of $\{q_0\}$. A DFA state is accepting if its underlying set contains any NFA accept state; it is tagged with the highest-priority token whose accept state appears in that set (this is where rule-order tie-breaking is baked directly into the automaton).

Stage 4 — maximal-munch scanning loop. Run the DFA from its start state, consuming one input character per transition, and remember the most recent state that was accepting along with the position where that acceptance occurred. On reaching the dead/trap state (or end of input) with no further progress possible, roll back to that last-recorded accepting position, emit a token of the recorded class, and restart the DFA from its start state at that position. ```text function ε-closure(S): // S: set of NFA states stack ← S; result ← S while stack not empty: pop state t for each ε-edge (t → u): if u not in result: add u to result; push u return result function move(S, c): // one-symbol transition on a set return { u | ∃ t in S with edge t --c--> u } function subset_construction(NFA): start ← ε-closure({nfa.start}) Dstates ← { start }, unmarked Dtrans ← {} while ∃ unmarked T in Dstates: mark T for each symbol c in Σ: U ← ε-closure(move(T, c)) if U is empty: continue // implicit dead state if U not in Dstates: add U as unmarked Dtrans[T, c] ← U accepting(T) ← true if T contains any NFA accept state tag(T) ← token of the highest-priority accept state in T return (Dstates, Dtrans, start, accepting, tag) function scan(input, DFA): tokens ← [] pos ← 0 while pos < length(input): state ← DFA.start lastAcceptPos ← -1 lastAcceptTag ← none i ← pos while true: if DFA.accepting(state): lastAcceptPos ← i lastAcceptTag ← DFA.tag(state) if i == length(input) or DFA.trans(state, input[i]) undefined: break state ← DFA.trans(state, input[i]) i ← i + 1 if lastAcceptPos == -1: error("no token matches at position", pos) tokens.append( (lastAcceptTag, input[pos .. lastAcceptPos]) ) pos ← lastAcceptPos + 1 return tokens ``` The inner `while true` loop is the maximal-munch scan: it keeps consuming characters past the last accepting state, hoping a longer match exists, only stopping when the DFA can go no further. It then backs up to the last point where it was in an accepting state — never to the first.

Construction complexity. For a lexical spec with total regex length $m$ (sum of all token regex sizes) and $k$ token rules:

• Thompson's construction produces an NFA with $O(m)$ states and $O(m)$ transitions — each of the constant-size operator rules (symbol, concatenation, union, star) adds $O(1)$ states, and there are $O(m)$ operators total. Merging $k$ NFAs adds one super-start state and $k$ ε-edges.
• The subset construction, in the worst case, produces a DFA with up to $2^{O(m)}$ states, since a DFA state is a subset of the up-to-$O(m)$ NFA states. This exponential blowup is real and provable: for the family of regexes $\Sigma^*a\Sigma^{n}$ ("some symbol $a$, $n$ positions from the end"), any DFA needs at least $2^{n}$ states, because the DFA must remember the last $n$ symbols seen, and there are $2^{n}$ distinct such histories that require distinguishable future behavior — a direct consequence of the Myhill–Nerode theorem, which says the minimum DFA size equals the number of equivalence classes of the relation "$x \sim y$ iff for all $z$, $xz \in L \Leftrightarrow yz \in L$."
• In practice, lexical specifications (identifiers, numbers, keywords, operators) do not exercise this pathology; real scanner-generator DFAs typically have a number of states within a small constant factor of the NFA size, and after minimization (via Hopcroft's $O(m \log m)$ algorithm or the simpler $O(m^2)$ partition-refinement), they shrink further by merging states with identical future behavior.

Running-time complexity. Once built, the DFA-driven scanner runs in $O(n)$ time on an input of length $n$: each input character triggers exactly one table lookup ($\delta(\text{state}, \text{char})$), and the maximal-munch loop never revisits a character more than once per emitted token — the outer loop's total work across all tokens is bounded by the number of characters consumed, which is $n$. (There is no re-scanning: the inner loop, restarted at `pos`, only walks forward past positions it has not yet looked at as part of the current token attempt; across the whole run each character is examined a bounded number of times — once when tentatively extending a match, and never again once a token boundary commits.) Space is $O(|Q| \cdot |\Sigma|)$ for the transition table, independent of input size.

Correctness — determinization preserves the language. Claim: $L(\text{DFA}) = L(\text{NFA})$. Proof sketch by invariant: after processing a prefix $w$, the DFA is in the state equal to $\text{ε-closure}(\{q : q \text{ reachable from an NFA start state by reading } w\})$. This holds by induction on $|w|$: base case $w=\varepsilon$ is the definition of the DFA start state; inductive step, reading one more symbol $c$, the `move`-then-`ε-closure` step by construction computes exactly the set of NFA states reachable after $wc$. Since the DFA state after $w$ is accepting iff it contains an NFA accept state, and by the invariant that set is exactly the reachable-NFA-states-after-$w$, the DFA accepts $w$ iff some run of the NFA accepts $w$ — which is precisely the definition of NFA language acceptance. $\blacksquare$

Correctness — maximal munch finds the longest match. The scanning loop maintains the invariant that `lastAcceptPos` always holds the greatest index $i$ seen so far such that `input[pos..i]` is accepted by the merged DFA (equivalently, matches some token regex). Since the loop only advances `i` and only overwrites `lastAcceptPos` when the current, larger `i` is accepting, `lastAcceptPos` is monotonically nondecreasing and, at loop exit, holds the largest such index reachable by any accepting path — because the DFA explores the unique deterministic continuation of the prefix, and any longer accepting string sharing that prefix must pass through the same deterministic states (determinism guarantees there is only one path to check, so nothing is missed). Hence the emitted token is the longest one matching at `pos`, and the tag attached is the highest-priority rule among those active in that accepting state, by construction of the tagging in Stage 3.

Honest tradeoffs. The subset construction trades exponential worst-case state blowup for O(n) runtime with no backtracking — for typical lexical specs this is a clear win, but pathological regex sets (as in some regex-heavy log-parsing or firewall-rule DFAs) can produce enormous tables, motivating either accepting a bigger table, keeping the NFA and simulating it directly in $O(nm)$ time (Thompson's own runtime NFA simulation, used by `grep -E` style engines to avoid blowup), or using lazy/on-the-fly determinization, which builds only the DFA states actually visited on real input.

Consider a tiny lexical spec, in priority order: 1. `IF` → `if` 2. `ID` → `[a-zA-Z][a-zA-Z0-9]*` 3. `NUM` → `[0-9]+` 4. (whitespace skipped, omitted for brevity) Scan the input `if9 x`.

Two subtleties this trace exposes:

• At step 2 the DFA state is accepting and tagged `IF` — this is the classic trap for a naive implementation that stops scanning the moment it sees an accepting state. Maximal munch instead keeps going, and at step 3 finds a longer match (`if9`), which is tagged `ID` because the `IF`-branch has died (there is no transition for `9` after matching `f`). The final answer, correctly, is that `if9` is one identifier token, not the keyword `if` followed by garbage `9`.
• Rule priority (`IF` before `ID`) only matters when both rules accept the same longest string — e.g., input `if` alone would tie at length 2 between `IF` and `ID`, and priority correctly picks `IF`. The example shows priority is a tie-break at equal length, never a substitute for maximal munch.

The theory underlying scanner construction traces back to the origins of automata theory and formal language theory in the mid-20th century, later crystallized into an engineering discipline by the Unix tool-building tradition.

Every production compiler front end uses this pipeline in one of two modes. Generated-table mode: tools like `flex`, ANTLR's lexer stage, and the JVM's `javac` lexer perform the NFA-to-DFA construction (often followed by minimization) at build time, emitting a transition table baked directly into the compiled scanner, so runtime cost is a tight loop of array lookups. Hand-written or hybrid mode: production compilers such as GCC and Clang/LLVM often hand-code the equivalent DFA logic directly in C/C++ for maximum control over error messages and performance, but the underlying state machine is the same automaton-theoretic object; some, like Clang, also special-case very hot paths (identifiers, whitespace) while still falling back to systematic DFA-style dispatch for the long tail of token kinds. Beyond compilers, the exact same theory powers text-search tools (`grep`, `ripgrep`), regex engines embedded in scripting languages (though many, like PCRE, trade the guaranteed-linear DFA approach for backtracking NFA simulation to support extra features such as backreferences), network intrusion detection systems that match packet payloads against thousands of signature regexes simultaneously (compiled into one large combined automaton, exactly as in Stage 2 of this article), and streaming log-analysis pipelines that must classify lines in a single linear pass. Anywhere a system must classify a prefix of a stream against a fixed menu of patterns in real time and bounded memory, this construction — or a close descendant of it — is doing the work. The token stream this machinery produces is exactly the input consumed by the next stage of compilation, covered under Context-Free Grammars for Parsing.

Ask the tutor: Can you show how the subset construction handles a regex with nested Kleene stars, like `(a|b)*abb`, step by step?