Re: [boost] [regex] any interest in finite automata-based regex engine?

From: Vladimir Pozdyayev (ardatur_at_[hidden])
Date: 2004-11-02 02:11:45

To Eric Niebler and John Maddock on the subject of "something
completely different":

Oh well. Mea culpa. Thanks.

And now for something more completely different.

JM> I forgot to say: without understanding the algorithm you are using, and the
JM> data it needs, it's hard to know whether or not Boost.Regex can support it,
JM> I think you may have been asked this already, but do you have a description
JM> anywhere of the algorithm you are using?

http://groups.yahoo.com/group/boost/files/anfa-regex/

EN> ... xpressive's
EN> compile-time design allows for multiple back-ends (NFA, backtracking
EN> NFA, DFA) without paying for ones that aren't used. However, xpressive
EN> is hard-coded to use a backtracking NFA for now, and there is no clean
EN> interface for plugging in a different back-end...

Maybe it's good time to officially separate regex components from
each other and define the way they should interact, thus allowing
users to connect them at their preference?

I can name three of them: syntax parser, state machine, and character
sets. The first two are interacting through either tree data
structures (passive/declarative way), or callbacks imitating the
parser shift-reduce activity (active/imperative way; the better one,
I think). The other two interact through "bool contains( char_t c )"
(and, possibly, additional functions to deal with more subtle stuff).
I understand that some algorithms could prefer to treat those three
as if they were closely related... well, whether it will become a
problem is a question of design. Opinions on this, as well as on the
whole subject, are welcome.

-- 
Best regards,
Vladimir Pozdyayev.