资源预览内容
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
亲,该文档总共7页全部预览完了,如果喜欢就下载吧!
资源描述
1第二章 高级语言及其语法描述6 (1)L(G 6)=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)(2)9证明:该文法存在一个句子 iiiei 有两棵不同语法分析树,如下所示,因此该文法是二义的。E+ TTFiEE + TFiFiE+ TFiET * FiFiTE- TTFiEE - TFiFiSS ei Si SSiiSei SiSiSi210.【答案】无二义文法为: 11. 【答案】第 3 章 词法分析7构造下列正规式相应的 DFA:(1) 1(0|1)*101解:(1)构造 NFA:0X1 5 2 Y0,113 411(2)确定化:构造状态转换矩阵如下: 重命名:I I0 I1X - 1,5,21,5,2 5,2 5,3,25,2 5,2 5,3,25,3,2 5,4,2 5,3,25,4,2 5,2 5,Y,3,25,Y,3,2 5,4,2 5,3,2(3)化简 (4)化简之后的状态表 分组0,1,2,3,4 5考察0,1,2,3,4 0=2,4 0,1,2,3,41=1,3,5 分化为:0,1,2,3、4、5再考察:0,1,2,3 0=2,4 分化为:0,1,2,、3、4、5再考察:0,1,2 0=2 0,1,21=1,3 分化为:0、1,2,、3、4、5(5)画出状态转换图:S 0 10 - 11 2 32 2 33 4 34 2 55 4 3S 0 10 - 11 1 22 3 23 1 44 3 2G1:SABAaAb|abBcB|G2:SABAaA|BbBc|bcG3:SAAAaAb|G4:S1S0|AA0A1|STS|TT(S)|()30 1 210130104101(3) 0*10*10*10*解:(1)构造 NFA:(2)确定化:构造状态转换矩阵如下: 重命名:I I0 I1X,7,1 7,1 2,8,37,1 7,1 2,8,32,8,3 8,3 4,9,58,3 8,3 4,9,54,9,5 9,5 6,10,Y9,5 9,5 6,10,Y6,10,Y 10,Y -10,Y 10,Y -(3)化简 如上表所示:0,1、2,3、4,5、6,7化简后的状态表为:(4)最简 DFA 状态转换图0 1 2 31 110 00 08 (1) (0|1) *01S 0 10 1 21 1 22 3 43 3 44 5 65 5 66 7 -7 7 -S 0 10 0 11 1 22 2 33 3 -11 X 7 1 2 Y8 3 4 9 5 6 101 0 0 0 04(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- x 0,., xi-1 i=1,.,9(6) (x0 )y0(x1 )y1 (x2 )y2.(x9 )y9其中 x0 xi- x 0,., 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,1 0,10 1X 1 2 Y3 4 5 60 构造状态转换矩阵: 重命名: 最小化 化简后的状态表分组:0,1,2,3、4,5,6,7 考察:0,1,2,3 0=1,4 分化为 0,1,2、3、4,5,6,7再考察:0,1,2 0=1 0,1,21=2,3 分化为 0,2、1、3 、 4,5,6,7再考察:4,5,6,7 0=4,5 4,5,6,71=6,7 分化为 0,2、1、3 、 4,5,6,7再重新命名为:0,20、11、32、4,5,6,73I I0 I1X,1,2 1,3,2 1,21,3,2 1,3,2 1,4,21,2 1,3,2 1,21,4,2 1,5,3,2,6,Y 1,2|1,5,3,2,6,Y 1,3,6,2,Y 1,4,6,2,Y1,3,6,2,Y 1,3,6,2,Y 1,4,6,2,Y 1,4,6,2,Y 1,5,3,2,6,Y 1,6,2,Y1,6,2,Y 1,3,6,2,Y 1,6,2,YS 0 10 1 21 1 32 1 23 4 24 5 65 5 66 4 77 5 7S 0 10 1 01 1 22 3 03 3 35最小化后的状态转换图为:0011 201 010,13(2)正规式 1*(011111)*1* 或 1*(0111*)*1* NFA: 101 1X 1 2 3 Y4 56 7 81 1构造状态转换矩阵: 重命名: 最小化 化简后的状态表分组:0,1,2,4,5,6,7、 3 考察:0,1,2,4,5,6,7 0=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最小化后的状态转换图为:12I I0 I1X,1,2,3,4,5,Y 3,4,5,Y 1,6,5,2,3,4,Y3,4,5,Y 3,4,5,Y 6,5,Y1,2,3,4,5,6,Y 3,4,5,Y 1,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,Y 1,6,5,7,8,2,3,4,Y 3,4,5,7,8,Y 3,4,5,Y 6,5,8,Y,3,43,4,5,6,8,Y 3,4,5,Y 6,5,7,8,Y,3,4 3,4,5,6,7,8,Y 3,4,5,Y 6,5,7,8,Y,3,4 S 0 10 1 21 1 32 1 43 - 54 1 45 1 66 1 77 1 7S 0 10 1 01 1 22 - 01210011016(a) aaa,bX 10Y构造状态转换矩阵: 重命名:I Ia IbX,0,Y 0,1,Y 10,1,Y 0,1,Y 11 0,Y 0,Y 0,1,Y 1化简: 重命名后的状态表:分化为:0,1,3、2 考察:0,1,3a = 1 0,1,3b = 2 分化为:0,1,3、2画出确定化后的有限自动机: 最小化的有限自动机: ababab120 3a(b)最少化:首先分为终态集和非终态集:0,1 、2,3,4,50,1a=10,1b=2,42,3,4,5a=1,3,0,5 可分为2,4 和3,52,4b=3,53,5b=2,4形成划分:0,12,43 ,5最少化后的 DFA:S a b0 1 21 1 22 3 3 1 2S a b0 0 11 0 aab1070a1 2babab14每个 1 都有 0 直接跟在右边:(10|0) *1010015画出 NFA:SBA0,1 10C1F1000,10,1等价的左线性正规文法:FA1|B0|C0|C1S0|1|S0|S1A1|S1B0|S0CA1|B0|C0|C1
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号