Groups | Search | Server Info | Login | Register
Groups > comp.compilers > #3717
| Path | csiph.com!weretis.net!feeder9.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end |
|---|---|
| From | Clint Olsen <clint.olsen@gmail.com> |
| Newsgroups | comp.compilers |
| Subject | Announce: Pyre - A Regular Expression Engine Based on Brzozowski Derivatives |
| Date | Sun, 08 Feb 2026 00:58:52 +0000 |
| Organization | Compilers Central |
| Sender | johnl%iecc.com |
| Approved | comp.compilers@iecc.com |
| Message-ID | <26-02-005@comp.compilers> (permalink) |
| MIME-Version | 1.0 |
| Content-Type | text/plain; charset="UTF-8" |
| Injection-Info | gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="59444"; mail-complaints-to="abuse@iecc.com" |
| Keywords | available, DFA |
| Posted-Date | 07 Feb 2026 20:40:09 EST |
| X-submission-address | compilers@iecc.com |
| X-moderator-address | compilers-request@iecc.com |
| X-FAQ-and-archives | http://compilers.iecc.com |
| Xref | csiph.com comp.compilers:3717 |
Show key headers only | 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
Announce: Pyre - A Regular Expression Engine Based on Brzozowski Derivatives Clint Olsen <clint.olsen@gmail.com> - 2026-02-08 00:58 +0000
csiph-web