Java Reference
In-Depth Information
function
F
irst
(
α
)
returns
Set
foreach
A
∈
N
on
T
erminals
()
do
VisitedFirst
(A)
←
false
9
ans
←
I
nternal
F
irst
(
α
)
return
(
ans
)
end
function
I
nternal
F
irst
(
Xβ
)
returns
Set
if
Xβ=⊥
then return
(
10
∅
)
if
X∈Σ
then return
(
11
{X}
)
/ X
is a nonterminal.
/
12
ans
←∅
if not
VisitedFirst
(
X
)
then
VisitedFirst
(
true
foreach
rhs
∈
ProductionsFor
(
X
)
←
13
X
)
do
ans
←
ans
∪
I
nternal
F
irst
(
rhs
)
14
if
SymbolDerivesEmpty(
X
)
15
then
ans
←
ans
∪
I
nternal
F
irst
(
β
)
return
(
ans
)
end
16
Figure 4.8: Algorithm for computing First(
α
).
of the associated production is decremented by 1. This process continues until
the worklist is exhausted. The algorithm establishes two structures related to
derivations of
λ
, as follows:
•
RuleDerivesEmpty(
p
) indicateswhether or not production
p
can derive
λ
.
When every symbol in rule
p
's RHS can derive
λ
,Marker
6
establishes
that
p
can derive
λ
.
•
SymbolDerivesEmpty(A) indicates whether or not the nonterminal A can
derive
λ
. When any production for A can derive
λ
,Marker
7
establishes
that A can derive
λ
.
Both forms of information are useful in the grammar analysis and parsing
algorithms discussed in Chapters 4, 5, and 6.
A set commonly consulted by parser generators is First(
). This is the set of
all terminal symbols that can begin a sentential form derivable from the string
α
