LL, LR debate

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
table-driven parsers:


(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
        can't handle.
(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
        any more.


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


                                E -> E + T | E - T | T
                                T -> T * N | T / N | N
                                N -> (E) | 1 | 2 | ...
becomes
                                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
difficult.


It should probably be pointed out that the (less common) RIGHT-associative
operators (e.g. exponentiation) are more naturally expressed with top-down
grammars.
--
Michael L. Scott
Computer Science Dept. (716) 275-7745, 5671
University of Rochester FAX 461-2018
Rochester, NY 14627-0226 scott@cs.rochester.edu
--

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