[boost] Re: Boost and regular expressions

From: Dave Abrahams (abrahams_at_[hidden])
Date: 1999-09-05 13:08:38

> Both NFA and DFA approaches have advantages.  As I recall, and it's been
> a while, a DFA uses time linear in the amount of text to search, but
> potentially exponential space to store the DFA,

That's not the way I remember it. I thought the only explosion with DFAs
occurred in trying to reduce them to their most compact form... but you
don't have to do that. Anyway, I'm not expert in it. I hope someone will
correct me.

> I very much welcome John's participation

Me, too!

> -- what is most important is a
> clean syntax -- the semantics can be fixed to be whatever we need them
> to be.

Okay, here's the problem I'm clumsily trying to address:

the exact problem I had with the Perl-style match? I think it was that the
match could get "stuck" in a greedy match of an alternative in an expression
made up of terms "or"ed together... something like that. In other words, it
is possible to write an expression of the form: A|B|C... (where A,B,C... are
sub-expressions) such that it would fail to properly match text that would
have been matched by one of A,B,C... alone.

Perhaps John can correctly identify the issue I'm pointing at and reassure
me that regex++ doesn't suffer from it.

-Dave