[GSoC] Does this proposal look good?

Florian Weimer fweimer@redhat.com
Wed Apr 24 10:56:00 GMT 2013


On 04/24/2013 12:45 PM, Tim Shen wrote:
> I'm very interested in implementing a NFA->DFA module(does that mean a
> Thompson automaton?) so that the exponential searching algorithm can
> be reduced to a linear state transition(though the states may be
> potentially exponential) loop. I can't understand how some language
> dare use a search algo as a final solution :)

DFA construction requires exponential space even for a fairly restricted 
subset of regular expressions.  The cache misses from large DFAs (which 
can arise in practice, not just with maliciously crafted regular 
expressions) often negate the wins from a simplified execution model.

-- 
Florian Weimer / Red Hat Product Security Team



More information about the Libstdc++ mailing list