Thompson's NFA Construction

Ken Thompson (Unix grep author) figured out in 1968 how to compile a regex into an NFA (Nondeterministic Finite Automaton): a graph of states + ε (epsilon) transitions you can take without consuming input.

For each regex piece, build a sub-NFA with one entry and one exit:

literal 'a':       (start) --a--> (end)

a|b:               (start) --ε--> (a-NFA) --ε--> (end)
                          --ε--> (b-NFA) --ε-/

ab:                (a-NFA) --ε--> (b-NFA)

a*:                (start) --ε--> (a-NFA) --ε--> (end)
                          ↑________ε________|
                          |__________________ε__> (end)

a+:                (a-NFA) --ε--> (start) of a-NFA
                                  loop AND fall-through to end

a?:                (start) --ε--> (a-NFA) --ε--> (end)
                          --ε--> (end)

To MATCH: start at the entry state. The "current set" is all states reachable via ε-transitions. For each input character, advance every state in the current set that has a transition on that character. If the exit state ever appears in the current set, we have a match.

This is the linear-time algorithm. No backtracking, no catastrophic explosions. Runtime: O(text_length * num_states), and num_states is bounded by 2 * regex_length.