{"schemaVersion":"1.0","type":"TechArticle","types":["Article","TechArticle"],"slug":"i-built-a-regex-engine-in-about-100-lines-of-python-xara8","url":"https://zyvop.com/i-built-a-regex-engine-in-about-100-lines-of-python-xara8","title":"I Built a Regex Engine in About 100 Lines of Python","subtitle":"A tiny Python regex engine built with Thompson’s NFA algorithm, tested against nearly 12 million comparisons and designed to avoid catastrophic backtracking.","tldr":"What happens when you build your own regular expression engine? I wrote one in just 96 lines of Python using Thompson’s NFA algorithm. It supports core regex features, avoids backtracking, and passed nearly 12 million comparisons against Python’s built-in re module.","keywords":["Finite Automata","Programming","Python","Regular Expressions","Algorithms","Tutorial"],"entities":["DevForHelp","Finite Automata","Programming","Python","Regular Expressions","Algorithms","Tutorial","ZyVOP"],"keyTakeaways":["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."],"headings":["Why a regex can hang","How it works","The pattern becomes a machine","Matching follows every path at once","Testing it against Python’s re","How fast is it?","What it can’t do","What I took away","The complete code","Credits and sources"],"outboundLinks":["https://swtch.com/~rsc/regexp/regexp1.html"],"contentText":"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. &gt;&gt;&gt; from miniregex import Regex &gt;&gt;&gt; r = Regex(\"a(b|c)*d\") &gt;&gt;&gt; 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: char reads one character. any reads any character except a newline. That is .. split reads nothing and offers two ways forward. Choices and loops are built from it. match means 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 from a, 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 like x+). 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 re 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\") -&gt; True (the whole text matches) Regex(\"(a|b)*c\").search(\"xxabcxx\") -&gt; 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 re module, from the standard library, served as the referee. Tested with Python 3.12 on Linux.","contentHash":"sha256:1e71b41aab1c0cb18f62c4e2418258fda12265c86f90a678aac830c02271bfbd","authorName":"DevForHelp","authorUrl":"https://zyvop.com/author/devforhelp","authorSameAs":[],"category":"Tutorial","tags":["Finite Automata","Programming","Python","Regular Expressions","Algorithms"],"audience":"Software engineers and developers building applications with Tutorial","tone":"Practical and evidence-based engineering guidance","readingTimeMinutes":8,"wordCount":1918,"faqs":null,"primaryTopic":"Tutorial","publishedAt":"2026-11-18T12:58:06.657Z","updatedAt":"2026-11-18T12:58:06.657Z","canonicalUrl":"https://zyvop.com/i-built-a-regex-engine-in-about-100-lines-of-python-xara8"}