Converting Perls regex engine from Pure NFA to hybrid DFA/NFA (was Re: [SPOILER] Perl 'Hard' Quiz of the Week #2005-03-22)

On Wed, 30 Mar 2005 09:43:14 -0500, Daniel Martin <martin-+m399P62/[email protected]> wrote:
> Ronald J Kimball <[email protected]> writes:
> 
> > That's not a counterexample.  The FSM doesn't meet the stated criteria, as
> > the accepting state has two ways in for the input 1.
> 
> Greg Bacon included too much context when replying - he was objecting
> to my first paragraph, not the second.  The "one way in for each
> input" is necessary only if the reversed machine is going to be a
> deterministic finite automaton (i.e. a FSM).  He was not contending
> that reversing the arrows led to a defective FSM.  His objection was
> that the NFA you got by reversing the arrows led to no string
> accepted, and not to what I had stated.
> 
> And he's right, in that reversing the arrows alone is not enough - you
> need to also reverse the accept and start states in the general case.
> 

Seems like there are a lot of folks on this list who are both
interested in and knowledgable about DFA/NFA and FSM's in general.

Id like to appeal to you all to help work on the next generation of
perls regex engine. The objective is to introduce DFA matching
abilities as far as possible without breaking the current expectations
of the NFA engine.

Ive already implemented a TRIE based optimisation, and im in the
testing phase of a DFA implementation that uses Aho-Corasick matching.
Other possibilities would be to optimize simple patterns like
a+b*c+d?ef*? into a single DFA based regop. I dont envision handling
alternations (due to potentially brutal memory requirements) but
simple patterns seem to be appropriate optimization targets.

I was going to say it would be nice to see a Hard Quiz of a DFA
implementation that can handle the quantifiers +, *, and ? (as well as
their minimal equivelents +?, *? and ??) as I might be able to use it
as a basis for such an optimisation in the engine. :-)

Anyway, the point is if anybody is interested there is interesting
low-ish hanging fruit in bleadperl for adding DFA related regops to
the NFA engine. Of course this requires C skills and some time
learning how the engine currently works, but the product will benefit
us all....

If anybody is interested please do let me know. 

Cheers,
Yves

-- 
perl -Mre=debug -e "/just|another|perl|hacker/"