Java Reference
In-Depth Information
LR(0) item
Progress of rule in this state
E
→•
plus E E Beginning of rule
E
→
plus
•
EE Processed a plus,expectanE
E
→
plus E
•
E
Expect another E
E
→
plus E E
•
Handle on top-of-stack, ready to reduce
Figure 6.8: LR(0) items for production E
→
plus E E.
symbol
denotes that there is
nothing
on this rule's RHS. We make this clear
when representing such rules as items. For A
λ
→λ
, the only possible item is the
reducible A
.
We now define a
parser state
as a set of LR(0) items. While each state is
formally a set, we drop the usual braces notation and simply list the the set's
elements (items). The LR(0) construction algorithm is shown in Figure 6.9.
The start state for our parser—nominally state 0—is formed at Marker
7
by including fresh items for each of the grammar's goal-symbol productions.
For our example grammar in Figure 6.2, we initialize the start state with
Start
→•
E$. The algorithm maintains
WorkList
—a set of states that need to
be processed by the loop at Marker
8
. Each state formed during processing
is passed through A
→•
, which determines at Marker
9
if the set of items
has already been identified as a state. If not, then a new state is constructed at
Marker
10
. The resulting state is added to
WorkList
at Marker
11
.Thestate's
row in the parse table is initialized at Marker
12
.
The processing of a state begins when the loop at Marker
8
extracts a state
s
from the
WorkList
.WhenC
dd
S
tate
ompute
G
oto
is called on state
s
, the following
steps are performed:
1. The
closure
of state
s
is computed at Marker
17
.
If a nonterminal
B appears just after the bookmark symbol (
), then in state
s
we can
process a B once one has been found. Transitions from state
s
must
include actions that can lead to discovery of a B.C
•
in Figure 6.10
returns a set that includes its supplied set of items along with fresh items
for B's rules. The addition of fresh items can trigger the addition of
still more fresh items. Because the computed answer is a set, no item
is added twice. The loop at Marker
14
continues until nothing new is
added. Thus, this loop eventually terminates.
losure
2. Marker
18
determines transitions from
s
. When a new state is added
during LR(0) construction, Marker
12
sets all actions for this state as
error. Transitions are defined for each grammar symbol
X
that appears
after the bookmark. C
in Figure 6.10 defines a transition at
Marker
20
from
s
to a (potentially new) state that reflects the parser's
ompute
G
oto