Java Reference
In-Depth Information
Lookahead
Nonterminal abcdq$
S
111 11
C
23 3
A
455 55
B
67777
Q
9
8
9
Figure 5.10: LL(1) table. The blank entries should trigger error actions
in the parser.
The resulting entry indicates which, if any, production of the CFGs should be
applied at this point in the parse.
For practical purposes, the nonterminals and terminals should be mapped
to small integers to facilitate table lookup using a two-dimensional array. The
procedure for constructing the parse table is shown in Figure 5.9. Upon the
procedure's completion, any entry marked 0 will represent a terminal symbol
that does not predict any production for the associated nonterminal. Thus, if
a 0 entry is accessed during parsing, then the input string contains an error.
Using the grammar shown in Figure 5.2 and its associated Predict sets
shown in Figure 5.3, we construct the LL(1) parse table shown in Figure 5.10.
The table's contents are the rule numbers for productions as shown in Fig-
ure 5.2, with blanks rather than zeros to represent errors.
Finally, using the parse table shown in Figure 5.10, we trace the behavior
of an LL(1) parser on the input string abbdc$in Figure 5.11.
It can be di
cult for inexperienced compiler writers to create LL(1) grammars.
This is because LL(1) requires a unique prediction for each combination of
nonterminal and lookahead symbols.
It is easy to write productions that
violate this requirement.
Fortunately, most LL(1) prediction conflicts can be grouped into two cat-
egories:
common prefixes
and
left recursion
. Simple grammar transformations
that eliminate common prefixes and left recursion are described below, and
these transformations allow us to obtain LL(1) form for most CFGss. How-
ever, there are some languages of interest for which no LL(1) grammar can be
constructed (see Section 5.6).
