regex-master

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

1. 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).

2. 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.

3. 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.

4. Build in this order:

• Parser -> AST.
• AST -> bytecode / epsilon-NFA.
• Thompson VM matcher.
• Optional enhancements: DFA cache, one-pass specialization, submatch extraction.

5. 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.