Regex Engine

# Regex Engine PRD

## Overview
Build a working regular expression engine that can compile and execute patterns against input strings.

## Requirements
- Support literal character matching
- Support metacharacters: `.` (any char), `^` (start), `$` (end)
- Quantifiers: `*` (0+), `+` (1+), `?` (0 or 1), `{n}`, `{n,m}`
- Character classes: `[abc]`, `[a-z]`, `[^abc]`
- Predefined classes: `\d`, `\w`, `\s` and their negations
- Grouping with `()` and alternation with `|`
- Capture groups — return matched substrings
- Greedy vs lazy matching (`*?`, `+?`)
- Escape sequences: `\\`, `\.`, etc.
- A `match(pattern, text)` function that returns match objects
- A `test(pattern, text)` function that returns boolean
- Handle edge cases: empty pattern, empty string, nested quantifiers
- Performance: handle patterns up to 100 chars against 10KB text

## Tech Stack
- Any language (Node.js, Python, Go, Rust)
- No regex libraries allowed — build the engine from scratch

## Scoring Criteria
- **Functional (40%)**: Core matching works, quantifiers, character classes, groups
- **Quality (20%)**: Clean parser/compiler architecture, handles edge cases, no crashes
- **Fidelity (25%)**: All specified features implemented, capture groups work
- **Speed (15%)**: Time bonus