[Haskell-cafe] Re: Efficient parallel regular expressions

[Achim Schneider]

"Dan Piponi" <dpiponi at gmail.com> 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.
>
Considering that he's talking about a mud, I figure the grammar is a
quite straightforward

command = l[eft] | r[ight] | ... | t[ake] <item> | c[ast] <spell>

That is, I'd be very surprised if you even need more than two or three
characters lookahead, much less backtracking.

Parsec is a thousand times more efficient for such things than regular
expressions, and you can just lazily parse all the input into a list
of data constructors and happily fold it into your state...
The only thing more straightforward than this is reading a xml with
HaXML (if you have a DTD, that is)


-- 
(c) this sig last receiving data processing entity. Inspect headers
for copyright history. All rights reserved. Copying, hiring, renting,
performance and/or quoting of this signature prohibited.