编译作业参考答案.docx

《编译作业参考答案.docx》由会员分享，可在线阅读，更多相关《编译作业参考答案.docx（29页珍藏版）》请在优知文库上搜索。

1、1. L(G)=abc2. 1.(GN)是无符号整数。3. G3:E-D+EID-EIDD0l234567894. 1.(GZl)=anbnn05. (1)G5:N-*DNIEE02468D-*E13579(2)G5:NABEBDBEA-*l23456789Efol2468DAO6. (1) E=T E= i+F=i+(E)= i+(E+T)= i+(T+T)(5) E= E+TEnE+TT+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*iEzKE+TIzTT*FIIIFFi=i+(F+T)=i+(i+T)=i+(i+F)=i+(i+i)i+i*i的两棵语法树不同,故文法是二

2、义的。abc的两棵语法树不同,故文法是二义的。b9.(1)(2)该文法生成的语言是后缀表达式,或称为逆波兰式。10.(1)该文法生成的语言是“可并列或嵌套的配对的括号串”。(2)文法是二义的，因为句子“()()”有两棵不同的语法树。SSTS(S)SIIS(三)SIII11.可构造E+T*F的语法树如右所示：S(三)SIIS(三)SIIIE短语：E+T*FT*F故为文法的句型。E+T其中，T*F是直接短语和句柄T*F13.(1)最左推导最右推导(2)文法规则可有：(3)短语直接短语句柄S=ABSS=ABSS-ABSAaabbaa=aBS=ABAaA-aaaa=aSBBS=ABaaBfSBBb=a

3、BBS=ASBBaabb=abBS=ASBbaabb=abbS=ASbbaabb=abbAa=Abbaaaa=abbaa=abbaaaa14. (1)Gl:SCD(2)G2:SfiSolAC-*aCbIA-*OAlDaDbI(3) G3:S-0S0aSaa15. WaW上下文无关，W对应编程语言中的各种括号；amcndm上下文有关。16. (1)Gl:AfaAl(2)G2:AfaAlaB(3)G3:AfaAIbBIeC|BfbBbBfbBIeClCfCCl17,6、7和11题的文法等价。1%刻画语言的语法有文法、正则式和自动机等方式。第4章1 .构造下列正规式相应的DFA2 2)l(1010*

4、l(010)*l)*0由正规式构造NFA:状态01-S00Z1,412233034505664+Z由NFA构造状态子集：(错误)编号状态子集IoIi01-1S0220Z1,434+3Z41,42,505252,53,6663,63,4,Z1,47473,4,Z3，,Z1,4,089+83,5,Z3,Z1,4,6101191,4,02Zl,4,129+103,Z3,Z1,4104111,4,62,5,40132+123,66132,5,453,6,01415145616153,6,03,4,Z14741664171745014正确：由NFA构造状态子集:编号状态子集IoIi011S0220Z1,

5、4343Z41,42,505252,50,3,6660,3,60,3,4,Z1,474+70,3,4,Z0,3,5,Z0,1,4815+80,3,5,Z03,Z1,4,6910+90,3,Z03Z1,494101,4,62,4,50112112,4,550,3,612612561313641414450122150,1,425,Z0,1,41615+162,5,Z0,3,66以上即为所求的DFA(I)FA图略)(4)b(ab)*bb)*ab由所给出的正规式构造出对应的NFA:NFA的状态表格:状态IaIb-S001,321Z2030+Z由NFA转换成DFA:编号状态子集IaIbab-SSO00

6、021211,30,ZZ22OOz0,Z13212此即为所求之DFAo2.NFA的状态表格如口状态01-XZXYX,zx,zY利用表格构造状态子集:编号状态子集IOIlO1-SXZXOS+0Zx,zY12+1x,zx,zX,132YX,33X,X,zX4S+4X,Y,ZX,zX,43由以上表格构造相应的DFA:状态O1-SV,QU,QUZVZQVQ,U+ZZZ利用表格构造状态子集:编号状态子集IOIl01-1SV,QU,Q232V,QV,zU,Q433U,QVU,Q,Z56+4v,zZZ775VZ7+6U,Q,ZV,zU,Q,Z46+7ZZZ77O(b)已经为DFA,先将非终态与终态分开：(0

7、),(1,2,3,4,5),其中4的a输入后的状态不同，进行分割。(0),(4),(1,235)依次分割。(0),(4),(1,5),(2,3)(0),(4),(1,5),(2),(3)(至此已经不能分割。所以L5可视为同一个点。最小化的DFA为：7.根据题意构造相应的NFA。由于E和F状态由初态不能通过任何路径到达,所以在NFA中可以省略,并且引入新的终态Z：状态IaIb-SAQAABZBQI)DABQQDZZ构造状态子集得，编号状态子集IaIbab-1SAQ232AABZ243QQDZ35+4BZQD36+5DZAB276DAB277BQD36化简：(1,2,3,6,7),(4,5)(1,

8、6,7),(2,3),(4,5)(1),(6,7),(2,3),(4,5)化简成1、6、2、4四个状态：11 .构造相应的NFA:状态absAAAS-ZSA利用表格构造状态子集:编号状态子集IaIbab-+1ZSAA222AAS3+3ASASA32构造出的DFA如下:所以其正则式为(ab)a(aba)*12 .(1)改变为：单词:=1标识符d整数标识符：=1标识符d标识符整数:=d整数1表示字符，d表示数字。相应的DFA为：第5章1.(1)S-(T)(T,S)-(S,S)f(a,S)-(a,(T)-(a,(T,S)-*(a,(S,S)一(a,(a,S)(a,(a,a)S-(T)-*(T,S)(

9、S,S)一(T),S)-*(T,S),S)(T,S,S),S)f(S,S,S),S)-(T),S,S),S)(T,S),S,S),S)(S,S),S,S),S)一(a,S),S,S),S)(a,a),S,S),S)(a,a),A,S),S)一(a,a),(T),S)-(a,a),(三),S)-*(a,a),(a),S)(a,a),(a),a)(2)改写文法如下：S-*a(T)-*s,T,一,ST,递归子程序为：P(三)(if(SYM=三,a,)P(a);elseif(SYM=三,)P();elseif(SYM=三,(,)GetSymO；PCT)；match(,),)；)elseError();

10、P(T)P(s);P(,)；P(T,)if(SYM=*,*)(match(*,*);P；P(T,);)elseif(SYM=(*)*)return;elseerror();(3)First(三)=a()First(T)=a()First(T,)=,Follow(三)=W,)Follow(T)=)Follow(T,)=)Select(S-*a)=aSelect(S-*A)=Select(S-*(T)=(Select(T-*ST,)=a(Select(T,-,ST)=,Select(T,=)由于相同左部的Select集的交集为空，所以所改写的文法是LL(I)的。写出该文法的预测分析表:aA()#Sfa-A一TST,sr-*s,T一,ST一#OK(4)对符号串(a,a)#的分析过程步骤分析栈剩余输入串所用产生式1#S(a,a)#Sfcr)2#)T(a,a)#(匹配3#)Ta,a)#