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

From: Vladimir Pozdyayev (ardatur_at_[hidden])
Date: 2004-10-26 01:13:50

To Vladimir Prus:

> Interesting. Is the algorithm from some published paper that you could
> link/post? Or do you have a formal description?

The paper describing this algorithm is submitted for publication
(offline) but not out yet. I am considering possibilities of
publishing another version online---can you advise me on the subject
of the best way to do it (other than creating & promoting my own
site :) )?

To Reid Sweatman:

> Very nice.  I've banged up against that one painfully recently (not with
> Boost's regex engine, be it noted <g>), and frankly, that's quite a
> guarantee given the features you mention.

Well, I developed this one without boost.regex in mind, firstly. It's
just that I don't feel like creating a whole new regex library from
scratch, and regex seems to be a right place to fit this in.

To Eric Niebler:

> Interesting. You say it supports substring capturing. Does it also
> support backreferences?

Unfortunately, no. It's proven somewhere out there that regex matching
with backrefs is NP-hard---so, I guess, no linear guarantee ever.
<sob>

-- 
Best regards,
Vladimir Pozdyayev.