Re: Bottom-up versus Top-down

On 29 Nov 1997 00:03:58 -0500, George C. Lindauer <gclind01@spd.louisville.edu> wrote:
>Top down parsing is much easier to implement, but,
>bottom-up parsing is more efficient. YACC and other code generators
>tend to generate the type of state tables required to do bottom-up
>parsing efficiently...


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. However (and as pointed out
in the Dragon book), top-down parsers can also be table-driven. Has
anyone seen any publications which support the claim that bottom-up
parsing is more efficient than top-down parsing and under what
circumstances? I have not. (I suspect that the claim also hinges upon
how you define "efficient".)


Note that I am fully aware LR and LALR can parse a larger class of
grammars than LL. What I am asking for is a head-to-head comparison
between the two techniques on the same (hopefully non-trival) grammar
conducted in a reasonably scientific manner. My hunch is that both
techniques are equally efficient if implemented in a reasonable and
comparable manner. Thus the only reason to prefer LR/LALR over LL is
because your grammar requires it.


[I did not witness the events first-hand, but it appears that LALR
grew strength from languages, like C, that were difficult if not
impossible to cast as LL grammars, while LL took root in the Pascal
languages for which LL was nearly ideal. (Or perhaps more correctly,
Wirth purposefully designed the language to make it amenable to LL
parsing.) I am sure someone with first-hand knowledge will correct me
if I am mistakened.]


Mark
--
Mark K. Gardner (mkgardne@cs.uiuc.edu)
University of Illinois at Urbana-Champaign
Real-Time Systems Laboratory
--

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