| name | regex-master |
| description | Master-level regular expression design, explanation, and engine implementation guidance grounded in Russ Cox's regex corpus and linked materials. Use when tasks involve constructing or explaining regex patterns, comparing VM/NFA/DFA/Pike/one-pass engines, building regex interpreters or bytecode VMs, implementing state-machine matchers in C or OCaml, designing submatch extraction, discussing regex complexity/philosophy, or integrating regex with code-search pipelines such as trigram-prefilter plus exact verification. |
Regex Master
Execute this workflow whenever regex theory or implementation quality matters more than ad-hoc pattern guessing.
Workflow
- Classify request into one or more tracks:
- Pattern construction/explanation.
- Engine architecture (VM/NFA/DFA/one-pass/Pike).
- Implementation in C or OCaml.
- Search-at-scale (index + regex verification).
- Load only needed references:
- Use
references/russ-cox-regexp-map.md for conceptual and historical grounding.
- Use
references/implementation-playbook.md for concrete engineering decisions.
- Select a strict scope contract before coding:
- Core regular syntax only (
()|*+?, literals, escapes).
- Optional safe extensions (classes, non-greedy quantifiers).
- Reject non-regular features unless user explicitly accepts loss of guarantees.
- Build in this order:
- Parser -> AST.
- AST -> bytecode / epsilon-NFA.
- Thompson VM matcher.
- Optional enhancements: DFA cache, one-pass specialization, submatch extraction.
- Validate behavior with adversarial tests:
- Empty regex/input.
- Nested quantifier ambiguity.
- Known catastrophic-backtracking families to confirm non-backtracking stability.
Philosophy and Interpretation Standard
- Explain regex semantics in automata terms first, syntax sugar second.
- State complexity claims precisely and tie them to feature scope.
- Prefer deterministic failure messages when unsupported features appear.
- Keep parser, compiler, VM, and optional DFA layers independent for easier proof and tuning.
Implementation Starters
Use reusable code under scripts/ as baseline seeds.
C seed
- File:
scripts/regex_vm_c.c
- Provides: recursive-descent parser, AST, bytecode compiler, Thompson-style VM, program dump.
- Build and run:
gcc -O2 -std=c11 scripts/regex_vm_c.c -o /tmp/regex_vm_c
/tmp/regex_vm_c 'a(b|c)*d' 'abcbcd'
OCaml seed
- File:
scripts/regex_vm_ocaml.ml
- Provides: algebraic AST, compiler to instruction array, VM simulation, instruction dump.
- Build and run:
ocamlopt -O3 scripts/regex_vm_ocaml.ml -o /tmp/regex_vm_ocaml
/tmp/regex_vm_ocaml 'a(b|c)*d' 'abcbcd'
Mandatory output quality for responses
- Include a formal syntax subset statement.
- Include engine model (VM/NFA/DFA) and why it was chosen.
- Include asymptotic behavior and memory strategy.
- Include at least one counterexample or edge case in tests.
- If discussing code search, include trigram-prefilter architecture before regex execution.
