RE#: high performance derivative-based regex matching with intersection, complem

Re:RE#: high performance derivative-based regex matching wit... by kazinator on Thursday July 24, 2025 @08:51PM (#44678213)

> The first industrial implementation of derivatives for standard regexes in an imperative language (C#) materialized a decade later [Saarikivi et al. 2019]

Nope; I did it in TXR in early 2010:

  b839b5a212fdd77c5dc95b684d7e6790292bb3dc    Wed Jan 13 12:24:00 2010 -0800    Impelement derivative-based regular expressions.

[ Parent | on HN ]

Re:RE#: high performance derivative-based regex matching wit... by def-lkb on Thursday July 24, 2025 @09:57PM (#44678614)

https://sourceforge.net/projects/libre/ dates back to 2001. (One could object it is not imperative enough, whatever that means :))

[ Parent | on HN ]

Re:RE#: high performance derivative-based regex matching wit... by burntsushi on Friday July 25, 2025 @09:47AM (#44683083)

The claim here wasn't just "first implementation of derivatives." It was a far more precise "first industrial implementation of derivatives for standard regexes in an imperative language."

[ Parent | on HN ]

Re:RE#: high performance derivative-based regex matching wit... by high_na_euv on Friday July 25, 2025 @07:26AM (#44681965)

Whats TXR

[ Parent | on HN ]

Re:RE#: high performance derivative-based regex matching wit... by gjm11 on Friday July 25, 2025 @08:40AM (#44682472)

It isn't clear to me what exactly OP means by "industrial" but it seems possible that they might not consider it to apply to TXR.

[ Parent | on HN ]

Re:RE#: high performance derivative-based regex matching wit... by kazinator on Friday July 25, 2025 @03:07PM (#44687048)

I implemented it as a committed feature in a programming language designed to be used for solving problems in the real world, rather than accompanying academic research into the topic.

No different from what was done in C#.

[ Parent | on HN ]

Re:RE#: high performance derivative-based regex matching wit... by burntsushi on Friday July 25, 2025 @09:49AM (#44683109)

What is TXR? Was this implementation really "industrial"? Did it have the caching present in RE# to avoid worst case exponential compile times? Did it support Unicode? Did it have prefilters? What kind of match semantics did it support?

"industrial" in this context to me means something like, "suitable for production usage in a broad number of scenarios."

IDK if RE# lives up to that, but their benchmark results are impressive. This paper is a year old. In which production systems is RE# used?

[ Parent | on HN ]