brzozowski

A regular expression engine built from Brzozowski derivatives, in Rust.

Instead of compiling a pattern into an NFA and simulating it (Thompson's construction), this takes the older, algebraic route: the derivative D_c(R) is "the regex that remains after consuming c". Matching is then just deriving the pattern character by character and asking whether what's left accepts the empty string. The DFA falls out of the same operation — its states are the distinct derivatives of the pattern.

Usage

// (ab)*
let re = Regex::Star(Box::new(Regex::cat(
    Regex::Char('a'),
    Regex::Char('b'),
)));

// Derive on the fly
assert!(re.matches("abab"));

// Or precompute the DFA and match in O(1) per character
let dfa = Dfa::build(&re);
assert!(dfa.matches("abab"));

How it works

• nullable() — does this regex accept the empty string?
• derive(c) — the Brzozowski derivative, one rule per constructor
• matches() — fold derive over the input, then check nullable
• Dfa::build() — BFS over derivatives; each distinct derivative is a state

Normalization

Derivatives grow without bound unless simplified. cat and alt are smart constructors that apply the identities as terms are built.

alt normalizes modulo ACI (associativity, commutativity, idempotence) by flattening nested alternations into a sorted set and rebuilding a single canonical tree. This is what makes the state set finite — without it, a*a* grows one Alt layer per input character and Dfa::build never terminates. Brzozowski's finiteness theorem holds only modulo ACI, and this is where that clause earns its keep.

Status

Supports concatenation, alternation, and Kleene star over char.

Not yet: a parser (patterns are built as ASTs by hand), ? and + sugar, character classes and ., anchors, capture groups, lazy DFA construction.

Backreferences are out of scope — they aren't regular, and are precisely what forces the backtracking this approach avoids.

References

• Brzozowski (1964), Derivatives of Regular Expressions
• Owens, Reppy & Turon (2009), Regular-expression derivatives reexamined
• Cox (2007), Regular Expression Matching Can Be Simple And Fast

License

GPL-3.0