编译原理答案

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=) *<( +* i>* )>+ T>+ F>+ (b) <说明表>=; BEGIN=<说明表> REAL=<标识符表> <变量>=:= ;=<语句表> :==i

BEGIN<<说明> BEGIN ;<<变量> ;>; <标识符表>>; i>; i>:=

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··S则f(R）>g(S) 1 ○ f g ＋ 1 1 * 1 1 ↑ 1 1 ( 1 1 ) 1 1 i 1 1 2根据·<的优先关系 ○ f g ＋ 1 2 * 1 2 ↑ 1 2 ( 1 2 ) 1 1 i 1 2 3根据·<的优先关系 ○ f g ＋ 3 2 * 3 2 ↑ 3 2 ( 1 2 ) 3 1 i 3 2 4根据=的优先关系 ○

２３

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 ２４