Re: [boost] Spirit C++ parser framework

From: David Abrahams (abrahams_at_[hidden])
Date: 2001-06-07 21:53:18

----- Original Message -----
From: "joel de guzman" <isis-tech_at_[hidden]>

> 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>

Since compilation times are typically bounded by lexical analysis, usually
other factors such as expressive power tend to win out in comparisons of
parsing technology. LR(1) and LALR(1) parsers tend to be more capable than
LL(1) as far as I know, and people have been reluctant to compensate with
backtracking.

> 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>

I think computer scientists are trained to concentrate more on provable
worst-case performance than on practical results with real grammars.

-Dave