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 $
4
13
$
2,3,4
2
S→•AB
2
8
5
b
5
3
S→•ac
3
11
4
S→•xAc
1
6
5
A→•a
3
12
1
6
S
→
x
•
Ac
9
18
c
7
7
A
10
19
→•
a
2
8
S→A•B
8
17
9,10
9
B→•b
7
16
10
B→•
3
11
S
→
a
•
c
6
15
12
A
→
a
•
4
13
Start→S•
5
14
$
5
14
Start
→
S $
•
6
15
S→ac•
7
16
B
→
b
•
8
17
S→AB•
9
18
S
11
20
→
xA
•
c
10
19
A→a•
11
20
S
→
xAc
•
Figure 6.29: LALR(1) analysis of the grammar in Figure 6.25.
Now consider the grammar in Figure 6.25 and its LALR(1) construction shown
in Figure 6.29. The items listed under the column for Marker
27
are the
targets of edges placed in the propagation graph to carry symbols to the point
of reduction. For example, consider Items 6 and 7. For the itemS
→
x
•
Ac,we
have
a is generated in Item 7, c can follow
the reduction to A.Marker
28
therefore adds c directly to Item 5's
ItemFollow
set. However, c is not useful until it is time to apply the reduction A
γ=
c. Thus, when the item A
→•
→
a.Thus,
propagation edges are placed between Items 7 and 19 by Marker
27
.
In most cases, lookahead is either
generated
(when First(
γ
)
∅
)or
propa-
gated
(when
γ=λ
). However, it is possible that First(
γ
)
∅
and
γ⇒
λ
,asin
⇒
λ
Item 2. Here,
.Thus,
Marker
28
causes b to contribute to Item 5's
ItemFollow
set. Additionally, the
γ=
B;wehaveFirst(B)
={
b
}
but we also have B
