[Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)

[Roman Cheplyaka]

* Chris Kuklewicz <haskell at list.mightyreason.com> [2011-09-13 08:21:55+0100]
> I wrote regex-tdfa, the efficient (though not yet lightning fast) Posix-like engine.
> 
> You are not the first to want an efficient Perl-like engine.  The answer you
> seek flows from Russ Cox (though in C++):
> 
> > http://google-opensource.blogspot.com/2010/03/re2-principled-approach-to-regular.html
> 
> > http://code.google.com/p/re2/
> 
> Quoting relevant bit:
> 
> > It also finds the leftmost-first match, the same match that Perl would, and
> > can return submatch information. The one significant exception is that RE2
> > drops support for backreferences¹ and generalized zero-width assertions,
> > because they cannot be implemented efficiently.

Hi Chris, thanks for the response.

There's one thing about Cox's work that I don't understand. On the
page [1] he mentions that the algorithm falls back to direct NFA
simulation (search for "If all else fails" on that page).
This defeats his goal of defending against DoS attacks (the second
paragraph of that page).

And I wouldn't be comfortable with an algorithm that is worst-case
exponential either.

Then there's another issue: I specifically want a combinator library,
and not every automaton-based algorithm can serve this purpose in a
statically typed language (unless there's some clever trick I don't
know).

[1]: http://swtch.com/~rsc/regexp/regexp3.html

-- 
Roman I. Cheplyaka :: http://ro-che.info/