Writing a Scanner

Everything so far has been a link in one chain. Now we forge the whole thing and get a working scanner out the other end. The pipeline is exactly the sequence of pages you have read: regular definitions for each token → Thompson's construction into one big \varepsilon-NFA with each token's accept state tagged by which token it recognises → subset construction into a DFA → minimization into a compact table. That table, wrapped in a driver loop, is the scanner. This page is about the two things the theory left out: how to combine many token patterns into one machine, and the small but crucial driver that turns "recognise a string" into "repeatedly bite off the next token" — with the longest-match backtracking and the input buffering that make it fast and correct.

One machine for all the tokens

A scanner does not run one automaton per token type. Instead lex takes the whole list of patterns — p_1, p_2, \ldots, p_n, each with an action — and builds the NFA for the alternation p_1 \mid p_2 \mid \cdots \mid p_n, but with a twist: each pattern's accept state is labelled with the token it recognises (and its rule number, to break ties). After subset construction, a single DFA state may therefore be accepting for several tokens at once — it carries the set of rule numbers whose NFA accept states it contains. Two rules resolve any clash, and you have met both already:

Longest match (maximal munch). Keep running the DFA as long as it can move; the token is the longest prefix that ended in some accepting state.
Rule priority. If that longest lexeme is accepted by several rules at once, choose the one with the lowest rule number — the pattern listed first in the spec (so keywords, listed before identifiers, win their spelling).

The longest-match driver: run, remember, backtrack

Here is the subtlety maximal-munch forces on us. The DFA might march happily forward, pass through an accepting state, and only later hit a dead end — by which point it has read characters past the last good token. So the driver must remember the last accepting state it saw and, on getting stuck, back up the input pointer to that point. The loop is:

state ← DFA start lastAccept ← none; lastPos ← none while state has a transition on the current char c: state ← move(state, c) advance the input pointer over c if state is accepting: lastAccept ← (token of state) // remember the WIN lastPos ← current pointer // and where it ended // stuck. Retreat to the last win: if lastAccept is none: report a lexical error else: roll the input pointer back to lastPos // give back the over-read chars emit token lastAccept for the lexeme up to lastPos resume scanning from lastPos

The "roll back" step is the whole reason a scanner needs to peek ahead and retreat. Consider a language with both < and <= as tokens: reading < then = reaches the le accept, but reading < then a letter must give back that letter and emit lt. Without the remembered lastPos, the scanner would either stop too early (missing <=) or consume the letter it should have left for the next token.

Table-driven vs direct-coded scanners

There are two ways to turn the DFA into a program, a classic engineering trade-off:

	Table-driven	Direct-coded
Form	a 2-D array `next[state][char]` read by one generic loop	the DFA compiled into control flow — a labelled block per state, `goto`/`switch` between them
Made by	`lex`, `flex`	`re2c`, hand-writing
Size	compact table, tiny code	larger code, no table lookup
Speed	a memory load per character (cache misses on big tables)	faster — branches predict well, values stay in registers

Both encode the same DFA and the same longest-match driver; they differ only in whether the transition function lives in a data array or in the instruction stream. Table-driven scanners are the textbook default because a generator can emit them trivially; direct-coded scanners win on raw throughput, which is why performance-critical tools generate them.

Input buffering and the sentinel trick

The driver reads and occasionally backs up over characters, so it needs the recent input still in memory — you cannot un-read from a stream. The classic solution is the two-buffer scheme: two halves of a buffer, each N characters, refilled alternately. Two pointers walk it — lexemeBegin (start of the current lexeme) and forward (the scanning head) — and backing up is just moving forward back toward lexemeBegin. The naïve version tests, on every character, both "have I run off the end of this half?" and "is this the character I want?" — two comparisons per byte.

The sentinel optimisation halves that. Place a special \texttt{eof} character at the end of each buffer half (and at the true end of input). Now the inner loop tests only against the sentinel; only when it hits one does it do the more expensive check of "real end of input, or just a buffer boundary to reload?". One comparison per character in the common case — a measurable win in a loop that runs once per source byte.

A table-driven scanner, running

Below is the real thing in miniature: a hand-built DFA table over a tiny token set — identifiers [a\text{-}z][a\text{-}z0\text{-}9]^{*}, numbers [0\text{-}9]^{+}, and the single character + — driven by the exact longest-match-with-backtracking loop above. Feed it ab12+7 and watch it bite off one token at a time.

// Character classes keep the table small. function classOf(c: string): "letter" | "digit" | "plus" | "space" | "other" { if (c >= "a" && c <= "z") return "letter"; if (c >= "0" && c <= "9") return "digit"; if (c === "+") return "plus"; if (c === " ") return "space"; return "other"; } // DFA: state 0 = start. -1 = no transition (stuck). // Accepting states carry a token name. const NEXT: Record<number, Partial<Record<string, number>>> = { 0: { letter: 1, digit: 2, plus: 3, space: 4 }, 1: { letter: 1, digit: 1 }, // identifier: letters/digits 2: { digit: 2 }, // number: digits 3: {}, // '+' (single char, no outgoing) 4: { space: 4 }, // run of whitespace }; const ACCEPT: Record<number, string> = { 1: "id", 2: "num", 3: "plus", 4: "ws" }; function scan(src: string): string[] { const out: string[] = []; let i = 0; while (i < src.length) { let state = 0, pos = i; let lastTok: string | null = null, lastPos = i; // run the DFA, remembering the last accepting position while (pos < src.length) { const nxt = NEXT[state]?.[classOf(src[pos])]; if (nxt === undefined) break; // stuck state = nxt; pos++; if (ACCEPT[state] !== undefined) { // a WIN — remember it lastTok = ACCEPT[state]; lastPos = pos; } } if (lastTok === null) throw new Error(`lexical error at '${src[i]}'`); const lexeme = src.slice(i, lastPos); // back up to the last win if (lastTok !== "ws") out.push(`${lastTok}(${lexeme})`); i = lastPos; // resume from there } return out; } console.log(scan("ab12 + 7").join(" ")); console.log(scan("hello99+42").join(" "));

Notice ab12 comes out as one id token, not id then num: state 1 keeps accepting through the digits, so maximal munch swallows all four characters. Whitespace is recognised (state 4) but its token is dropped before output. And each token ends by rolling i back to lastPos — the remembered last-accepting position — exactly the backtracking the driver spec called for.

Production compilers almost universally hand-write their scanners rather than generate them, and for good reasons. Speed: the lexer touches every byte of source, so it is a hot loop, and a hand-tuned direct-coded scanner (careful character-class tables, sentinels, no per-token allocation) beats a generic table interpreter. Error messages: a hand-written lexer can emit "unterminated string literal starting here" with a caret under the exact column, recover gracefully, and handle the thousand real-world quirks (digraphs, trigraphs, Unicode identifiers, raw strings, >> in nested templates) that a pure regex spec makes awkward. Tools like re2c sit in between — you write patterns in comments and it generates a fast direct-coded scanner you can still read and tweak. The lesson: lex is a wonderful way to prototype and to teach the theory, but the theory's real value is that it tells you exactly what your hand-written loop must do — longest match, rule priority, backtrack, buffer.

The driver's inner loop lives or dies by two conditions being checked in the right order with the right operator: "am I still inside the buffer?" and "does the DFA have a move on this character?" Write it as

while (pos < src.length && NEXT[state][classOf(src[pos])] !== undefined) { … }

and the logical && short-circuits: if pos is past the end, the second half is never evaluated, so you never index past the buffer. Swap in the bitwise & by mistake and both operands are always evaluated — the scanner reads src[pos] when pos is out of bounds (an undefined character, a wrong class, or a crash in a language with real arrays). Worse, & forces both sides to integers, so a truthy/falsy transition test silently becomes a numeric AND and the loop condition turns to nonsense.

The related bug is forgetting to back up at all: if the driver emits a token at the point it gets stuck rather than at the last accepting position, then <= vs <, or 3.14 vs 3., silently mis-tokenise. Always emit from lastPos (the remembered win), never from wherever the DFA happened to die.