[GSoC] Does this proposal look good?
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++