《编译原理(清华大学 第2版)课后习题答案》由会员分享，可在线阅读，更多相关《编译原理(清华大学 第2版)课后习题答案（36页珍藏版）》请在金锄头文库上搜索。
1、1 第三章第三章 N=D=N=D= 0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9 N=ND=NDDN=ND=NDD L=aL=a |a(0|1|3.|9)|a(0|1|3.|9)n n 且且 n=1n=1 (0|1|3.|9)(0|1|3.|9)n n 且且 n=1n=1 ab,ab, a an nb bn n n=1n=1 第第 6 6 题题. . (1)(1) = = = i i (2)(2) = = = () = () = ()=(i)=(i) (3)(3) = = * = * =i*i=i*i (4)(4) = + + = + = *+ = *+ = *
2、+ = = i*i+ii*i+i (5)(5) = +=+ = +=i+=i+ = i+i+ = i+(i+() = i+(i+(+) = i+(i+(+) = i+(i+i)i+(i+i) (6)(6) = + = + = + = i+i+ = i+i+* = i+i+* = = i+i*ii+i*i 第第 7 7 题题 * *i i i i+ + i i 2 + + i i i i* * i i 第第 9 9 题题 语法树语法树 s ss * ss+a aa 推导: S=SS*=SS+S*=aa+a* 11.11. 推导推导:E=E+T=E+T*F:E=E+T=E+T*F 语法树语法树:
3、: E E+ T TF* 短语短语: : T*FT*F E+T*FE+T*F 直接短语直接短语: : T*FT*F 句柄句柄: : T*FT*F 1212 3 短语：短语： 直接短语：直接短语： 句柄：句柄： 13.(1)13.(1)最左推导：最左推导：S S = ABSABS = aBSaBS =aSBBS=aSBBS = aBBSaBBS = abBSabBS = abbSabbS = abbAaabbAa = abbaaabbaa 最右推导：最右推导：S S = ABSABS = ABAaABAa = ABaaABaa = ASBBaaASBBaa = ASBbaaASBbaa = AS
4、bbaaASbbaa = AbbaaAbbaa = a1b1b2a2a3a1b1b2a2a3 (2)(2) 文法：文法：S S ABSABS S S AaAa S S A A a a B B b b (3)(3) 短语：短语：a1a1 , , b1b1 , , b2,b2, a2a2 , , , , bbbb , , aaaa , , abbaa,abbaa, 直接短语：直接短语： a1a1 , , b1b1 , , b2,b2, a2a2 , , , , 句柄：句柄：a1a1 1414 (1)(1) S S ABAB A A aAbaAb | | B B aBbaBb | | (2)(2)
5、S S 1S01S0 S S A A A A 0A10A1 | 第四章第四章 1.1. 1.1. 构造下列正规式相应的构造下列正规式相应的 DFADFA (1)(1)1(0|1)*1011(0|1)*101 NFANFA 0123 1101 0,1 4 (2)(2) 1(1010*|1(010)*1)*01(1010*|1(010)*1)*0 NFANFA 4 2 00 0 4 0 0 0 0 10 11 1 01 0 1 0 (3)NFA(3)NFA (4)NFA 01 b 3 6 a 2 bb 4 a b 5 b 2.2.解：构造解：构造 DFADFA 矩阵表示矩阵表示 0 01 1 XX
6、0 0ZZXX ZZ * *X,ZX,ZYY X,ZX,Z * *X,ZX,ZX,YX,Y YYX,YX,Y 01 a 3 4 b a,b 2 aa b 5 X,YX,YX,Y,ZX,Y,ZXX X,Y,ZX,Y,Z * *X,Y,ZX,Y,ZX,YX,Y 其中其中 0 表示初态， 表示初态，* *表示终态表示终态 用用 0 0，1 1，2 2，3 3，4 4，5 5 分别代替分别代替 X ZZ X,ZX,Z YY X,YX,Y X,Y,ZX,Y,Z 得得 DFADFA 状态图为：状态图为： 3 50 2 1 1 4 0 0 1 0 0 1 1 0 1 0 3 3解：构造解：构造 DFADFA
7、 矩阵表示矩阵表示 构造构造 DFADFA 的矩阵表示的矩阵表示 0 01 1 SS0 0V,QV,QQ,UQ,U V,QV,QZ,VZ,VQ,UQ,U Q,UQ,UVVQ,U,ZQ,U,Z Z,V* ZZZZ VVZZ Q,U,Z* *V,ZV,ZQ,U,ZQ,U,Z ZZZZZZ 其中其中 0 表示初态， 表示初态，* *表示终态表示终态 替换后的矩阵替换后的矩阵 0 01 1 0 00 01 12 2 1 13 32 2 2 24 45 5 3* 6 66 6 4 46 6 5* 3 35 5 6 66 66 6 构造构造 DFADFA 状态转换图（略）状态转换图（略） 4 4 （1 1
8、）解）解 构造状态转换矩阵：构造状态转换矩阵： 6 a ab b 000* 0* 0,10,111 0,10,1* *0,10,111 1100 转换为转换为 a ab b 0 0* *1 12 2 1 1* *1 12 2 2 20 0 22，33 00，11 22，3a=0,33a=0,3 2,3,0,12,3,0,1 0,1a=1,10,1a=1,1 0,1b=2,20,1b=2,2 （2 2）解：首先把）解：首先把 M M 的状态分为两组：终态组的状态分为两组：终态组00，和非终态组，和非终态组11，2 2，3 3，4,54,5 此时此时 G=(G=( 0,0, 1,2,3,4,51,
9、2,3,4,5 ) ) 1,2,3,4,51,2,3,4,5a a=1,3,0,5=1,3,0,5 1,2,3,4,51,2,3,4,5b b=4,3,2,5=4,3,2,5 由于由于44a a=0=0 1,2,3,51,2,3,5a a=1,3,5=1,3,5 因此应将因此应将1,2,3,4,51,2,3,4,5划分为划分为4,1,2,3,54,1,2,3,5 G=(041,2,3,5)G=(041,2,3,5) 1,2,3,51,2,3,5a a=1,3,5=1,3,5 1,2,3,51,2,3,5b b=4,3,2=4,3,2 因为因为1,51,5b b=4=4 2323b b=2,3=
10、2,3 所以应将所以应将1,2,3,51,2,3,5划分为划分为1,52,31,52,3 G=(01,52,34)G=(01,52,34) 1,51,5a a=1,5=1,5 1,51,5b b=4=4 所以所以1,51,5 不用再划分不用再划分 2,32,3a a=1,3=1,3 2,32,3b b=3,2=3,2 因为因为 22a a=1=1 33a a=3=3 所以所以2,32,3应划分为应划分为2323 所以化简后为所以化简后为 G G（ 0,2,3,4,1,50,2,3,4,1,5） 7.7.去除多余产生式后，构造去除多余产生式后，构造 NFANFA 如下如下 7 S A B D Q
11、 Z a b b a b b b a b a b 确定化，构造确定化，构造 DFADFA 矩阵矩阵 a ab b S SA AQ Q A AA AB,ZB,Z B,ZB,ZQ QD D Q QQ QD,ZD,Z D DA AB B D,ZD,ZA AD D B BQ QD D 变换为变换为 a ab b 0 00 01 13 3 1 11 12 2 2 2* *3 34 4 3 33 35 5 4 41 16 6 5 5* *1 14 4 6 63 34 4 化简：化简： G=(0,1,3,4,6),(2,5)G=(0,1,3,4,6),(2,5) 0,1,3,4,6a=1,30,1,3,4,
12、6a=1,3 0,1,3,4,6b=2,3,4,5,60,1,3,4,6b=2,3,4,5,6 所以将所以将0,1,3,4,60,1,3,4,6划分为划分为 0,4,61,30,4,61,3 G=(0,4,6),(1,3),(2,5)G=(0,4,6),(1,3),(2,5) 0,4,6b=3,6,40,4,6b=3,6,4 所以所以 划分为划分为0,4,60,4,6 G=(0),(4,6),(1,3),(2,5)G=(0),(4,6),(1,3),(2,5) 不能再划分，分别用不能再划分，分别用 0 0，4 4，1 1，2 2 代表各状态，构造代表各状态，构造 DFADFA 状态转换图如下；
13、状态转换图如下； 8 01 4 a,b a a b ba b 2 8 8代入得代入得 S S = = 0(1S|1)|0(1S|1)| 1(0S|0)1(0S|0) = = 01(S|)01(S|) | | 10(S|)10(S|) = = (01|10)(S|)(01|10)(S|) = = (01|10)S(01|10)S | | (01|10)(01|10) = = (01|10)(01|10)* *(01|10)(01|10) 构造构造 NFANFA S A B Z 0 1 0 1 1 0 由由 NFANFA 可得正规式为可得正规式为(01|10)(01|10)* *(01|10)=(
14、01|10)(01|10)=(01|10)+ + 9.9.状态转换函数不是全函数状态转换函数不是全函数, ,增加死状态增加死状态 8,8, G=(1,2,3,4,5,8),(6,7)G=(1,2,3,4,5,8),(6,7) (1,2,3,4,5,8)(1,2,3,4,5,8)a a=(3,4,8)=(3,4,8) (3,4)(3,4)应分出应分出 (1,2,3,4,5,8)(1,2,3,4,5,8)b b=(2,6,7,8)=(2,6,7,8) (1,2,3,4,5,8)(1,2,3,4,5,8)c c=(3,8)=(3,8) (1,2,3,4,5,8)(1,2,3,4,5,8)d d=(3
15、,8)=(3,8) 所以应将所以应将(1,2,3,4,5,8)(1,2,3,4,5,8)分为分为(1,2,5,8),(1,2,5,8), (3,4)(3,4) G=(1,2,5,8),(3,4),(6,7)G=(1,2,5,8),(3,4),(6,7) (1,2,5,8)a=(3,4,8)(1,2,5,8)a=(3,4,8) 8 8 应分出应分出 (1,2,5,8)b=(2,8)(1,2,5,8)b=(2,8) (1,2,5,8)c=(8)(1,2,5,8)c=(8) (1,2,5,8)d=(8)(1,2,5,8)d=(8) G=(1,2,5),(8),(3,4),(6,7)G=(1,2,5),(8
