Patterns are machines
A regular expression like (a|b)*abb describes a language with three operations: concatenation (one thing after another), alternation | (one or the other) and the star * (zero or more repeats). Stephen Kleene proved in 1956 that regular expressions describe exactly the languages finite automata recognise — the same regular languages, from a different angle.
Ken Thompson turned that theorem into a program in 1968: compile a regex into an NFA, then run the NFA. Thompson's construction is still how engines like RE2 and Go's regexp guarantee linear time on any input. Today you'll write it.
One start, one end
The trick is that every piece of the regex becomes a small NFA with exactly one start state and one end state. Bigger pieces glue smaller ones together with ε moves, never touching their insides. A provided parser turns the pattern into a tree of lit, cat, alt, star, empty and class nodes; build walks the tree and makes the pieces.
- lit a: start —a→ end.
- empty: start —ε→ end.
- cat AB: start —ε→ A, A's end —ε→ B, B's end —ε→ end.
- alt A|B: start —ε→ A and B; both ends —ε→ end.
- star A*: start —ε→ A and —ε→ end (zero times); A's end —ε→ A's start (again) and —ε→ end.
- class [a-c]: one move per character in the set.
Each piece adds at most a couple of states and four ε moves, so the NFA is about twice the size of the pattern — that's why compilation is fast.