Back to Projects
Thompson
Regular expression engine in Go built on Ken Thompson's 1968 construction, compiled to WebAssembly to animate the NFA reading a string one character at a time.
Architecture Overview
Pattern → syntax tree (recursive descent) → NFA (Thompson's construction, renumbered left to right) → simulation over the current state set; Trace records fired and epsilon edges per step, and Graph/DOT export the NFA as JSON nodes/edges or Graphviz.
Key Challenges
Keeping matching linear for patterns like (x+x+)+y that blow up backtracking engines, using a generation-stamped mark array so each state enters a set at most once per step, while recording the same run in detail for the visualizer without diverging from Match.
Security Considerations
Not a security-focused project; the linear-time guarantee does make it immune to the catastrophic backtracking behind ReDoS.
Future Improvements
Possible next steps: subset construction into a DFA, unanchored search, and capture groups.
Technical Impact
- Built a regex engine in stdlib-only Go: a recursive-descent parser, Thompson's NFA construction from patched fragments, and a set-of-states simulation that matches in linear time.
- Supported full-Unicode literals, alternation, grouping, * + ? quantifiers, character classes, negated classes, and \d \w \s shorthands, with position-tagged syntax errors.
- Verified correctness by diffing 3,000 random patterns against Go's regexp package over every string up to length 5, plus a pathological-pattern test that guards linear-time matching.
- Compiled the engine to WebAssembly and exposed compile/trace to JavaScript, driving an interactive visualizer that animates active states and fired edges step by step.