replacing guile with haskell?

ajb at ajb at
Wed Oct 22 22:02:32 EDT 2003

G'day all.

Quoting Peter Simons <simons at>:

> Just curious: Why would you want something like that? I thought that
> the good thing(tm) about regular expressions is that they can be
> parsed by a finite state machine rather than a recursive descent
> parser, [...]

Regular expressions can be parsed by a finite state machine.  POSIX
regexes can't.  Or, at least, not quite, particularly when you have
substring extraction and substitution to take into account.  At the
very least, you need some kind of backtracking NFA.

The story is even worse for Perl-compatible regexes.  Nobody is
entirely sure what classes of computation can be done with this
language but, for example, it's possible to construct a Perl regex
which only matches strings of prime length.

> so for all I know, the C regular expression library that comes
> with your system is most likely much faster than any Parsec code would
> every be.

Well, you never know until you try.  There _is_ overhead in converting
strings from Haskell to C and back again.  Yes, Parsec is probably the
wrong fit, but I think there might be merit in at least trying a full
Haskell implementation.

Andrew Bromage

More information about the Haskell-Cafe mailing list