Regular Expressions as a Backtracking Virtual Machine

The specification defines matching as a program, not a language

Section 22.2 of ECMA-262 does not describe a regular expression as a set of strings. It compiles the pattern into a Matcher: an Abstract Closure taking a MatchState (the input, an end index, and the captures so far) and a MatcherContinuation, and returning either a MatchState or failure. Every construct is a rule for building a Matcher from sub-Matchers. Concatenation AB builds a matcher that runs A with a continuation that runs B. Alternation A|B runs A; if A's continuation ultimately fails, it runs B: alternatives are ordered, and the first that leads to overall success wins, not the longest. Quantifiers are defined by RepeatMatcher, which for a greedy A* tries one more A first and the continuation second, and for a lazy A*? tries the continuation first. Backtracking is not a mechanism added on top; it is simply the continuation returning failure and the caller trying its next choice. This is why ECMAScript regexes can express backreferences ((a+)\1) and lookaround, which are not regular, and why their running time is not bounded by the length of the input.

// Leftmost-first, not longest: the spec tries alternatives in order and takes the first success.
console.log("/a|ab/ on 'ab' matches:", "ab".match(/a|ab/)[0], "| POSIX leftmost-longest would give 'ab'");
console.log("/ab|a/ on 'ab' matches:", "ab".match(/ab|a/)[0]);

// A backreference makes the language non-regular: (a+)\1 is "a repeated an even number of times".
console.log("/(a+)\\1/ matches 'aaaa' as", JSON.stringify("aaaa".match(/^(a+)\1$/)?.[0]), "and 'aaa' as", "aaa".match(/^(a+)\1$/));

// Greedy takes as much as possible then backs off; lazy takes as little as possible then extends.
const html = "<b>bold</b><b>x</b>";
console.log("greedy:", html.match(/<b>.*<\/b>/)[0]);
console.log("lazy:", html.match(/<b>.*?<\/b>/)[0]);

// Captures inside a quantified group keep the LAST iteration's value (RepeatMatcher resets them per iteration).
console.log("(\\w)+ on 'abc' captures:", "abc".match(/(\w)+/)[1]);
// Named groups, and the d flag for match indices (ES2022).
const m = /(?<year>\d{4})-(?<month>\d{2})/d.exec("on 2026-09-04");
console.log("named groups:", m.groups.year, m.groups.month, "| indices:", JSON.stringify(m.indices.groups.year));

Catastrophic backtracking: where the exponent comes from

Because failure at the end of the input sends control back to the most recent choice point, a pattern with nested or overlapping quantifiers that ultimately fails explores every way of dividing the input between them. (a+)+b against aaaa…a (no b) tries every composition of n as a sum of positive parts: 2ⁿ⁻¹ paths. (a|a)*b doubles at each character. (\w+\s?)*$ against a line with a trailing non-word character, the Cloudflare pattern, is quadratic-to-exponential depending on the text. The specification does not merely permit this behaviour; it requires it, because the matcher's observable results (which alternative matched, what each capture holds) depend on exploring in this order. An engine that returned a different answer to save time would be non-conforming. What engines may do is recognise patterns whose answer is unaffected by the search order and match those with a linear-time automaton, or add a fallback that switches to linear matching after a backtracking budget is exceeded, as long as the result is the same.

// Nested quantifiers on a failing input. Doubling the input roughly doubles the time
// at each step until the engine either finishes or (in V8, with a budget) falls back.
// Kept small: at n = 24 the pure backtracking cost is ~2^23 steps.
function timeMatch(re, s) { const t0 = performance.now(); const r = re.test(s); return [performance.now() - t0, r]; }
for (const n of [14, 16, 18, 20, 22, 24]) {
  const input = "a".repeat(n);                          // no trailing b: every path must be tried
  const [ms, matched] = timeMatch(/^(a+)+b$/, input);
  console.log("n =", String(n).padStart(2), " (a+)+b :", ms.toFixed(2).padStart(8), "ms", matched ? "" : "(no match)");
}
// The same language, written without ambiguity, is linear: a+ b.
const [fastMs] = timeMatch(/^a+b$/, "a".repeat(100000));
console.log("n = 100000, ^a+b$      :", fastMs.toFixed(2).padStart(8), "ms  <- unambiguous, one path");
console.log("If the exponential rows stop growing past some n, this engine has a backtracking budget with a linear fallback.");

// (?=(a+))\1 matches a+ once, greedily, and never gives characters back: the lookahead's
// capture is fixed when the lookahead succeeds, and \1 then consumes exactly that text.
const atomic = /^(?:(?=(a+))\1)+b$/;
const t0 = performance.now();
const matched = atomic.test("a".repeat(24));
console.log("atomic version on 24 a's:", (performance.now() - t0).toFixed(3), "ms, matched:", matched);
const t1 = performance.now();
atomic.test("a".repeat(100000));
console.log("atomic version on 100000 a's:", (performance.now() - t1).toFixed(3), "ms (linear)");

How engines execute the matcher

No engine interprets the specification's closures literally. V8's Irregexp parses the pattern into an AST, performs analysis (which characters can start a match, minimum match length, whether captures are needed), and compiles it either to a compact bytecode interpreted by a register machine or, once a regex is hot enough, to native machine code specialised for that pattern, with the same tiering philosophy as the rest of the engine (chapter 8). Backtracking is implemented with an explicit stack of choice points, not recursion, so a pathological pattern exhausts a heap-allocated backtrack stack (throwing a RangeError in some engines) rather than the native stack. SpiderMonkey imported Irregexp in 2014 and still uses it. JavaScriptCore's YARR does the same interpret-then-JIT dance. All three additionally have or have had a linear-time engine (a Thompson-style NFA simulation over the same AST) used only when analysis proves the pattern has no backreferences or lookaround, either as the primary engine for such patterns or as a fallback after a backtracking budget is spent.

Two engine-level facts leak into program behaviour. First, regex compilation is expensive and cached: a regex literal in a loop creates a new RegExp object each iteration (the literal evaluates to a fresh object every time since ES5), but engines cache the compiled code by pattern and flags, so the cost is object allocation, not recompilation. Second, `lastIndex` is state on the object: a g or y regex used with test/exec continues from where it stopped, which is why reusing a global regex across unrelated strings produces alternating results. String.prototype.matchAll and replaceAll clone the regex (via SpeciesConstructor and lastIndex copying) precisely to avoid that shared state.

const g = /a/g;
console.log("global regex reused:", g.test("a"), g.test("a"), g.test("a"), "<- lastIndex advanced past the only 'a', then reset");
console.log("lastIndex after a failed test:", g.lastIndex);
g.lastIndex = 0;
for (const m of "a-a-a".matchAll(g)) void m;          // matchAll clones g (copying lastIndex) and advances the clone
console.log("matchAll clones the regex and leaves lastIndex at 0:", g.lastIndex);
// The sticky flag anchors at lastIndex exactly: a tokenizer primitive.
const tok = /\s*(\d+|[+*])/y;
const out = []; let m;
tok.lastIndex = 0;
while ((m = tok.exec("12 + 34*5"))) out.push(m[1]);
console.log("sticky tokenizer:", out.join(" "));

The `u` and `v` flags change the alphabet, not just the syntax

Without u, the matcher's alphabet is UTF-16 code units: . matches one code unit, [^x] can match half of a surrogate pair, and /^.$/ fails on 𝒳. With u (ES2015), the input is treated as a sequence of code points, \u{1D4B3} escapes are allowed, \p{Script=Greek} property escapes (ES2018) become available, and case-insensitive matching uses Unicode simple case folding instead of the ASCII-and-Latin-1 rules. The v flag (ES2024) is a superset that makes character classes a small set algebra: nested classes [[a-z]--[aeiou]] (difference), [\p{L}&&\p{Script=Latin}] (intersection), and string properties such as \p{RGI_Emoji} that match multi-code-point sequences (a flag emoji is two code points; a family emoji is seven). v also reserves more punctuation inside classes, so some u-valid patterns are v-syntax errors by design. The flags are therefore not decorations; they select which of three alphabets (code units, code points, or strings) the whole machine operates over.

const s = "𝒳";                                   // U+1D4B3, a surrogate pair in UTF-16
console.log("no flag:", s.match(/./g).length, "code units matched by . |", "/^.$/ :", /^.$/.test(s));
console.log("u:", s.match(/./gu).length, "code point matched by . |", "/^.$/u:", /^.$/u.test(s));
console.log("negated class without u splits the pair:", JSON.stringify("𝒳".replace(/[^a]/, "_")));
console.log("property escape needs u:", /\p{Script=Greek}/u.test("λ"), "| without u, \\p is just 'p':", /\p{Script=Greek}/.test("p{Script=Greek}"));
console.log("case folding under u:", /ſ/iu.test("s"), /ſ/i.test("s"), "(long s folds to s only in Unicode mode)");
const flag = "🇯🇵";                                  // two regional indicator code points
console.log("v matches the whole flag emoji:", /^\p{RGI_Emoji}$/v.test(flag), "| code points:", [...flag].length);
console.log("class set difference with v:", "hello world".match(/[[a-z]--[aeiou]]+/gv).join(","));
console.log("u accepts an unescaped ( in a class:", /[(]/u.test("("));
try { new RegExp("[(]", "v"); } catch (e) { console.log("v requires it escaped:", e.constructor.name, "- syntax is reserved for future set operations"); }