Re:Building a Regex Engine in Fewer Than 40 Lines of Code
by yellowflash on Tuesday December 05, 2017 @10:13AM
(#15852155)
Regular expressions are truly elegant. If the regex engine is built in a functional (compositional style), it is even more elegant.
This particular Functional pearl is my favorite, http://sebfisch.github.io/haskell-regexp/regexp-play.pdf
For TLDR on the paper, It slowly builds an abstraction and implementation on regex engine which runs on O(mn) where m is length of the regex and n - length of the text. Then they generalize it to do grouping and even extend it to match context free grammar (using lazy evaluation mostly).
And my implementation of the same in scala (40 lines if you ignore some niceties, and its terribly fast asymptotically) https://gist.github.com/yellowflash/826004277874cadabbc502e6...
For TLDR on the paper, It slowly builds an abstraction and implementation on regex engine which runs on O(mn) where m is length of the regex and n - length of the text. Then they generalize it to do grouping and even extend it to match context free grammar (using lazy evaluation mostly).