编译原理 第四章 语法分析—自上而下分析
FOLLOW（B）= FOLLOW（B`）={c} ④证明该文法是否是LL（1）文法？
因为文法G`(A)中只含有一个多候选式的定义式A`?ABc??和B`?bB`??。
只需证明：
FIRST（A`）?FOLLOW（A`）={a, ?}?{#，d}=? FIRST（B`）?FOLLOW（B`）={b, ?}?{#，d}=? 该文法是LL（1）文法。
⑤构造相应的LL（1）分析表
因为 FIRST（A）={a}，所以M[A，a]= A?aA`；
因为 FIRST（S`）={b，?}，所以M[S`，b]= S`?bAS`， 又因为??FIRST（S`），则对{d，#}?FOLLOW（S`）， 所以M[A`，d]= A`??，M[A`，#]= A`??； 因为FIRST（B）={d}，所以M[B，d]= B?dB`；
因为FIRST（B`）={b}，所以M[B`，b]= B`?Bb`， 又因为??FIRST（B`），则对{c}?FOLLOW（B`）， 所以M[B`，c]= B`??。 LL(1)分析表 a b c d # A A?aA` A` A`?ABc B A`?? A`?? B?dB` 制作人：李明新 共28页第21页 13-3-24
编译原理 第四章 语法分析—自上而下分析
B` B`?Bb` B`??
⑥输入串aadc#的分析过程。
步骤 0 1 2 3 4 5 6 7 8 9 10 符号栈 ＃A ＃A`a ＃A` ＃cBA ＃cBA`a ＃cBA` ＃cB ＃cB`d ＃cB` ＃c ＃ 输入串 aadc＃ aadc＃ adc＃ adc＃ dc＃ dc＃ dc＃ dc＃ c＃ c＃ ＃ 所用产生式 A?aA` 匹配 A`?ABc A?aA` 匹配 A`?? 匹配 B`?? 匹配 结束 作业 :
⑴根据P76表4.1写出表达式 (i+i)*i 的预测分析过程。 ⑵P81 1, 2(1)(2)(3)
制作人：李明新 共28页第22页 13-3-24
编译原理 第四章 语法分析—自上而下分析
作业解析
一、P76的文法写出表达式 (i+i)*i 的预测分析过程。 解答：
步骤 符号栈 输入串 所用的产生式
0 #E （i+i）*i# 1 #E`T （i+i）*i# E?TE` 2 #E`T`F （i+i）*i# T?FT` 3 #E`T`）E（ （i+i）*i# F?（E） 4 #E`T`）E i+i）*i#
5 #E`T`）E`T i+i）*i# E?TE` 6 #E`T`）E`T`F i+i）*i# T?FT` 7 #E`T`）E`T`i i+i）*i# F?i 8 #E`T`）E`T` +i）*i# 9 #E`T`）E` +i）*i# T`?? 10 #E`T`）E`T+ +i）*i# E`?+TE` 11 #E`T`）E`T i）*i#
12 #E`T`）E`T`F i）*i# T?FT` 13 #E`T`）E`T`i i）*i# F?i 14 #E`T`）E`T` ）*i#
15 #E`T`）E` ）*i# T`?? 16 #E`T`） ）*i# E`?? 18 #E`T` *i#
19 #E`T`F* *i# T`?*FT` 20 #E`T`F i# 21 #E`T`i i# F?i 22 #E`T` #
23 #E` # T`?? 24 # # E`??
二、考虑下面文法G
S? a?^?（T） T?T，S?S
⑴消除文法的左递归。
制作人：李明新 共28页第23页 13-3-24
编译原理 第四章 语法分析—自上而下分析
⑵经改写后的文法是否是LL（1）的？给出它的预测分析表。 解答：
⑴经考察该文法S? a?^?（T）的各侯选式的首字符都是终结符号，所以只有T?T，S?S是直接左递归。根据改写算法，改写后的文法是：
S? a?^?（T） T?ST`
T`?，ST`??
⑵证明改写后的文法是否是LL（1）的.
①证明S? a?^?（T）各侯选式的FIRST是否两两相交。 FIRST（a）?FIRST（^）=?
FIRST（a）?FIRST（（）=? FIRST（^）?FIRST（（）=?
②证明T`?，ST`??的FIRST（T`）和FOLLOW（T`）是否相交。
求FIRST（T`）={，，?}
FOLLOW（T`）={ ? }
FIRST（T`）? FOLLOW（T`）={，，?}?{ ? }=?
该文法是LL（1）的。
⑶构造预测分析表
a ， ^ （ ） # S S? a S?^ S?（T） 制作人：李明新 共28页第24页 13-3-24
编译原理 第四章 语法分析—自上而下分析
T T?ST` T?ST` T?ST`
T` T`?，ST` T`??
二、下面的文法G
E? TE` E`?+E?? T?FT`
T`?T?? F?PF` F`?*F`??
P?（E）?^?a?b
⑴计算这个文法的每个非终结符的FIRST和FOLLOW。⑵证明这个文法是LL（1）的 ⑶构造它的预测分析表。 解答：
⑴求非终结符的FIRST和FOLLOW。 求非终结符的FIRST：
因为E`?+E??，所以FIRST（E`）={+， ?}。 因为F`?*F`??，所以FIRST（F`）={*， ?}。 因为P?（E）?^?a?b，
所以FIRST（P）={（， ^， a， b ?。 因为F?PF`，所以FIRST（F）= FIRST（P）。 因为T?FT`，所以FIRST（T）={FIRST（F）。
制作人：李明新 共28页第25页 13-3-24