LL(1) vs. LR(1)

I was told that LR(1) parsers are much more powerful than the LL(1)
parsers because they recognize more grammars. Please note, I am just
compare LL(1) to LR(1) and not LL(k), LR(k), LALR, or any other
variant.


I can see that LR(1) parsers are probably more powerful because to
create the parsing table, a stack is used. For LL(1) you just look at
the next input and do a trial and error approach (of course you can
left-factor, and most certainly you have to remove left-recursions
otherwise you'll go into an infinite loop - all this may result in
less backtracking although it's not guaranteed). Aside from the more
complex data structures and algorithms used by the LR(1), I don't
really see any grammars that a LR(1) parser can parse that a LL(1)
cannot. Can anyone give me a grammar that is in LR(1) but not in
LL(1)?


Another curiosity is the efficiency of LL(1) and LR(1) algorithms. Due
to backtracking, LL(1) may end up being exhaustive in that it may
backtrack to the point that it reaches the last production in which it
will try to apply. This exhaustive search means LL(1) is bounded by an
exponential (am I correct?). However, the LR(1) algorithms for
producing the parsing table also seems to be exponential; when you
find the "closure" and "goto" of LR(1) items, you look at each item
and in turn each of these items may require you to do "closure" and
"goto" again. Because of this fan-out, it seems LR(1) algorithm for
creating parsing table (btw: I'm talking about the algorithm presented
in the new dragon book) is also bounded exponentially (am I
correct?). So it seems LR(1) requires the same computational power as
LL(1)?


P.S. - Where can I find a complete FAQ on basic compiler theory? The
only FAQ I found is this: http://www.faqs.org/faqs/compilers/, and it
does not have any discussion on theory.


Thank you,
Will

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