Announce: Pyre - A Regular Expression Engine Based on Brzozowski Derivatives

After working intermittenly on this project for several years, I was
finally able to get it in a state where it's worth sharing. Some of you may
remember me posting about regular expressions and DFA generation here some
time ago.


https://github.com/clintolsen/pyre


Pyre is a Python implementation of a regular-expression engine built using
Brzozowski derivatives. Unlike traditional engines that first translate the
expression into an NFA and then to a DFA, a derivative-based engine
constructs the DFA directly from the expression by repeatedly applying
derivative rules. This also allows novel set operations like language
complement `~RE` and intersection `RE & RE` in an efficient manner. Because
matching is performed on the resulting DFA, the recognizer runs in linear
time and does not require backtracking.


The project includes:


- A lexer and parser written in PLY
- A full AST of regular-expression operators
- DFA construction using derivatives
- Capture-group support
- match() and search() APIs
- A command-line interface called pyre


I got interested in interpreters and translators during an internship at
Intel working on a test pattern generator for IEEE 1149.1 compliant test
access ports. The tool was written using lex & yacc, and I had John's
O'Reilly book as my guide. Since then I've been fascinated with this topic.


Thanks to everyone who participated in the discussions helping me with
pyre.


-Clint

Return to the comp.compilers page.
Search the comp.compilers archives again.