Re: Bottom-up versus Top-down

The recursive ascent procedure does in fact parse just as fast a
recursive descent. I had a graduate student a few years back and he
and I reworked yacc to produce recursive ascent parsers in C. The
results were very good. The recursive ascent would beat the recursive
descent for some of our test grammars, i.e., Pascal, C subset, etc.
The down-side...the number of recursive routines corresponded to the
number of states and these parsers were on the order of 20 times
larger than the corresponding recursive descent parsers. We also had
to write low level code to help with stack manipulation...very tricky
and machine specific. Quite a cost! We published a paper on it in
the Southeast Conference of the ACM if you are interested in digging
it up.


Jeff Jenness


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

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