Re: Bottom-up versus Top-down

bromage@cs.mu.oz.au (Andrew Bromage)
7 Dec 1997 22:10:34 -0500

          From comp.compilers

Related articles
[8 earlier articles]
Re: Bottom-up versus Top-down thetick@magelang.com (Scott Stanchfield) (1997-12-02)
Re: Bottom-up versus Top-down dwight@pentasoft.com (1997-12-02)
Re: Bottom-up versus Top-down neitzel@gaertner.de (1997-12-05)
Re: Bottom-up versus Top-down jmccarty@sun1307.spd.dsccc.com (1997-12-05)
Re: Bottom-up versus Top-down sperber@informatik.uni-tuebingen.de (1997-12-07)
Re: Bottom-up versus Top-down henry@zoo.toronto.edu (Henry Spencer) (1997-12-07)
Re: Bottom-up versus Top-down bromage@cs.mu.oz.au (1997-12-07)
Re: Bottom-up versus Top-down jeffj@csm.astate.edu (Jeff Jenness) (1997-12-10)
Re: Bottom-up versus Top-down thetick@magelang.com (Scott Stanchfield) (1997-12-10)
Re: Bottom-up versus Top-down torbenm@diku.dk (1997-12-12)
| List of all articles for this month |

From: bromage@cs.mu.oz.au (Andrew Bromage)
Newsgroups: comp.compilers
Date: 7 Dec 1997 22:10:34 -0500
Organization: Comp Sci, University of Melbourne
References: 97-11-123 97-11-155 97-11-178 97-12-024
Keywords: parse



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


Post a followup to this message

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