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

For the non-terminal F, we have two rules. First, given rule 7: F ::= ( E ) , and that
rst( ( E ) ) = f ( g,

table[F, ( ] = 7

Second, given rule 8: F ::= id , and since (obviously) rst( id ) = f id g,

table[F, id ] = 8

LL(1) and LL(k) Grammars

We say a grammar is LL(1) if the parsing table produced by Algorithm 3.5 produces no
conflicts, that is, no entries having more than one rule. If there were more than one rule,
then the parser would no longer be deterministic.
Furthermore, if a grammar is shown to be LL(1) then it is unambiguous. This is easy to
show. An ambiguous grammar would lead to two left-most derivations that differ in at least
one step, meaning at least two rules are applicable at that step. So an ambiguous grammar
cannot be LL(1).
It is possible for a grammar not to be LL(1) but LL(k) for some k > 1. That is, the
parser should be able to determine its moves looking k symbols ahead. In principle, this
would mean a table having columns for each combination of k symbols. But this would
lead to very large tables; indeed, the table size grows exponentially with k and would be
unwieldy even for k = 2. On the other hand, an LL(1) parser generator based on the table
construction in Algorithm 3.5 might allow one to specify a k-symbol lookahead for specific
non-terminals or rules. These special cases can be handled specially by the parser and so
need not lead to overly large (and, most likely sparse) tables. The JavaCC parser generator,
which we discuss in Section 3.5, makes use of this focused k-symbol lookahead strategy.

Removing Left Recursion and Left-Factoring Grammars
Not all context-free grammars are LL(1). But for many that are not, one may define equiv-
alent grammars (that is, grammars describing the same language) that are LL(1).

LeftRecursion

One class of grammar that is not LL(1) is a grammar having a rule with left recursion,
for example direct, left recursion,

Y ::= Y
Y ::=

(3.25)

Clearly, a grammar having these two rules is not LL(1), because, by denition, rst(Y)
must include rst() making it impossible to discern which rule to apply for expanding Y.
But introducing an extra non-terminal, an extra rule, and replacing the left recursion with
right recursion easily removes the direct left recursion:

Y ::= Y 0
Y 0 ::= Y 0
Y 0 ::=

(3.26)