Java Reference
In-Depth Information
Start
E
E
E
plus
E
plus
E
$
E
E
Start
Figure 6.17: Two derivations for E plus E plus E $. The parse tree on
top favors reduction in State 5; the parse tree on bottom
favors a shift.
form: a string of vocabulary symbols derivable (in two di
ff
erent ways)
from the goal symbol.
For our example, E plus E plus E is almost a complete sentential form. We
need only append $ to obtain E plus E plus E $.
To emphasize that the derivations are constructed for the same string,
Figure 6.17 shows the derivations above and below the sentential form. If the
reduction is performed, then the earlyportion of E plus E plus E $ is structured
under a nonterminal; otherwise, the input string is shifted so that the latter
portion of the sentential form is reduced first. The parse tree that favors the
reduction in State 5 corresponds to a
left-associative grouping
for addition,
while the shift corresponds to a
right-associative grouping
.
Having analyzed the ambiguity in the grammar of Figure 6.16, we next
eliminate the ambiguity by creating a grammar that favors left-association—
the reduction instead of the shift. Such a grammar and its LR(0) construction
are shown in Figure 6.18. The grammars in Figures 6.16 and 6.18 generate
the same language. In fact, the language is regular, denoted by the regular
expression num (plus num)
$. So we see that even simple languages can
have ambiguous grammars. In practice, diagnosing ambiguity can be more
