🐟 Autiepie

A regular expression engine built from scratch using Thompson's NFA construction.

Backtracking-free • Linear-time matching • AST Parser • Thompson NFA • Modern C++

What this is

Autiepie compiles a pattern into a non-deterministic finite automaton and simulates it directly, so matching is linear in the length of the input and there is no backtracking to blow up on. The pipeline is the classic one: pattern goes through a lexer, a recursive descent parser builds an AST, the AST is turned into an NFA with Thompson's construction, and the matcher walks the state set one character at a time.

Why the name

• Autie comes from automata, which is what the whole thing is built on.
• Pie is there because a systems project does not have to sound intimidating.

Table of Contents

• Project Structure
• Architecture
• Thompson NFA Construction
• Performance
• Features
• Build & Run
• Usage
• Test Coverage
• Known Limitations
• Contributing
• License
• References

Project Structure

autiepie
│   CMakeLists.txt
│   main.cpp
│   LICENSE.md
│   README.md
├── assets
│   ├── architecture.excalidraw
│   ├── architecture.png
│   ├── architecture.svg
│   ├── banner.png
│   ├── nfa-graphs.png
│   └── performance-graph.png
├── include
│   ├── automaton.h
│   ├── regex.h
│   ├── lexer
│   │   ├── lexer.h
│   │   ├── token.h
│   │   └── token_type.h
│   └── parser
│       ├── parser.h
│       └── node
│           ├── anchor_node.h
│           ├── ast_node.h
│           ├── capture_group_node.h
│           ├── charclass_node.h
│           ├── concat_node.h
│           ├── epsilon_node.h
│           ├── kleene_node.h
│           ├── literal_node.h
│           ├── pipe_node.h
│           ├── plus_node.h
│           ├── question_node.h
│           └── wildcard_node.h
├── src
│   ├── automaton.cpp
│   ├── regex.cpp
│   ├── lexer
│   │   └── lexer.cpp
│   └── parser
│       └── parser.cpp
└── tests
    └── test.cpp

Architecture

Input -> Lexer -> Parser -> NFA Construction -> Matching Simulation -> Output

• Lexer turns the pattern string into a stream of tokens (literals, operators, brackets).
• Parser is a recursive descent parser that builds an AST while respecting operator precedence.
• Automaton turns the AST into a Thompson NFA and runs it with an epsilon closure simulation.
• API is the Regex class, with match() and search().
  • match() requires the whole input to be consumed by the pattern.
  • search() looks for a matching substring anywhere in the input.

Thompson NFA Construction

Every pattern compiles into an NFA where each state has either an epsilon transition or a transition labelled with a character.

Construct	Fragment
Literal a	one state consuming a
Concatenation AB	the exits of A are patched onto the start of B
Alternation A|B	a split state fans out to both, both land on a shared merge state
Kleene star A*	split state with a loop edge back into itself and a skip edge past it
Plus A+	same loop as the star but the fragment starts inside A, so one pass is mandatory
Question A?	split state that either enters A or jumps to the merge state
Dot .	one state that accepts any single character
Character class [abc]	one state carrying the expanded set
Negated class [^abc]	the same state with the membership test inverted
Anchors ^ $	epsilon edges the closure may only walk at offset 0 / at end of input
Escape `x	the metacharacter becomes an ordinary literal
Group ( )	the child fragment wrapped in a pair of capture marker states

Matching keeps a set of current states, computes the epsilon closure after every input character, and checks whether the accepting state is in the set. That gives O(n × m) behaviour (n = text length, m = number of states) and no catastrophic backtracking.

Performance

• Construction is O(pattern length).
• Matching is O(text length × NFA states).
• No exponential blow-up, which makes it safe to run user supplied patterns.

Features

Feature	Syntax	Example	Status
Literal matching	abc	Regex("abc").match("abc") -> true	✅
Alternation	a|b|c	Regex("cat|dog").match("dog") -> true	✅
Kleene closure	a*	Regex("a*b").match("aaab") -> true	✅
Plus quantifier	a+	Regex("a+").match("aaa") -> true	✅
Question quantifier	a?	Regex("colou?r").match("color") -> true	✅
Wildcard	.	Regex("a.c").match("abc") -> true	✅
Character classes	[abc]	Regex("[abc]").match("b") -> true	✅
Character ranges	[a-z], [0-9]	Regex("[0-9]+").match("123") -> true	✅
Negated classes	[^0-9]	Regex("[^a-z]").match("1") -> true	✅
Hyphen in classes	[-a], [a-]	Regex("[-a]").match("-") -> true	✅
Start anchor	^	Regex("^hello").search("hello world") -> true	✅
End anchor	$	Regex("world$").match("world") -> true	✅
Grouping	(...)	Regex("(ab)*").match("abab") -> true	✅
Empty group	()	Regex("()a").match("a") -> true	✅
Empty branch	(a|)	Regex("(a|)").match("") -> true	✅
Capturing groups	(expr)	groups are numbered and marked in the automaton	✅
Escape sequences	`*	Regex("`*").match("*") -> true	✅
Substring search	search()	Regex("ab").search("xxxabyyy") -> true	✅
Full-text matching	match()	the pattern has to consume the whole string	✅

Escapes use a backtick instead of a backslash, so patterns written inside C++ string literals do not need to be double escaped. The escapable characters are * | ` ( ) + ? . [ ] ^ $ - , and escaping anything else is an error.

Build & Run

Quick build with g++

g++ -std=c++17 -Iinclude -o autiepie main.cpp src/lexer/lexer.cpp src/parser/parser.cpp src/automaton.cpp src/regex.cpp
./autiepie

CMake build

cmake -B build
cmake --build build

That produces two executables, autiepie (the test table in main.cpp) and autiepie_tests (the assertion based checks in tests/test.cpp).

Usage

Basic matching

#include "regex.h"

Regex r("hello");
r.match("hello");          // true
r.match("hello world");    // false
r.search("hello world");   // true

Quantifiers

Regex r1("a*b");
r1.match("b");        // true
r1.match("aaab");     // true

Regex r2("a+");
r2.match("a");        // true
r2.match("");         // false

Regex r3("colou?r");
r3.match("color");    // true
r3.match("colour");   // true

Character classes and ranges

Regex digit("[0-9]+");
digit.match("12345");         // true

Regex word("[a-zA-Z]+");
word.match("HelloWorld");     // true

Regex not_digit("[^0-9]");
not_digit.match("a");         // true
not_digit.match("5");         // false

Regex hyphen("[-a]");
hyphen.match("-");            // true

Alternation, wildcard, anchors

Regex animal("cat|dog|bird");
animal.match("dog");          // true

Regex any_char("a.c");
any_char.match("abc");        // true

Regex start_anchor("^hello");
start_anchor.match("hello");        // true
start_anchor.search("hello there"); // true

Regex end_anchor("world$");
end_anchor.match("world");          // true
end_anchor.match("world peace");    // false

Grouping

Regex group("(ab)*");
group.match("abab");          // true

Regex empty_group("()a");
empty_group.match("a");       // true

Regex empty_branch("(a|)");
empty_branch.match("");       // true

Escapes and search

Regex star("`*");
star.match("*");              // true

Regex r("abc");
r.search("xyzabc123");        // true
r.search("ab c");             // false

Test Coverage

main.cpp runs a table of 183 cases and prints pattern, text, expected, actual and a pass/fail column for each one. It covers literals, the three quantifiers, alternation, character classes and ranges, negated classes, the wildcard, both anchors, grouping and nesting, escapes, empty patterns and substring search.

tests/test.cpp is a smaller assertion based suite that returns a non-zero exit code when something fails, so it can be dropped into a script or a CI step.

Known Limitations

Limitation	Reason / workaround
No backreferences (\1)	not a regular language feature, a Thompson NFA cannot express it
No lookahead or lookbehind	not implemented
No Unicode classes	ASCII only for now
No lazy quantifiers (*?, +?)	matching is greedy
No POSIX classes ([:alpha:])	classes are written out by hand
No case insensitive flag	would go in as a constructor option
Capture offsets are not reported	the markers exist in the automaton, the reporting pass does not

Contributing

Bug reports, patches and ideas are welcome. Things that would be worth doing:

• Unicode support and the shorthand classes \d, \w, \s
• an API for reading capture group offsets back out
• non-greedy quantifiers
• case insensitive and multiline flags
• DFA compilation and minimisation
• caching the epsilon closure instead of recomputing it
• a proper benchmark suite

License

MIT. See LICENSE.md.

References

• https://swtch.com/~rsc/regexp/regexp1.html
• https://perl.plover.com/Regex/article.html
• https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html
• https://deniskyashif.com/2019/02/17/implementing-a-regular-expression-engine/
• https://xysun.github.io/posts/regex-parsing-thompsons-algorithm.html
• https://burntsushi.net/regex-internals/