编译作业参考答案.docx
1. L(G)=abc2. 1.(GN)是无符号整数。3. G3:E-D+EID-EIDD0l234567894. 1.(GZl)=anbnn>05. (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+T>T+T=>F+T=i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iEzKE+TI×z×TT*FIIIFFi=i+(F+T)=i+(i+T)=i+(i+F)=i+(i+i)i+i*i的两棵语法树不同,故文法是二义的。abc的两棵语法树不同,故文法是二义的。b9.(1)(2)该文法生成的语言是后缀表达式,或称为逆波兰式。10.(1)该文法生成的语言是“可并列或嵌套的配对的括号串”。(2)文法是二义的，因为句子“()()”有两棵不同的语法树。SSTS(S)SIIS(三)SIII11.可构造E+T*F的语法树如右所示：S(三)SII£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=>ASBBaabb=>abBS=>ASBbaabb=>abbS=>ASbbaabb=>abbAa=>Abbaaaa=>abbaa=abbaaaa14. (1)Gl:SCD(2)G2:SfiSolAC-*aCbIA-*OAlDaDbI(3) G3:S-0S0aSaa15. WaW上下文无关，W对应编程语言中的各种括号；a"mcndm上下文有关。16. (1)Gl:AfaAl£(2)G2:AfaAlaB(3)G3:AfaAIbBIeC|£BfbBbBfbBIeCl£CfCCl17,6、7和11题的文法等价。1%刻画语言的语法有文法、正则式和自动机等方式。第4章1 .构造下列正规式相应的DFA2 2)l(1010*l(010)*l)*0由正规式构造NFA:状态01-S00Z1,412233034505664+Z由NFA构造状态子集：(错误)编号状态子集IoIi01-1S0220Z1,434+3Z41,42,505252,53,6663,63,4,Z1,474÷73,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,434÷3Z41,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-SSO00021211,30,ZZ22OO÷z0,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),(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)DABQQDZ÷Z构造状态子集得，编号状态子集IaIbab-1SAQ232AABZ243QQDZ35+4BZQD36+5DZAB276DAB277BQD36化简：(1,2,3,6,7),(4,5)(1,6,7),(2,3),(4,5)(1),(6,7),(2,3),(4,5)化简成1、6、2、4四个状态：11 .构造相应的NFA:状态ab÷sAAAS-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)-*(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();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)#
