《编译作业参考答案.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)#