Annotated Bibliography of Regular Expression Engines

Cox, Russ (Jan 2007). “Regular Expression Matching Can Be Simple And Fast”. Retrieved 17 July 2020.

Russ Cox demonstrates a case where a short regular expression can cause some regex engines to take an unreasonably long time to complete a search, while others can complete the search in microseconds. The article starts with the theory of regular expressions and how they can be expressed as deterministic and non-deterministic finite automata, then builds up the code of a simple regex engine step by step from there. In Cox’s words, “good theory leads to good programs”. Understanding the theory of regular expressions leads to writing implementations that are robust and performant. The article also compares several regex engines according to their performance and implemenations.

Gallant, Andrew (23 Sep 2016). “ripgrep is faster than {grep, ag, git grep, ucg, pt, sift}”. Retrieved 17 July 2020.

ripgrep is a code searching tool similar to ack, The Silver Searcher, or grep -r. It aims to have faster performance than any of the alternatives. ripgrep’s author, Andrew Gallant, benchmarks ripgrep and other similar tools and explains in-depth how he achieved these results. This includes a comparison of available regex engines. Authors of applications that use regular expressions can learn about techniques used by regex engines, the pros and cons of each strategy, and how that affects your application.