Java Reference
In-Depth Information
1 Start
→
E$
2 E
→
EplusE
3
|
num
State 0
Goto
State 1
Goto
State 2
Goto
Start→•E $
2
E→num •
E
→E • plus E
3
E
→•
EplusE
2
Start
→
E
•
$
4
E
→•
num
1
State 3
Goto
State 4
Goto
State 5
Goto
E
→
Eplus
•
E
5
Start
→
E $
•
E
→
EplusE
•
E
→
E
•
plus E
3
E
→•
EplusE
5
E
→•
num
1
Figure 6.16: An ambiguous expression grammar.
finding a string with multiple derivations—should one exist. Recall that a
parser state represents transitions made by the CFSMwhen recognizing viable
prefixes. The bookmark symbol shows the progress made thus far. Symbols
appearing after the bookmark are symbols that can be shifted tomake progress
toward a successful parse. While our ultimate goal is the discovery of an input
string with multiple derivations, we begin by trying to find an ambiguous sen-
tential form. Once identified, the sentential form can easily be extended into a
terminal string by replacing nonterminals using the grammar's productions.
Using State 5 in Figure 6.16 as an example, the steps taken to understand
conflicts are as follows:
1. Using the parse table or CFSM, determine a sequence of vocabulary sym-
bols that cause the parser to move from the start state to the inadequate
state. For Figure 6.16, the simplest such sequence is EplusE,which
passes through States 0, 2, 3, and 5. Thus, in State 5 we have EplusEon
the top-of-stack. One option is a reduction by E
→
EplusE. However,
with the item E
→
E
•
plus E, it is also possible to shift a plus and then
an E.
2. If we line up the dots of these two items, we obtain a snapshot of
what is on the stack upon arrival in this state and what may be suc-
cessfully shifted in the future. Here we obtain the sentential form prefix
EplusE
reduce conflict tells us that there are two po-
tentially successful parses. We therefore try to construct two derivation
trees for E plus E plus E, one assuming the reduction at the bookmark
symbol and one assuming the shift. Completing either derivation may
require extending this sentential prefix so that it becomes a sentential
•
plus E.Theshift
/
