Static Analysis for Checking the Disambiguation Robustness of Regular Expressions
summary
Defines robustness as agreement between POSIX vs greedy match extraction and proves the decision problem PSPACE-complete. Builds a greedy NFA model and reduces robustness checking to reachability in an exponential robustness graph explored on-the-fly; implements a base algorithm (≈1 hour for 10,000 regexes, ~3% timeouts) and an optimized analysis that runs the corpus in ~2.5 minutes and reduces failures to <0.04%, and finds ~4% non-robust real-world regexes.
AI-written summary · about
chapters (12)
- 0:00Regex disambiguation robustness
- 2:28Disambiguation policies in engines
- 5:00Impact of non-robust regexes
- 6:24Greedy NFA model
- 11:30Robustness via exploration graph
- 14:45Robustness decision complexity
- 15:28Algorithm implementation
- 17:14Summary of contributions
- 18:21Q&A: Streaming and parsing
- 19:47Q&A: Grammar ambiguity link
- 20:52Q&A: Beyond classical regex
- 21:57Closing remarks
related talks
24mSolving String Constraints with Regex-Dependent Functions through Transducers wi
37mAll About Regular Expressions
51mRegular Expressions in C++, Present and Future
21mEfficient Matching of Regular Expressions with Lookaround Assertions
29mVerified and Efficient Matching of Regular Expressions with Lookaround
14mRegex Matching with Counting-Set Automata
22mA Categorical Basis for Robust Program Analysis
01h 03mCompile-Time Regular Expressions