Java Reference
In-Depth Information
Algorithm 3.9 Computing goto
Input: a state s, and a symbol X 2 T [N
Output: the state, goto(s;X)
r fg
for each item [Y ::= X,
a
] in s do
add [Y ::= X ,
a
] to r
end for
return closure(r)
Example. Consider the computation of goto(s
0
;E), where s
0
is in (3.40). The relevant
items in s
0
are [E
0
::= E,
#
] and [E ::= E
+
T,
+/#
]. Moving the to the right of the E in
the items gives us f[E
0
::= E,
#
], [E ::= E
+
T,
+/#]
g. The closure of this set is the set
itself; let us call this state s
1
.
goto(s
0
, E) = s
1
= f[E
0
::= E ,
#
],
[E ::= E
+
T,
+/#
]g
In a similar manner, we can compute
goto(s
0
, T) = s
2
= f[E ::= T ,
+/#
],
[T ::= T
*
F,
+/*/#
]g
goto(s
0
, F) = s
3
= f[T ::= F ,
+/*/#
]g
goto(s
0
,
(
) involves a closure because moving the across the
(
puts it in front
of the E.
goto(s
0
,
(
) = s
4
= f[F ::=
(
E
)
,
+/*/#
],
[E ::= E
+
T,
+/)
],
[E ::= T,
+/)
],
[T ::= T
*
F,
+/*/)
],
[T ::= F,
+/*/)
],
[F ::=
(
E
)
,
+/*/)
],
[F ::=
id
,
+/*/)
]g
goto(s
0
,
id
) = s
5
= f[F ::=
id
,
+/*/#
]g
We continue in this manner, computing goto for the states we have, and then for any
new states repeatedly until we have defined no more new states. This gives us the canonical
LR(1) collection.
Search WWH ::
Custom Search