This is the mail archive of the
mailing list for the libstdc++ project.
Re: [GSoC] Does this proposal look good?
- From: Florian Weimer <fweimer at redhat dot com>
- To: Tim Shen <timshen91 at gmail dot com>
- Cc: gcc at gcc dot gnu dot org, libstdc++ at gcc dot gnu dot org
- Date: Wed, 24 Apr 2013 12:56:41 +0200
- 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>
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