NOTES.md

Notes

TODO

Hard (impossible?) to implement in a DFA

• Non-greedy repetition (*?, +?)
• Subexpression calls
• Assertions (lookahead/lookbehind)

Possible and should be implemented

• Anchors
• Character property inversion
• Character set inversion
• Character set composition
• Case-insensitive mode
• Multi-line mode
• Free-spacing mode
• Capturing

Other work

• DFA minimization
• NFA with lazy DFA transformation
• Recheck algorithm for finding ReDoS vulnerabilities
• Much more documentation

Links

Implementations

• Irregexp
• .NET
• one-more-re-nightmare
• Python
• RE2
• Recheck
• Ruby
• Rust (PR)
• TCL
• V8
  • Tier up
  • Deterministic

Various papers, blog posts, and articles

• A Closer Look at TDFA
• NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions (2000)
• Static Detection of DoS Vulnerabilities in Programs that use Regular Expressions (2017)
• On the Impact and Defeat of Regular Expression Denial of Service (2020)
• Russ Cox series
• A DFA for submatch extraction
• Compiling Nondeterministic Transducers to Deterministic Streaming Transducers
• Translating Regular Expression Matching into Transducers
• DFA minimization
• NFA minimization
• Lazy DFAs
• TruffleRuby regexp analyzer
• Practical Experience with TRegex and Ruby
• Optimizing based on source encoding in graal
• Regular Expressions, Text Normalization, Edit Distance

Ruby

• RubyConf 2013: Beneath The Surface: Harnessing The True Power of Regular Expressions in Ruby
• Exploring Ruby's Regular Expression Algorithm