From: Robert Dober Date: 2007-04-12T03:27:04+09:00 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. > No it must be me who is confused, I thought that backtracking cannot be avoided in regexs like e.g. %r{[a]*.*a} when trying for a greedy match, let me see the NFA should be something like X start second a start term . second second how could backtracking avoid when no a is found in the state? The DFA of course could never backtrack but is there a DFA for this regex? Hope to learn a little bit more about what I seem to have forgotten ;) Cheers Robert %r > -mental > > > > -- You see things; and you say Why? But I dream things that never were; and I say Why not? -- George Bernard Shaw