Groups | Search | Server Info | Login | Register

Groups > comp.compilers > #3717

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

Show all headers | View raw

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

Back to comp.compilers | Previous | Next | Find similar

Thread

Announce: Pyre - A Regular Expression Engine Based on Brzozowski Derivatives Clint Olsen <clint.olsen@gmail.com> - 2026-02-08 00:58 +0000

csiph-web