Possible regex engine optimizations?

Re: [perl6-language] Does ::: constrain the pattern engine implementation?

On Wed, 28 Aug 2002, Dan Sugalski wrote:

> A medium-term goal for the regex engine is to note where a DFA would give 
> correct behaviour and use one, rather than going through the more 
> expensive generalized regex engine we'd otherwise use.

What would it take to make an experimental prototype of this?

I'm willing to take a stab at it, assuming I can find the time.  Since my 
free time always seems to get absorbed by other things, let's not set any 
expectations -- I can't promise to accomplish anything at all!  But until 
someone else with time is ready to tackle this, there's nothing to lose...
(If someone else is ready to tackle it, don't wait on me right now!)

I'm assuming the best way to implement such a DFA would be to compile into 
Parrot opcodes rather than writing an "engine" to interpret the DFA; does 
that seem like the right approach?

The other possible optimization that comes to mind would be to try to use 
registers as much as possible to execute the regex and only use a stack if 
unavoidable.  This would be more complex, but it ought to be faster.

Suppose that someday we have a DFA-based regex engine that can only handle 
a subset of the full pattern syntax.  I hope that we'll still be able to 
automatically factor out subpatterns of more complex patterns, so that the 
parts which are simple enough can be implemented with a DFA, and let the 
expensive generalized regex engine handle the rest...  (I hope it wouldn't 
be necessary for the programmer to explicitly separate out the subpatterns 
which could be optimized!)

Deven

• Possible regex engine optimizations? by Deven T. Corzine
• Re: Possible regex engine optimizations? by Steve Fink
• Re: Possible regex engine optimizations? by Melvin Smith