Re: [Haskell-cafe] Re: Efficient parallel regular expressions

On Tue, 2008-11-04 at 10:02 -0800, Dan Piponi wrote:

On Tue, Nov 4, 2008 at 9:26 AM, Achim Schneider wrote:

...

Martijn van Steenbergen wrote: For anything remotely connected to parsing, always use parsec.

I'd not be surprised if the beast is touring complete in itself...

Actually, this can count against you. It's very easy to use Parsec to build an innocent looking grammar that's too slow to use because it'll do all kinds of backtracking to find a way to make your input fit the grammar. I recommend Parsec for lots of tasks, but take care to design the grammar so it doesn't take exponential time to do anything.

Backtracking points are explicit in Parsec which is one of the whole points of it. This makes it pretty difficult to "innocently" end up with exponential behavior. Backtracking requires a use of the 'try' combinator. It's pretty easy to recognize potentially dangerous uses of 'try'. If you use 'try' willy-nilly or you just throw 'try' in when you are having difficulties then I can quite easily imagine one quickly ending up with exponential behavior. Otherwise, it should not be "easy" to do and if you like you can not use 'try' (or 'try' using combinators) at all and you surely won't get exponential behavior (as far as Parsec is concerned).