From Newsgroup: comp.compilers

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
--- Synchronet 3.21b-Linux NewsLink 1.2