编译作业参考答案.docx

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

1、1. 1(G)=abc2. 1(GN)是无符号整数。3. G3:E-D+EID-EIDD01234567894. 1(GZ1)=anbnn05. (1)G5:N-*DNIEE02468D-*E13579(2)G5:NABEBDBEA-*123456789Efo12468DAO6.(1)E=TE=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的两棵语法树不同,故文法是二义的。abc的两棵语

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

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

4、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,02Z1,4,129+103,Z3,Z1,4104111,4,62,5,40132+123,66132,5,453,6,01415145616153,6,03,4,Z14741664171745014正确：由NFA构造状态子集:编号状态子集IoIi011S0220Z1,4343Z41,42

5、,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-SSO00021211,30,

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

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

8、,(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)(S,S)一(T),S

9、)-*(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),S)-*(a,a),(a),S)(a,a),(a),a)(2)改写文法如下：S-*a(T)-*s,T,一,ST,递归子程序为：P(S)(if(SYM=,a,)P(a);e1seif(SYM=,)P();e1seif(SYM=,(,)GetSymO；PCT)；match(,),)；)e1seError();P(T)P(s);P(,)

10、；P(T,)if(SYM=*,*)(match(*,*);P；P(T,);)e1seif(SYM=(*)*)return;e1seerror();(3)First(S)=a()First(T)=a()First(T,)=,Fo11ow(S)=W,)Fo11ow(T)=)Fo11ow(T,)=)Se1ect(S-*a)=aSe1ect(S-*A)=Se1ect(S-*(T)=(Se1ect(T-*ST,)=a(Se1ect(T,-,ST)=,Se1ect(T,=)由于相同左部的Se1ect集的交集为空，所以所改写的文法是11(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)#TfST4#)T