Regular Expressions in C++, Present and Future
summary
Explains how C++ regex compilers build NFAs and how four concrete algorithms behave: naive DFS with backtracking, DFS plus memoization (polynomial time O(states×length) but O(states×length) memory), NFA/BFS (streaming with one-row memory) and DFA (fast O(n) match but potentially exponential precomputation). Shows the StackOverflow outage cause: a pattern with 2^n paths and n=32 taking ~90 seconds in DFS, lists costly features (capturing groups, backreferences, brace quantifiers) and recommends re2 fallback strategy, state limits, and compile-time or JIT regex approaches.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 4:57Regular Expressions Examples
- 20:58DFA
- 24:19Algorithm Characteristics
- 25:57Implementation Algorithm Matrix
- 27:36Capturing Groups
- 30:40Back Reference
- 34:05Conclusion
- 35:48T1 Line
- 37:32Recap
- 39:30Comments
- 41:45Other Questions
related talks
37mAll About Regular Expressions
14mRegex Matching with Counting-Set Automata
01h 03mCompile-Time Regular Expressions
21mEfficient Matching of Regular Expressions with Lookaround Assertions
22mStatic Analysis for Checking the Disambiguation Robustness of Regular Expressions
24mSolving String Constraints with Regex-Dependent Functions through Transducers wi
29mVerified and Efficient Matching of Regular Expressions with Lookaround
19mDerivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics