Re: [boost] [soc 07] SoC 2007 Projects

From: Hugh Wimberly (hugh.wimberly_at_[hidden])
Date: 2007-04-12 10:06:43

> My advise: implement a simple DFA and use it only for patterns without
> captures (regex_constants::nosubs) or fancy assertions (eg. look-ahead).
>   If you need captures and leftmost-biased semantics, just use the
> backtracking NFA.

My intention all along was to see what functionality I could get the DFA to
achieve while still being very fast; I hadn't even intended to add
look-ahead assertions unless time looked favorable. I'd certainly like to
see if I can make captures fast, and from what I've seen, for common regexes
without assertions, the DFA really is faster, often considerably. Could you
send me the tests you performed? I'd be really interested in it.

> Oh, and make the DFA so that I can use it in xpressive, too! :-)

I hadn't looked into xpressive (I'm fairly new to Boost), so I don't know
what hurdles that will add, but I'd certainly like to make this
functionality as widely available as possible, so thanks for pointing out
xpressive.

Regards,
Hugh Wimberly

On 4/12/07, Joel de Guzman <joel_at_[hidden]> wrote:
>
> Eric Niebler wrote:
> > Jeff Garland wrote:
> >> Hi All -
> >>
> >> I'm happy to announce that Boost will be mentoring 9 Google SoC
> projects this
> >> year.  They are:
> > <snip>
> >
> >> Application to extend Boost regex with recursive matching, named
> >> sub-expressions, and automata-based matching
> >>                                      Hugh Wimberly   John Maddock
> > <snip>
> [...]
>
> > My advise: implement a simple DFA and use it only for patterns without
> > captures (regex_constants::nosubs) or fancy assertions (eg. look-ahead).
> >   If you need captures and leftmost-biased semantics, just use the
> > backtracking NFA.
> >
> > Oh, and make the DFA so that I can use it in xpressive, too! :-)
>
> FWIW, Spirit2 uses lexertl -- a DFA engine by Ben Hanson. Hartmut
> Kaiser did some benchmarks and found it to be almost as fast as RE2C
> Hartmut integrated it with Spirit2 and we are very happy with it.
> There's room for a couple of DFA engines, I guess...
>
> http://re2c.org/
> http://www.benhanson.net/lexertl.html
>
> Regards,
> --
> Joel de Guzman
> http://www.boost-consulting.com
> http://spirit.sf.net
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>