260 ~ Theory of Computer Science
Table 7.6 Bottom-up Parsing for xl + (x2)
Step
State
Unread
Pushdown
Rule
Production
input
stack
used
applied
1
p
xl + (x2)
Zo
2
p,:
I + (x2)
Zo
Rj
3
p
1 + (x2)
xZo
R 2
4
P1
+ (x2)
xZo
R 1
5
P
+ (x2)
1.1:Z o
R 2
6
P+
+ (x2)
1.>:Zo
R 1
7
P+
+ (.>:2)
FZ o
R s
F -7 x1
8
P+
+ (x2)
TZ o
R 6
T -7 F
9
P+
+ (.12)
EZ o
R 4
E-7T
10
P
(.>:2)
+EZ o
R 2
11
p(
.>:2)
+EZ o
Rj
12
P
x2)
(+EZ o
R 2
13
Px
2)
(+EZ o
R 1
14
P
2)
x(+EZ o
R 2
15
P2
)
x(+EZ o
R 1
16
P
)
2x(+EZ o
R 2
17
P;
$
2x(+EZ o
R 1
18
P;
$
F(+EZ o
Rg
F -7 x2
19
PI
$
T(+EZ o
R 6
T -7 F
20
P;
$
E(+EZ o
R 4
E-7T
21
P
$
)E(+EZ o
R 2
22
Ps
A
)E(+EZ o
R 1
23
Ps
A
F+EZ o
R 7
F -7 (E)
24
Ps
A
T+EZ o
R 6
T -7 F
25
Ps
A
EZ o
R 3
E-7E+T
26
Ps
A
Zo
R 10
27
Ps
A
A
R 11
By backtracking the productions that we applied, we get a rightmost
derivation E ~ E + T ~ E + F ~ E + (E) ~ E + (D ~ E + (F) ~ E + (x2)
~ T + (x2) ~ F + (x2) ~ xl + (x2).
In Chapter 8 we will discuss how LR(k) grammars are amenable for
parsing.
7.5 SUPPLEMENTARY EXAMPLES
EXAMPLE 7.15
Construct a pda accepting all palindromes over {a, b}.
Solution
Let L = {w E {a. b} * Iw = VI}}. Before constructing the required pda, note
that L consists of palindromes of odd or even length. If w in L is of odd