Java Reference
In-Depth Information
-
If both parse trees are desirable (as in Exercise 38), then the gram-
mar's language contains a
pun
. While puns may be tolerable in
natural languages, they are undesirable in the design of computer
languages. A program specified in a computer language should
have an unambiguous interpretation.
-
If only one tree has merit, then the grammar can often be modified
to eliminate the ambiguity. While there are inherently ambiguous
languages (see Exercise 14), computer languages are not designed
with this property.
•
The grammar is not ambiguous, but the current table-building approach
could not resolve the conflict. In this case, the conflict might disappear
if one or more of the following approaches is taken:
-
The current table-construction method is given more lookahead.
-
A more powerful table-construction method is used.
It is possible that no amount of lookahead or table-building power can
resolve the conflict, even if the grammar is unambiguous. We consider
such a grammar in Section 6.4.2 and in Exercise 37.
When an LR(
k
) construction algorithm develops an inadequate state, it is
an unfortunate but important fact that it is impossible to decide automati-
cally which of the above problems a
icts the grammar. This follows from
the impossibility of an algorithm to determine if an arbitrary CFGs is am-
biguous [HU79, GJ79]. It is therefore also impossible to determine generally
whether a bounded amount of lookahead can resolve an inadequate state.
As a result, human (rather than mechanical) reasoning is required to un-
derstand and repair grammars for which conflicts arise. Sections 6.4.1 and 6.4.2
develop intuition and strategies for such reasoning.
Consider the grammar and its LR(0) construction shown in Figure 6.16. The
grammar generates sums of numbers using the familiar
infix
notation. In the
LR(0) construction, all states are adequate except State 5. In this state a plus
can be shifted to arrive in State 3. However, State 5 also allows reduction by
the rule E
reduce conflict
for LR(0). To resolve this conflict it must be decided how to fill in the LR
parse table for State 5 and the symbol plus. Unfortunately, this grammar is
ambiguous, so a unique entry cannot be determined.
While there is no automatic method for determining if an arbitrary gram-
mar is ambiguous, the inadequate states can provide valuable assistance in
→
EplusE. This inadequate state exhibits a shift
/
