Java Reference
In-Depth Information
1 S
→
AC$
2 C
→
c
3
| λ
4 A
→
aBCd
5
|
BQ
6 B
→
bB
7
| λ
8 Q
→
q
9
| λ
Figure 5.2: ACFGs.
Rule
A
X
...X
m
First(
X
...X
m
) Derives
Follow(A) A sw r
1
1
Number
Empty?
1
S A C $
a,b,q,c,$
No
a,b,q,c,$
2 Cc
c
No
c
3
λ
Ye s
d,$
d,$
4 AaBCd
a
No
a
5
BQ
b,q
Ye s
c,$
b,q,c,$
6 BbB
b
No
b
7
λ
Ye s
q,c,d,$
q,c,d,$
8 Qq
q
No
q
9
λ
Ye s
c,$
c,$
Figure 5.3: Predict calculation for the grammar of Figure 5.2.
•
The grammar may be
ambiguous
, allowing multiple, distinct deriva-
tions of some string. Such grammars cannot be accommodated by
any
deterministic parsing method.
Finally, as discussed in Section 5.6, there are some languages for which no
LL(
k
) grammar is possible (see also Exercise 26).
We now apply the algorithm in Figure 5.1 to the grammar shown in
Figure 5.2. Figure 5.3 shows the Predict calculations. For each produc-
tion of the form A
→X
...X
m
, the fourth column shows First(
X
...X
m
).
1
1
The next column indicates whether
X
...X
m
⇒
λ
. The rightmost column
1
shows Predict(A
→X
1
...X
m
)—the set of symbols that predict the produc-
tion A
→X
1
...X
m
. This set includes First(
X
...X
m
), as well as Follow(A)if
1
...X
m
⇒
λ
X
1
.
