From: Tim X Date: 2007-04-12T20:10:06+09:00 Subject: Re: Slow ruby regexes "Robert Dober" writes: > Subject: Re: Slow ruby regexes > > On 4/11/07, MenTaLguY wrote: >> On Wed, 11 Apr 2007 16:53:26 +0900, "Robert Dober" 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. >> Guys, I think your possibly mixing up backtracking and backreferences. It is backreferences (referencing a earlier match, often to use as part of the definition of a latter match) that NFA is not able to do. both approaches use backtracking. The NFA approach is able to parallelise the choices, reducing the overheads of backtracking. So, given n different possible paths to follow, instead of, in the worst case, trying n-1 paths and having to backtrack after each one, you can try all n paths at once. At least, I htink thats what the article was saying form a very quick read and from what I can remember from my computability course and finite automata (oh so many years ago now!). Tim -- tcross (at) rapttech dot com dot au