发布时间 : 星期日 文章编译原理答案更新完毕开始阅读310e6c59250c844769eae009581b6bd97f19bca7
S A B a b S∷＝bB{aB} A∷＝Sa B∷＝Ac c #
第九次作业：
P144 10. 证明下述文法不是简单优先文法： （1） S∷＝bEb
E∷＝E+T | T （2） S∷＝bEb
E∷＝F | F+T | T | i T∷＝i | (E) 证明：
(1)画语法树： S
╱ │ ╲ b E b ╱ │ ╲ E + T
可以得出b=E和b>E,因此该文法不是简单优先文法。 (2)因该文法中含 E∷=i
T∷=i
右部两个产生式相同，故该文法不是简单优先文法.
P145 11. 构造下述文法的优先关系矩阵，它们是简单优先文法吗？ S∷＝M | U
M∷＝iEtMeM | a U∷＝iEtS | iEtMeU E∷＝b
解：优先关系矩阵如下 S M U i E t e a b S = M =< = U < = i < < E = t = > e => > a < < b < 其中含多重定义的表项，因而该文法不是简单优先文法。
P145 12. 根据图4.25的语法树，确定全部优先关系：
２１
(a) E=+ +=T T=* *=F (=E E=) *<( +
BEGIN<<说明> BEGIN
P145 13. 利用表4.6文法G[E]的优先关系矩阵，来分析符号串#b(((aa)a)a)b#和#((aa)a)#。 (1) 步骤 符号栈 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 (2) 步骤 符号栈 1 2 3 4 5 6 7 8 9
关系 < < < < < > = = > > = = > > = = > > = > > 关系 < < < > = = > > = ２２
输入串 规则 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 )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 输入串 规则 ((aa)a)# (aa)a)# aa)a)# a)a)# a)a)# M∷=a )a)# a)# a)# L∷=Ma) a)# M∷=(L # #b #b( #b(( #b((( #b(((a #b(((M #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 #((M #((Ma #((Ma) #((L #(M
10 11 12 13 #(Ma #(Ma) #(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） 用迭代法构造优先函数； （3） 用有向图法构造优先函数；
（4） 用优先函数表分析符号串i+i*i↑i 解：（1） + * ↑ ( ) ( ＋ >· >· >· ·< >· >· * ·< >· >· ·< >· >· ↑ ·< ·< ·< ·< >· >· ( ·< ·< ·< ·< ) >· >· >· = >· >· i ·< ·< ·< ·< （2）用迭代法构造优先函数 若R=S则f(R）=g(S) 若R·
２３
f g ＋ 3 2 * 3 4 ↑ 3 4 ( 1 4 ) 3 1 i 3 4 循环○2―○4 f g f g f g 最终结果： f g （3）
＋ 3 2 * 5 4 ↑ 5 6 ( 1 6 ) 7 1 i 7 6 ＋ 3 2 * 5 4 ↑ 5 6 ( 1 6 ) 7 1 i 7 6 ＋ 3 2 * 5 4 ↑ 5 6 ( 1 6 ) 5 1 i 5 6 ＋ 3 2 * 5 4 ↑ 5 4 ( 1 4 ) 5 1 i 5 4 ２４