From: Robert Klemme <shortcutter@...>
Date: 2007-04-16T19:55:05+09:00
Subject: Re: Slow ruby regexes

On 14.04.2007 15:23, MenTaLguY wrote:
> To be fair, I oversimplified a bit because I couldn't think of a better
> example until just now.  Though you can prune the DFA with priorities in
> the NFA, an expression like /^(?:(abc)|(a)).*$/ still requires more
> sophisticated handling, explicitly tracking alternative matches.
> 
> Here's an implementation of a Thompson NFA which does Perl-style
> capture:
> 
>  http://swtch.com/~rsc/regexp/nfa-perl.y.txt
> 
> The same approach works if you construct the DFA in advance or via
> memoization of the Thompson NFA evaluation (which is probably the better
> of the two for reasons already discussed).

Hmm...  I was more after how you would notate the RX for a DFA based 
engine to do the prioritization.  I do not know a DFA based engine that 
would actually allow to write a RX pattern to do that.

Of course, when building engines manually you can do a lot - and 
probably a lot more than what actual RX engines allow.  But since I'm 
interested in *using* them vs. writing RX engines your solution was not 
exactly what I expected. :-)

Kind regards

	robert