Re: [boost] Spirit C++ parser framework

From: joel de guzman (isis-tech_at_[hidden])
Date: 2001-06-07 21:16:31

----- Original Message -----
From: "Julian Smith" <jules_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, June 08, 2001 7:35 AM
Subject: Re: [boost] Spirit C++ parser framework

> David Abrahams <abrahams_at_[hidden]> wrote:
>
> > I have received the OK from a compiler vendor using a recursive descent
> > backtracking parser for C++ to reveal their identity. And the winner
is...
> >
> > Metrowerks
>
> Looks like g++ might be moving to a recursive descent parser too - there's
> an article (dated Oct 2000) about this at
> http://gcc.gnu.org/ml/gcc/2000-10/msg00573.html .
>
> - Julian
> http://www.op59.net/
>
>

<quote>
(Many of you know that this is work that is very near and dear to me;
I've been trying to get this work done for a couple of years.  I'm
very glad that we're going to get a chance to do this; it will
tremendously improve g++.)
</quote>

Shouldn't we do some rethinking? Why do comp-sci classes
teach that bottom up parsing is `better'? Agreed, the *worst
case* performance is exponential, yet what we should be
concerned with is the *average case* and I see now that it can
be much faster than bottom up.

Why? another quote:

<quote>
PCCTS (the Purdue Compiler-Construction Tool Set) builds LL(k) parsers
which average about 2-3x as fast as YACC's parsers. The primary
difference between them is that LL stack management can be implemented
directly with machine instructions on most machines, whereas LR stack
handling requires an interpreter... hence the 2-3x difference (for
example, it was about 2x for Pascal).
</quote>

Also, as I asserted, ambiguities in a typical grammar never span the
whole input (which of course leads to the exponential worst case scenario).
Typically ambiguities span a line or two, a block at the most (C/C++
declarators for example).

<Of course, many of you are much more well informed than
me on this issue and I humbly submit if I am proven wrong>

-Joel de Guzman