Re: Bottom-up versus Top-down

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




--

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