Well, PCRE, the most widely used regex lib in my experience, has a "DFA" mode (scare quotes because it's actually an NFA mode. See [1]). So the option is there,

Well, PCRE, the most widely used regex lib in my experience, has a "DFA" mode (scare quotes because it's actually an NFA mode. See [1]). So the option is there, even if most people use PCRE in standard recursive kablooey mode. I was working on a drop-in managed wrapper around re2[2] so .NET developers would have access to a good regex library, but damned if starting a company hasn't gotten in the way of finishing it. Still, re2 bindings are available for most other common platforms. (Also I don't believe Java's regex engine is automata-based, which would explain the performance gains.) 1. http://fanf.livejournal.com/37166.html http://fanf.livejournal.com/37166.html 2. http://code.google.com/p/re2/ http://code.google.com/p/re2/