Re: Bottom-up versus Top-down

Jeff Jenness <jeffj@csm.astate.edu>
10 Dec 1997 00:41:26 -0500

          From comp.compilers

Related articles
[9 earlier articles]
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: Jeff Jenness <jeffj@csm.astate.edu>
Newsgroups: comp.compilers
Date: 10 Dec 1997 00:41:26 -0500
Organization: Arkansas State University
References: 97-11-123 97-11-155 97-11-178 97-12-044
Keywords: parse, performance

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


Post a followup to this message

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