Chapter 7: pushdown Automata ~ 255
F --7 xl
F --7 x2
E--7 E + T
E--7 T
T--7 T :i~ F
T--7 F
G = ({T F, E} L, p, E), where L = {x, L 2, +, *, (,)} and P consists of
F --7 (E)
Let us construct a top-down parser for L(G).
T --7 A
F --7 .12
F --7 (E)
F --7 xl
Step 1 We eliminate left recursion by applying Theorem 7.7 to the left
recursive variables E and T. We replace E --7 E + T and E --7 T by E --7 TE',
E' --7 + TE' and E' --7 A (E' is a new variable). Similarly, T --7 T " F and
T --7 F are replaced by T --7 FT', T' --7 * FT' and T' --7 A The resulting
equivalent grammar is
G J = ({T. F, E, T'. E'L L, P'. E), where P' consists of
E --7 TE'
E' --7 +TE'
E' --7 A
T --7 FT'
T' --7 ~ FT'
Step 2 We apply Theorem 7.6 for left factoring to F --7 xl and F --7 x2 to
get new productions F --7 xN --7 N --7 1 and N --7 2.
The resulting equivalent grammar is
G~ = ({T. F. E, T', E1. L, pI!, E) where pI! consists of
PI: E --7 TE'
P 6 T ' --7 ;\
Po: E' --7 +Te
P~
F --7 (E)
!
Po.: E' --7 A
P s F --7 xN
P:J,: T --7 FT'
P 9 N --7 1
P s : Til --7 ~;: FT'
P lO : N --7 2
Step 3 The grammar G~ obtained III step 2 IS an LL(l) grammar. The
parsing table
.
.
.
Table 7.3.
IS gIven m
TABLE 7,3 Parsing Table for Example 7.12
.\
x
2
+
';'
E
E
P.
E
E
E
E
P,
E
T
E
P 4
E
E
E
E
P 4
E
r
E
P s
E
E
E
E
P 7
E
r
Po
E
E
E
E
Po
E
Po
E'
P 3
E
E
E
P 2
E
E
P 3
N
E
E
Pg
PiC
E
E
E
E