Regular Expressions
A regular expression is a small language: literal characters, a choice, and a repeat. Everything else is shorthand. What is not small is the question of how a machine decides whether a string matches, because there are two entirely different ways to do it and they give the same answers. One walks the pattern depth-first and reverses out of dead ends; the other keeps every state the input could be in and advances all of them together. On most patterns the first is quicker. On some patterns it takes more steps than there are atoms, and Thompson's 1968 paper is why the second exists. Nothing here is timed: the difference is combinatorial, so it is counted.
New to regular expressions? Start here
A regular expression is a small pattern language: literal characters, a choice between alternatives, and a repeat. That is nearly all of it, and everything else is shorthand built from those three.
The interesting part is not the notation, it is how a machine decides whether a string matches. There are two entirely different ways, they give the same answers, and on some patterns one takes a few hundred steps where the other takes more steps than there are atoms. This page runs both on the same input and counts.
Everything is a switch
Underneath all of it is one part: a switch that is either on or off, and that can be operated by another switch rather than by a finger. That is the whole of the hardware vocabulary. AND is two switches in a row, so both must be on. OR is two side by side, so either will do. NOT turns the answer around.
There is nothing else in the box. Adding, remembering, choosing and counting are all arrangements of those three, and the machines in this topic are those arrangements, in the order somebody had to think of them.
The machine for this idea on its own is Flip-Flop, if you would rather press it than read about it.
Every state at once, against the one that gives up and tries again
1 The pattern taken apart into states and the jumps between them
The pattern taken apart into states and the jumps between them. A jump marked empty costs nothing to follow, and a state can be reached more than once for free, which is the property the fast engine is built on.
2 Every state the input could be in, held at once, one character at a time
Every state the input could be in, held at once, one character at a time. The set can never be bigger than the machine, and that bound is the whole reason this is one pass.
| after | states held | steps so far |
|---|
3 The same pattern run by backtracking instead, and its steps counted
The same machine, walked depth-first with a stack instead of a set. Not a straw man: this is how a backtracking engine explores exactly the same states, and on ordinary patterns it does less work than the other one.
| input | state set | backtracking | ratio |
|---|
4 The input where the two diverge: one steady, the other doubling
Where the two diverge. One pattern lets the same run of characters be matched in an exponential number of ways, and a backtracker tries them.
| claim | held | measured |
|---|---|---|
| both engines agree about whether the input matches, in all 21 cases | yes | they explore the same machine; only the order differs |
| on the hard pattern the backtracker's steps grow faster than the input | yes | 2:14, 4:78, 8:1790, 12:36862, 16:720894, 20:gave up, 24:gave up |
| while the state-set engine's steps stay proportional to the work | yes | 2:18, 4:55, 8:189, 12:403, 16:697, 20:1071, 24:1525 |
| because it holds at most 25 states at once, out of 73 in the machine | yes | a state already in the set costs nothing to add again, so the set can never be larger than the machine. That bound is what makes the whole search one pass. |
| on ordinary patterns the backtracker is the CHEAPER of the two, in 14 of 14 cases here | yes | it stops at the first way that works, where the set engine carries every possibility to the end. Backtracking is not a worse algorithm; it is one whose worst case is unbounded, and that is a different complaint |
| this grammar has no backreferences and no lookaround, for two different reasons | yes | backreferences genuinely take a pattern outside the regular languages, and no automaton of this kind can express them. LOOKAROUND is a different case: bounded lookaround stays regular and can be compiled into an automaton, so it is absent here because this grammar is small, not because it could not be done. The first version of this line said both were impossible, which an outside review corrected. |
| the comparison is a step count and never a time | yes | a millisecond in a browser measures whatever else the machine was doing. The blowup here is combinatorial, so it is counted, and the number is the same wherever this page runs. |
What is real here, and what is not
Steps, never milliseconds
A time measured in a browser is a measurement of the browser. The difference between these two engines is combinatorial rather than constant-factor, so it is counted: the numbers on this page are the same wherever it runs, which a millisecond would not be.
Backtracking is not the worse algorithm
On every ordinary pattern here it does LESS work than the state-set engine, because it stops at the first way that works while the other carries every possibility to the end. Its problem is not that it is slow, it is that its worst case has no bound. Those are different complaints and the page prints both.
This grammar is deliberately small, and could not be larger
Literals, a choice, and the three repeats. No backreferences, which genuinely take a pattern outside the regular languages so no automaton of this kind can express them. And no lookaround, which is a different case: bounded lookaround stays regular and compiles into an automaton perfectly well, so it is missing here because the grammar is small rather than because it is impossible. An outside review caught this page treating the two as one.
The notation is older than the algorithm
Kleene's regular algebra is 1951 and Thompson's paper is 1968. The subject here is the simulation, not the syntax, and conflating the two is a common way of getting the history wrong by seventeen years.
The backtracker is given a budget
Two million steps, after which it reports that it gave up rather than hanging the page. That is not the algorithm failing gracefully -- a real one has no such budget, which is why a pattern like this one takes a service down.
Sources
- Ken Thompson, Programming Techniques: Regular Expression Search Algorithm, CACM 11(6):419-422, June 1968 — the construction this page simulates.
- Russ Cox, Regular Expression Matching Can Be Simple And Fast, 2007 — the modern account of why the two engines diverge, and the source of the pathological pattern used here.
- Logical Art, the studio this belongs to.