Java Reference
In-Depth Information
State 0
Goto
State 1
Goto
State 2
Goto
Start→•S $
1
Start→S •
$
13
S →lp •Mrp
10
S
→•
lp M rp
2
S →lp •Urb
9
S
→•
lb M rb
3
M
→•
expr
6
S
→•
lp U rb
2
U
→•
expr
6
S
→•
lb U rp
3
State 3
Goto
State 4
Goto
State 5
Goto
State 6
Goto
S
→
lb
•
Mrb
5
S
→
lb U
•
rp
8
S
→
lb M
•
rb
7
M
→
expr
•
S
→
lb
•
Urp
4
U
→
expr
•
M
→•
expr
6
U
→•
expr
6
State 7
Goto
State 8
Goto
State 9
Goto
S
→
lb M rb
•
S
→
lb U rp
•
S
→
lp U
•
rb
12
State 10
Goto
State 11
Goto
State 12
Goto
S→lp M • rp
11
S→lp M rp •
S→lp U rb •
State 13
Goto
Start
→
S $
•
Figure 6.36: LR(0) construction.
we compute
ItemFollow
(15)
={
rb
,
rp
}
. Thus, State 6 contains a reduce
/
reduce
conflict. For LALR(1), the rules M
→
expr and U
→
expr can each be followed
by either rp or rb.
Because LALR(1) is based on LR(0), there is exactly one state with the
kernel of State 6. Thus, States 2 and 3 must share State 6 when shifting an expr.
If only we could split State 6, so that State 2 shifts to one version and State 3
shifts to the other, then the lookaheads in each state could resolve the conflict
between M
expr.TheLR(1) construction causes such splitting,
because a state is uniquely identified not only by its kernel from LR(0) but also
its lookahead information.
SLR(
k
)andLALR(
k
) supply information to LR(0) states to help resolve
conflicts. In LR(
k
), such information is part of the items themselves. For LR(
k
),
we extend an item's notation from A
→
expr and U
→
,
w
]. For LR(1),
w
is a (terminal) symbol that can follow A when this item becomes reducible.
For LR(
k
),
k
≥
→α•β
to [ A
→α•β
0,
w
is a
k
-length string that can follow A after reduction. If
symbols x and y canbothfollowA when A
→α•β
becomes reducible, then the
corresponding LR(1) state contains both [ A
, y ].
Notice how nicely the notation for LR(
k
) generalizes LR(0). For LR(0),
w
must be a 0-length string. The only such string is
→α•β
, x ]and[A
→α•β
λ
, which provides no
information at a possible point of reduction, since
λ
does not occur as input.
