南京邮电大学 编译原理 课后习题答案和讲解2(3)

＃∈FOLLOW(E) FOLLOW(E)={#}

规则二

)∈FOLLOW(E) FOLLOE(E)={ )，#}

FIRST(E’)-{ε}FIRST(T’)-{ε}FIRST(F’)-{ε}规则三 FOLLOW(E) FOLLOW(E) FOLLOW(T) FOLLOW(T) FOLLOW(F) FOLLOW(F) 最后结果为：

FIRST(E’)={+, ε} FIRST(F’)={*, ε}

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) ={ (，a，b，∧} FIRST(T’)={ (，a，b, ε，∧) FOLLOE(E)={ ), ＃} FOLLOW(E’)={＃，)} FOLLOW(T)={＋，＃，）} FOLLOW(T’)= {＋，＃，）}

FOLLOW(F)={ (，)，a，b，＋，＃，∧} FOLLOW(F’)={ (，)，a，b，＋，＃，∧} FOLLOW(P)= { (，)，a，b，＋，＃，∧,*} （2）证明该文法是LL（1）文法：

FOLLOW(E’) FOLLOW(E’)={# ，)} FOLLOW(T) FOLLOW(T)={＋，＃，）} FOLLOW(T’) FOLLOW(T’)= {＋，＃，）}

FOLLOW(F) FOLLOW(F)={ (，)，a，b，＋，＃，∧} FOLLOW(F’) FOLLOW(F’)= { (，)，a，b，＋，＃，∧} FOLLOW(P) FOLLOW(P)= { (，)，a，b，＋，＃，∧,*} FOLLOW(T) FOLLOW(T)={+}

FOLLOW(F) FOLLOW(F)={ (，a，b，∧} FOLLOW(P) FOLLOW(P)={*}

１１

证明：对于规则E’::=+E |ε，T’::=T |ε，F’::=*F’ |ε （仅有一边能推出空串） 有FIRST(+E)={+}∩FIRST(ε)= ?，FIRST(T)={(, a, b, ∧}∩FIRST(ε)= ? FIRST(*F’)={*}∩FIRST(ε)= ?，FIRST(+E)={+}∩FOLLOW(E’)= {#, )}=? FIRST(T)={(, a, b, ∧}∩FOLLOW(T’)= {+, #, )}=?

FIRST(*F’)={*}∩FOLLOW(F’)= { (，)，a，b，＋，＃，∧}=? 所以该文法是LL（1）文法。 （3）构造文法分析表 E E’ T T’ F F’ P

下面分析符号串a*b+b

步骤 分析栈 余留输入串 所用的产生式 1 #E a*b+b# E→TE’ 2 #E’T a*b+b# T→FT’ 3 #E’T’F a*b+b# F→PF’ 4 #E’T’F’P a*b+b# P →a 5 #E’T’F’a a*b+b#

6 # E’T’F’ *b+b# F’→*F’ 7 # E’T’F’* *b+b#

8 # E’T’F’ b+b# F’ →ε 9 # E’T’ b+b# T’ →T 10 # E’T b+b# T→FT’ 11 # E’T’F b+b# F→PF’ a E→TE’ T→FT’ T’ →T F→PF’ F’ →ε P →a b + * ( E→TE’ T→FT’ T’ →T F→PF’ F’ →ε P →(E) ) E’→ε T’ →ε F’ →ε ∧ # E→TE’ T→FT’ T’ →T F→PF’ E’→+E E→TE’ E’→ε T→FT’ T’ →T F→PF’ T’ →ε T’ →ε F’ →ε F’ →ε F’→*F’ P →b F’ →ε F’ →ε P →∧ １２

12 # E’T’F’P b+b# P →b 13 #E’T’F’b b+b#

14 #E’T’F’ +b# F’ →ε 15 #E’T’ +b# T’ →ε 16 #E’ +b# E’→+E 17 #E+ +b# 18 #E b# E→TE’ 19 #E’T b# T→FT’ 20 #E’T’F b# F→PF’ 21 # E’T’F’P b# P →b 22 # E’T’F’b b# 23 # E’T’F’ # F’ →ε 24 # E’T’ # T’ →ε 25 #E’ # E’→ε 26 # # 成功 所以符号串a*b+b是该文法的句子；

P145 13. 利用表4.6文法G[E]的优先关系矩阵，来分析符号串#b(((aa)a)a)b#和#((aa)a)#。 (1) 是文法的句子

步骤 1 2 3 4 5 6 7 # #b #b( #b(( #b((( #b(((a #b(((M < < < < < > = 符号栈 关系 输入串 规则 b(((aa)a)a)b# (((aa)a)a)b# ((aa)a)a)b# (aa)a)a)b# aa)a)a)b# a)a)a)b# a)a)a)b# M∷=a １３

8 9 10 11 12 13 14 15 16 17 18 19 20 21

#b(((Ma #b(((Ma) #b(((L #b((M #b((Ma #b((Ma) #b((L #b(M #b(Ma #b(Ma) #b(L #bM #bMb #Z = > > = = > > = = > > = > > )a)a)b# a)a)b# a)a)b# L∷=Ma) a)a)b# M∷=(L )a)b# a)b# a)b# L∷=Ma) a)b# M∷=(L )b# b# b# L∷=Ma) b# M∷=(L # # Z∷=bMb (2) 不是文法的句子

步骤 1 2 3 4 5 6 7 8 9 10 11

符号栈 关系 输入串 规则 # #( #(( #((a #((M #((Ma #((Ma) #((L #(M #(Ma #(Ma) < < < > = = > > = = > １４

((aa)a)# (aa)a)# aa)a)# a)a)# a)a)# M∷=a )a)# a)# a)# L∷=Ma) a)# M∷=(L )# # 12 13

#(L #M > > # L∷=Ma) # M∷=(L P146 17. 设已给文法G[S]: E∷＝E+T | T

T∷＝T*F | F F∷＝P↑F | P

P∷＝(E) | i

（1） 用迭代法构造优先函数； （2） 用优先函数表分析符号串i+i*i↑i

解：

( i * + ) ↑

( ·< ·< ·< ·< i ·< ·< ·< ·< * ·< >· >· ·< >· >· + ·< >· >· >· >· >· ) = >· >· >· >· >· ↑ ·< >· ·< ·< >· ·< （1）用迭代法构造优先函数 若R=S则f(R）=g(S) 若R··S则f(R）>g(S)

1 初始值 ○ f g ＋ 1 1 * 1 1 ↑ 1 1 ( 1 1 ) 1 1 i 1 1 2根据·<的优先关系修改f和g值 ○

１５