Java Reference
In-Depth Information
Algorithm 3.7 The LR(1) Parsing Algorithm
Input: Action and Goto tables, and the input sentence w to be parsed, followed by the
terminator
#
Output: a right-most derivation in reverse
Initially, the parser has the configuration
Stack
Input
s
0
a
1
a
2
:::a
n
#
where a
1
a
2
:::a
n
is the input sentence
repeat
If Action[s
m
;a
k
] = ss
i
, the parser executes a shift (the s stands for \shift") and goes
into state si,
i
, going into the configuration
Stack
Input
s
0
X
1
s
1
X
2
s
2
:::X
m
s
m
a
k
s
i
a
k+1
:::a
n
#
Otherwise, if Action[s
m
;a
k
] = ri (the r stands for \reduce"), where i is the number
of the production rule Y ::= X
j
X
j+1
:::X
m
, then replace the symbols and states
X
j
s
j
X
j+1
s
j+1
:::X
m
s
m
by Y s, where s = Goto[s
j1
;Y ]. The parser then outputs
production number i. The parser goes into the configuration
Stack
Input
s
0
X
1
s
1
X
2
s
2
:::X
j1
s
j1
Y s a
k+1
:::a
n
#
Otherwise, if Action[s
m
;a
k
] =
accept, then the parser halts and the input has been
successfully parsed
Otherwise, if Action[s
m
;a
k
] = error, then the parser raises an error. The input is not
in the language
until either the sentence is parsed or an error is raised
Example. Consider (again) our grammar for simple expressions, now in (3.31).
1. E ::= E
+
T
2. E ::= T
3. T ::= T
*
F
4. T ::= F
5. F ::=
(
E
)
6. F ::=
id
(3.31)
The Action and Goto tables are given in Figure 3.7.
Search WWH ::
Custom Search