Java Reference
In-Depth Information
Marker
7
:
We initialize
StartItems
by including LR(1) items that have $ as
the follow symbol:
StartItems
←{
[ Start
→•
RHS(
p
),$]
|
p
∈
P
roductions
F
or
(Start )
}
Marker
13
:
We augment t he LR(0) item so that A
dvance
D
ot
returns the
appropriate LR(1) items:
return
{
∈
state
}
[ A
→αX•β
,a]
|
[ A
→α•Xβ
,a]
.
Marker
15
:
This entire loop is replaced by the following:
foreach
[ A
→α•
B
γ
, a ]
∈
ans
do
foreach
p
∈
P
roductions
F
or
(
B
)
do
foreach
b
∈
First(
γ
a)
do
31
ans
←
ans
∪{
[ B
→•
RHS(
p
),
b
]
}
Figure 6.38: Modifications to Figures 6.9 and 6.10 to obtain an LR(1)
parser
procedure
T
ry
R
ule
I
n
S
tate
(
s
,
r
)
if
[LHS(
r
)
→
RHS(
r
)
•
,
w
]
∈
s
then call
A
ssert
E
ntry
(
s
,
w
,
reduce r)
end
Figure 6.39: LR(1) version of T
ry
R
ule
I
n
S
tate
.
can follow A can also follow B.Thu ,Marker
31
considers each symbol
in First(
a). The current state receives an item for reach rule for B and each
possible followsymbol. Figure 6.14 shows T
γ
—the LR(0)method
for determining if a state calls for a particular reduction. The LR(1) version of
T
ry
R
ule
I
n
S
tate
is shown in Figure 6.39.
Figure 6.40 shows the LR(1) construction for the grammar in Figure 6.35.
States 6 and 14 would be merged under LR(0). For LR(1), these states di
ry
R
ule
I
n
S
tate
er
by the lookaheads associated with the reducible items. Thus, LR(1) is able to
resolve what would have been a reduce
ff
reduce conflict under LR(0).
The number of states (such as States 6 and 14) that split during LR(1)
construction is usually much larger. Instead of constructing a full LR(1) parse
table, one could begin with LALR(1), which is based on the LR(0) construction.
States could then be split selectively. As discussed in Exercise 35, LR(
k
)can
resolve only the reduce
/
/
reduce conflicts that arise during LALR(
k
)construction.
Ashift
reduce conflict in LALR(
k
) will also be present in the corresponding
LR(
k
) construction. Exercise 36 considers how to split LR(0) states on demand
/
