Improving std.regex(p)

[Ellery Newcomer]

On 06/18/2010 05:08 PM, sybrandy wrote:
>> 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

The NFA->DFA algorithms are what I was referring to. My copy of the 
dragon book suggests that DFAs usually have O(n^3) initialization time 
but O(n^2 * 2^n) worst case relative to the number of states. I'd love 
to be shown wrong, though.

>
> 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.

Isn't what you're describing an NFA?

>
> 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

You don't get a performance hit with DFAs on knarly regexen (actually, 
they would be faster than NFAs), just regexen that take forever to 
compile. I wonder if it would be possible to mechanically detect problem 
cases for DFA compilation and on detection switch over to an NFA engine.