Regex Engines

A regex pattern is just text — \d{3}-\d{3}-\d{4} is meaningless on its own. Something has to read that pattern, read your input string, and decide whether (and where) they line up. That something is the regex engine, and how it’s built has real consequences for correctness and performance, not just theory.

There are two broad families of regex engine you’ll encounter.

Backtracking engines

Most languages you’ll actually type regex into — JavaScript, Python’s re, Java’s Pattern, Ruby, and PCRE (used by PHP and many command-line tools) — use a backtracking NFA (nondeterministic finite automaton) engine. It works roughly like this:

1. Start at some position in the string.
2. Try to match the first piece of the pattern.
3. If it matches, move on to the next piece. If it doesn’t, or a later piece fails, backtrack — undo the last decision and try a different alternative.
4. Repeat until the whole pattern matches, or every alternative has been exhausted at every starting position.

This is why alternation (|) tries options in order, left to right, and stops at the first one that lets the rest of the pattern succeed — it’s not “smart” about picking the best overall match, it’s exploring a tree of possibilities one branch at a time.

Notice that a|ab matches just "a" inside "ab", not "ab". The engine tries the a branch first, it succeeds immediately, and it never even attempts the ab branch. Order matters in a backtracking engine in a way it wouldn’t in some other matching strategies.

The cost of backtracking

Backtracking is flexible — it’s what lets these engines support features like backreferences (\1) and lookaround ((?=...), (?<=...)), which you’ll meet in later lessons. But flexibility has a price: in pathological cases, a backtracking engine can end up retrying an exponential number of combinations before giving up. A classic example is a pattern like (a+)+$ tested against a long run of a characters followed by a character that breaks the match:

// Don't run this against long input — it can hang for minutes
/(a+)+$/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!");

This is called catastrophic backtracking, and it’s a real, recurring source of production incidents (search “ReDoS,” short for Regular Expression Denial of Service). You’ll learn how to spot and avoid these patterns later in the course — for now, just know that a pattern that looks correct can still be dangerously slow.

Finite-automaton engines

The other family — RE2 (used inside Google and available as a library for many languages), Rust’s regex crate, and Go’s regexp package — takes a different approach. Instead of exploring branches with backtracking, they compile the pattern into a finite automaton that examines each input character exactly once, tracking every possible match state simultaneously. The tradeoff: matching time is guaranteed to be linear in the length of the input, no matter how the pattern is written — but in exchange, these engines drop backreferences and some lookaround forms, because those features fundamentally require backtracking-style exploration.

Why this matters going forward

Every lesson from here on describes what a pattern means, but keeping the engine’s step-by-step, try-then-backtrack behavior in your head will help you predict which match it finds when there’s more than one possibility — especially once you get to quantifiers and groups, where greedy vs. lazy matching is really just a question of which order the engine tries things in.

What’s next

With the engine’s behavior in mind, the next lesson starts with the simplest building block of all: literals — matching exact characters, and the small set of symbols that aren’t literal at all.