Re: Bottom-up versus Top-down

G'day all.


Mark K. Gardner <mkgardne@cs.uiuc.edu> wrote:


>)I have often heard the claim that bottom-up parsing is more efficient
>)than top-down parsing.


jmccarty@sun1307.spd.dsccc.com (Mike McCarty) writes:


>I have also heard that claim. It is not true.


Blanket statements of the form "technology X is more efficient than
technology Y" tend to be false at least some of the time, and tend to
be meaningless without further definitions or context.


In this case, it depends on:


- How naturally the grammar maps onto a grammar that the
parser construction method will accept.
- How the constructed parser is mapped onto the target
language.
- The target language.
- The compiler for the target language.
- The target architecture.


There's probably more.


Of these, I believe that the first two are the most important. For
example, Edinburgh Prolog is most naturally modelled by an infinite
lookahead precedence parser. Turning it into a recursive descent
parser (even if you assume no user-definable operators) would be a
very difficult exercise.


In the case of the HP3000 parser that you cited:


> The recursive descent parser more naturally fit the architecture of
> the machine, which was optimized for the types of operations required.


One might expect the same not to be true of the interpreted Java VM,
where the cost of a method call can be quite large. (Disclaimer: I
have not tested this, so I reserve the right to be wrong.)


>)One of the justifications often given is that
>)bottom-up parsers are table-driven while top-down parsers are usually
>)implemented as recursive-descent parsers. However (and as pointed out
>)in the Dragon book), top-down parsers can also be table-driven.


Bottom-up parsers can also be implemented as recursive-ascent parsers,
which just goes to show how important it is to be careful when mapping
a parser (be it LL, LR, precedence, CYK or whatever) onto your
intended target language.


Cheers,
Andrew Bromage
--

Return to the comp.compilers page.
Search the comp.compilers archives again.