Java Reference
In-Depth Information
1 S
→
[SCL
1 S
→
[S
2
| λ
2
|
T
3 CL
→
]
3 T
→
[T]
4
| λ
4
| λ
(a)
(b)
Figure 5.18: Attempts to create an LL(1) grammar for DBL.
be LL(1) because it is free of left recursion and common prefixes. However, the
ambiguity present in the grammar of Figure 5.17 is retained in this grammar.
Any sentential form containing CL CL can generate the terminal ] two ways,
depending on which CL generates the ] and which generates
λ
.Thus,the
string [[]has two distinct parses.
To resolve the ambiguity, we create a grammar that follows the Java and
C convention: Each ] is matched with the
nearest unmatched
[. This approach
results in the grammar shown in Figure 5.18(b). This grammar generates
zero or more unmatched opening brackets followed by zero or more pairs
of matching brackets. In fact, this grammar is parsable using most bottom-
up techniques (such as SLR(1), which is discussed in Chapter 6). While this
grammar is factored and is not left-recursive, it is not LL(1) because the [ token
is in the predict sets for both rules for S (Rules 1 and 2 of Figure 5.18(b)). The
following analysis explains why this grammar is not LL(
k
)forany
k
:
[
∈
Predict(S
→
[S)
[
∈
Predict(S
→
T)
[[
∈
Predict
2
(S
→
[S)
[[
∈
Predict
2
(S
→
T)
···
[
k
∈
Predict
k
(S
→
[S)
[
k
∈
Predict
k
(S
→
T)
In particular, when an LL parser sees only open brackets, it cannot decide
whether to predict a matched or an unmatched open bracket. Bottom-up
parsers have an advantage here because they can delay applying a production
until an entire RHS is matched. On the other hand, top-down methods cannot
delay. Rather, they must predict a production based on the first (or first
k
)
symbols derivable from a RHS. To parse languages containing if-then-else
constructs, the ability to postpone segments of the parse is crucial.
