Java Reference
In-Depth Information
These
k
tokens are called the
lookahead
of an LL(
k
) parser. If it is possible to
construct an LL(
k
) parser for a CFGs such that the parser recognizes the CFGs's
language, then the CFGs is an
LL
(
k
)
grammar
.
An LL(
k
) parser can peek at the next
k
tokens to decide which production
to apply. However, the
strategy
for choosing productions must be established
when the parser is constructed. In this section, the strategy is formalized by
defining a function called Predict
k
(
p
). This function considers the grammar
production
p
and computes the set of length-
k
token strings that predict the
application of rule
p
. We assume henceforth that we have one token of looka-
head (
k
=
1). The generalization is left to the reader as Exercise 16. Thus, for
rule
p
, Predict(
p
) is the set of terminal symbols (i.e., length-1 strings) that call
for applying rule
p
.
Consider a parser that is presented with the input string
β ∈ Σ
.Sup-
α
a
pose the parser has constructed the derivation S
⇒
lm
α
A
Y
...Y
n
.Atthis
1
point,
has been matched and A is the leftmost nonterminal in the derived
sentential form. Thus,
some
production for A must be applied to continue the
leftmost derivation. Because the input string contains an a as the next input
token, the parse must continue with a production for A that derives a as its
first terminal symbol.
Recalling the notation from Section 4.5.1 on page 127, we must examine
the set of productions
α
P
={
p
∈
P
roductions
F
or
(A)
|
a
∈
Predict(
p
)
}
One of the following conditions must be true of the set
P
and the next input
token
a
:
•
P
is the empty set. In this case, no production for A can cause the next
input token to be matched. The parse cannot continue and a syntax error
is issued, with a as the o
ending token. The productions for A can be
helpful in issuing error messages that indicate which terminal symbols
could be processed at this point in the parse. Section 5.9 considers error
recovery and repair in greater detail.
ff
•
P
contains more than one production. In this case, the parse could
continue, but
nondeterminism
would be required to pursue the inde-
pendent application of each production in
P
.Fore
ciency, we require
that our parsers operate deterministically. Thus parser constructionmust
ensure that this case cannot arise.
•
P
contains exactly one production. In this case, the leftmost parse can
proceed deterministically by applying the only production in set
P
.
A grammar can be analyzed to determine whether each terminal symbol pre-
dicts (at most) one of the rules for the nonterminal A. If such analysis holds
