Java Reference
In-Depth Information
Figure 4.9 shows the progress of F
as it is invoked on the nonterminals
of Figure 4.1. The level of recursion is shown in the leftmost column. Each
call to F
irst
irst
(
Xβ
) is shown with nonblank entries in the
X
and
β
columns. A
“
” indicates that the call does not recurse further. Figure 4.10 shows another
grammar and the computation of its First sets. For brevity, recursive calls to
I
on null strings are omitted.
Termination of First(A) must be handled properly in grammars where the
computation of First(A) appears to depend on First(A), as follows:
nternal
F
irst
A
→
B
···
B
→
C
···
C
→
A
In this grammar, First(A) depends on First(B), which depends on First(C),
which depends on First(A). In computing First(A), we must avoid endless
iteration or recursion. A sophisticated algorithm could preprocess the gram-
mar to determine such cycles of dependence. We leave this as Exercise 19
and present a clearer but slightly less e
cient algorithm in Figure 4.8. This
algorithm avoids endless computation by remembering which nonterminals
have already been visited, as follows:
•
First(
α
) is computed by invoking F
irst
(
α
).
•
Before any sets are computed, Marker
9
resets
VisitedFirst
(A)foreach
nonterminal A.
•
VisitedFirst
(
) is set at Marker
13
to indicate that the productions of A
already participate in the computation of First(
X
α
).
Parser-construction algorithms often require the computation of the set of
terminals that can
follow
anonterminalA in some sentential form. Because we
augment grammars to contain an end-of-input token ($), every nonterminal
except the goal symbol
must
be followed by some terminal. Formally, for
A
∈
N
,
Follow(A)
={
b
∈Σ|
S
⇒
+
α
Ab
β}.
Follow(A)providesthe
right context
associated with nonterminal A.For
example, only those terminals in Follow(A) can occur after a production for A
is applied.
