Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics

Explore a groundbreaking 19-minute conference talk from PLDI 2023 that introduces a novel derivative-based theory and algorithm for nonbacktracking regex matching. Delve into the development of a new regex backend for .NET that supports anchors, counting, and preserves backtracking semantics while allowing for lookaround extensions. Examine the formal proof of correctness, a rarity in industrial regex matcher implementations, and learn about the comprehensive foundation, matching algorithm, and key implementation aspects involving a regex rewrite system. Gain insights from the extensive evaluation conducted over industrial case studies and comparisons with other regex engines. Access supplementary materials, including reusable artifacts, to further understand this significant advancement in regex matching technology.

[PLDI'23] Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics