One of the most interesting ways to handle regex and general parsing IMO is by using derivitives. I'm not sure if this uses any of the ideas from that area, but

One of the most interesting ways to handle regex and general parsing IMO is by using derivitives. I'm not sure if this uses any of the ideas from that area, but with derivitive based regex parsing instead of constructing some specific program to parse some language, you parse by instead transforming the original language to be the language of the union of the old language as well as the character just seen. In addition to being incredibly simple to implement compared to traditional regex and parser generators, I think it is also interesting in that while it is really simple and looks like you are interpreting a language, it is actually powerful enough to parse arbitrary CFGs in O(n^3) with some help from memoization and fixpoints. See http://matt.might.net/articles/parsing-with-derivatives/ http://matt.might.net/articles/parsing-with-derivatives/ for more details. I think the interesting aspect in terms of performance with something like this is that the derivitive based parsing system is explicitly streaming since it only stores the remaining input string and a regex string. Also, I think you can get around some of the performance issues with constructing these strings by replacing certain parts of the regex with more traditional NFAs/DFAs. In particular, I think this method provides an easy way to use simple equality matching for constant strings, DFAs for Kleene star, NFAs for the rest of the typical NFA features like the or operator and negation, then finally using the derivitive for very complicated features like capturing groups and backreferences.