Chapter 7: Pushdown Automata ~ 259
TABLE 7.5 The Precedence Relation for Example 7.14.
Stack symbol/
2
+
8$
Input symbol
Zo
.\
(
)
v'
v'
-/
-/
1
-/
-/
-/
-/
2
v'
-/
-/
-/
+
E
T
-/
v'
-/
F
-/
-/
-/
-/
Using the precedence relation and the moves given at the beginning of this
section we can construct a deterministic pda. As in the construction of top-down
parser. when we look ahead for one symbol we 'remember' it by changing state.
The deterministic pda which acts as a bottom-up parser is
A. = (Q. L
I
• 1. a. p. Zoo 0)
where
r = L U {$}. Q = {p} U {p er: (J E II}
1= {E. T. F} U 1: U {Zo, S}
and ais given by the following rules:
R
o(p. G, A) = (p. A)
Rc
o(Per' A. a) = (p, (Ja) for all (a. (J) R,
a(Per. A. T + E) = (Po, E) when (T (J) E P
R",
a(Per' A. Ta) = (Per. Ea) when (T, CJ) E P and a E 1 - {+}
R"
a(Per. A. F 'C n = (Per' T) when (F, CJ) E P
R f
a(Per. A. Fa) = (Per. Ta) when (F. CJ) E P and a E 1 - {,,}
Ra(Per' A. Ee) = (Per' F) when ( ). CJ) E P
Rei
a(Per' A. lx) = (Pu' F) when (1, CJ) E P
Rq
a(Per' A. 2x) = (Pu. F) when (2. CJ) E P
RiO: a(ps. A, E) = (Ps. A)
R 11 : a(ps. A. Zo) = (Ps. A)
As A. is deterministic. we have dropped parentheses on the R.H.S. of
R 1 - R 11. Using the pda A. we can get a bottom-up parsing for any input string
w. The bottom-up parsing for xl + (x2) is given in Table 7.6.