Java Reference
In-Depth Information
1 S
→
Stmt $
2 Stmt
→
if expr then Stmt else Stmt
3
|
if expr then Stmt
4
|
other
Figure 5.17: Grammar for if-then-else.
Almost all common programming language constructs can be specified by
LL(1) grammars. One notable exception, however, is the if-then-else construct
present in programming languages such as Java
TM
and C. The if-then-else
language defined in Figure 5.16 has an endif token that
closes
each if.For
languages that lack this delimiter, the if-then-else construct is subject to the
so-called
dangling else
problem. This occurswhen a sequence of nested condi-
tionals contains more thensthanelses, which leaves open the correspondence
of thenstoelses. Programming languages resolve this issue by mandating
that each else is matched to its closest, otherwise unmatched then.
We next show that no LL(
k
) parser can handle languages that embed the
if-then-else construct shown in Figure 5.17. This grammar has common pre-
fixes that can be removed by the algorithm in Figure 5.13, but this grammar
has a more serious problem. As demonstrated by Exercises 10 and 13, the
grammar in Figure 5.17 is
ambiguous
and is therefore not suitable for LL(
k
)
parsing. Recall that an ambiguous grammar can produce at least two distinct
parses for some string in the grammar's language. Ambiguity and its possible
remediation are considered in greater detail in Chapter 6.
We do not intend to use the grammar of Figure 5.17 for LL(
k
)parsing.
Instead, we study the
language
of this grammar to show that
no
LL(
k
) grammar
exists for this language. In studies of this kind, it is convenient to redact
unnecessary detail to expose a language's problematic aspects. In the language
defined by the grammar of Figure 5.17, the if expr then Stmt portion serves as
an
opening bracket
and the else Stmt portion serves as an
optional closing bracket
.
Thus, the language of Figure 5.17 is structurally equivalent to the
dangling
bracket language
(DBL) defined as follows:
[
i
]
j
DBL
={
|
i
≥
j
≥
0
}.
We next show that DBL is not LL(
k
)forany
k
.
We can gain some insight into the problem by considering some grammars
for DBL. Our first attempt is the grammar shown in Figure 5.18(a), in which CL
generates an optional closing bracket. Superficially, the grammar appears to
