Re: Bottom-up versus Top-down

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


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.


I have also heard that claim. It is not true. I have myself hand coded
a recursive descent version, a shift-reduce version, and a precedence
driven version of an expression parser for the HP3000 (several years
ago). The recursive-descent version was the *fastest* of the
three. The HP3000 was a purely stack-based machine, and it was easy to
show that the actual machine implementation of the shift-reduce and
the recursive descent actually did equivalent amounts of work. The
recursive descent parser more naturally fit the architecture of the
machine, which was optimized for the types of operations required. The
hardware manipulation of the stack was more efficient than
instructions in the code, you see.


)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".)


Definitely top-down parsers can be table driven, and in more than one
way.


)Note that I am fully aware LR and LALR can parse a larger class of
)grammars than LL.


This is "academically" true, but "realistically" false. No one
actually *uses* languages for which there is an LALR grammar, but not
an LL. Note that we *do* use languages for which there is not *even*
an LALR grammar (FORTRAN, for example).


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


No one uses such languages, to my knowledge. And experience has shown
me that the two parsing techniques are, indeed, equivalent in actual
speed.


)[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.]


I don't know where this bit of misinformation came from, but it is EASY
to get an LL grammar for C. Just take the one in the ANSI standard, and
remove left recursion, replacing it with right recursion.


PASCAL was designed with the intent of making it compilable in one
pass, to demonstrate the successive refinement paradigm of program
development (i.e. to encourage that technique), and to be "safe" for
learning how to do systems type programming without actually being
able to crash the system (which is why compilers for it generated
p-code and arithmetic cannot be done on pointers). The language is
equally easy to represent as an LL or an LR grammar, as is C.


Mike
--

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