[Haskell-cafe] Re: Efficient parallel regular expressions

[Derek Elkins]

On Tue, 2008-11-04 at 10:02 -0800, Dan Piponi wrote:
> On Tue, Nov 4, 2008 at 9:26 AM, Achim Schneider <barsoap at web.de> wrote:
> > Martijn van Steenbergen <martijn at van.steenbergen.nl> 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).