---
license: agpl-3.0
tags:
- snapkitty
- october-2026-drop
- c
- python
- regex
- thompson-nfa
- zero-dependency
- developer-tools
---

> Mirrored from [https://github.com/SNAPKITTYWEST/snapkitty-regex](https://github.com/SNAPKITTYWEST/snapkitty-regex) at commit `b14a2eb`. Part of the **SnapKitty October 2026 main drop**.

# snapkitty-regex

A Thompson NFA regular expression engine in C — under 700 lines, zero
dependencies, no exponential backtracking, ever.

Built as an exercise from the guides in
[AHMADALIPARR/build-your-own-x](https://github.com/AHMADALIPARR/build-your-own-x)
("Build your own `Regex Engine`"), primarily Russ Cox's
*[Regular Expression Matching Can Be Simple And Fast](https://swtch.com/~rsc/regexp/regexp1.html)*.

## The idea

Most popular regex engines (Perl, Python, Ruby, Java, PCRE) simulate an
NFA by *backtracking*: guess a path, and retry on failure. On patterns
like `a?a?a?aaa` that means trying all 2^n combinations — Perl needs
**60+ seconds** to match a 29-character string.

This engine instead simulates *all* NFA paths in parallel, tracking the
set of reachable states one input character at a time (Thompson's 1968
algorithm). Matching is **O(m·n)** worst case for pattern length m and
text length n. There are no pathological inputs.

```
infix pattern --re2post--> postfix --post2nfa--> NFA --pump--> match?
                  (explicit '.' concat)   (Thompson construction)
```

## Syntax

| construct | meaning |
|---|---|
| `abc` | literal characters match themselves |
| `e1 e2` | concatenation |
| `e1\|e2` | alternation |
| `e*` | zero or more |
| `e+` | one or more |
| `e?` | zero or one |
| `(e)` | grouping |
| `\` + metachar | literal metacharacter: `\* \+ \? \| \( \) \\` |
| `.` | literal dot (no wildcard — see roadmap) |

Precedence: `|` weakest, then concatenation, then `* + ?`. Matching is
byte-oriented.

## Build & test

```sh
make          # builds ./regex, clean compile, zero warnings
make test     # 82-check correctness harness (fullmatch, search, bad patterns)
make bench    # pathological benchmark vs Python's re
```

## Usage

```sh
$ ./regex 'a(bb)+a' abbbba abba abbba
abbbba: MATCH
abba: MATCH
abbba: NO MATCH

$ ./regex -s 'colou?r' 'the colour blue'
the colour blue: MATCH
```

Exit codes: `0` all matched, `1` some didn't, `2` usage/bad pattern.

As a library (`src/regex.h`):

```c
Regex *re = re_compile("(ab|cd)+e");
int m = re_fullmatch(re, "cdabe");  /* whole string */
int p = re_match(re, "cdabex");     /* prefix of string */
int s = re_search(re, "xxcdabexx"); /* anywhere in string */
re_free(re);
```

## Benchmark

`a?`^n`a`^n against `a`^n — the article's pathological case:

| n | snapkitty-regex | python `re` |
|---|---|---|
| 10 | 0.0011s | 0.0000s |
| 20 | 0.0010s | 0.0442s |
| 24 | 0.0013s | 0.7139s |
| 26 | 0.0014s | 3.0580s |
| 500 | 0.0021s | (heat death of universe) |

(The ~1ms floor on our side is process-spawn overhead, not matching.)

## What's hardened vs the article's reference code

- **No fixed static buffers** — postfix output and the paren stack are
  sized from the input instead of `char buf[8000]` / `paren[100]`.
- **Backslash escapes** for metacharacters.
- **Literal dots** — a `.` in the pattern can't collide with the postfix
  concatenation operator anymore (this crashes the original).
- **Real error paths** — malformed patterns and `malloc` failures return
  `NULL` instead of crashing; partial allocations unwind cleanly.
- **Reusable, releasable** — compiled patterns are opaque `Regex*`
  values with `re_free`; the accept state and dedup generation are
  per-pattern, not globals.
- **Prefix match + search** on top of full match.

## Roadmap

- `.` wildcard / character classes `[a-z]`
- Capture groups and submatch extraction
- DFA / hybrid execution for very large inputs
- Streaming matcher API

---

### 💼 Commercial License

SnapKitty code is free and open under **AGPL-3.0** for open-source use. Building a commercial product or service? A **proprietary commercial license** from Snapkitty Collective LLC lets you ship this code without the AGPL's source-sharing and network-use obligations.

**[→ Get a commercial license](mailto:A.parr@belespritdaccord.uk?subject=Commercial%20license:%20snapkitty-regex)** · A.parr@belespritdaccord.uk