Java Reference
In-Depth Information
call
Stack
.
push(
StartState
)
accepted
←
false
while not
accepted
do
action
←
Table
[
Stack
.
TOS( )][
InputStream
.
peek()]
if
action
=
1
shift
s
then
call
Stack
.
push(
s
)
2
if
s
∈
AcceptStates
then
3
accepted
←
true
call
InputStream
.
advance()
else
else
if
action
=
reduce A
→γ
then
call
Stack
.
pop(|γ|)
4
call
InputStream
.
prepend(A)
else
5
call
error
()
6
Figure 6.3: Driver for a bottom-up parser.
We have seen that an LR parse constructs a rightmost derivation in reverse.
Each reduction step in the LR parse uses a grammar rule such as A
→γ
to
replace
by A.Asequenceof
sentential forms
is thus constructed, beginning
with the input string and ending with the grammar's goal symbol.
Given a sentential form, the
handle
is defined as the sequence of symbols
that will next be replaced by reduction. The di
γ
culties lie in identifying
the handle and in knowing which production to employ in the reduction
(should there be multiple productions with the same RHS). These activities
are choreographed by the parse table.
A suitable parse table for the grammar in Figure 6.4 is shown in Figure 6.5.
This same grammar appears in Figure 5.2 on page 148 to illustrate top-down
parsing. Readers familiar with top-down parsing can use this grammar to
compare the methods.
To conserve space, shift and reduce actions are distinguished graphically
in our parse tables:
•
AshifttoState
s
is denoted by
.
s
•
Reduction by rule
r
is indicated by an unboxed entry of
r
.
•
Blank entries are error actions.
