Java Reference
In-Depth Information
procedure
D
erives
E
mpty
S
tring
()
foreach
A
∈
N
on
T
erminals
()
do
SymbolDerivesEmpty(A)
←
false
foreach
p
∈
P
roductions
()
do
RuleDerivesEmpty(
p
)
←
false
Count
(
p
)
←
0
1
foreach
X∈
RHS(
p
)
do
Count
(
p
)
←
Count
(
p
)
+
1
2
call
C
heck
F
or
E
mpty
(
p
)
foreach
X∈
WorkList
do
3
WorkList
←
WorkList
−{X}
4
foreach
x
∈
O
ccurrences
(
X
)
do
5
p
←
P
roduction
(
x
)
Count
(
p
)
←
Count
(
p
)
−
1
call
C
heck
F
or
E
mpty
(
p
)
end
procedure
C
heck
F
or
E
mpty
(
p
)
if
Count
(
p
)
=
0
then
RuleDerivesEmpty(
p
)
←
true
6
A
LHS(
p
)
if not
SymbolDerivesEmpty(A)
then
←
SymbolDerivesEmpty(A)
←
true
7
WorkList
←
WorkList
∪{
A
}
8
end
Figure 4.7: Algorithm for determining nonterminals and productions
that can derive
λ
.
An algorithm to compute the productions and nonterminals that can derive
λ
is shown in Figure 4.7. The computation utilizes a
worklist
at Marker
3
.A
worklist
is a set that is augmented and diminished as the algorithmprogresses.
The algorithm is finished when the worklist is empty. Thus, the loop at
Marker
3
must account for changes to the set
WorkList
. To prove termination
of algorithms that utilize worklists, it must be shown that all worklist elements
appear a finite number of times.
In the algorithm shown in Figure 4.7, the worklist contains nonterminals
that are discovered toderive
. The integer
Count
(
p
) is initialized atMarkers
1
and
2
to the number of symbols on
p
's RHS. The count for any production of
the form A
λ
,itsLHSisplaced
on the worklist at Marker
8
. When a symbol is taken from the worklist at
Marker
4
, each occurrence of the symbol is visited atMarker
5
and the count
→λ
is 0. Once a production is known to derive
λ
