Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics
summary
A derivative-based algorithm produces input-linear matching without actual backtracking while preserving PC (backtracking) semantics and supporting anchors and counting; it ships as a new .NET regex backend in .NET7, implements a regex rewrite system plus BDD-based alphabet compression for Unicode, caches lazily built location-derivative states, falls back to NFA when needed, and undergoes thousands of tests and industrial benchmarks (including CredScan) that show fewer pathological outliers; the implementation comes with what authors claim is the first industrial proof of correctness.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:45Matching algorithms trade-offs
- 2:21Non-backtracking engine in .NET
- 3:48Regex syntax semantics
- 5:34Key innovations
- 7:20Unicode compression with BDDs
- 8:45Derivatives and caching
- 10:13Anchors alternation challenges
- 11:39Backtracking simulation
- 13:27Integration into .NET
- 14:10Benchmark results
- 15:37Q&A
related talks
51mRegular Expressions in C++, Present and Future
37mAll About Regular Expressions
14mRegex Matching with Counting-Set Automata
19mVerbatim++: Verified, Optimized, and Semantically Rich Lexing with Derivatives
29mVerified and Efficient Matching of Regular Expressions with Lookaround
24mSolving String Constraints with Regex-Dependent Functions through Transducers wi
18mRegular Expression Matching using Bit Vector Automata
22mStatic Analysis for Checking the Disambiguation Robustness of Regular Expressions