Parsing - Introduction to Compiler Construction in a Java World - page 116

3.4.4 LL or LR?
Figure 3.10 illustrates the relationships among the various categories of grammars we have
been discussing.
FIGURE 3.10 Categories of context-free grammars and their relationship.
Theoretically, LR(1) grammars are the largest category of grammars that can be parsed
deterministically while looking ahead just one token. Of course, LR(k) grammars for k > 1
are even more powerful, but one must look ahead k tokens, more importantly, the parsing
tables must (in principle) keep track of all possible token strings of length k. So, in principle,
the tables can grow exponentially with k.
LALR(1) grammars make for parsers that are almost as powerful as LR(1) grammars
but result in much more space-ecient parsing tables. This goes some way in explaining
the popularity of parser generators such as YACC and Bison.
LL(1) grammars are the least powerful category of grammars that we have looked at.
Every LL(1) grammar is an LR(1) grammar and every LL(k) grammar is an LR(k) grammar.
Also, every LR(k) grammar is an unambiguous grammar. Indeed, the LR(k) category
is the largest category of grammars for which we have a means for testing membership.
There is no general algorithm for telling us whether an arbitrary context-free grammar is
unambiguous. But we can test for LR(1) or LR(k) for some k; and if it is LR(1) or LR(k),
then it is unambiguous.
In principle, recursive descent parsers work only when based on LL(1) grammars. But as
we have seen, one may program the recursive descent parser to look ahead a few symbols,
in those places in the grammar where the LL(1) condition does not hold.
LL(1), LR(1), LALR(1), and recursive descent parsers have all been used to parse one
programming language or another. LL(1) and recursive descent parsers have been applied to