I think only backtracking engines (not DFAs) have the exponential run
time problem. Regular expression grammar is itself context free (so it's
parsable efficiently), the NFA and NFA->DFA algorithms are polynomial,
and the generated DFA makes one transition per input character.
Andrei
I don't know how practical it is, but I had a thought to allow some of
these nasty regexes to run better: use threads. In theory, and I have
not done any work to test/prove this so it's very theoretical, you can
have multiple threads running in parallel each testing a potential path.
Granted, there's always the issue of spawning/managing threads and
potentially overloading the system by spawning too many, however it may
be a viable alternative if you really HAVE to execute a particularly
nasty regex.
Anyway, it's just a thought. I'd hate to lose the benefits of a NFA if
we're afraid of the potential performance hit if a user writes a bad regex.
Casey
