Java Reference
In-Depth Information
function
C
ompute
LR0(
Grammar
)
returns
(
Set
,
State
)
States
←∅
StartItems
←{
Start
→•
RHS(
p
)
|
p
∈
P
roductions
F
or
(Start )
}
7
StartState
←
A
dd
S
tate
(
States
,
StartItems
)
while
(
s
←
WorkList
.
ExtractElement()) ⊥
do
call
C
8
(
States
,
s
)
return
((
States
,
StartState
))
end
function
A
ompute
G
oto
dd
S
tate
(
States
,
items
)
returns
State
if
items
States
then
9
s
←
newState
(
items
)
States
←
States
∪{
s
}
10
WorkList
←
WorkList
∪{
s
}
11
error
else
s
←
FindState
(
items
)
return
(
s
)
end
function
A
Table
[
s
][
]
←
12
dvance
D
ot
(
state
,X
)
returns
Set
return
{
→α•Xβ∈
state
}
A
→αX•β|
A
13
end
Figure 6.9: LR(0) construction.
progress after shifting across
every
item in this state with
after the
bookmark. All such items indicate transition to the same state since the
parsers we construct must operate deterministically. In other words, the
parse table has only one entry for a given state and symbol.
X
We now cons t ruc t an LR(0) parse table for the grammar shown in Figure 6.2. In
Figure 6.11 each state is shown as a separate box. The
kernel
of state
s
is the set
of items explicitly represented in the state. We use the convention of drawing
a line within a state to separate the kernel and closure items, as in States 0, 1,
and 5. In the other states, no item contains a
before a nonterminal, so no
closure items are indicated for those states. Next to each item in each state is
the state number reached by shifting the symbol next to the item's bookmark.
In Figure 6.11 the transitions are also shown with labeled edges between
the states. If a state contains a reducible item, then the state is double-boxed.
The edges and double-boxed states emphasize that the basis for LR parsing is
a
deterministic finite automaton
(DFA), called the
characteristic finite-state
machine
(CFSM).
A
viable prefix
of a right sentential form is any prefix that does not ex-
tend beyond its handle. Formally, a CFSM recognizes its grammar's viable
•
