Java Reference
In-Depth Information
Expr
Expr
Expr
-
Expr
Expr
-
Expr
Expr
-
Expr
id
id
Expr
-
Expr
id
id
id
id
(a)
(b)
Figure 4.3: Two parse trees for id - id - id.
Exercises 16 and 17 consider how to detect both forms of useless nontermi-
nals. Many parser generators verify that a grammar is in reduced form. An
unreduced grammar probably contains errors that result from mistyping of
grammar specifications.
Some grammars allow a derived string to have two or more di
erent parse
trees (and thus a nonunique structure). Consider the following grammar,
which generates expressions using the infix operator for subtraction.
ff
1 Expr
→
Expr - Expr
2
|
id
This grammar allows two di
erent parse trees for id - id - id, as illustrated in
Figure 4.3. The tree in Figure 4.3(a) models the subraction of the third id from
the di
ff
erence
of the last two id symbols from the first. If the id symbols have values 3, 2, and
1, then tree Figure 4.3(a) evaluates to 0, while tree Figure 4.3(b) evaluates to 2.
Grammars that allow di
ff
erence of the first two. The tree in Figure 4.3(b) subtracts the di
ff
erent parse trees for the same terminal string are
called
ambiguous
. They are rarely used because a unique structure (i.e., parse
tree) cannot be guaranteed for all inputs. Hence, a unique translation, guided
by the parse tree structure, may not be obtained.
It seems we need an algorithm that checks an arbitrary CFG for ambiguity.
Unfortunately, no algorithm is possible for this in the general case, as the prob-
lem is
undecidable
[HU79, Mar03]. For certain grammar classes, successful
ff
