The short answer
Quick answer: A regular expression engine compiles your pattern into a small program and runs it against the text. There are two main designs. Backtracking engines, used by JavaScript, Python, Java, PCRE and .NET, try one way of matching, and if it fails, go back and try another. They support rich features but can take exponential time on certain patterns. Automaton-based engines, used by RE2, Go and Rust, track all possible matches at once and guarantee time proportional to the length of the text, but leave out features such as backreferences.
What a regex describes
A regular expression is a compact description of a set of strings. The building blocks:
| Syntax | Meaning |
|---|---|
abc | These characters in order |
a|b | Either one |
a*, a+, a? | Zero or more, one or more, zero or one |
[a-z], \d, . | A character from a set |
^, $, \b | Positions: start, end, word boundary |
(...) | Group and capture |
MDN's regular expressions guide is a good syntax reference. This article is about what happens when you run one.
Step 1: Compile the pattern
Like any language, a pattern is first parsed into a tree (see how compilers work) and then converted into something executable. The classic target is a finite automaton: a set of states with transitions between them labelled by characters.
For the pattern ab*c:
(start) --a--> (1) --c--> (match)
^ |
+-b+
State 1 loops on b and moves to the match state on c.
The natural form is a nondeterministic finite automaton (NFA), where a state may have several possible next moves. How the engine deals with those choices is the whole difference between the two designs.
Design A: Backtracking
A backtracking engine treats matching as a search. At every choice point it picks one option and remembers the alternative. If it later gets stuck, it returns to the most recent choice and tries the other.
Take a.*c against abcxc:
amatchesa..*is greedy: it grabs everything,bcxc.cneeds a character but the text is finished. Fail.- Backtrack:
.*gives back one character. Nowcmatches the finalc. Success.
This design makes powerful features easy to add: capture groups, lazy quantifiers, lookahead and lookbehind, and backreferences such as (\w+)\s\1 to find a repeated word. Backreferences go beyond what "regular" languages can express in theory, and only backtracking handles them directly.
Design B: Simulating all paths at once
The alternative, described in Russ Cox's well-known article Regular Expression Matching Can Be Simple And Fast, never backtracks. It reads the text one character at a time and keeps a set of all states the automaton could be in.
- For each character, every active state advances.
- States with no valid transition drop out.
- If the match state is ever active, there is a match.
The set can never be larger than the number of states in the pattern, so the total work is at most (text length × pattern size). No input can make it explode.
A further step converts the NFA into a deterministic finite automaton (DFA), where each state has exactly one transition per character. That is faster still, at the cost of potentially many states, so engines often build the DFA lazily and cache it.
| Backtracking | Automaton (NFA/DFA simulation) | |
|---|---|---|
| Worst-case time | Exponential | Linear in the text |
| Backreferences | Yes | No |
| Lookaround | Yes | Limited or none |
| Used by | JavaScript, Python re, Java, PCRE, .NET | RE2, Go, Rust regex, grep tools |
Catastrophic backtracking
Consider ^(a+)+$ against aaaaaaaaaaaaaaaaaaaaaaaaaaaa!.
The text can never match, because of the final !. But a backtracking engine does not know that. There are many ways to split a run of as between the inner + and the outer +, and the engine tries every one before giving up. Each extra a roughly doubles the work. Thirty characters can take seconds; forty can take hours.
Patterns at risk share a shape:
- Nested quantifiers:
(a+)+,(a*)*,(\w+\s?)*. - Overlapping alternatives under a quantifier:
(a|aa)+,(\d|\d\d)+. - Adjacent quantifiers that can match the same text:
\d+\d+,.*.*=.
The trigger is almost always a string that nearly matches and then fails at the end.
ReDoS: when it becomes a security problem
If an attacker can send input to a vulnerable pattern, they can pin a CPU core with a tiny request. This is a regular expression denial of service, described by OWASP. In single-threaded servers such as Node.js, one such request blocks every other user; see what is the event loop. It has caused real outages at large companies.
How to write safe, fast patterns
- Avoid nested quantifiers. Rewrite
(a+)+asa+. - Be specific. Prefer
[^"]*to.*when matching up to a quote. A narrower class leaves fewer ways to match. - Anchor when you can.
^and$stop the engine retrying at every position. - Limit input length before matching untrusted text.
- Use a linear-time engine for untrusted input. RE2 has bindings for many languages; Go and Rust use this design by default.
- Set a timeout where the engine supports one, as .NET does.
- Use atomic groups or possessive quantifiers (where available) to forbid backtracking into a group.
- Do not use regex for nested formats. HTML, JSON and programming languages need a real parser. Likewise, do not rely on pattern filters to stop attacks such as SQL injection; use parameterised queries.
Greedy vs lazy
Quantifiers are greedy by default: they match as much as possible, then give back as needed. Adding ? makes them lazy: match as little as possible, then extend.
Text: <b>one</b> and <b>two</b>
<b>.*</b> matches the whole line
<b>.*?</b> matches <b>one</b>
Lazy is not automatically faster. It changes which match is found, and it still backtracks. A negated class such as <b>[^<]*</b> is usually both clearer and quicker.
Other optimisations engines use
- Literal prefiltering. If the pattern must contain
error:, the engine first uses a fast substring search to find candidates. - Compile once. Compiling a pattern is not free. Build it outside the loop and reuse it.
Frequently asked questions
Why is my regex slow?
Most often catastrophic backtracking: nested or overlapping quantifiers combined with input that almost matches. Simplify the pattern or switch engines.
What is the difference between an NFA and a DFA?
An NFA can have several possible next states for a character; a DFA has exactly one. They recognise the same patterns, but a DFA is faster to run and can be much larger.
Can regular expressions parse HTML?
Not reliably. HTML allows arbitrary nesting, which regular expressions cannot describe. Use an HTML parser.
Are all regex engines the same?
No. Syntax and features differ between flavours, and so do performance guarantees. Test patterns in the engine you will actually use.
Conclusion
A regex is a tiny program, and the engine that runs it matters. Backtracking engines are flexible but can be driven into exponential time; automaton engines are predictable but more limited. Write specific patterns, avoid nested quantifiers, and never run a backtracking regex on untrusted input without a length limit or timeout.
Related articles
- How a Compiler Turns Your Code Into Machine Instructions
- What Is the Event Loop and Why Is Node.js Single-Threaded?
- What Is SQL Injection and How to Prevent It
- How Hash Maps Achieve O(1) Lookups
Sources and further reading
