root `WRITEUP` NU-RE
NU-RE A tiny regex engine based on Brzozowski derivatives `2025-02-11` Project Files • GitHub Repo • nu-re.c NU-RE is a 200-line regex engine in C99 that does away with finite automata and backtracking by using regular expression derivatives. It’s a small practical implementation of the algorithms described in Derivatives of Regular Expressions (Brzozowski, 1964) and Regular-expression derivatives reexamined (Owens, Reppy, Turon). See the project’s readme for more on this. NU-RE’s feature set, regular expression grammar and test suite are identical to CPS-RE’s, modulo lazy and possessive quantifiers, because NU-RE is not a backtracking engine. And, like CPS-RE, it supports regular expression intersection and complementation. It’s a shame nobody talks about Brzozowski derivatives. A regular language is fully determined by its derivatives and their nullability, and, due to Brzozowski, for both we have natural algorithms operating directly on regular expressions. The upshot is that regular expressions are not just human friendly; they're also fundamentally computer friendly.
© 2025 Emilien Breton `NU-RE/WRITEUP.md`

NU-RE

A tiny regex engine based on Brzozowski derivatives 2025-02-11

NU-RE is a 200-line regex engine in C99 that does away with finite automata and backtracking by using regular expression derivatives. It’s a small practical implementation of the algorithms described in Derivatives of Regular Expressions (Brzozowski, 1964) and Regular-expression derivatives reexamined (Owens, Reppy, Turon). See the project’s readme for more on this.

NU-RE’s feature set, regular expression grammar and test suite are identical to CPS-RE’s, modulo lazy and possessive quantifiers, because NU-RE is not a backtracking engine. And, like CPS-RE, it supports regular expression intersection and complementation.

It’s a shame nobody talks about Brzozowski derivatives. A regular language is fully determined by its derivatives and their nullability, and, due to Brzozowski, for both we have natural algorithms operating directly on regular expressions. The upshot is that regular expressions are not just human friendly; they're also fundamentally computer friendly.