Lexingspec

Finite Automata

The machine a lexer actually is: states, transitions on characters, and a set of accepting states. Drawing the identifier and number recognisers as automata makes the whole scanner mechanical, and makes the `123abc` problem visible before you write it.

The question

What does the state machine behind a lexer look like, and how do I derive one for a token family?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A five-tuple: a finite set of states, an input alphabet, a transition function, a start state and a set of accepting states. During a scan the *entire* representation of progress is one current state plus one input position — which is the concrete reason the phase costs constant memory and can be resumed anywhere.

What this phase may assume or do

A deterministic automaton must have at most one transition per (state, character) pair, and a scanner built on one may assume the input alphabet is fixed and known. Maximal munch adds an obligation the automaton alone does not carry: the scanner must remember the last position at which it was in an accepting state, and rewind to it when it reaches a state with no transition. Without that memory the automaton is correct and the scanner is not.

Key points

A finite automaton is states, an alphabet, a transition function, a start state and accepting states — nothing more.
During a scan the whole state is one integer plus one position, which is why lexing is constant-memory and restartable.
The identifier recogniser is two states; the number recogniser is four, one of which is deliberately non-accepting.
The implementation is a transition table indexed by state and character class, which is why generated scanners are fast.
Maximal munch requires two registers the automaton definition does not have: the last accepting position and its kind.
Rewinding to the last accepting position is what makes 1..5 and 123abc come out the way they do.
Merging families is a union plus determinisation, and ties at equal length are broken by a fixed rule priority.

Two automata, drawn out

A lexer's automaton is usually presented as one machine for the whole token set. It is much easier to derive one family at a time and then merge, and the two families worth doing by hand are identifiers and numbers, because between them they demonstrate everything: a self-loop, a required character, an optional suffix, and a state that is not accepting.

The identifier automaton is two states. From Start, a letter or underscore moves to Ident. From Ident, a letter, digit or underscore stays in Ident. Ident is accepting; Start is not. That is the entire recogniser for [A-Za-z_][A-Za-z0-9_]*, and it explains directly why _1 is a valid identifier and 1_ is not.

The number automaton is four states and has the interesting property. Int is accepting; Dot — reached after consuming a decimal point — is not, because 3. is not a complete float in a language that requires digits after the point. A scanner sitting in Dot when the input runs out must reject, and a scanner in Dot when it sees a non-digit must rewind to the last accepting position, which was the end of Int.

The number recogniser: four states, one of them non-accepting

UserLLMAgentToolDataDecisionHumanGuardrail

The transition table is the implementation

typicalThe Dot row is non-accepting in languages that require a digit after the decimal point — Rust, Go and Python all reject or reinterpret a bare 3. in expression position. C and C++ accept 3. as a valid floating constant, so their equivalent state *is* accepting. The automaton shape is the same; which states accept is a language decision, and it changes what 3..5 lexes as.

The picture becomes code by becoming a table. Rows are states, columns are character classes, cells are the next state or an error. The scan is then a two-line loop: look up the cell, move. That is what a generated scanner is, and it is why generated scanners are fast — the inner loop is a table index with no branching on token type at all.

Character *classes* rather than characters are the practical detail. A table indexed by all 256 byte values times a few dozen states is large and mostly repetitive; a table indexed by class — letter, digit, underscore, dot, quote, other — is small, with a 256-entry class lookup in front of it. flex and re2c both do this, and it is why their table sizes are reported in kilobytes rather than megabytes.

Read the Int row of the table below carefully, because it contains the 123abc problem in one cell. On a letter, Int has no transition. The scanner therefore stops, and because Int was accepting, it emits NUMBER("123") and resumes at the a. The next token is IDENTIFIER("abc"). Nothing has gone wrong at the automaton level: 123abc is a perfectly good number followed by a perfectly good identifier, and the resulting parse error names the identifier rather than the number. Whether that is acceptable is a language decision, discussed in [[lexer-hazards]].

Transition table for identifiers and numbers, merged

State	letter or _	digit	.	anything else	Accepting?
Start	→ Ident	→ Int	error	other rules	no
Ident	→ Ident	→ Ident	stop	stop	yes — IDENTIFIER
Int	stop (see `123abc`)	→ Int	→ Dot	stop	yes — NUMBER
Dot	rewind to Int	→ Frac	rewind to Int	rewind to Int	NO — `3.` is incomplete
Frac	stop	→ Frac	stop	stop	yes — NUMBER

Maximal munch needs one extra register

The five-tuple definition says nothing about what to do when a transition is missing — a pure automaton simply rejects. A scanner cannot reject; it has to produce the longest token it did manage and continue from there. So a real scanner carries two extra values beyond the current state: the position of the last accepting state it passed through, and which token kind that state accepted.

When the transition function fails, the scanner emits the remembered kind, rewinds the input to the remembered position, and restarts from Start. If there was no remembered accepting state, it is a genuine lexical error. This is the whole of maximal munch as an algorithm, and it is three variables.

The rewind is where the cost is. A scanner that frequently enters long non-accepting runs before failing re-reads those characters, and in the worst case the scan becomes quadratic. flex --backup exists precisely to report which states can require this, so that patterns causing it can be rewritten. In practice, for normal programming-language token sets, backing up is rare and bounded — but it is real, and it is the reason 1..5 needs thought.

The scanner loop with the last-accept register

1state = Start
2lastAcceptPos = -1
3lastAcceptKind = none
4pos = start
5 
6while true:
7    next = table[state][classOf(src[pos])]
8    if next == ERROR:
9        break
10    state = next
11    pos = pos + 1
12    if isAccepting(state):
13        lastAcceptPos = pos
14        lastAcceptKind = kindOf(state)
15 
16if lastAcceptPos < 0:
17    report lexical error at start, advance one character
18else:
19    emit token(lastAcceptKind, src[start .. lastAcceptPos])
20    resume scanning at lastAcceptPos      // this is the rewind

Three variables turn an automaton into a scanner. Note that pos may be well past lastAcceptPos when the loop breaks — those characters are re-read by the next token's scan, and that re-reading is exactly what flex --backup reports on.

Merging the families

A real lexer needs one automaton for all token kinds, not one per family, and the construction is the union: make a new start state with epsilon transitions to each family's start state, then determinise. That is Thompson's construction followed by subset construction, which is [[nfa-vs-dfa]] in full.

The merge introduces one new question: when two patterns accept at the same length, which wins? Maximal munch does not decide it, because the lengths are equal. The universal answer is a fixed priority — in flex, the earlier rule in the file; in a hand-written scanner, the order of the branches. This is exactly the mechanism that makes a keyword pattern beat an identifier pattern, and it is why in a generated lexer the keyword rules are written above the identifier rule.

It is also the reason the keyword-table approach is preferred in hand-written scanners. Twenty keyword patterns merged into one automaton produce a state machine with a state for every prefix of every keyword — i, if, in, int, inte… — which is a trie, and correct, and larger than an identifier automaton plus a hash lookup. Both are fine; the table is smaller and makes contextual keywords possible.

How it works

The steps, in the order the compiler takes them.

Write each token family as a pattern, then draw its automaton: one state per meaningful phase of the match.
Mark exactly the states that represent a complete token as accepting, and be deliberate about the ones that do not — a trailing decimal point is the standard case.
Merge the families by adding a start state with epsilon transitions to each family start, then determinise with subset construction.
Assign a priority to each accepting state so that ties at equal match length resolve to one kind.
Build the transition table over character classes rather than raw characters, with a 256-entry class map in front of it.
Implement the scan loop with the last-accept registers, rewinding on transition failure and reporting a lexical error only when no accepting state was ever reached.
Minimise the automaton if table size matters; Hopcroft's algorithm does it in O(n log n).

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A state that should be non-accepting is marked accepting, so 3. lexes as a float and 3..5 becomes a float followed by a dot rather than the range the author wrote.
The scanner does not rewind on transition failure, so a partial match consumes characters that belonged to the next token and the error surfaces one token later than the mistake.
The last-accept registers are not reset between tokens, and after one long token every subsequent short token gets the wrong kind — a bug that only appears in a particular token ordering.
A pattern causes frequent backing up and lexing becomes quadratic on large machine-generated files, showing up as a build that is fine on hand-written sources and unusable on generated ones.
Two patterns accept at the same length with no priority defined, so the tool picks arbitrarily and a keyword lexes as an identifier — every use of that keyword becomes a confusing parse error.

When it helps

Deriving a scanner for a new token family: drawing the states first makes the accepting-state decisions explicit instead of accidental.
Debugging a scanner that takes the wrong length: the automaton view localises it to a missing transition or a mismarked accepting state in seconds.
Reasoning about incremental rescanning, where "what is the state at this offset" is the question an editor needs answered.

When it hurts

Drawing automata by hand for a full language with a hundred operators is not a good use of time; that is exactly what a generator does correctly and instantly.
For constructs that are not regular — interpolation, nested comments — an automaton is the wrong model and forcing it produces a state explosion instead of a counter.

What it costs

Every one of these is paid by something.

A table-driven automaton buys a branch-free inner loop and correctness by construction, and costs table memory plus a build step to generate it.
Character classes buy a much smaller table and cost one extra indirection per character, plus the requirement that no pattern needs to distinguish two characters in the same class.
Minimising the automaton buys a smaller table and costs construction time, and it destroys the correspondence between states and the patterns they came from — which makes the generated scanner harder to debug.
Merging keywords into the automaton buys one uniform machine and costs a state per prefix of every keyword; a separate hash lookup costs one lookup per identifier and keeps the automaton small.

What else you could do

What a different compiler or language does instead, and when that is better.

A hand-written switch-based scanner, which is the same automaton with the states implicit in the program counter. Easier to debug and to give good errors, and the accepting-state decisions are now implicit rather than checked.
A backtracking regex engine per token family, tried in order. Simple to write, considerably slower, and dangerous on untrusted input — see [[regular-languages]].
A trie over the operator and keyword vocabulary, walked directly. For the fixed-symbol part of a language this is often the clearest implementation and gives longest-match for free.

See it for yourself

The flag, dump or tool that shows you this directly.

re2c --emit-dot patterns.re | dot -Tsvg -o fa.svg renders the generated automaton — the picture in this lesson, for your own patterns.
flex -v grammar.l reports the DFA state count and the compressed table sizes; flex --backup lists the states from which rewinding can occur.
flex -d makes the generated scanner narrate which rule matched at run time, which is the accepting-state decision printed per token.
python3 -m tokenize on a file containing 3., 3..5 and 123abc shows what Python's automaton decided for each of the boundary cases in this lesson.
Our lexer stepper at /compilers/lexer shows the current state and the last accepting position as it walks, which is the loop in this lesson executing.

Plausible wrong readings

Stated the way a confident engineer states them.

"The automaton implements maximal munch." It does not. The automaton recognises; maximal munch is the scanner's rewind policy, and it needs two registers the automaton definition has no place for.
"Every state a scanner passes through is accepting." The interesting states are the ones that are not — a trailing decimal point being the standard example, and the reason 1..5 works.
"A DFA cannot be wrong, so a generated lexer cannot be wrong." The automaton is correct for the patterns given. Which states accept, and the priority between them, are the decisions, and both are yours.
"Backing up is a theoretical concern." It is what flex --backup exists to report, and it is the difference between linear and quadratic scanning on the wrong pattern set.

Misconceptions

The claim, and what is actually true.

A DFA has to be drawn by hand.

It is derived mechanically from the patterns by Thompson's construction and subset construction. Drawing one by hand is a way to understand a family, not a way to build a lexer.

More states means a slower scanner.

A table-driven scan is one lookup per character regardless of state count. More states costs table memory and cache pressure, not per-character work.

If the automaton accepts, the token is right.

The automaton may accept at several lengths. Which one the scanner emits is decided by the rewind policy, and that is where 123abc and 1..5 are settled.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A finite automaton is a set of states with arrows labelled by characters. Start in the start state, follow an arrow for each character, and if you end in an accepting state the input matched. An identifier recogniser is two states; a number recogniser is four. That is what a lexer is underneath.

practical

When deriving an automaton for a token family, spend the time on which states accept. A state reached after a decimal point with no digits yet should not accept, or 3..5 breaks. Then implement the rewind: remember the last accepting position and kind, and when a transition fails, emit that token and resume there. Those three variables are the whole difference between a recogniser and a scanner.

advanced

The property that makes automata the right model for modern tooling is that the state is a single small value. An incremental lexer can store the automaton state at the start of each line and, after an edit, resume from the nearest unaffected line rather than the file start — and can stop rescanning as soon as it reaches a line whose stored state matches the recomputed one, because from that point the token stream is provably unchanged. This is exactly what editors and tree-sitter do. It works only while the scanner state really is small: add a mode stack for string interpolation or a comment depth counter and the state becomes a structure that must be serialised and compared, which is why tree-sitter requires external scanners to implement explicit serialise and deserialise functions with a fixed size budget. The formal property becomes an API constraint.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

specThe five-tuple definition, the equivalence with regular expressions and Hopcroft's minimisation bound are formal results and do not vary by tool. What varies is which states a language marks accepting — the trailing-decimal-point case genuinely differs between C, which accepts 3., and Rust and Go, which do not.

implementationThe table-over-character-classes design described here is what flex and re2c generate as of their current releases, with flex reporting compressed table sizes under -v. A hand-written scanner has the same automaton with states encoded in control flow and no table at all, which is why its performance profile differs even though the recognised language is identical.

simplifiedThe number automaton here handles decimal integers and simple floats. A real numeric literal recogniser also covers hexadecimal, binary and octal prefixes, exponents, digit separators such as 1_000_000, and type suffixes — typically fifteen to twenty-five states rather than four, though the structure and the accepting-state reasoning are unchanged.

If you were asked this in an interview

Draw the automaton for a floating-point literal and tell me which states are not accepting.
What does a scanner have to remember beyond the current state, and why?
How does your automaton lex 123abc, and is that the right answer?

Connections

DSAtrie dfs

API Designapi-state-machines