[boost] [soc][regex] Linear-time perl regex matching (was: [soc 07] SoC 2007 Projects)

From: Eric Niebler (eric_at_[hidden])
Date: 2007-06-04 17:15:09

Hugh Wimberly wrote:
>> 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, my poor addled brain. Too long ago, I promised to make my Boost port 
of Russ Cox's O(N) Perl regex engine -- a modified Thompson NFA -- 
available. It does captures and Perl's leftmost biased rule (as opposed 
to the POSIX leftmost longest rule). As I mentioned, I found the 
performance to be pretty bad in the common case, but without exponential 
blow-up in the pathological cases. YMMV.

You can find the code in thompson-nfa-perl-regex.cpp at 
http://www.boost-consulting.com/vault/index.php?directory=Strings%20-%20Text%20Processing&

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com