From: MenTaLguY <mental@...>
Date: 2007-04-12T00:34:52+09:00
Subject: Re: Slow ruby regexes

On Wed, 11 Apr 2007 16:53:26 +0900, "Robert Dober" <robert.dober@gmail.com> wrote:
> What I actually meant is that given the need for backtracking
> abilities it will just not be possible to "guess" what the user meant
> when he/she uses too general an expression and I am talking about NFA
> here.

I'm a little confused -- the regexp features which require backtracking correspond to well-defined elements of the syntax.  There isn't any need to guess whether the user requires backtracking or not, one can simply see whether such expressions are present in a particular regexp.

For "pure" regular expressions (which can be matched by NFAs), backtracking and NFA-based evaluation yield equivalent results, except that the NFA approach is O(n) in the number of characters, rather than backtracking's worst-case exponential complexity.

-mental