George Russell wrote:
> Lennart Augustsson <[EMAIL PROTECTED]> wrote:
> > > Parser combinators are fine if the grammar is very simple or you don't
> > > care about CPU times. But using them in a serious compiler for Haskell
> > > would be like building a computer out of stone knives and bearskins.
> > So this is your opinion, what kind of evidence have you got for this claim?
> Parser combinators don't actually seem to analyse the grammar at compile time
> at all, and instead just try all possibilities. This looks like stone-age
> technology to me. The first version of MLj was written with parser
> combinators. As a result the parsing was much much slower, even after
> various exponential blow-ups had been painfully tracked down and removed.
> Error correction was hopeless. And worst of all, there were a number
> of lurking ambiguities in the grammar which weren't discovered until it was
> exposed to the rigour of LALR parsing.
Continuing the unscientific experiments I resurrected an old Haskell parser I
wrote in Haskell with parsing combinators.
Here are the results (on a 450MHz PII):
wc -c 152702
wc -l 3081
real 2.82 s
user 2.459s
sys 0.359s
This parser has error recovery and good error messages (better than you get
from yacc&co). It uses backtracking in a few places where the Haskell grammar
is rather icky. Haskell is not LR(k) for any k%, so to use LR based
parser generators you have to jump through hoops to make a parser.
So parsing combinators are a bit slower than generated parsers, but the
parsing is fast enough for me. The time disappears in the rest of the
processing.
What I dislike with parser generators (at least the ones I've seen) is the
total lack of abstraction possibilites. An example, Haskell contains quite
a few comma separated list. Instead of just repeating the pattern for this
you abstract it into a higher order parser.
Coming from a functional language I naturally expect abstraction, and I won't
settle for less.
To correct another misconception, there are implementations of parsing
combinators that do analyze the grammar as a "first pass" and then uses
the gathered information.
I think parsing combinators have gotten a bad name because people have
been using the implementations that you can find in papers and articles.
These implementations are for mostly explanatory purposes; you can do much
much better.
-- Lennart
% I have at least not seen any formulation of the grammar that is.
I doubt you can do it.
