renfa

A regular-expression engine built with Thompson's NFA construction and a Pike VM simulation, in pure Python with zero dependencies.

renfa parses a regex, compiles it to a non-deterministic finite automaton the way Ken Thompson described in 1968, and matches by simulating that automaton, so matching is linear in the input length, with none of the catastrophic backtracking that makes naive regex engines blow up on inputs like (a*)*b. Every stage is built and explained from first principles.

A regex engine is where automata theory stops being abstract: a pattern becomes a graph of states, and "does this string match?" becomes "can a token reach an accept state?" Building the parser, the NFA, and the simulation is the clearest way to understand why the right algorithm matches in O(n·m) and the usual one doesn't.

import renfa

r = renfa.compile("a(b|c)*d")
bool(r.fullmatch("abcbcd"))   # True
bool(r.search("xxabdyy"))     # True   (matches anywhere)
bool(r.match("abdzzz"))       # True   (matches a prefix)

# Submatch capture, with an re-like Match object:
m = renfa.compile(r"(\d+)-(\d+)").search("date 12-2026 end")
m.group(0)   # '12-2026'
m.group(1)   # '12'
m.groups()   # ('12', '2026')
m.span(2)    # (8, 12)

# Named groups (?P<name>...) — by name or number, and groupdict():
m = renfa.compile(r"(?P<day>\d+)-(?P<year>\d+)").search("12-2026")
m.group("day")   # '12'
m.groupdict()    # {'day': '12', 'year': '2026'}

# Higher-level helpers, like re:
renfa.compile(r"\d+").findall("a12b3c456")     # ['12', '3', '456']
renfa.compile(r"\s+").sub("_", "a  b\tc")      # 'a_b_c'
renfa.compile(r"\s*,\s*").split("a, b ,c")     # ['a', 'b', 'c']

# Or skip the compile step entirely, like re's module functions
# (patterns are memoized in a small cache):
renfa.search(r"\d+", "abc123").group(0)         # '123'
renfa.findall(r"\w+", "one two three")          # ['one', 'two', 'three']

# The classic backtracking blow-up — linear here, no hang:
renfa.compile("(a*)*b").fullmatch("a" * 40)   # None, instantly

The pipeline

pattern ──▶ Parser ──▶ AST ──▶ NFA compiler ──▶ ε-NFA ──▶ Pike VM ──▶ match?
            (recursive          (Thompson         (state set
             descent)            construction)     simulation)

• Parser. Recursive descent with the classic precedence: alternation | looser than concatenation, looser than the repetition operators * + ?, the bounded forms {n}, {n,}, {n,m}, and their lazy variants (*?, +?, ??, {n,m}?). Supports groups (capturing, non-capturing (?:…), and named (?P<name>…)), character classes ([a-z], [^…]), ., anchors ^ $ and word boundaries \b \B, escapes and shorthands (\d \w \s and their negations). A bad pattern raises a ParseError naming the offset.
• NFA compiler. Thompson's construction: each AST node becomes a small NFA fragment with dangling arrows, wired together compositionally. No backtracking is ever encoded.
• Pike VM. Simulate the NFA by advancing a set of active states one input character at a time. Linear time, and the natural place to add submatch capture.

The full design (the Thompson construction, why the Pike VM is O(n·m), the capture and priority machinery, and the differential-testing philosophy) is in docs/DESIGN.md, with the key decisions recorded as ADRs.

Correctness by differential testing

An engine like this has a perfect oracle: Python's own re module. Beyond hand-written cases, renfa is tested by generating random patterns and random strings and asserting renfa agrees with re on match / no-match, over thousands of pairs. A divergence is a bug, reproducible from its seed.

Status & roadmap

• Parser. Pattern → AST, full precedence, classes, anchors, escapes/shorthands, ParseError
• NFA compiler. Thompson construction, compiled to a flat Char/Jmp/Split/Assert/Match program (no backtracking encoded)
• Pike VM matcher. Linear-time state-set simulation; fullmatch / match / search
• Differential test harness. A curated matrix plus seeded random patterns, each checked against re
• Submatch capture. Numbered groups ((?:…) non-capturing) and named groups (?P<name>…) via thread-carried save slots and a priority-ordered VM; an re-like Match object (group by number or name / groups / groupdict / span), differentially checked against re
• Higher-level API. finditer / findall / sub / split (capturing groups interleaved, maxsplit), with re-compatible non-overlapping and empty-match semantics; also exposed as module-level functions (renfa.search(pat, text), …) over a small compile cache, like re
• Lazy quantifiers. *? +? ?? {n,m}? (prefer the fewest repeats)
• Case-insensitive matching. renfa.compile(pattern, ignorecase=True) (like re.IGNORECASE); literals and classes fold case, [^…] correctly too
• CLI. A grep-like front end: python -m renfa [-c] [-v] PATTERN [FILE…]

A note on semantics

renfa matches Python's re on everything the differential suite covers. The one intended divergence is the empty-loop capture corner: what a group captures when a nullable body repeats under * (e.g. ((a)?)*). re performs a trailing empty iteration that clears the capture; renfa follows the Thompson/RE2 lineage and keeps the last non-empty one. Both are defensible; engines really do disagree here, so the random differential avoids nullable bodies under a quantifier.

Limitations

A Thompson NFA with a Pike VM buys linear-time matching, and the price is a smaller language. Most of what is missing is missing because of that guarantee, not in spite of it.

Not expressible in this engine, by construction:

• Backreferences. \1 and friends need to remember what a group captured and compare against it, which a finite automaton cannot do — matching with backreferences is NP-hard in general, and that is exactly the property this design gives up.
• Lookahead and lookbehind. (?=…), (?!…), (?<=…), (?<!…) are not implemented.
• Atomic groups and possessive quantifiers. They exist to control backtracking, and there is no backtracking here to control.

Two of those are currently accepted rather than rejected, and silently mean something else. This is the sharpest edge in the engine and worth stating plainly:

pattern	subject	renfa	Python re
(a)\1	"aa"	no match	match
(a)\1	"a1"	match	no match
\p{L}	"p{L}"	match	PatternError

\1 parses as a literal 1, and \p{L} as the literal characters p{L}. The code says so — vm.py:115 notes that backreferences are not interpreted — but the user sees a pattern that compiled, and the differential suite never catches it because the generator does not emit either construct. Rejecting both at parse time would be the better behaviour; until then, this table is the warning.

Also absent:

• Unicode property classes. No \p{…}, no \P{…}, no script or category matching.
• Inline flags. (?i) is not parsed — pass IGNORECASE to compile instead. The parse error you get for (?i) and for lookahead is "nothing to repeat", which is the parser reporting where it gave up rather than what it did not support.
• re.MULTILINE, DOTALL, VERBOSE. IGNORECASE is the flag that exists.
• re.sub, re.split, finditer. The surface is search, match, fullmatch and the CLI; there is no substitution API.

And one intended semantic difference, described in full under A note on semantics above: what a group captures when a nullable body repeats under *. renfa keeps the last non-empty capture, re clears it. Engines genuinely disagree, and the random differential avoids nullable bodies under a quantifier for that reason.

Performance

The point of an NFA simulation isn't raw speed (renfa is pure Python), it's shape. bench/bench.py measures the classic backtracking blow-up (a*)*b at growing input sizes; the per-character cost stays flat, the empirical proof that matching is linear:

(a*)*b over n as	time	µs / char
250	0.5 ms	2.1
1000	2.0 ms	2.0
4000	8.0 ms	2.0

A backtracking engine explores exponentially many paths on that input and hangs; renfa never backtracks, so it just gets predictably slower with size. Throughput on a normal pattern (\w+ over a 100k-char document) is ~0.4 M chars/s. Numbers are indicative, from the dev machine; run python bench/bench.py for your own.

Command line

A grep-like front end ships with the engine:

$ printf 'apple\nbanana\navocado\n' | python -m renfa '^a'
apple
avocado
$ python -m renfa -c '\d+' access.log      # count matching lines
$ python -m renfa -v 'error' app.log        # lines that do NOT match

Exit status follows grep: 0 if any line matched, 1 if none, 2 on error.

Building & testing

Pure standard library, no dependencies:

python -m unittest discover -s tests -t .

License

MIT