编译原理(第3版)课本习题答案.doc

第二章 高级语言及其语法描述6（1）L（G6）=0,1,2,.,9+（2）最左推导：N=ND=NDD=NDDD=DDDD=0DDD=01DD=012D=0127N=ND=DD=3D=34N=ND=NDD=DDD=5DD=56D=568最右推导：N=ND =N7=ND7=N27=ND27=N127=D127=0127N=ND=N4=D4=34N=ND=N8=ND8=N68=D68=5687【答案】：SABC | AC | CA1|2|3|4|5|6|7|8|9BBB|0|1|2|3|4|5|6|7|8|9C1|3|5|7|98（1）最左推导：E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*iE=T=T*F=F*F=i*F=i*(E)=i*(E+T)=i*(T+T)=i*(F+T)=i*(i+T)=i*(i+F)=i*(i+i)最右推导：E=E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*i=F+i*i=i+i*iE=T=T*F=T*(E)=T*(E+T)=T*(E+F)=T*(E+i)=T*(T+i)=T*(F+i)=T*(i+i)=F*(i+i)=i*(i+i)E-TTFiEE-TFiFiE+TTFiEE+TFiFiE+TFiET*FiFiT(2)9证明：该文法存在一个句子iiiei有两棵不同语法分析树，如下所示，因此该文法是二义的。SSeiSiSSiiSeiSiSiSiSTS|TT(S)|()10.【答案】无二义文法为： 11. 【答案】G1:SABAaAb|abBcB|G2:SABAaA|BbBc|bcG4:S1S0|AA0A1|G3:SAAAaAb|第3章 词法分析7构造下列正规式相应的DFA：(1) 1(0|1)*101解：（1）构造NFA：0X152Y0,113411（2）确定化：构造状态转换矩阵如下： 重命名：II0I1X-1,5,21,5,25,25,3,25,25,25,3,25,3,25,4,25,3,25,4,25,25,Y,3,25,Y,3,25,4,25,3,2S010-1123223343425543(3)化简 (4)化简之后的状态表 分组0,1,2,3,4 5S010-1112232314432考察0,1,2,3,40=2,4 0,1,2,3,41=1,3,5 分化为：0,1,2,3、4、5再考察：0,1,2,30=2,4 分化为：0,1,2,、3、4、5再考察：0,1,20=2 0,1,21=1,3 分化为：0、1,2,、3、4、5(5)画出状态转换图：01210130104101 (3) 0*10*10*10*解：（1）构造NFA：11X712Y8349561010000（2）确定化：构造状态转换矩阵如下： 重命名：II0I1X,7,17,12,8,37,17,12,8,32,8,38,34,9,58,38,34,9,54,9,59,56,10,Y9,59,56,10,Y6,10,Y10,Y -10,Y10,Y -S0101211223433445655667-77-(3)化简 如上表所示：0,1、2,3、4,5、6,7化简后的状态表为：S0100111222333-（4）最简DFA状态转换图012311100008（1）（0|1）*01 （2）=0，1，2，3，4，5，6，7，8，9(1|2|3|4|5|6|7|8|9）*(0|5)|（0|5） （3）1*0(01*0)1)*0*1(10*1)0)*（4）a*b*c*.z* (5) (x0)(x1) (x2).(x9) =0,1,.,9 其中x0 xi- x0,., xi-1 i=1,.,9 (6) (x0)y0(x1)y1 (x2)y2.(x9)y9 其中x0 xi- x0,., xi-1 i=1,.,9 如果 ym,则 yn= (m=0,.,9) (n=0,1,.,m-1,m+1,.,9) 其中y0,.,y9,0,1,.,9 (7) b*(aab)*9（1）正规式（0|1）*（010）（0|1）* NFA:0,10,101X12Y34560构造状态转换矩阵： 重命名：II0I1X,1,21,3,21,21,3,21,3,21,4,21,21,3,21,21,4,21,5,3,2,6,Y1,2|1,5,3,2,6,Y1,3,6,2,Y1,4,6,2,Y1,3,6,2,Y1,3,6,2,Y1,4,6,2,Y 1,4,6,2,Y1,5,3,2,6,Y1,6,2,Y1,6,2,Y1,3,6,2,Y1,6,2,YS01012113212342456556647757 最小化 化简后的状态表S01010112230333 分组：0,1,2,3、4,5,6,7 考察：0,1,2,30=1,4 分化为 0,1,2、3、4,5,6,7再考察：0,1,20=1 0,1,21=2,3 分化为 0,2、1、3、4,5,6,7再考察：4,5,6,70=4,5 4,5,6,71=6,7 分化为 0,2、1、3、4,5,6,7再重新命名为：0,20、11、32、4,5,6,73最小化后的状态转换图为：0011201010，13（2）正规式 1*（011111）*1* 或 1*（0111*）*1* NFA:1011X123Y4567811构造状态转换矩阵： 重命名：II0I1X,1,2,3,4,5,Y3,4,5,Y1,6,5,2,3,4,Y3,4,5,Y 3,4,5,Y6,5,Y1,2,3,4,5,6,Y 3,4,5,Y1,6,5,7,2,3,4,Y,86,5,Y 5,7,Y,8,3,41,2,3,4,5,6,7,8,Y 3,4,5,Y1,6,5,7,8,2,3,4,Y 3,4,5,7,8,Y 3,4,5,Y6,5,8,Y,3,43,4,5,6,8,Y 3,4,5,Y6,5,7,8,Y,3,4 3,4,5,6,7,8,Y 3,4,5,Y6,5,7,8,Y,3,4 S010121132143-5414516617717 最小化 化简后的状态表S010101122-0分组：0,1,2,4,5,6,7、 3 考察：0,1,2,4,5,6,70=1 0,1,2,4,5,6,71=2,3,4,6,7 分化为 0,2,4,5,6,7、1、3再重新命名为：0,2,4,5,6,70、11、32最小化后的状态转换图为：21001101112（a） aaa,bX10Y构造状态转换矩阵： 重命名：IIaIbX,0,Y0,1,Y10,1,Y0,1,Y110,Y0,Y0,1,Y1Sab01211223312化简： 重命名后的状态表：Sab00110分化为：0,1,3、2 考察：0,1,3a = 1 0,1,3b = 2 分化为：0,1,3、2画出确定化后的有限自动机： 最小化的有限自动机： aab10ababab1203a（b）最少化：首先分为终态集和非终态集：0，1、2，3，4，50，1a=10，1b=2，42，3，4，5a=1，3，0，5 可分为2，4和3，52，4b=