Re: Bottom-up versus Top-down

torbenm@diku.dk (Torben AEgidius Mogensen)
12 Dec 1997 14:44:09 -0500

          From comp.compilers
Related articles
[11 earlier articles]
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: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: comp.compilers
Date: 12 Dec 1997 14:44:09 -0500
Organization: Department of Computer Science, U of Copenhagen
References: 97-11-123 97-11-155 97-11-178 97-12-024 97-12-055 97-12-073
Keywords: parse

"Scott Stanchfield" <thetick@magelang.com> writes:


>For some info on converting grammar from LALR to LL, see


> http://www.scruz.net/~thetick/lalrtoll.html


As I see it, a major advantage of LR over LL is the ability to use
operator precedence rules instead of using a non-ambiguous grammar.
Though precedence-annotated grammars can be rewritten to a
non-ambiguous grammar and left-recursion can be eliminated from this,
the size of the resulting grammar can be very large if you have both
prefix, infix and postfix operators. In addition to increasing the
size of the grammar, the disambiguating rewrites also slow down the
parsing by requiring more derivation steps.


That said, LR tables are often larger than LL tables, and the same is
true for explicitly written recursive descent/ascent. This doesn't
seem to be a problem until you get extremely large grammars, though.


Torben Mogensen (torbenm@diku.dk)
--

Post a followup to this message

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