thompson.c

// Thompson's algorithm for NFA execution.

// Each NFA state is numbered 0 through n-1.
// An n-bit vector represents a superposition of NFA states, called a superstate.
// A state has a superstate as its successor, as a function of the input symbol.
// This induces a superstate-to-superstate successor mapping:

for (next_superstate = 0, successor = successors[symbol]; superstate; superstate >>= 1, successor++)
    next_superstate |= *successor & -(superstate & 1);

// Run this, starting with an initial superstate, for each symbol of the input string.
// The final superstate is accepting if any of its states are accepting. This algorithm
// runs in O(m n) time, where m is the length of the input string. The space required for
// the state successor table is O(k n log(n)) words for a k-symbol alphabet, likely k = 256.