From: Robert Klemme <shortcutter@...>
Date: 2007-04-12T16:10:07+09:00
Subject: Re: Slow ruby regexes

On 10.04.2007 21:14, MenTaLguY wrote:
> On Wed, 11 Apr 2007 03:56:28 +0900, "Robert Dober" <robert.dober@gmail.com> wrote:
> 
>> The bad news is that the power of regexs will just not let you escape
>> with bad design all the time, so knowing a lot about regexes is a
>> necessary thing to use them well.
> 
> No, the bad news is that the bad design of most "regex" implementations will not let you escape with using "regexes" as if they were true regular expressions; knowing a lot about the implementation of the regex engine is a necessary thing to use them well.
>  
>> But you are right of course that Ruby's current Regex implementation
>> is not state of the art, useful, very useful nevertheless.
> 
> NFAs were state-of-the-art in the 1960s.  Backreferences are nice, but in other respects we've actually regressed since then.
> 
> I'm not suggesting we abandon backreferences and so forth (which are useful sometimes), but rather that NFAs should be used for evaluating the majority of "regexes" which don't use non-regular features.

I think you got NFA and DFA mixed up: DFA's are the ones that do not 
suffer backtracking issues.

	robert