Re: Bottom-up versus Top-down

sperber@informatik.uni-tuebingen.de (Michael Sperber, Mr. Preprocessor)
7 Dec 1997 22:00:46 -0500

          From comp.compilers

Related articles
[6 earlier articles]
Re: Bottom-up versus Top-down rod.bates@wichita.boeing.com (Rodney M. Bates) (1997-12-02)
Re: Bottom-up versus Top-down henry@zoo.toronto.edu (Henry Spencer) (1997-12-02)
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: sperber@informatik.uni-tuebingen.de (Michael Sperber, Mr. Preprocessor)
Newsgroups: comp.compilers
Date: 7 Dec 1997 22:00:46 -0500
Organization: Wilhelm-Schickard-Institut, Kakerlakenzuchtverein
References: 97-11-123 97-11-155 97-11-178
Keywords: parse

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


> I have often heard the claim that bottom-up parsing is more efficient
> than top-down parsing. 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.


Quite the reverse is true. Bottom-up parsing can be implemented by
mutually recursive procedures. That technique is called "recursive
ascent" and it is considerably faster than table interpretation.


@Article{Pennello1986,
    author = "Pennello, Thomas J.",
    title = "Very Fast {LR} Parsing",
    journal = "{SIGPLAN} Notices"},
    year = 1986,
    volume = 21,
    number = 7,
    pages = "145--151"
}


The above paper shows how to do it in assembler. A high-level
language formulation is in:


@INPROCEEDINGS{SperberThiemann1995,
CROSSREF = {PEPM1995},
AUTHOR = {Michael Sperber and Peter Thiemann},
TITLE = {The Essence of {LR} Parsing},
PAGES = {146-155},
YEAR = 1995
}


-- =


Cheers =8-} Mike
Friede, Voelkerverst=E4ndigung und =FCberhaupt blabla




--


Post a followup to this message

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