Re: LL vs LR, strengths and weaknesses

[ Hopefully, this can be my last world on this subject. I'm sure we're all
    getting bored with this by now. - Jack]


Just a quick review: We're comparing the relative merits of parsing
expressions; in particular, bottom-up using


LR grammar: E -> E + T | E - T | T
                                T -> T * N | T / N | N
                                N -> (E) | 1 | 2 | ...


or top-down using


LL grammar: E -> T E'
                                E'-> + T E' | - T E' | (empty)
T -> N T'
T'-> * N T' | / N T' | (empty)
N -> (E) | 1 | 2 | ...


I think we've established that these are the two "canonical" grammars for
expressions. In 92-05-085, Michael Scott
(scott@cs.rochester.edu) does a very nice job of comparing the two
approaches. In particular, he correctly points out that:


> This is LL parsing at its absolute worst; if you can stomach expressions,
> you won't object to anything else.


In particular, he points out that LR grammar parse tree for an
expression can be generated using the LL grammar in a top-down fashion by
using inherited attributes: if E -> T E', the parse tree for T is handed
to the "parser" for E', which consumes the operator and the other operand,
cons's them up, and passes the result along to the next E'.


An ingenious solution, sort of like "parsing with continuations."
Let's agree to call this "the canonical LL hack." :-)


Michael Scott continues:


> It should probably be pointed out that the (less common) RIGHT-associative
> operators (e.g. exponentiation) are more naturally expressed with top-down
> grammars.


To be fair, it should be mentioned that right-recursion _can_ be
used in an LR parser; it only causes the maximum stack depth to become
unbounded, something that's going to happen anyways (if we allow
parentheses). LL(k) parsing techniques can't handle left-recursion
_at_all_.


Finally, I think what we've established is that there is no
"right" way to think about parsing. Some people will find that annoyance
of the "canonical hack" is more than compensated by the clarity of
top-down parsing, and will opt to use an LL parser-generator. Others
(like myself) have been so warped by using yacc that our brains have
turned inside out and LR parsing seems perfectly clear while LL is murky.
(Either that, or we've been looking at the results of too many CPS
transformations! :-)


BTW, what _I_'d really like to see is a version of yacc that
allows me to specify a special "reduce function" for productions, such
that the production is reduced iff the "reduce function" evaluates to
"true".
--

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