Java Reference
In-Depth Information
procedure
C
omplete
T
able
(
Table
,
grammar
)
call
C
ompute
L
ookahead
()
foreach
state
∈
Table
do
foreach
rule
∈
Productions
(
grammar
)
do
call
T
ry
R
ule
I
n
S
tate
(
state
,
rule
)
call
A
ssert
E
ntry
(
StartState
,
GoalSymbol
,
accept )
21
end
procedure
A
ssert
E
ntry
(
state
,
symbol
,
action
)
if
Table
[
state
][
symbol
]
=
error
22
then
Table
[
state
][
symbol
]
←
action
else
call
R
eport
C
onflict
(
Table
[
state
][
symbol
]
,
action
)
23
end
Figure 6.13: Completing an LR(0) parse table.
•
There is at most one item present in any double-boxed state—the rule
that should be applied upon entering the state. Upon reaching such
states, the CFSM has completely processed a rule. The associated item is
reducible
, with the marker moved as far right as possible.
•
If the CFSM's input string is syntactically invalid, then the parser will
enter a state such that the o
ff
ending terminal symbol cannot be shifted.
The table established during LR(0) construction at Marker
20
in Figure 6.10 is
almost suitable for parsing by the algorithm in Figure 6.3. Each state is a row
of the table, and the columns represent grammar symbols. Entries are present
only where the LR(0) construction allows transition between states—these are
the shift actions. To complete the table we apply the algorithm in Figure 6.13,
which establishes the appropriate reduce actions.
For LR(0), the decision to call for a reduce is reflected in the code of
Figure 6.14; arrival in a double-boxed state signals a reduction irrespective of
the next input token. As reduce actions are inserted, A
reports any
conflicts
that arise when a given state and grammar symbol call for multiple
parsing actions. Marker
22
allows an action to be asserted only if the relevant
table cell was previously undefined (cells are initialized to the value of error
at Marker
12
). Finally, Marker
21
calls for acceptance when the goal symbol
is shifted in the table's start state. Given the construction in Figure 6.11 and
the grammar in Figure 6.2, LR(0) analysis yields the parse table is shown in
Figure 6.15.
ssert
E
ntry
