🔍 Regular Expression Engine

Thompson's NFA construction with guaranteed linear-time matching

Overview

A complete regular expression engine built from scratch. Uses Thompson's NFA construction to guarantee O(n·m) matching time (n = input length, m = pattern size) — no pathological backtracking like PCRE-based engines.

This is a production-quality approach: the same algorithm used by grep, RE2, and Go's regexp package.

Concepts Demonstrated

Algebraic data types — regex AST and NFA state representation
Recursive descent parsing — regex syntax → AST with operator precedence
Thompson's construction — AST → NFA with ε-transitions
NFA simulation — set-based epsilon-closure (no backtracking)
Module design — clean API surface with internal implementation

Supported Syntax

Pattern	Matches
`.`	Any character (except newline)
`\d` `\w` `\s`	Digit, word char, whitespace
`\D` `\W` `\S`	Negated character classes
`[abc]`	Character class
`[a-z]`	Character range
`[^abc]`	Negated character class
`*` `+` `?`	Zero+, one+, optional
`\|`	Alternation
`(...)`	Grouping
`^` `$`	Start/end anchors

Key Functions

Function	Description
`compile`	Parse pattern string → compiled regex
`matches`	Full-string match test
`find`	Find first match (returns position + text)
`find_all`	Find all non-overlapping matches
`replace`	Replace first match with string
`replace_all`	Replace all matches
`split`	Split string on pattern

Architecture: Thompson's NFA

(* 1. Parse: string → AST *)
type regex = Char of char_matcher | Seq of regex * regex
           | Alt of regex * regex | Star of regex | ...

(* 2. Compile: AST → NFA (Thompson's construction) *)
(* Each regex node becomes a small NFA fragment *)
(* Fragments are connected via ε-transitions *)

(* 3. Simulate: NFA × string → bool *)
(* Track set of active states; advance on each character *)
(* No backtracking — always O(n × m) *)

This three-phase architecture separates concerns cleanly: parsing validates syntax, compilation builds the automaton, and simulation runs it efficiently.

Usage

let r = compile "ab+c" in
matches r "abbc"          (* → true  *)
matches r "ac"            (* → false *)
find r "xxxabbcyyy"       (* → Some (3, "abbc") *)
find_all r "abc abbc"     (* → ["abc"; "abbc"] *)
replace r "abc" "X"       (* → "X" *)
split r "xabcyabbcz"      (* → ["x"; "y"; "z"] *)

Why No Backtracking?

Many regex engines (Perl, Python, Java) use backtracking, which can take exponential time on pathological patterns like (a+)+b against "aaaaaa...". Thompson's NFA avoids this entirely by tracking all possible states simultaneously — if any state reaches an accept state, the match succeeds.