Java Reference
In-Depth Information
State
LR(0) Item
Goto
Prop Edges
Initialize
State
Placed by Step
ItemFollow
First(
γ
)
27
29
28
0
1
Start→•S $
1
??
$
2,3,4,5
2
S→•lp M rp
2
6
3
S→•lb M rb
3
10
4
S→•lp U rb
2
7
5
S→•lb U rp
3
11
2
6
S
→
lp
•
Mrp
10
??
rp
8
7
S
9
??
rb
9
→
lp
•
Urb
8
M
6
14
→•
expr
9
U
6
15
→•
expr
3
10
S→lb•Mrb
5
??
rb
12
11
S→lb•Urp
4
??
rp
13
12
M
6
14
→•
expr
13
U
6
15
→•
expr
6
14
M
•
15
U→expr •
→
expr
Figure 6.37: Par tial LALR(1) analysis. Notice the propagation of rp
and rb to Item 14 from Items 8 and 12, respectively. Item 15
suffers a similar fate from Items 13 and 9. This leads to a
reduce/reduce conflict between M
→
expr and U
→
expr on rp
and rb in State 6.
The full LR(1) construction for the grammar in Figure 6.35 is given in
Figure 6.40). For now, consider two of the construction's LR(1) items:
[ S
→
lp
•
Mrp, $ ]and[M
→
expr
•
, rp ]
The first item is not ready for reduction, but indicates that $ will follow the
reduction to S when the item eventually becomes reducible (State 11 of Fig-
ure 6.40). The second item calls for a reduction by rule M
→
expr when rp is
the next input token.
In LR(
k
), a state is a set of LR(
k
) items, and construction of the CFSM
is basically the same as with LR(0). States are represented by their kernel
items, and new states are generated as needed. Figure 6.38 presents an LR(1)
construction algorithm in terms of modifications to the LR(0) algorithm shown
in Figures 6.9 and 6.10. At Marker
31
, any symbol that can follow B due
to the presence of
γ⇒
λ
γ
is considered; when
, then any symbol a that
