Java Reference
In-Depth Information
Level
Rule
Marker Result Comment
F
ollow
(B)
0
F
ollow
(B)
0
S
→
ABc
{
c
}
21
0
{
c
}
Returns
24
F
ollow
(A)
0
F
ollow
(A)
0
S
→
A Bc
{
b,c
}
21
0
{
b,c
}
Returns
24
F
ollow
(S)
0
F
ollow
(S)
0
{}
Returns
24
Figure 4.12: Follow sets for the grammar in Figure 4.10. Note that
Follow(S)
={}
because S does not appear on the RHS of
any production.
•
Before any sets are computed, Marker
17
resets
VisitedFollow
(A)foreach
nonterminal A.
•
VisitedFollow
(A) is set atMarker
19
to indicate that the symbols following
A are already participating in this computation.
Figure 4.12 shows the progress of F
as it is invoked on the nonterminals
of Figure 4.10. As another example, Figure 4.13 shows the computation of
Follow sets for the grammar in Figure 4.1.
ollow
First and Follow sets can be generalized to include strings of length
k
rather
than length 1. First
k
(
α
)isthesetof
k
-symbol terminal prefixes derivable from
α
. Similarly, Follow
k
(A)isthesetof
k
-symbol terminal strings that can follow
A in some sentential form. First
k
and Follow
k
are used in the definition of pars-
ing techniques that use
k
-symbol lookaheads (for example, LL(
k
)andLR(
k
)).
The algorithms that compute First
1
(
α
)andFollow
1
(A) can be generalized to
compute First
k
(
α
)andFollow
k
(A) sets (see Exercise 26).
This ends our discussion of CFGs and grammar-analysis algorithms. The
First and Follow sets introduced in this chapter play an important role in the
automatic construction of LL and LR parsers, as discussed in Chapters 5 and 6,
respectively.
