Java Reference
In-Depth Information
19. The algorithm presented in Figure 4.8 retains no information between
invocations of F
. As a result, the solution for a given nonterminal
might be computed multiple times.
irst
(a) Modify the algorithm so it remembers and references valid previous
computations of First(A)
∈
N
.
(b) Frequently an algorithm needs First sets computed for
all
X∈
N
.
Devise an algorithm that e
,
A
ciently computes First sets for all non-
terminals in a grammar. Analyze the e
ciency of your algorithm.
Hint:
Consider constructing a directed graph whose vertices rep-
resent nonterminals. Let an edge (
A
,
B
)representthatFirst(B)de-
pends on First(A).
(c) Repeat this exercise for the Follow sets.
20. Prove that F
irst
(A) correctly computes First(A)foranyA
∈
N
.
21. Prove that F
ollow
(A) correctly computes Follow(A)foranyA
∈
N
.
22. Let G be any CFG and assume
L(G). Show that G can be transformed
into a language-equivalent CFG that uses no
λ
λ
-productions.
23. A
unit production
is a rule of the form A
B. Show that any CFG that
contains unit productions can be transformed into a language-equivalent
CFG that uses no unit productions.
→
24. Some CFGs denote a language with an infinite number of strings; others
denote finite languages. Devise an algorithm that determines whether a
given CFG generates an infinite language.
Hint:
Use the results of Exercises 22 and 23 to simplify the analysis.
25. Let G be an unambiguous CFG without
λ
-productions.
(a) If
x
∈
L(G), show that the number of steps needed to derive
x
is
linear in the length of
x
.
(b) Does this linearity result hold if
-productions are included?
(c) Does this linearity result hold if G is ambiguous?
λ
26. The algorithms in Figures 4.8 and 4.11 compute First(
α
)andFollow(A).
(a) Modify the algorithm in Figure 4.8 to compute First
k
(
).
Hint:
Consider formulating the algorithm so that when First
i
(
α
α
)is
computed, enough information is retained to compute First
i
+1
(
α
).
(b) Modify the algorithm in Figure 4.11 to compute Follow
k
(A).
