24 # # E`
二、考虑下面文法G
S T
a
^（T） S
T，S
⑴消除文法的左递归。
⑵经改写后的文法是否是LL（1）的？给出它的预测分析表。 解答：
⑴经考察该文法S终结符号，所以只有T法，改写后的文法是：
S T
T`
aST` ，ST`
^（T）
a
^
（T）的各侯选式的首字符都是S是直接左递归。根据改写算
T，S
⑵证明改写后的文法是否是LL（1）的.
①证明S
a
^（T）各侯选式的FIRST是否两两相交。
FIRST（^）=FIRST（（）=FIRST（（）=
FIRST（a）
FIRST（a）FIRST（^）
②证明T`否相交。
，ST`
的FIRST（T`）和FOLLOW（T`）是
求FIRST（T`）={，，
FOLLOW（T`）={
} }
FIRST（T`）? FOLLOW（T`）={，，
该文法是LL（1）的。
⑶构造预测分析表
}?{ }=?
a ， ^ （ ） #
S S T T
a SST` T
^ SST` T
（T） ST`
T` T`，ST` T`
二、下面的文法G
E E` T
T`F F`
P
TE` +EFT` TPF` *F`（E）
^
a
b
⑴计算这个文法的每个非终结符的FIRST和FOLLOW。 ⑵证明这个文法是LL（1）的 ⑶构造它的预测分析表。 解答：
⑴求非终结符的FIRST和FOLLOW。 求非终结符的FIRST：
因为E`因为F`因为P
+E*F`（E）
，所以FIRST（E`）={+， ，所以FIRST（F`）={*， ^
a
b，
。
}。 }。
所以FIRST（P）={（， ^， a， b 因为F因为T因为E因为T`
PF`，所以FIRST（F）= FIRST（P）。 FT`，所以FIRST（T）={FIRST（F）。 TE`，所以FIRST（E）= FIRST（T）。 T
，
{
}
。
所以FIRST（T`）= FIRST（T）
={（， ^， a， b ，求非终结符的FOLLOW： 因为E
TE`的E是文法的开始符号，FOLLOW（E）={#}，
FIRST（））\\{
}={#，)}
又因为P（E），所以FOLLOW（E）={#}
因为E因为E
TE`，所以FOLLOW（E`）=FOLLOW（E） TE`，并且E`≠
，
所以FOLLOW（T）=FIRST（E`）\\{}, 又因为E`
,
FOLLOW（E）={+}
{#,}}={+，
所以FOLLOW（T）={+}#,
}. 因为T#,
}. 因为T
FT`，并且T`≠
FT`，所以FOLLOW（T`）=FOLLOW（T）={+，
，
所以FOLLOW（F）=FIRST（T`）\\{},又因为T`所以FOLLOW（F）={（，^，a，b ={（，^，a，b 因为F
PF`，
{+，#,
,
FOLLOW（T）
}={（，^，a，b ,+，#,
所以FOLLOW（F`）=FOLLOW（F）={（，^，a，b ,+，#,
. 因为F
PF`，并且F`≠
，
,
所以FOLLOW（P）=FIRST（F`）\\{},又因为F`所以FOLLOW（P）={*
={*}
FOLLOW（F） {（，^，a，b,+,）,#
,#
.
={*,（，^，a，b ,+，⑵证明这个文法是LL（1）的 ①证明P
(E)
^
a
b各侯选式的FIRST是否两两相交。 FIRST（^）=FIRST（a）=FIRST（b）=
*F`
非终结符号的
FIRST（(E)）
FIRST（(E)）FIRST（(E)）
FIRST（^）
FIRST（^）FIRST（a）
②证明E`
+E
FIRST（a）=FIRST（b）=FIRST（b）=,T`
T
,F`
FIRST和FOLLOW是否相交。
FIRST（E`）? FOLLOW（E`）={+，
}?{#,
}=?
FIRST（T`）? FOLLOW（T`） ={（， ^， a， b ，
?{+，#, }=?
FIRST（F`）? FOLLOW（F`） ={*，
}?{（，^，a，b ,+，#,
=?
该文法是LL（1）的。
⑶构造预测分析表
+ * ( ) a b ^ # E TE` TE` TE` TE` E` +E`
T FT` FT` FT` FT` T`
T
T T T
F PF` PF` PF` PF` F`
*F`
P (E) a b ^
语法分析-自上而下分析
