Stackless & String-processing

[Fernando Pereira]

In article <7mlvju$6v3$1 at brick.cswv.com>, Neel Krishnaswami
<neelk at brick.cswv.com> wrote:

> In article <7mkrrt$a81$1 at cronkite.cc.uga.edu>,
> Graham Matthews <graham at sloth.math.uga.edu> wrote:
> >
> >[Parser Combinators] 
> >
> >They are something like what Neel is talking about (as the name
> >"parser combinators" suggests you write small "string parsers" as
> >functions, and then have "parser combinators" that stitch these
> >together). Note that in this parser combinator approach there is no
> >distinction between the code for "the pattern" and the code for "the
> >processing" -- they are all written in the same language
> >(Clean/Haskell in my case). 
<snip>
> This really seems like a clean and straightforward way of doing
> things.  My experience with recursive descent parsers has been pretty
> bad, but now I suspect that this is because I wasn't organizing my
> work in a systematic enough fashion. 
Clean and straightforward it may be, but not efficient, and subject to
termination problems on left-recursive grammars. Techniques for
compiling regular expressions and deterministic context-free grammars
into efficient pattern-matching/parsing automata do not extend readily
to programs in a general purpose declarative (functional or logic)
programming language. Certain clever things can be done (in particular
see "The Functional Treatment of Parsing," by Rene Leermakers,
Kluwer Academic Publishers, 1993), but, as far as I know, nothing beats
the automata-theoretic optimization techniques for pattern matching and
parsing, of which the typical modern compiler for regular expressions
is just the best-known instance.

-- F