Simple Regex Engine

A vanilla JavaScript (bun) RegExp engine implementing Thompson's Construction and NFA simulation. It supports basic regex features and provides O(N*M) time complexity guarantees, making it resistant to ReDoS (Regular Expression Denial of Service) attacks that plague backtracking engines.

Features

• Literals: a, abc
• Concatenation: ab
• Union (Alternation): a|b
• Quantifiers: * (zero or more), + (one or more), ? (zero or one)
• Character Classes: [a-z], [0-9], [^a]
• Groups: (ab)
• Anchors: ^ (start), $ (end)
• Dot: . (any char except newline)

Usage

Library Example:

const { compile, match, RegExpEngine } = require('<path-to-regexp-engine>');

// Simple usage
const result = match('a*', 'aaaa');
if (result) {
  console.log(`Matched: ${result.match} at index ${result.index}`);
}

// Pre-compile for performance
const engine = compile('[a-z]+@[a-z]+\\.com');
if (engine.test('test@example.com')) {
  console.log('Valid email format!');
}

CLI Example:

The package comes with a CLI tool similar to grep.

# Basic usage
echo "hello world" | <path-to-cli.js> "hello"

# With file
<path-to-cli.js> "^ERROR" log.txt

Architecture

1. Parser: Converts regex string to an Abstract Syntax Tree (AST).
2. Compiler: Converts AST to a Non-deterministic Finite Automaton (NFA) using Thompson's Construction.
3. Matcher: Simulates the NFA execution on the input string (maintaining a set of active states).

License

MIT