Hmm. I kinda wonder how something like a regexp engine based on marpa would fall. It would probably be slower in the common well behaved cases, as well as preprocessing. But I wonder if there are any cases that couldn't be done in a O(n) way if you limit yourself to only one match (instead of finding all possible matches like it actually can do). Marpa definitely handles most degenerate regexp cases linearly (once you make the match generation not do overlapping entries), but there may be some regexp feature it can't handle?

Bringing a fully general CFG parser to parse regexps would be like hunting mosquitos with a nuke though..