There is a line of code almost all of us have written at some point that looks completely harmless: preg_match('/^(\w+\s?)*$/', $text), or its JavaScript cousin /^([a-z]+\s?)+$/. With a ten-character string it answers in microseconds. With a thirty-character string it can take hours. It is not a bug in the machine or the interpreter: it is the way the regular expression engine underneath searches. Understanding how it decides where to try each match is the difference between a validator and a denial of service.
A pattern is a program in miniature
A regular expression is not a search string with wildcards: it is the description of a formal language. The mathematician Stephen Kleene defined the operations that sustain it in 1951 (concatenation, alternation and the Kleene star), and in 1968 Ken Thompson turned them into something executable inside grep, the tool that still searches text on every Unix server. That foundational work fixed the key idea: a pattern can be transformed into a finite state machine, a graph of states and transitions that consumes the text character by character and ends either in an accepting or a rejecting state.
That is where a promise almost nobody exploits comes from: if the pattern is a graph, walking it costs at most n characters multiplied by m states. Linear time, predictable, no surprises. The catch is that not every engine is built that way.
Thompson’s construction: from text to automaton
Thompson proposed translating each operator into an automaton fragment with a single entry and a single exit, then stitching the fragments together: concatenation joins one fragment’s exit to the next one’s entry, alternation forks, and the star loops back through empty transitions (the so-called epsilon transitions, which consume no character). The result is an NFA (Nondeterministic Finite Automaton): a machine in which, from a given state and with a given character, several valid paths may exist at once. A word matches the pattern if some path leads from the start state to the end state.
That “some path” can be resolved in two ways. The first is backtracking: the engine picks a branch, moves forward and, if it was wrong, undoes the work and tries another. That is what Perl, PCRE, Python’s re, Java, .NET, PHP and JavaScript’s engine do. The second is simulating the whole automaton: keeping track, at each step, of the set of all reachable states and advancing the entire set at once. That is what RE2, Go, Rust’s regex crate, Hyperscan and the classic POSIX tools do.
Why backtracking goes exponential
With the string aaaaaaaaaaaaaaaaaaaaaaaaaaaaX and the pattern ^(a+)+$, the engine first tries a single block of a, then two, then three… When the trailing X fails, it backtracks and splits the letters a different way. The number of ways to split n letters into groups is on the order of 2n: with 30 letters that is over a billion combinations, and each one is walked in full before being discarded. That behaviour has a name of its own, ReDoS (Regular Expression Denial of Service), and it has taken down real services: Cloudflare’s global outage in July 2019 started with a rule in its firewall (WAF) written as a regular expression that suffered catastrophic backtracking, and Stack Overflow’s 2016 blackout had a similar origin.
The important part is that the pattern is not “bad” for being complex, but for being ambiguous: if the same piece of text can be split in many ways among nested quantifiers, backtracking investigates all of them. An automaton engine is unimpressed: it holds a set of states, marks the subset it has already visited and discards repeats. It never explores the same state twice for the same position in the text.
What an automaton cannot do
So why do we keep using backtracking engines? Because some constructs break regular language theory. The best known is the backreference: (\w+)\s+\1 looks for a repeated word and demands that the second piece be exactly equal to the captured one. The automaton would have to “remember” a piece of text of variable length, something a finite state graph cannot represent; the language stops being regular and the matching problem becomes NP-complete. The same happens with variable-length lookaround, pattern recursion ((?R)) or PCRE subroutines.
That is why Rust and Go gave up those features in their default engines: they prefer not being able to write a pattern over that pattern being able to hang the process. And that is why RE2 proves you can have almost everything: linear NFA simulation, captures included, using a trick (the lazy DFA) that builds the relevant state sets into a cache instead of materialising all 2m possible states in advance.
Details that decide real-world speed
Beyond the algorithm, some design decisions show up day to day. Modern engines compile the pattern to bytecode and some translate it into machine code on the fly: PCRE2’s JIT runs several times faster than the interpreter, and JavaScript’s V8 engine (Irregexp) generates native code for every compiled pattern. The search strategy matters too: without anchors (^, $, \b), the engine tries the pattern at every position of the text, so anchoring is usually the cheapest optimisation there is.
And then there are differences in meaning. Quantifiers are greedy by default (they devour as much as possible and then backtrack), but a question mark makes them lazy and changes which match you get. Shorthand classes such as \w or \d are not universal: in Unicode mode they can match accented letters or digits from other alphabets, while in ASCII mode they are limited to [0-9A-Za-z_]. Across millions of lines, that difference produces different results, not just different timings.
How to choose an engine (and a pattern) without risking the server
The practical rule fits in two sentences. If you write the pattern and the text comes from inside your system, any engine will do. If a third party controls the text — a form, an HTTP header, an external log — the pattern becomes an attack surface, and you want an engine with a linear-time guarantee or, at the very least, a time limit and a cap on input length. Languages whose standard libraries backtrack have alternatives: RE2/J in Java, the regex package with a timeout in Python, Rust’s and Go’s automaton engines in new services.
When reviewing an inherited pattern, three signals reveal the risk: nested quantifiers ((a+)*, (\w+\s?)*), alternations inside repeated groups ((a|a)*) and broad star wildcards such as .* in front of text that may fail. They are fixed by anchoring, using atomic groups ((?>...)) or possessive quantifiers (a++, which never backtrack), and above all by measuring with long, hostile inputs before putting them into production. A regular expression engine is, literally, a small interpreter able to run a program written by whoever controls the pattern; treating it as such is the only way an email validator stops being a time bomb.
