2.5 Regex to NFA to DFA in Lexical Analysis

Now we can connect the theory to the first real compiler phase. A lexer takes source text and produces tokens. A lexer generator takes regular expressions for token kinds and produces code that performs that scan. The standard route is:

token regexes
  -> NFA fragments
  -> combined NFA
  -> DFA by subset construction
  -> minimized/compressed DFA
  -> table-driven or code-generated scanner

Not every production lexer literally follows every step at runtime, and hand-written lexers may use direct conditionals instead of generated tables. Still, this route explains why regular expressions, NFAs, DFAs, priority, and longest match belong together.

Building NFAs from Regex

Thompson construction builds an NFA by composing fragments. Each fragment has an entry and an exit. Symbol fragments consume one character. Union adds a new entry that branches with epsilon edges. Concatenation connects one exit to the next entry. Star adds epsilon edges that allow zero repetitions, one repetition, or many repetitions.

For the regex:

(a | b)* abb

the construction begins with fragments for a and b, combines them into a union, wraps that union in a star, then concatenates fragments for a, b, and b. The result is not necessarily small, but it is easy to build correctly. Correctness is more important than beauty at this stage because later subset construction and minimization can reshape the automaton.

Combining Token Rules

A lexer does not usually build one automaton per token and try them separately. A common construction creates a new combined start state with epsilon transitions into each token's NFA. Each token NFA has an accepting state labeled with its token kind and priority.

For example:

IF      = if
IDENT   = [A-Za-z_][A-Za-z0-9_]*
INT     = [0-9]+
EQEQ    = ==
EQ      = =
WS      = [ \t\r\n]+

The combined NFA can explore all token patterns from the same source position. After conversion to a DFA, a single deterministic machine represents all those competing token languages. Some DFA states may correspond to multiple NFA accepting states, which means multiple token rules match the same prefix.

That is where lexer policy enters.

Longest Match and Priority

Most programming-language lexers use maximal munch, also called longest match. Starting at the current source position, the scanner consumes the longest prefix that matches any token rule. If several rules match the same longest prefix, a priority rule breaks the tie, often by declaration order.

This policy avoids bad tokenization. Suppose the input is:

ifx

If the scanner greedily returned IF after seeing if, the remaining x would become IDENT(x). But most languages want ifx to be one identifier. Longest match chooses IDENT(ifx) because it is longer than IF.

Now consider:

if

Both IF and IDENT match length 2. Longest match cannot decide, so priority decides. If IF has higher priority than IDENT, the token becomes IF. Another common design scans it as IDENT(if) and then checks a keyword table to rewrite it to IF. Both strategies are valid if they are consistent and tested.

Scanner Output and Error Boundaries

A lexer should not merely accept or reject an entire file. It should produce a stream of tokens with source spans:

FN     "fn"     line 1, col 1..2
IDENT  "main"   line 1, col 4..7
LPAREN "("      line 1, col 8
RPAREN ")"      line 1, col 9
ARROW  "->"     line 1, col 11..12
IDENT  "int"    line 1, col 14..16

Source spans make diagnostics possible. If the lexer finds an unknown character, an unterminated string, or an invalid numeric literal, it should report where the problem begins and often where scanning recovered. The parser and type checker will later depend on these spans for their own diagnostics.

Some token rules are skipped rather than emitted. Whitespace and comments usually affect line/column tracking but do not become parser-visible tokens. Newlines may be significant in some languages, in which case the lexer must emit them or synthesize layout tokens such as INDENT and DEDENT.

One Combined Automaton, Many Token Rules

Production lexer generators do not usually run one DFA per rule. They build an NFA for every token pattern, attach an accepting token kind and priority to each, add a fresh shared start with epsilon edges to all rule starts, determinize the result, then minimize or compress it. A DFA state may contain accepting NFA states for several rules; the chosen token is the highest-priority rule among the longest accepted prefix.

For input >=, a combined machine may pass through an accepting > state and then an accepting >= state. The scanner records both positions and returns the latter because it is farther. For ifx, the identifier rule reaches acceptance after three characters while the keyword rule accepts after two, so identifier wins before priority even matters. These traces should be unit tests, not folklore.

Generated-Scanner Engineering

• Store character classes rather than a full Unicode transition column when possible.

• Emit a clear failure path for “no token matches at this offset”; never loop forever on a bad character.

• Preserve rule names and source locations in generated metadata so a tokenization bug can be tied back to the grammar rule that won.