[Haskell-cafe] Re: Efficient parallel regular expressions

wren ng thornton wren at freegeek.org
Thu Nov 6 04:00:22 EST 2008

ChrisK wrote:
> If you need to be left-biased then you need a perl-style engine, and you 
> can use the regex-pcre or pcre-light haskell package and the PCRE 
> library.  These are obtainable from Hackage.  I doubt PCRE uses a simple 
> DFA...

I don't know if regex-pcre or pcre-light supports the (?{...})-ism of 
Perl 5.6 and above, but if it does then it's fairly easy to implement 
the trie automaton I mentioned in my previous post: just add a (?{ 
$value = ... }) action to the end of each component regex and read out 
the value of $value after you match. You'll still want to run the 
automata through a minimizer/optimizer after gluing all the components 
together, otherwise you still get O(n) behavior since you don't share 
the work for common prefixes.

Live well,

More information about the Haskell-Cafe mailing list