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 <fwei...@redhat.com> 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
