Java Reference
In-Depth Information
of products, each T can now derive a product, with the simplest product
consisting of a single num. Thus, the rules for T are based on the rules for E,
substituting times for plus. Figure 6.21 shows a parse tree for the input string
from Figure 6.20, with multiplication having precedence over addition.
Figure 6.22 shows a portion of the LR(0) construction for our precedence-
respecting grammar. States 1 and 6 are inadequate for LR(0) because in each of
these states, there is the possibility of shifting a times or applying a reduction
to E. Figure 6.22 shows a sequence of parser actions for the sentential form
E plus num times num $, leaving the parser in State 6.
Consider the shift
reduce conflict of State 6. Todetermine if the grammar in
Figure 6.21 is ambiguous, we turn to the methods described in Section 6.4. We
proceed by assuming the shift and reduce are
each
possible given the sentential
form E plus T times num $.
/
•
If the shift is taken, then we can continue the parse in Figure 6.22 to
obtain the parse tree shown in Figure 6.21.
•
Reduction by rule E
EplusTyields E times num $, which causes the
CFSM in Figure 6.22 to block in State 3 with no progress possible. If we
try to reduce using T
→
num,thenweobtainE times T $, which can be
further reduced to EtimesE$. Neither of these phrases can be further
reduced to the goal symbol.
→
Thus, E times num $ is not a valid sentential form for this grammar and a
reduction in State 6 for this sentential form is inappropriate.
With the item E
EplusTmust
be appropriate under some conditions. If we examine the sentential forms
EplusT$and E plus T plus num $, we see that the E
→
EplusT
•
in State 6, reduction by E
→
EplusTmust be ap-
plied in State 6 when the next input symbol is plus or $,butnottimes. LR(0)
could not selectively call for a reduction in any state; however, methods that
can consult lookahead information in T
→
can resolve this conflict.
Consider the sequence of parser actions that could be applied between a
reduction by E
ry
R
ule
I
n
S
tate
EplusTand the next shift of a terminal symbol. Following
the reduction, E must be shifted onto the stack. At this point, assume terminal
symbol plus is the next input symbol. If the reduction to E can lead to a
successful parse, then plus can appear next to E in
some
valid sentential form.
An equivalent statement is plus
→
∈
Follow(E), using the Follow computation
from Chapter 4.
SLR(
k
)parsingusesFollow
k
(A) to call for a reduction to A in any state
containing a reducible item for A. Algorithmically, we obtain SLR(
k
)byper-
forming the LR(0) construction in Figure 6.9; the only change is to the method
T
,whoseSLR(1) version is shown in Figure 6.23. For our ex-
ample, States 1 and 6 are resolved by computing Follow(E)
ry
R
ule
I
n
S
tate
.The
SLR(1) parse table that results from this analysis is shown in Figure 6.24.
= {
plus
,
$
}
