Java Reference
In-Depth Information
1. Follow(S) contains
#
, that is, the terminator follows the start symbol.
2. If there is a rule Y ::= X in P, follow(X) contains rst() fg.
3. If there is a rule Y ::= X in P and either = or rst() contains , follow(X)
contains follow(Y ).
This definition suggests a straightforward algorithm.
Algorithm 3.4 Compute follow(X) for all non-terminals X in a Grammar G
Input: a context-free grammar G = (N;T;S;P)
Output: follow(X) for all non-terminals X in G
follow(S) f
#
g
for each non-terminal X 2 S do
follow(X) fg
end for
repeat
for each rule Y ::= X
1
X
2
:::X
n
2 P do
for each non-terminal Xi
i
do
Add rst(X
i+1
X
i+2
:::X
n
)fg to follow(X
i
), and if Xi
i
is the right-most symbol
or rst(X
i+1
X
i+2
:::X
n
) contains , add follow(Y ) to follow(X
i
)
end for
end for
until no new symbols are added to any set
Example. Again, consider our example grammar (3.21). By steps 1 and 2 of Algorithm
3.4,
follow(E) = f
#
g
follow(E
0
) = fg
follow(T) = fg
follow(T
0
) = fg
follow(F)
= fg
From rule 1, E ::= TE
0
, follow(T) contains first(E′)
0
)fg = f+g, and because rst(E
0
)
contains , it also contains follow(E). Also, follow(E
0
) contains follow(E). So, round 1 of
step 3 yields,
follow(E
0
) = f
#
g
follow(T)
= f
+
,
#
g
We get nothing additional from rule 2, E
0
::=
+
TE
0
. follow(T) contains first(E′)−{},
0
)fg,
but we saw that in rule 1. Also, follow(E
0
) contains follow(E
0
), but that says nothing.
We get nothing additional from rule 3, E
0
::= .
From rule 4, T ::= FT
0
, follow(F) contains first(T
0
) - fg = f
*
g, and because rst(T
0
)
contains , it also contains follow(T). Also, follow(T
0
) contains follow(T). So, we have
follow(T
0
) = f
+
,
#
g
follow(F)
= f
+
,
*
,
#
g
Rules 5 and 6 give us nothing new (for the same reasons rules 2 and 3 did not).
Search WWH ::
Custom Search