Java Reference
In-Depth Information
of grammar symbols in
α
. Formally,
∈Σ|α⇒
a
First(
α
)
={
a
β}
α⇒
λ
Some texts include
λ
in First(
α
)if
. Those approaches ultimately require
frequent subtraction of
λ
from symbol sets. We adopt the convention of
never
α⇒
λ
including
λ
in First(
α
), even if
. When the results from the algorithm
shown in Figure 4.7 are available,
α
derives
λ
if and only if every symbol in
α
derives
λ
.
First(
α
) is computed by scanning
α
from left to right.
If
α
begins with
aterminalsymbola, then clearly First(
. If a nonterminal symbol
A is encountered, then the grammar productions for A must be consulted.
Nonterminals that can derive
α
)
= {
a
}
potentially disappear during a derivation, so
the computation must account for this as well.
As an example, consider the nonterminals Ta i l and Prefix from the gram-
mar in Figure 4.1. Each nonterminal has one production that contributes
information directly to the nonterminal's First set. Each nonterminal also has
a
λ
λ
-production, which contributes nothing. The solutions are as follows:
First(Ta i l )
= {
+
}
First(Prefix)
= {
f
}
In some situations, the First set of one symbol can depend on the First sets of
other symbols. To compute First(E), the production E
→
Prefix ( E ) requires
⇒
λ
computation of First(Prefix). Because Prefix
, First((E))mustalsobe
included. The resulting set: First(E)
.
The primary computation for the algorithm shown in Figure 4.8 is carried
out by the function I
={
v
,
f
,
(
}
nternal
F
irst
, whose input argument is the string
Xβ
.
If
Xβ
is not empty, then
X
is the string's first symbol and
β
is the rest of the
string. I
nternal
F
irst
then computes its answer as follows:
•
The empty set is returned if
Xβ
is empty at Marker
10
.Wedenotethis
condition by
⊥
to emphasize that the empty set is represented by a null
list of symbols.
•
If
X
is a terminal, then First(
Xβ
)is
{X}
at Marker
11
.
•
The only remainingpossibility is that
X
is a nonterminal. If
VisitedFirst
(
X
)
is
false
, then the productions for
X
are recursively examined for in-
clusion. Otherwise,
X
's productions already participate in the current
computation.
•
At Marker
15
we test if
X
can derive
λ
, as determined previously by
the algorithm in Figure 4.7. If
X
can derive
λ
, then we must include all
symbols in First(
β
).
