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

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/