This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [GSoC] Does this proposal look good?


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]