On 6/7/2010 8:01 PM, Joel de Guzman wrote:
On 6/8/10 12:10 AM, Eric Niebler wrote:
An interesting research project would be to investigate whether xpressive's hybrid static/dynamic NFA design can be applied to DFAs as well, with similar perf wins. This would be a non-trivial undertaking, like completely reimplementing xpressive.
Just to remind you, there's a very good DFA implementation underneath Spirit Lex. The interface is not perfect (Ben has requested for some input in that area), but the implementation is very good. Spirit Lex is proto on top of lexertl (Ben's work). We find it to be one of the fastest lexer, close to performance to the fastest (RE2C) which is a code-gen that generates a humongous switch.
I haven't forgotten. IIRC, lexertl is like dynamic xpressive: it accepts strings as input and builds a FSA. I was speculating about what the lexertl equivalent of static xpressive would look like and whether it would be even faster. Then static xpressive could use static lexertl for simple regexes, and dynamic xpressive could use the dynamic one. -- Eric Niebler BoostPro Computing http://www.boostpro.com