RegexInt

A small regular-expression interpreter written in TypeScript, built as a learning project. It parses a pattern into an AST and matches input with a backtracking engine — the same overall design as PCRE-style regex engines.

Is this useful? Not as a replacement for JavaScript's built-in RegExp (that engine is faster and more complete). It is useful for understanding how regex actually works: tokenizing, recursive-descent parsing, and backtracking matching. Reading ~500 lines here teaches what a decade of .match() calls doesn't.

Pipeline

pattern string ──▶ Parser ──▶ AST ──▶ Matcher ──▶ MatchResult
                (parser.ts)  (ast.ts) (matcher.ts)

• src/parser.ts — recursive-descent parser. Alternation binds loosest, quantifiers tightest, just like a real engine.
• src/ast.ts — the node types the parser produces.
• src/matcher.ts — continuation-passing backtracking matcher.
• src/index.ts — the public Regex class.
• src/cli.ts — a CLI that also prints the parsed AST.

Usage

import { Regex, match } from "./src/index.js";

const re = new Regex("(\\d{4})-(\\d{2})-(\\d{2})");
re.test("2026-07-23");            // true
re.search("date: 2026-07-23");    // { match: "2026-07-23", index: 6, groups: [...] }

new Regex("\\d+").findAll("a1b22c333").map(m => m.match); // ["1", "22", "333"]

match("a.*?c", "axcxc")?.match;   // "axc"  (lazy quantifier)

CLI

npm run demo -- "(cat|dog)s?" "I have dogs"

Prints whether it matched, the span, captured groups, and the full AST.

Supported syntax

Feature	Examples
Literals & concatenation	abc
Any char	. (not newline)
Alternation	`a
Quantifiers	* + ? {n} {n,} {n,m}
Lazy quantifiers	*? +? ?? {n,m}?
Character classes	[abc] [a-z0-9_] [^...]
Shorthands	\d \D \w \W \s \S
Anchors	^ $
Groups	(...) capturing, (?:...) non-capturing
Escapes	\. \( \n \t …

Not implemented (deliberately, to keep it small): backreferences, lookaround, named groups, Unicode property escapes, flags (i/g/m).

Develop

npm install
npm test        # 56 assertions, cross-checked against native RegExp
npm run build   # type-check + emit to dist/

A note on catastrophic backtracking

Because this is a backtracking engine, pathological patterns like ^(a+)+$ against a long non-matching string take exponential time — they will appear to hang. That's not a bug; it's the well-known failure mode of backtracking regex engines, and reproducing it here is part of the lesson. Production engines like RE2 avoid it by compiling to an NFA and matching in linear time — a natural next extension for this project.