This is the mail archive of the 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?

Hmm...So finally we need partially compiled NFA(Because DFA is a
special NFA, so can be embeded in an NFA)? That's worth trying.
Anyway, I don't know much about it. Maybe I should read others code or
just wirte a prototype first, if my proposal's accepted by GCC :)

On Wed, Apr 24, 2013 at 6:56 PM, Florian Weimer <> wrote:
> 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

Tim Shen

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