Regular Expressions Reading List

Regex is one of main interests. Over the years I’ve been learning about them, I’ve accumulated some valuable materials - mostly related to perdormance and engine internals.

• Mastering Regular Expressions, 3rd Edition, Jefferey Friedl, 2009
• Regex101 - online regex tester and debugger
• Test app - original thanks to Kamil Szubrycht
• OWASP on ReDoS
• Maciek Rząsa: Performance of Regular Expressions
• Katafrakt: Regular expression how do they work?
• The true power of regular expressions
• FlashText algorithm vs regular epxressions for keyword matching
• Sam Safron: Debugging 100% CPU usage in production Ruby on Rails systems
• Jeff Atwood: Regex performance
• Mimicking atomic groups in JS regex
• RexEgg - Regex Tutorial, especially:
  • Explosive quantifiers
  • Mastering quantifiers
• regular-expressions.info:
  • Possesive quantifiers
  • Catastrophic backtracking
  • Regex engine internals
• Russ Cox regex series:
  • Regular Expression Matching Can Be Simple And Fast
  • Regular Expression Matching: the Virtual Machine Approach
  • Regular Expression Matching in the Wild
  • Regular Expression Matching with a Trigram Index
• Loggly:
  • Five invaluable techniques to improve regex performance
  • Regexes bad, better, best
• ReDoS cases:
  • Sam Safron: Debugging 100% CPU usage in production Ruby on Rails systems
  • CloudFlare postmortem (2019)
  • StackOverflow postmortem (2016)
  • Rack (Ruby web server interface)
  • Atom editor (2016)
• ReDoS research:
  • Virginia Tech Blogpost
  • [Virginia Tech Paper](http://people.cs.vt.edu/~davisjam/downloads/publications/DavisCoghlanServantLee-EcosystemREDOS-ESECFSE18.pdf
  • SoK: Demystifying Regular Expression Denial of Service ReDoS survey
• Optimisations
  • Using Selective Memoization to Defeat Regular Expression Denial of Service (ReDoS)
  • Ruby Core: memoisation that makes many regex polynomial instead of exponential
  • V8 (JavaScript) optimisations: 1, 2
  • .Net 7 Regex improvements
  • .Net 5 Regex performance improvements
  • V8 (JavaScript) Regex series esp
    • Improving V8 regular expressions
    • An additional non-backtracking regex engine
• Internals
  • .Net Symbolic regex matcher
  • Regular Expressions and Onigmo, the Ruby regular expression engine
  • Rust Regex development
  • Very ambitious persional project - building an own regex engine, described step-by-step
  • [Maciej Rząsa (yours truly], talk: Magical journey through regex engine internals](https://www.youtube.com/watch?v=ZM2h7GxdKL8)
• Code
  • Onigmo - Ruby library to debug regex engine internals (parsing and compiling
  • Python re - regular expression engine source code - in python
  • Ruby regexec.c - the bulk of Ruby’s regex engine - in C