
Regular expressions felt like magic to me, so I built one to see how they work. miniregex.py uses only the standard library and is 96 lines of code (142 counting comments and blank lines).
It supports literals, ., *, +, ?, |, parentheses and backslash escapes. It never backtracks, so its running time can’t explode.
To check it, I used Python’s own re module as a referee on nearly 12 million comparisons. The complete code is at the end.
>>> from miniregex import Regex
>>> r = Regex("a(b|c)*d")
>>> r.fullmatch("abcbd"), r.fullmatch("abx"), r.search("zzabcdzz")
(True, False, True)fullmatch asks whether the whole text matches. search asks whether any part of it does.
Why a regex can hang
Most engines, including Python’s re, try one way to match and back up to try another when it fails. That is called backtracking, and it is usually fast.
But with repetition inside repetition, the number of ways to split up the text grows exponentially. In my benchmark, Python’s re needs about 2.3 seconds for a 78-character pattern against a 26-character text, and every extra character doubles that.
The older alternative is Ken Thompson’s algorithm from the 1960s: turn the pattern into a small machine and follow all the possible paths at once.
Russ Cox explained it, and showed how badly backtracking can go wrong, in his 2007 article “Regular Expression Matching Can Be Simple And Fast.” This engine is that idea in Python.
How it works
The pattern becomes a machine
An NFA is a set of states joined by arrows. Mine has four kinds:
charreads one character.anyreads any character except a newline. That is..splitreads nothing and offers two ways forward. Choices and loops are built from it.matchmeans success.
The compiler is a small recursive-descent parser that builds the machine in a single pass.
Each piece of the pattern returns a fragment: a start state plus the arrows that still lead nowhere. Joining two pieces means pointing the first one’s loose arrows at the second one’s start.
Matching follows every path at once
Instead of trying one path and backing up, the matcher keeps the set of every state the machine could be in right now. It moves the whole set forward one character at a time.
Take a(b|c)*d and the text abcd. After the a, the machine could be about to read a b, a c or a d, so the set holds all three. After the d, the set contains the match state, and the text matches.
The set can never be larger than the number of states. So every character costs a bounded amount of work, and the total time is proportional to the pattern length times the text length.
search is the same loop with one extra idea: it adds the start state to the set at every step. That is the same as starting a match at every position.
Testing it against Python’s re
For these features, whether a string matches does not depend on how an engine searches, so re is an exact referee. I compared both fullmatch and search:
Every small pattern. All 111,110 sequences of up to five tokens (
a,b,.,\.,*,+,?,|,(and)). 16,083 were valid in both engines, and each was tried against all 341 texts of up to four characters made froma,b,.and a newline. That is 10,968,606 comparisons, with zero disagreements.Random larger patterns. 20,000 patterns with nested groups, empty branches and escapes: 1,000,000 more comparisons, zero disagreements.
Breaking it on purpose. I broke the engine ten different ways, one small edit at a time (for example, making
x*behave likex+). The tests caught all ten.
You can reproduce the first check yourself. Save this next to miniregex.py and run it; it takes under a minute:
import itertools
import re
from miniregex import Regex
tokens = ["a", "b", ".", "\\.", "*", "+", "?", "|", "(", ")"]
texts = ["".join(t) for n in range(5) for t in itertools.product("ab.\n", repeat=n)]
checked = 0
for n in range(1, 6):
for combo in itertools.product(tokens, repeat=n):
pattern = "".join(combo)
try:
expected, mine = re.compile(pattern), Regex(pattern)
except (re.error, ValueError):
continue # skip patterns that either engine refuses
for text in texts:
assert bool(expected.fullmatch(text)) == mine.fullmatch(text), (pattern, text)
assert bool(expected.search(text)) == mine.search(text), (pattern, text)
checked += 2
print(f"no disagreements in {checked:,} comparisons")It prints no disagreements in 10,968,606 comparisons.
The random test also showed that re can be the slow side. On 285 of the 20,000 patterns it could not finish within 0.2 seconds on some text, so the test counts those instead of comparing them.
My engine needed at most 4 milliseconds to run all of the test texts on any one of them.
Writing the error tests taught me one more lesson. My first version quietly treated [ab] as the literal text [ab], while real engines read a character class.
A pattern that silently means something else is worse than one that fails. So the engine now refuses [, ], {, }, ^, $ and escapes like \d with an error. A backslash makes them literal.
How fast is it?
This is a? repeated n times followed by a repeated n times, matched against n letters a. It is Russ Cox’s classic example.
I compiled each pattern first and timed only the matching. The miniregex times are so small that the differences between its rows are just noise:
n | Python | miniregex |
|---|---|---|
20 | 35.85 ms | 0.09 ms |
22 | 148.43 ms | 0.17 ms |
24 | 574.90 ms | 0.12 ms |
26 | 2,276.09 ms | 0.14 ms |
re’s time grows about four times for every two extra characters. If the doubling continued, n = 50 would take more than a year.
Mine handles the nested pattern (a+)+b against 100,000 characters in roughly a tenth of a second.
The comparison is not all flattering, though. On an ordinary pattern, re is about 60 times faster than my pure-Python engine (0.13 ms against 7.46 ms). The advantage here is a bounded worst case, not raw speed.
What it can’t do
Left out on purpose:
No character classes and no
\d.No anchors (
^and$) and no{m,n}repeats.No capture groups. It only answers yes or no.
No flags.
Many of these are easy additions: [abc] is just (a|b|c).
Parentheses nested a couple of hundred levels deep hit Python’s recursion limit.
Backreferences are different in kind. They give a regex more power than a finite machine has, which is why engines that support them typically have to backtrack.
What I took away
Backtracking is a choice, not a necessity. The patterns that freeze one engine are routine for another.
Tracking a set of states is the whole trick.
A referee makes testing cheap, and breaking your own code on purpose shows whether the tests would notice a bug.
Fail loudly on syntax you do not support.
The complete code
"""
miniregex.py - a regular expression engine in about 100 lines (Python 3, no dependencies).
Supports: abc . * + ? | ( ) and a backslash to take a special character literally, like \\.
Anything else that is special in regex syntax ([ ] { } ^ $ and escapes like \\d) raises a
ValueError, so a pattern is never quietly read as something other than what you meant.
Matching never backtracks. The pattern is compiled into an NFA (Thompson's construction)
and all of its possible states are simulated at once, so the time taken is proportional
to len(pattern) * len(text), however nasty the pattern.
Regex("(a|b)*c").fullmatch("ababc") -> True (the whole text matches)
Regex("(a|b)*c").search("xxabcxx") -> True (some part of the text matches)
"""
# ------------------------------------------------------------------
# 1. Compile the pattern into an NFA in a single pass. Each state is a list
# [kind, data, next1, next2]:
# "char": consume the character data, go to next1
# "any": consume any character except a newline, go to next1
# "split": consume nothing, go to next1 or next2
# "match": accept
# A "fragment" is a piece of NFA: (start state, exits). The exits are the dangling
# arrows, as (state, slot) pairs, that still have to be connected to whatever comes next.
# ------------------------------------------------------------------
def compile_nfa(pattern):
states, pos = [], 0
def new(kind, data=None, next1=None, next2=None):
states.append([kind, data, next1, next2])
return len(states) - 1
def patch(exits, target): # connect dangling arrows to a state
for i, slot in exits:
states[i][slot] = target
def peek():
return pattern[pos : pos + 1] # "" at the end of the pattern
def take():
nonlocal pos
pos += 1
return pattern[pos - 1]
def alternation(): # branch | branch | ...
start, exits = sequence()
while peek() == "|":
take()
start2, exits2 = sequence()
start, exits = new("split", None, start, start2), exits + exits2
return start, exits
def sequence(): # item item item ...
start = new("split") # an empty pattern: passes straight through
exits = [(start, 2), (start, 3)]
while peek() not in ("", "|", ")"):
item_start, item_exits = repeat()
patch(exits, item_start)
exits = item_exits
return start, exits
def repeat(): # an atom, optionally followed by * + or ?
start, exits = atom()
op = peek()
if op not in ("*", "+", "?"):
return start, exits
take()
loop = new("split", None, start) # next1 = enter the body, next2 = leave
if op == "?":
return loop, exits + [(loop, 3)]
patch(exits, loop) # after the body, come back to the split
return (loop if op == "*" else start), [(loop, 3)]
def atom():
c = take()
if c == "(":
fragment = alternation()
if peek() != ")":
raise ValueError("missing )")
take()
return fragment
if c in ("*", "+", "?"):
raise ValueError(f"nothing to repeat: {c}")
if c in "[]{}^$": # special in other regex dialects: refuse rather than misread
raise ValueError(f"unsupported: {c} (put a backslash before it to match it literally)")
if c == "\\": # an escaped character is taken literally
if not peek() or peek().isalnum():
raise ValueError(f"bad escape at position {pos}")
c = take()
state = new("char", c)
else:
state = new("any") if c == "." else new("char", c)
return state, [(state, 2)]
start, exits = alternation()
if peek():
raise ValueError("unmatched )")
patch(exits, new("match")) # the match state is always the last one
return states, start
# ------------------------------------------------------------------
# 2. Run the NFA: keep the set of every state we could be in, one character at a time.
# ------------------------------------------------------------------
def run(states, start, text, anywhere):
match = len(states) - 1
def closure(ids): # add every state reachable without consuming a character
seen, todo = set(), list(ids)
while todo:
i = todo.pop()
if i not in seen:
seen.add(i)
if states[i][0] == "split":
todo += (states[i][2], states[i][3])
return seen
current = closure([start])
for ch in text:
if anywhere and match in current:
return True
moves = []
for i in current:
kind, data, next1, _ = states[i]
if (kind == "char" and data == ch) or (kind == "any" and ch != "\n"):
moves.append(next1)
current = closure(moves + [start] if anywhere else moves)
if not current:
return False
return match in current
class Regex:
def __init__(self, pattern):
self.states, self.start = compile_nfa(pattern)
def fullmatch(self, text):
return run(self.states, self.start, text, anywhere=False)
def search(self, text):
return run(self.states, self.start, text, anywhere=True)Credits and sources
Russ Cox, Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...), January 2007. It describes Ken Thompson’s algorithm and builds NFAs from fragments with dangling arrows, the approach used here.
Python’s own
remodule, from the standard library, served as the referee.Tested with Python 3.12 on Linux.
Comments(0)
Join the discussion by logging into your account.
No comments yet. Be the first to comment!