Writing a Tiny Regex Engine to Actually Understand How Regex Matching Works

Regex syntax gets memorized rather than understood — most people can write a*b without being able to explain exactly what happens when the engine tries to match it against a specific string. Building a tiny regex engine that supports literal characters, . (any character), and * (zero or more of the preceding character) makes the mechanism concrete, using nothing more exotic than plain recursion.

Scoping this down on purpose

Full regex — character classes, groups, alternation, lookahead — is a genuinely large amount of machinery. This build supports exactly three things: matching a literal character, matching any character with ., and matching zero-or-more repetitions of the preceding element with *. That's enough to implement a*b, .*, and ab.c*d, and it's enough to see the actual recursive structure that every more complete engine builds on top of.

The base cases: what makes a match succeed or fail

function isMatch(text, pattern) {
    // Both fully consumed: successful match
    if (pattern.length === 0) {
        return text.length === 0;
    }

    const firstCharMatches = text.length > 0 &&
        (pattern[0] === text[0] || pattern[0] === '.');

    // ... star handling comes next; without it, this only
    // handles single-character matching, one character at a time
}

The empty-pattern base case is the one that trips people up first: an empty pattern only matches an empty remaining text, not "anything." If the pattern has been fully consumed but there's still text left over, that's not a match — the whole pattern has to account for the whole string, not just a prefix of it.

Handling *: the part that actually needs recursion

function isMatch(text, pattern) {
    if (pattern.length === 0) {
        return text.length === 0;
    }

    const firstCharMatches = text.length > 0 &&
        (pattern[0] === text[0] || pattern[0] === '.');

    if (pattern.length >= 2 && pattern[1] === '*') {
        return (
            isMatch(text, pattern.slice(2)) ||                        // zero occurrences: skip the starred char entirely
            (firstCharMatches && isMatch(text.slice(1), pattern))      // one more occurrence: consume a char, keep the star pattern active
        );
    }

    return firstCharMatches && isMatch(text.slice(1), pattern.slice(1));
}

The * branch is where the actual interesting logic lives, and it's genuinely just two recursive calls, combined with ||: try matching with the starred character consuming zero occurrences (skip past it in the pattern entirely), or — if the current text character actually matches — try consuming one occurrence of it and recursively check the same star pattern again against the remaining text, since * means "zero or more," and "one or more" is handled by re-trying the same rule repeatedly.

Tracing a*b against "aaab" step by step

Walking through the actual recursive calls makes the mechanism concrete in a way that reading the code alone doesn't:

isMatch("aaab", "a*b")
  pattern[1] === '*', so try both branches:
  → Branch 1 (zero 'a's): isMatch("aaab", "b")
      firstCharMatches: 'b' vs 'a' → false. This branch fails.
  → Branch 2 (consume one 'a'): isMatch("aab", "a*b")
      → Branch 1 (zero 'a's): isMatch("aab", "b") → 'b' vs 'a' → false
      → Branch 2 (consume one 'a'): isMatch("ab", "a*b")
          → Branch 1: isMatch("ab", "b") → 'b' vs 'a' → false
          → Branch 2: isMatch("b", "a*b")
              → Branch 1: isMatch("b", "b") → pattern and text both length 1, chars match, then isMatch("", "") → TRUE
Final result: TRUE

Each recursive call either tries to skip the starred character or consume one more instance of it, and the whole thing bottoms out once the text is short enough for the "zero occurrences" branch to align the remaining pattern with the remaining text exactly. This trace is also a genuinely good way to explain to someone else why a* is "zero or more" rather than "one or more" — the zero-occurrences branch is checked first, at every single level of recursion, not as a special edge case bolted on separately.

Why this implementation is exponential — and what real engines do instead

This recursive version has a real, practical problem: on a pattern with several consecutive * operators against a text that doesn't ultimately match, the number of recursive branches explored can grow exponentially, because the two branches at each * aren't memoized — the same (text, pattern) sub-problem can get recomputed many times across different recursive paths. This is the actual mechanism behind "catastrophic backtracking," a real performance problem in production regex engines when a pathological pattern meets a pathological input:

function isMatchMemoized(text, pattern, cache = new Map()) {
    const key = `${text}|${pattern}`;
    if (cache.has(key)) return cache.get(key);

    let result;
    if (pattern.length === 0) {
        result = text.length === 0;
    } else {
        const firstCharMatches = text.length > 0 &&
            (pattern[0] === text[0] || pattern[0] === '.');

        if (pattern.length >= 2 && pattern[1] === '*') {
            result = isMatchMemoized(text, pattern.slice(2), cache) ||
                (firstCharMatches && isMatchMemoized(text.slice(1), pattern, cache));
        } else {
            result = firstCharMatches && isMatchMemoized(text.slice(1), pattern.slice(1), cache);
        }
    }

    cache.set(key, result);
    return result;
}

Caching results for each unique (text, pattern) pair turns the exponential blowup into a polynomial-bounded number of distinct sub-problems, since there are only so many unique substrings of the original text and pattern to combine. Production regex engines use more sophisticated approaches — converting the pattern into a finite automaton rather than backtracking recursively at all — but memoization is the smallest, most direct fix to see why the naive recursive version can blow up, and why it matters.

What understanding this actually changes about how you write regex

• A greedy * tries to consume as much as possible first, only backing off if the rest of the pattern can't match otherwise — visible directly in the trace above, where "consume one more" is tried before "skip entirely" backs off to it on failure.
• Nested or ambiguous * patterns against a non-matching string are where performance problems actually come from — not a vague "regex is slow," but a specific, explainable branching explosion in exactly the kind of recursive structure built here.
• An empty pattern only ever matches an empty remaining string, which is the base case most people get wrong when reasoning about regex by intuition rather than by the actual matching algorithm.

If you're the kind of person who wants to understand a tool by rebuilding a small version of it rather than just using it, the same instinct applies well to parsing a messy real-world CSV file without a library — a different, more directly practical parsing problem built the same from-scratch way. And if you need actual production regex work done rather than a from-scratch learning exercise, this site's own URL encoder/decoder is a reasonable place to test a pattern's behavior against real strings before dropping it into application code.

Extending it: adding + (one or more)

Once the recursive structure for * is in place, adding + — one or more, rather than zero or more — is a small addition rather than a new algorithm, because + is really just "match the character once, then apply the same zero-or-more logic already built":

function isMatchExtended(text, pattern) {
    if (pattern.length === 0) {
        return text.length === 0;
    }

    const firstCharMatches = text.length > 0 &&
        (pattern[0] === text[0] || pattern[0] === '.');

    if (pattern.length >= 2 && pattern[1] === '*') {
        return (
            isMatchExtended(text, pattern.slice(2)) ||
            (firstCharMatches && isMatchExtended(text.slice(1), pattern))
        );
    }

    if (pattern.length >= 2 && pattern[1] === '+') {
        // one-or-more is: match once, then treat the rest as zero-or-more
        return firstCharMatches &&
            isMatchExtended(text.slice(1), pattern[0] + '*' + pattern.slice(2));
    }

    return firstCharMatches && isMatchExtended(text.slice(1), pattern.slice(1));
}

Rewriting a+ as "consume one a, then recurse treating the rest of the pattern as if it were a*" reuses the exact machinery already built for *, rather than writing a separate, parallel branch of logic — a small example of how a lot of regex's apparent surface complexity is actually a small number of underlying rules combined in different ways, not a large number of genuinely independent behaviors to memorize one by one.

What matching against anchors adds

Real regex also supports ^ and $ to anchor a match to the start or end of the string, which this simplified engine treats as implicit — every call to isMatch(text, pattern) here already requires the entire pattern to account for the entire text, which is closer to how ^pattern$ behaves in a full engine than how a bare, unanchored pattern behaves. Implementing genuine substring search — finding a match anywhere within a larger string, the way an unanchored regex normally works — means trying the match starting at every possible position in the text and returning true if any position succeeds:

function search(text, pattern) {
    for (let start = 0; start <= text.length; start++) {
        if (isMatchExtended(text.slice(start), pattern)) {
            return true;
        }
    }

    return false;
}

This distinction — a full match versus a search for a match anywhere in the string — is exactly the kind of thing that's easy to get backwards by intuition and immediately clear once you've had to implement both versions and see precisely where they diverge.

What a "real" regex engine does differently underneath

Production regex engines mostly don't work the way this recursive version does at all — they compile a pattern into a finite automaton (either an NFA or a DFA) before ever looking at the input text, and matching becomes a matter of walking that automaton character by character rather than exploring a tree of recursive branches. The practical benefit is exactly the one this post's memoized version approximates with a cache: guaranteed linear-time matching relative to the input length, with no possibility of the exponential blowup a naive backtracking approach can hit. Some engines — Python's re, PCRE, most engines behind .NET and Java — use backtracking similar in spirit to this post's naive recursive version, which is exactly why those engines are the ones vulnerable to catastrophic backtracking on pathological patterns. Others — RE2, Rust's regex crate, Go's built-in regexp — deliberately restrict which regex features they support specifically so they can guarantee automaton-based matching and sidestep the exponential blowup entirely, trading away a few advanced features (like backreferences) that are fundamentally incompatible with a pure automaton approach.

Why backreferences can't be built this way at all

It's worth naming a specific, genuine limit of the approach in this post rather than implying it scales to full regex with enough elbow grease: backreferences — a pattern like (a+)\1, matching a repeated group followed by the exact same text again — are not implementable as a pure finite automaton at all, which is precisely why automaton-based engines like RE2 explicitly don't support them. This recursive approach could be extended to support backreferences with more bookkeeping (tracking captured group contents through the recursion), but doing so would push it back into the same backtracking-based, potentially-exponential category as the naive version this post already flagged as risky. There's a genuine, well-understood theoretical reason certain regex features and guaranteed linear-time matching are mutually exclusive — this isn't a gap in this particular toy implementation, it's a real boundary in what regular expressions as a formalism can and can't do efficiently.

A practical takeaway for writing patterns, not just building engines

• A pattern with several consecutive * or + quantifiers against text that ultimately fails to match is the specific shape most likely to trigger catastrophic backtracking on a backtracking-based engine — recognizing that shape in your own patterns is worth more than memorizing a list of "dangerous" regex syntax.
• If you're validating user-supplied input against a pattern you don't fully control, testing that pattern against a deliberately pathological non-matching input before trusting it in production is a cheap, concrete way to catch a potential performance problem before an attacker or an unlucky user finds it for you.
• Knowing which category your language's engine falls into — backtracking (Python, PHP's PCRE, Java) versus automaton-based (Go, Rust, RE2) — tells you whether catastrophic backtracking is a real risk you need to actively guard against or a non-issue by construction.