From: MenTaLguY <mental@...>
Date: 2007-04-13T04:20:19+09:00
Subject: Re: Slow ruby regexes

On Fri, 13 Apr 2007 02:55:20 +0900, Jeremy Henty <onepoint@starurchin.org> wrote:
> I think this (and much of the rest of the discussion) rather misses
> the point.  The DFA algorithm performs poorly in some circumstances
> because it may backtrack to the *same* state *many* times.

DFA evaluation does not backtrack.  Assuming epsilon transitions are collapsed when constructing the DFA, for a given input string there will be exactly n (or less, in the case of failure) transitions taken, where n is the number of characters in the input string.

Perhaps you meant that the same NFA state is potentially represented in exponentially many different DFA states?  That would indeed be a problem, except...

> This is because there are eg. 3 ways of matching (a?)(a?)(a?) against "aa"
> (depending on which of the three a's you consider to be optional)

In the case of regular expressions, this ambiguity is resolved by the usual "greedy" versus "non-greedy" distinctions, which can be expressed by assigning weights to transitions in the NFA (thereby pruning the number of states in the resulting DFA).  This is pretty much the same way you have to deal with ambiguities when constructing Ragel grammars.

-mental