Java Reference
In-Depth Information
1 Start
→
E$
2 E
→
Eplusnum
3
|
num
State 0
Goto
State 1
Goto
State 2
Goto
Start→•E $
2
E→num •
E
→E • plus num
3
E
→•
Eplusnum
2
Start
→
E
•
$
4
E
→•
num
1
State 3
Goto
State 4
Goto
State 5
Goto
E
→
Eplus
•
num
5
Start
→
E $
•
E
→
Eplusnum
•
Figure 6.18: Unambiguous grammar for infix sums and its LR(0)
construction.
di
cult. In particular, finding the ambiguous sentential form may require
significant extension of a viable prefix. Exercises 37 and 38 provide practice in
finding and fixing a grammar's ambiguity.
Figure 6.19 shows a grammar and a portion of its LR(0) construction for a
language similar to infix addition, where expressions end in either a or b.
The complete LR(0) construction is left as Exercise 15. State 2 contains a
reduce
reduce conflict. In this state, it is not clear whether num should be
reduced to an E or an F. The viable prefix that takes us to State 2 is simply
num. To obtain a sentential form, this must be extended either to num a $ or
num b $. If we use the former sentential form, then F cannot be involved in
the derivation. Similarly, if we use the latter sentential form, E is not involved.
Thus, progress past num cannot involve more than one derivation, and the
grammar is not ambiguous.
/
Since LR(0) construction failed for the grammar in Figure 6.19, we could
try a more ambitious table-construction method from among those discussed
in Sections 6.5.1, 6.5.2, and 6.5.4. It turns out that none can succeed. All LR(
k
)
constructions analyze grammars using
k
lookahead symbols. If a grammar is
LR(
k
), then there is some value of
k
for which all states are adequate in the
LR(
k
) construction described in Section 6.5.4. The grammar in Figure 6.19 is
not LR(
k
)forany
k
. To see this, consider the following rightmost derivation of
asu
cientlylongstringnum plus ... plus num a:
