From Regular Expression to DFA Table: Inside a Lexer Generator

A lexer generator takes a list of patterns and emits a scanner that never consults the patterns again. What it emits is a table plus a loop, and the loop is short: read a byte, look up a transition, repeat. The table is a deterministic finite automaton over the byte alphabet, and its existence is the reason a generated scanner’s speed is independent of how many patterns were declared. Fifty patterns and five hundred patterns produce the same inner loop; only the table size differs.

Three constructions in sequence

The path from a regular expression to a table has four stages, and each one has a distinct cost.

Thompson’s construction turns each pattern into a nondeterministic automaton with epsilon transitions. Subset construction turns the union of those automata into a deterministic one. Minimisation, optional in principle but almost always worth it, merges states that cannot be distinguished by any future input. Table encoding then packs the transition function into arrays that a C loop can index without pointer chasing.

Each stage preserves the recognised language, so the correctness argument is local to each transformation. This is why lexer generators are considered trustworthy: no stage reasons about the whole language, only about one construction rule.

Thompson’s construction: two states per symbol

Thompson’s construction builds an automaton recursively from the syntax tree of the pattern. A literal symbol becomes a start state and an accept state joined by that symbol. Concatenation joins the accept of one fragment to the start of the next with an epsilon edge. Alternation adds a new start with epsilon edges to both branches and a new accept with epsilon edges from both. Kleene star adds a start and accept with epsilon edges that loop back.

The invariant is that each fragment has exactly one entry and one exit, which is what makes the composition rules simple. The size bound follows: at most two states per symbol or operator in the pattern, so a pattern of m symbols produces at most about 2m states. A specification with a few dozen patterns of a few dozen characters each lands in the low thousands of NFA states.

Epsilon edges are the awkward part. They carry no input, so a simulation must follow them freely, and the set of states reachable without consuming input is called the epsilon closure of a state set. Subset construction exists to remove them.

Subset construction: states become sets

A deterministic automaton is in one state at a time. A nondeterministic one is in a set of states. Subset construction simply makes that set the state: each DFA state is a set of NFA states, closed under epsilon transitions, and the transition on byte a is the epsilon closure of every NFA state reachable on a from any member of the set.

def determinize(start, alphabet, move, eps):
    """start: NFA state; move[s][a] -> set of states; eps[s] -> set of states."""
    def closure(states):
        stack, seen = list(states), set(states)
        while stack:
            s = stack.pop()
            for t in eps.get(s, ()):
                if t not in seen:
                    seen.add(t)
                    stack.append(t)
        return frozenset(seen)

    first = closure({start})
    dfa, work = {first: {}}, [first]
    while work:
        S = work.pop()
        for a in alphabet:
            nxt = set()
            for s in S:
                nxt |= move.get(s, {}).get(a, set())
            if not nxt:
                continue
            T = closure(nxt)
            dfa[S][a] = T
            if T not in dfa:
                dfa[T] = {}
                work.append(T)
    return dfa

The cost is the size of the result. A DFA can need up to 2^n states for an NFA of n states, and there are patterns for which that bound is reached. For lexer specifications it almost never is, because token patterns are shallow: an identifier, a number with a couple of forms, a string with escapes. The blow-up appears with patterns that count, such as “a string of as whose length is a multiple of seven”, and those are rare in a token specification for the same reason they are rare in a language.

The empty set is a legitimate DFA state and is where the transition function is undefined. Implementations usually give it an explicit error state, which lets the driver test one number instead of a range.

A state can accept several rules

Longest match needs one extra array. Each DFA state carries an accept entry: the rule number it accepts, or a sentinel for none. A state may accept more than one rule, in which case the lowest-numbered rule wins, which is the priority order from the specification.

The driver keeps the most recent accepting state and its input offset. On a transition into the error state, it rewinds to that offset and emits that rule. This is the whole of maximal munch at the automaton level, and it costs two words of mutable state per token rather than any rescanning.

Because a state can accept several rules, the automaton does not need a separate copy of the identifier path for every keyword. The keyword paths converge and the accept entry distinguishes them, which is exactly how the tables stay small.

The row is 256 entries wide

If the alphabet is bytes, each state’s transition row has 256 entries. Two bytes per entry for a thousand states is about half a megabyte, and every step of the scan touches a different entry, so the table is far larger than a cache and the accesses are effectively random. That is the dominant cost of a table-driven lexer, not the state count.

Two reductions bring it down by an order of magnitude or more.

The first is character equivalence classes. Two bytes that no state ever distinguishes can share a column. In practice most of the 256 byte values behave identically in every state: the digits form one class, the letters a few, the punctuation marks each their own. A typical specification collapses to fewer than 64 classes, and often to a few dozen, which cuts the row width by a factor of four or more before any packing.

The second is row compression. Many states have identical rows, especially inside the long paths that recognise identifiers and string bodies, where nearly every entry points to the same successor. Two standard encodings exploit that. Row displacement places each distinct row at an offset inside one flat array and adds a check array so that a lookup can verify the offset actually belongs to the state; rows that would collide are moved. Default compaction stores only the entries that differ from the state’s default successor, so a row with three exceptions costs six numbers rather than a full row.

After both, a scanner for a real language commonly fits in tens of kilobytes, small enough to stay resident in cache across a compilation. The trade is one extra indirection and a comparison per lookup, which is cheaper than the cache misses the uncompressed table would cause.

Minimisation and what it buys

Two states are equivalent when every suffix of input leads them to the same accept or reject outcome. Minimisation merges equivalent states and produces the unique smallest DFA for the language (unique up to the naming of states). Hopcroft’s algorithm does this in time proportional to n log n times the alphabet size for n states, which is negligible at build time.

The practical benefit is not only size. An unminimised subset construction often leaves pairs of states that differ only in members of their NFA-state sets that cannot affect acceptance, and those pairs inflate the table without changing behaviour. Running minimisation before encoding is the difference between a table that fits in a few tens of kilobytes and one that does not.

Minimisation does not change the longest-match bookkeeping: accept entries are part of the state’s identity for minimisation purposes, since two states that accept different rules are not equivalent.

Where determinisation stops being the right answer

The construction assumes the token language is regular. Nested comments, indentation-sensitive layout, string interpolation, and C’s typedef names all violate that assumption, and no table encodes them. Generators work around this with start conditions, which are several automata plus an explicit switch, or with hand-written hooks called from the scanner loop.

There is also a cost case against determinisation. When patterns are few and the input is short, a backtracking matcher is smaller and simpler; the automaton wins when the same scanner runs over millions of bytes and the pattern set is large. The measurement that matters is bytes scanned per table lookup, and for a compiler front end it is one, which is the property worth having.

The rule that decides which token the automaton emits at a given offset is covered in Maximal Munch and the Boundary Between Tokens. What happens when the scanner’s state must change under the parser’s influence is the subject of Context-Dependent Lexing.