All About Regular Expressions
summary
History and concrete tradeoffs: Thompson NFA compilation (1968) shows how regex compile to state machines and powers linear-time search used in grep which actually came from the QED editor; Aho–Corasick /egrep introduces character classes and fast string algorithms; popular engines like PCRE use backtracking and can suffer exponential slowdowns on crafted inputs; Russ Cox proves this empirically and ships RE2, a linear-time NFA engine that forbids backreferences to avoid pathological worst cases.
AI-written summary · about
chapters (9)
- 0:00Start
- 0:59Overview
- 5:00The Rand Project
- 7:00The Star Operator
- 8:19Finite Automata and Their Decision Problems
- 8:57Deterministic and Non-Deterministic Automata
- 13:05Regular Expression
- 24:19The Rules for Regular Expressions
- 29:17Efficient String Matching
related talks
51mRegular Expressions in C++, Present and Future
29mVerified and Efficient Matching of Regular Expressions with Lookaround
21mEfficient Matching of Regular Expressions with Lookaround Assertions
22mStatic Analysis for Checking the Disambiguation Robustness of Regular Expressions
01h 03mCompile-Time Regular Expressions
14mRegex Matching with Counting-Set Automata
24mSolving String Constraints with Regex-Dependent Functions through Transducers wi
22mEREQ: Regular Expressions with Quantifiers and Incremental Quantifier Elimination