Path: csiph.com!weretis.net!feeder9.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Clint Olsen 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> 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 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