Java Reference
In-Depth Information
procedure
S
tmt
()
if
ts
.
peek()= id
then
1
call
match
(
ts
,
id )
2
call
match
(
ts
,
assign)
3
call
V
al
()
4
call
E
xpr
()
5
else
if
ts
.
peek()= print
then
call
6
match
(
ts
,
print )
call
match
(
ts
,
id )
else
call
error
()
7
end
Figure 2.7: Recursive-descent parsing procedure for Stmt. The
variable
ts
is an input stream of tokens.
•
If id is the next input token, then the parse must proceed with a rule that
generates id as its first terminal. Because Stmt
id assign Val Expr is the
only rule for Stmt that first generates an id, it must be uniquely predicted
by the id token. Marker
1
in Figure 2.7 performs this test.
We say that the
predict set
for Stmt
→
→
id assign Val Expr is
{
id
}
.
•
Similarly, if print is the next input token, the production Stmt
→
print id is
predicted by the test at Marker
6
. The predict set for Stmt
→
print id is
{
print
}
.
•
Finally, if the next input token is neither id nor print, then neither rule
can be predicted. Given that the S
procedure is called only where the
nonterminal Stmt should be derived, the input must have a syntax error,
as reported at Marker
7
.
tmt
Computing the predict sets used in S
is relatively easy, because each pro-
duction for Stmt begins with a distinct terminal symbol (id or print). However,
consider the productions for Stmts:
tmt
Stmts
→
Stmt Stmts
Stmts
→λ
The predict sets for S
in Figure 2.8 cannot be computed so easily by
inspection because of the following:
tmts
