regex

A compact C++20 regular expression engine built around a recursive-descent parser and a Thompson-style NFA executor.

Scope

This repository intentionally targets a well-defined, interview-friendly subset instead of pretending to be a full std::regex replacement.

Supported syntax:

• literal characters
• grouping with ( and )
• alternation with |
• concatenation
• quantifiers *, +, and ?
• wildcard .
• escaped literals and control characters such as \*, \+, \(, \), \n, \t, and \r

Supported operations:

• compile a pattern into an NFA
• full-string match
• leftmost search with longest accepted prefix for a given start offset
• replace the first found match via MatchResult

Explicitly out of scope for this implementation:

• character classes like [a-z]
• capture-group extraction
• backreferences
• lazy quantifiers
• Unicode-aware matching

Why This Version Is Different From The Original Toy

• the parser was rewritten as a recursive-descent parser so postfix quantifiers bind correctly
• Thompson NFA construction for * and + was fixed to avoid invalid epsilon wiring
• epsilon-closure based execution replaced the earlier fragile recursive accept path
• cycle-safe graph destruction prevents crashes on quantified patterns
• a CLI, regression test runner, and benchmark executable were added
• the legacy test-suite.dat file is now used as a real regression source instead of dead data

Repository Layout

• regex/: engine sources, CLI, tests, and benchmark entry points
• test-suite.dat: data-driven regression cases
• BENCHMARK_RESULTS.md: measured Release benchmark results and trade-offs

Build

Debug build and test run:

cmake -S . -B build-local -DCMAKE_CXX_COMPILER=clang++
cmake --build build-local -j4
ctest --test-dir build-local --output-on-failure

Release benchmark run:

cmake -S . -B build-release -DCMAKE_BUILD_TYPE=Release -DCMAKE_CXX_COMPILER=clang++
cmake --build build-release -j4
./build-release/regex_benchmark

CLI Example

Full match:

./build-local/regex_cli --pattern '(ab|a)(bc|c)' --text 'abc' --mode full

Search plus replace:

./build-local/regex_cli --pattern 'ab+c' --text 'ts=42 zzabbbbbczz ok' --mode search --replace '<MATCH>'

Validation

• data-driven regression checks from test-suite.dat
• focused feature tests for wildcard, escapes, invalid syntax, empty-match handling, search, and replace
• benchmark smoke coverage via CTest

Measured Snapshot

• compile_nested_alternation: 2284.93 ns/op
• full_match_positive: 3755.53 ns/op
• search_in_log_line: 3573.92 ns/op

See BENCHMARK_RESULTS.md for context and design trade-offs.