|LL vs LR, no jihad initiation, but... email@example.com (1992-05-11)|
|LL, LR debate firstname.lastname@example.org (1992-05-13)|
|Re: LL, LR debate email@example.com (1992-05-18)|
|From:||firstname.lastname@example.org (Michael Scott)|
|Organization:||Computer Science Department University of Rochester|
|Date:||Wed, 13 May 1992 16:19:56 GMT|
In regard to the recent discussion of LL parsing and its relative merits
wrt LR parsing, allow me to recommend the comparison in Fischer and
LeBlanc's "Crafting a Compiler." It's pretty even-handed. Recent notes
have done a pretty good job of capturing the tradeoffs. My own summary,
based on experience writing compilers with both bottom-up and top-down
(1) top-down parsing is "more intuitive" in the sense that it's a
lot easier to teach to neophytes.
(2) "grammar hacking" is easier with a bottom-up parser; certain common
constructs (e.g. expressions) are more "naturally" expressed,
and changes are less likely to produce a grammar that the parser
(3) top-down parsers make it easier to handle semantic routines.
As several people have noted, you have to break your productions
into pieces or introduce new dummy symbols that generate epsilon
in order to get a semantic routine into the middle of a production
in yacc. Fancier bottom-up parser generators automate this process
somewhat, but they *cannot* let you put semantic routines in *arbitrary*
places; you still have to hack your grammar if you want to do
something in the left corner of a production.
(4) If you can't get hold of a parser generator (less of a problem
than it once was, but still possible), you'll want to parse top-down
with recursive descent.
(5) In table-driven parsers, management of space for attributes has
a very different "feel" in the top-down and bottom-up worlds,
and different programmers seem to have different preferences.
The "natural" attribute stack for bottom-up parsers is intuitive
and easy to automate, but inherited attributes are a hack. Automatic
management of space for top-down attributes is also possible,
but forces you to use a *lot* of copy rules. Ad-hoc, explicit
pushing and popping of a semantic stack is probably preferable in
top-down parsers; many programmers find it elegant, once they
get the hang of it.
(6) Bottom-up parsers can handle a larger class of languages, but this
doesn't seem to be a serious problem in practice; most "real"
languages have a grammar that's LL(1), or close enough to handle with
simple disambiguating rules.
(7) Top-down parsers require less table space, but this is seldom a problem
One clarification from an earlier post: you do NOT have to change the
associativity of your operators (i.e. change the semantics of your
language) to parse expressions top-down. You have to build a parse tree
that does not naturally reflect that associativity. During semantic
analysis, you use inherited attributes to push information across
E -> E + T | E - T | T
T -> T * N | T / N | N
N -> (E) | 1 | 2 | ...
E -> T T_tail
T_tail -> - T T_tail | + T T_tail | epsilon
T -> N N_tail
N_tail -> * N N_tail | / N N_tail | epsilon
N -> (E) | 1 | 2 | ...
This is LL parsing at its absolute worst; if you can stomach expressions,
you won't object to anything else.
T_tail and N_tail have inherited attributes that summarize the information
to the left in the expression. It's a little messy, but not really
It should probably be pointed out that the (less common) RIGHT-associative
operators (e.g. exponentiation) are more naturally expressed with top-down
Michael L. Scott
Computer Science Dept. (716) 275-7745, 5671
University of Rochester FAX 461-2018
Rochester, NY 14627-0226 email@example.com
Return to the
Search the comp.compilers archives again.