This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [GSoC] Does this proposal look good?
- From: Tim Shen <timshen91 at gmail dot com>
- To: Florian Weimer <fweimer at redhat dot com>
- Cc: gcc at gcc dot gnu dot org, libstdc++ at gcc dot gnu dot org
- Date: Wed, 24 Apr 2013 19:15:01 +0800
- Subject: Re: [GSoC] Does this proposal look good?
- References: <CAGBC11n27BskozoDT-RhU=iNEzmJJVarVejux+Za8Y8avM2vYQ at mail dot gmail dot com> <51779837 dot 4020000 at redhat dot com> <CAPrifDnd2ecO5Jfo1jfi++dEC9qRQGT3X_i9uk8Q7ynHATyGjg at mail dot gmail dot com> <5177BA69 dot 8080208 at redhat dot com>
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 <fweimer@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