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

[Roman Cheplyaka]

Chris,

Thank you for an interesting overview.

However, I'm not worried directly about DoS. I just want to build a
regex library which would be convenient to use for parsing regular
languages (by providing applicative interface and Perl semantics), and
not worse than alternatives performance-wise (including worst-case time
and space complexity).

> (3) Building an NFA from your regular expression can be cheap, but you would
> have be more clever than expanding "a(b{2,99}c){100}d" to have 100 copies of 99
> copies of b.

Are there any known algorithms more clever than that?

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