Java Reference
In-Depth Information
function
I
LL1(
G
)
returns
Boolean
foreach
A
s
∈
N
do
PredictSet
←∅
foreach
p
∈
ProductionsFor
(A)
do
if
Predict(
p
)
∩
PredictSet
∅
then return
(
false
)
PredictSet
←
PredictSet
∪
4
Predict(
p
)
return
(
true
)
end
Figure 5.4: Algorithm to determine if a grammar
G
is LL(1).
procedure
(
ts
,
token
)
if
ts
.
peek()=
token
then call
ts
.
advance()
else call
match
error
(Expected
token
)
end
Figure 5.5: Utility for matching tokens in an input stream.
The algorithm shown in Figure 5.4 determines whether a grammar is LL(1)
based on the grammar's Predict sets. The Predict sets for each nonterminal A
are checked for intersection. If no two rules for A have any prediction symbols
in common, then the grammar is LL(1). The grammar of Figure 5.2 passes this
test, and is therefore LL(1).
We are now prepared to generate the procedures of a recursive-descent parser.
The parser's input is a sequence of tokens provided by the stream
ts
.We
assume that
ts
o
ff
ers the following methods:
• peek
, which examines the next input token without advancing the input
• advance
, which advances the input by one token
The parsers we construct rely on the
method shown in Figure 5.5. This
method checks the token stream
ts
for the presence of a particular token.
To construct a recursive-descent parser for an LL(1) grammar, we write a
separate procedure for each nonterminal A.IfA has rules
p
1
match
,...,
p
n
,thenwe
formulate the procedure shown in Figure 5.6. The code constructed for each
p
i
,
p
2
is obtained by scanning the RHS of rule
p
i
(i.e., symbols
X
...X
m
)fromleft
1
