← thecodex.expert · The Codex Family of Knowledge
Tier 5 · Expert · Python Project

Regex Engine

Build a regular-expression matcher from scratch, supporting wildcards and repetition. Understand the theory behind a tool everyone uses but few understand.

🧠 Teaches how to think spoonfed, every age Last verified:

1 The Problem

We want to build a regex engine: match patterns with . (any character) and * (zero or more of the previous) against text. We will implement it with recursion that mirrors the formal definition of matching. It teaches the theory behind regular expressions — recursion, backtracking, and how an elegant definition becomes working code.

Where this shows up: every regex library, search tools, lexers (like the one in our interpreter!), input validation, find-and-replace. Regex is used everywhere and understood by few; building one puts you in rare company.

2 How to Think About It

Think recursively about matching, before any code:

The plan — in plain English
1. Match means: does the pattern match from the start of the text? → 2. Base case: an empty pattern matches anything (we have matched all we needed). → 3. A * means “zero or more”: try matching zero (skip it) OR one-then-recurse. → 4. A normal character (or .) must match here, then recurse on the rest. The recursion mirrors the definition exactly.

Yes

No

Yes

No

Yes

No

match pattern against text

Pattern empty?

Match! return true

Next is star?

Try zero, OR one then recurse

First char matches?

Recurse on the rest

No match

3 The Build — explained part by part

Here is a complete regex engine. It is short but deep — read each part’s explanation carefully.

Pythonregex.py
def match(pattern, text):
    # Does `pattern` match starting at the beginning of `text`?
    if not pattern:
        return True      # empty pattern matches (we are done)

    # Is the next token followed by a star? (e.g. "a*")
    if len(pattern) >= 2 and pattern[1] == "*":
        return match_star(pattern[0], pattern[2:], text)

    # A normal character or "." must match the first text character.
    first_matches = bool(text) and pattern[0] in (text[0], ".")
    if first_matches:
        return match(pattern[1:], text[1:])
    return False

def match_star(char, rest_pattern, text):
    # "char*" means zero or more of char.
    # Option 1: match zero — skip the star, try the rest now.
    if match(rest_pattern, text):
        return True
    # Option 2: match one char here, then try star again (backtrack).
    while text and (char == text[0] or char == "."):
        text = text[1:]
        if match(rest_pattern, text):
            return True
    return False

if __name__ == "__main__":
    print(match("a*b", "aaab"))     # True
    print(match("a.c", "axc"))      # True
    print(match("a*b", "aaac"))     # False
What each part does — in plain words
if not pattern: return True — the base case that makes the recursion work: once the pattern is empty, everything required has matched, so we succeed.

pattern[1] == "*" — look one ahead: if the next character is a star, this is a “zero or more” situation, handled specially by match_star. We pass the character, the pattern after the star, and the text.

pattern[0] in (text[0], ".") — a character matches if it equals the text’s character, or if the pattern character is . (the wildcard). Then we recurse on the rest of both.

match_star — option 1: try matching zero of the character by skipping straight to the rest of the pattern. If that succeeds, done.

match_star — option 2: otherwise consume one matching character and try again. This loop is backtracking: try consuming more and more, checking if the rest matches each time. If nothing works, return False.

why recursion? — matching is naturally recursive: “the pattern matches if the first part matches and the rest matches”. The code mirrors that definition almost word for word.
Common mistakes — and how to avoid them
✗ Forgetting the “match zero” option for * — then a*b cannot match "b".
✓ Always try skipping the starred char first, before consuming any.
✗ Not checking text is non-empty before text[0] — crashes at the end.
✓ Guard with bool(text) before indexing.
✗ Looking at pattern[1] without checking length — IndexError on a one-char pattern.
✓ Check len(pattern) >= 2 before peeking ahead.

4 Test & Prove Each Part

We test literal matches, the wildcard, and the star — including tricky cases where backtracking matters.

A literal pattern matches identical text
The . wildcard matches any single character
a* matches zero or more a characters
A pattern that should not match returns False
Pythontest_regex.py
def match(pattern, text):
    if not pattern:
        return True
    if len(pattern) >= 2 and pattern[1] == "*":
        return match_star(pattern[0], pattern[2:], text)
    first_matches = bool(text) and pattern[0] in (text[0], ".")
    if first_matches:
        return match(pattern[1:], text[1:])
    return False


def match_star(char, rest_pattern, text):
    if match(rest_pattern, text):
        return True
    while text and (char == text[0] or char == "."):
        text = text[1:]
        if match(rest_pattern, text):
            return True
    return False


def test_literal():
    """A literal pattern matches identical text."""
    assert match("abc", "abc") is True


def test_wildcard():
    """. matches any single character."""
    assert match("a.c", "axc") is True


def test_star_many():
    """a* matches several a's."""
    assert match("a*b", "aaab") is True


def test_star_zero():
    """a* matches zero a's."""
    assert match("a*b", "b") is True


def test_no_match():
    """A non-matching pattern returns False."""
    assert match("a*b", "aaac") is False

Run with pytest -v. The test_star_zero case — a*b matching just "b" — proves the “match zero” branch works. The two star cases together show why both options in match_star are needed.

5 The Interface

matchmatch(pattern, text)true if pattern matches
Examples
match("a*b", "aaab")  -> True
match("a.c", "axc")   -> True
match("a*b", "aaac")  -> False

6 Run It & Automate It

Run it locally
python3 regex.py
Try patterns with . and *. This is a real (if minimal) regex engine.

Jenkins runs the tests automatically — each line explained below.

What you should see when it works
Terminala real run
True
True
False
If it breaks — how to fix it
🚨 a*b fails to match "b".
Your match-zero branch is missing. Try match(rest, text) first in match_star.
🚨 IndexError.
You indexed empty text or a too-short pattern. Add the length/emptiness guards.
GroovyJenkinsfile
// Jenkinsfile — automated tests on every change.
pipeline {
    agent any
    stages {
        stage('Get the code') { steps { checkout scm } }       // download the code
        stage('Install') { steps { sh 'python3 -m venv venv && . venv/bin/activate && pip install pytest' } }  // test tool
        stage('Test') { steps { sh '. venv/bin/activate && pytest -v' } }   // run every test
    }
    post {
        success { echo 'All tests passed.' }
        failure { echo 'A test failed — look above.' }
    }
}
🎯 Try this next — make it yours
  1. Anchors. Support ^ (start) and $ (end). (Teaches: position matching.)
  2. Plus. Add + (one or more). (Teaches: a variation on star.)
  3. Character classes. Support [abc]. (Teaches: sets in patterns.)
What you learned
You built a regex engine with recursion and backtracking — the theory behind a tool everyone uses but few understand. You saw how an elegant recursive definition of “match” becomes working code. Related: re, Functions & Scope.