Thompson's NFA, one character at a time

What you're looking at

Each circle is a state. Large circles read exactly one character, and the label on their arrow says which. Small circles are junctions: they read nothing, and their dashed ε-arrows are moves the machine may take for free. The machine starts at the state with the arrow coming in from nowhere. When the input runs out, the string matches if the double circle is lit.

The engine anchors at both ends, so the whole string has to match. Wrap a pattern in .*( … ).* to search inside a longer string instead.

Building the machine

Ken Thompson described this construction in 1968. It compiles a pattern bottom-up, and each piece becomes a fragment: a start state plus a list of arrows that don't point anywhere yet. Every operator does the same small thing. It makes a state or two, then aims the loose arrows. Here is what each operator produces on its own, drawn by the same engine as the machine above.

This is the whole of *, from nfa.go. The call to e.patch(s.ID) aims every loose arrow of the inner fragment back at the new junction, and that is the loop.

case nStar:
	e := b.build(n.left)
	s := b.newState(KindSplit)
	s.Out = e.start
	e.patch(s.ID)
	return frag{s.ID, []*int{&s.Out1}}

Running it without guessing

A backtracking engine follows one path at a time. When a guess fails it rewinds and tries the next one, and on patterns like (x+x+)+y the number of ways to split the input grows exponentially. Thompson's simulation never guesses. It carries the set of every state the machine could be in, and each character turns that set into the next one. A state enters the set at most once per character, so matching takes time proportional to the length of the input times the number of states, whatever the pattern is. Go's own regexp package is built on the same guarantee.

for _, id := range clist {
	s := n.States[id]
	if s.consumes(r) {
		nlist = m.add(nlist, s.Out, -1) // add follows ε-arrows too
	}
}
clist, nlist = nlist, clist

Watch the set stay small on the classic trap. Twenty x's with no y takes a backtracker millions of steps; here it is twenty steps, each touching a handful of states.

Load the backtracking trap

The source

The engine is a few hundred lines of Go with no dependencies: a recursive-descent parser, the construction, the simulation, and tests that check 3,000 random patterns against Go's regexp package. This page runs that exact code. Read it at github.com/swayam5342/thompson.