《编译作业参考答案.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()#S
11、fa-A一TST,sr-*s,T一,ST一#OK(4)对符号串(a,a)#的分析过程步骤分析栈剩余输入串所用产生式1#S(a,a)#Sfcr)2#)T(a,a)#(匹配3#)Ta,a)#TfST4#)TSa,a)#Sfa5ft)T,aa,a)#a匹配6#)T,a)#T,-*,ST,7#)TS,a)#,匹配8#)TSa)#Sfa9#)Taa)#a匹配10#)T)#Tfe11#)#)匹配12接受所以(a,a)#是G的句子。6 .(2)B有相同左因子，所以该文法不是LL(I)的。B-*D(b)改写为BfDBBi此时最终的文法为：SABSBaBDB,BiDd而此文法不是LL(I)的。(4)因为文法具有
12、左通归，所以不是LL(I)的。改写该文法：S-i(E)EfSE，E-+SE-SEI计算新文法的First集和Follow集。VFirstFollowSi(#+-Ei()E,+-)计算SeIeCt集：Select(S-i)=iSelect(S-*(E)=(Select(E-*SE,)=i(Select(E,SE,)=+Select(E,-SE)=-Select(E,-*)=)由此可以看出此文法是LL(I)的。构造相应的递归下降识别器：P(三)(if(SYM=i)match(i);elseif(SYM=()(match(*();P(E);match(*);)P(E)P(三);P(E);P(E,)i
13、f(SYM=+)(match(+);P(三);P(E,);elseif(SYM=*-*)(match(一);P(三);P(E,);elseif(SYM=*)*)returnelseerror();7 .消除了左递归，提取了左公因子并不一定是LL(I)的。(1)改写文法得，A-*baBBfbaBbbbba消除公共左因子得：A-*baBBB,aB,aBbbb求其First集和Follow集：VFirstFollowAb#Bab#bBab#b计算SeIeCt集：Select(AbaB)=bSelect(A=#Select(BbB,=bSelect(B-*a=aSelect(B,aBbb=aSelec
14、t(B,b=b由此可见所改写的文法是LL(I)的。(3)改写文法得：SAaIbAbabA,A,-aabA,求以上状态的First集和Follow集:VFirstFollowSbAbaA,aa求每个产生式的Select集合得：Select(S-Aa)=bSelect(Sb)=b由此可见，此文法不是LL(I)的。(5)可以看出A有公共左因子。消去得，S今AbIaaA-aA,A,(Al)此时，已经消除了左递归，并且没有了公共左因子。但是Select(S-Ab)=aSelcect(Saa)=a显然文法不是LL(I)的。第1题(1)FIRSTVT-LASTVT表非终结符FIRSTVT集LASTVT集Sa
15、(a)Ta(,)a(,)(2)算符优先关系表aA(),a(优先关系唯一，所以是一个算符优先文法。(3)算符优先函数表：4442455352aa()检验发现，存在优先函数。(4)对输入串(a,a)#的算符优先分析过程为栈(STACK)当前输入字符(CHAR)剩余输入串(INPUT_STRING)动作(ACTION)#(a,a)#移进#(a,a)#移进#(a,a)#归约:Sa#(S9a)#移进#(S,a)#移进#(S,a)#归约:Sa#(S,S)#归约:TTT,S#(T)#移进#(T)#归约:S(T)#S#对输入串(a,(a,a)#的算符优先分析过程为:栈f(SYN(top)关系剩余序列动作产生式
16、#0a,(a,a)#移进，读#(2(a,a)#归约，不该Sa#(2(a,a)#移进，读#(,4a,a)#移进，读#(,(2a)#规约，不读Sa#(,(2a)#移进，读#(，(,4)#日约，不读Sa#(,(,4)#归约，不该,s#(,(2Z)#移进，读#(,()4#规约，不读S(T)#(,4#规约，不读,s#(2#移进，读#0#S4规约，OK不读S弓第2题文法:SaA(T),ss(a,a)的最右推导过程为：S=(T)=b(T,S)=(T,a)=t(S,a)=(a,a)(a,(a,a)的最右推导过程为：S=b(T)=(T,S)I(T,(T)=b(T,(T,S)T(T,(T,a)T(T,(S,a)=
17、(T,(a,a)=(S,(a,a)三5(a,(a,a)对输入串(a,a)#的规范归约过程为:栈(StaCk)剩余输入串(inputleft)动作(action)#(a,a)#移进#(a,a)#移进#(a,a)#归约by:Sa#(S#(T,a)#,a)#归约by:TTS移进#(T,a)#移进#(T,a归约by:Sa#(T,S归约by:TTT,S#(T移进#(T)归约by:S(T)#S#对输入串(a,(a,a)#的规范归约过程为:栈剩余输入串动作#(a,(a,a)#移进#(a,(a,a)#移进#(a,(a,a)#归约by:Sa#(S,(a,a)#归约byTS#(T,(a,a)#移进#(T,(a,a
18、)#移进#(T,(a,a)#移进#(T,(a,a)#归约by:Sa#(T,(S,a)#归约byrTS#(T,(T,a)#移进#(T,(T,a)#移进#(T,(T,a)#归约by:Sa#(T,(T,S)#归约by:TTS#(T,(T)#移进#(T,(T)#归约by:S(T)#(T,(S)#归约by:TT,S#(T)#移进#(T)#归约by:S(T)#s#第七章LR分析法3.(1)构造增广文法，SS文法的LR(O)项目有：3. S.AS7. Sb.11. A.a4. SAS8. A.SA12. Aa.1.S,.S2.SS.5.SAS.6.S.b9.AS.A10.ASA.(2)所产生的NFA略。由规
19、则构造所需的DFA:则LR(O)项目集规范族为:C=10,11,12,13,14,15,16,17(3)可以看到II,16,17存在着移进一归约的冲突。冲突是不能用SLR(I)的方法来解决。比如16:对于状态SAS.和S6.bFonOW(三)=礼a,b与b相交不为空。所以以上文法不是SLR(I)文法。(4)为验证该文法是否为LALR或LR(I)的，构造LR项目集。对于15,产生了移进一归约矛盾，所以这个文法不是LR(I)文法。于是也不是LALR文法。10.(1)对于该文法构造LR(O)项目规范族:s,.sII:S,S.13:A-a.Ba15:Bb.Ab16:A-aB.aS.AB12:SA.BB
20、.bAbA今.aBa17:A-aBa.A-.aBaB.bAbB.A-.18:B-bA.bA-.B.14:SAB.19:BbAb.可见存在着移进一归约冲突，这个文法不是LR(O)文法。考虑用SLR(I)来解决问题:构造SLR(I)分析表，发现该文法是SLR(I)文法。状态ACTIONGOTOabSAB0s3r3r3121acc2r5S5r543r5S5r564rl5S3r3r386S77r2r28S99r4r4(3)先构造该文法的LR(O)项目集规范总10:S,.SII:S,S.S.Ad12:Sa.AdS-.eBdSa.BrS-.aBrA-.aS-.eArB-.a该文法存在着归约-归约冲突，所以
21、7对于状态16:Aa.B-a.Follow（八）=drFollow(B)=d两个集合相交不为空，所以该文法也构造该文法的LR(I)文法可得该文法,10:S,9S,#12:Sa.Ad,#S.aAd,#Sa.Br,#S.eBd,#A.a,dS-.aBr,#B-.a,rS.eAr,#13:Se.Bd,#II:S,S.,ftSe.Ar,B-.a,dA-.a,r&13: Se.Bd15:SaB.r19:SaAd.B.a16:Aa.I10rSaBr.Se.ArBa.11kSeBd.A.a17:SeB.dI12rSeAr.14: SaAd18:SeA.rF是LR(0)文法。r)不是SLR(I)文法。是LR的
22、。15: SaA.d,#110:SlaAd.小16: SaB.r,#Ill:SaBr.,#17: Aa.,d112:SeBd.,#Bb.,r113:SeAr.,#18: SeB.d,#18:SeA.r,#19:B-a.,dA-a.,r可以看到存在着移进一归约的冲突，不是LR(O)文法。在IO中FonoW（八）与b相交不为空。所以也不为SLR(D文法。构造该文法的LR(I)项目集规范族：10:S-.A,#14:B-A.b,#19:B-a.,bA-.aB,#15:B-a.,#A-a.B1bA-.，#A-a.B1bB-.Ab,bII:S-A.,#B-.Ab,bB-.a,b12:A-a.B,#B-.a
23、,bA-.aB,bB-.Ab,#,B-.aB,bA-,bB-.a,#A-.aB,bI10:B-AB.,bA-.aB,b16:B-Ab.,#A-.,b17:A-aB.,b13:A-aB.,#18:B-A.b,b其中存在冲突，所以文法也不是LR(I)文法。构造LR(I)分析表(略)。(5)构造LR(O)的分析表：10: S.A A.aB A- .11: S-A.12: S-aB B-. Ab B-. a A-. aB A-.13: S-aB.14: B-A.b15: B-a.A-a B B-.Ab B-. a A-. aB A-.15.构造该文法的LR(O)项目集规范集：10:S,.S12:S,a
24、.15:S(T.)19:TT,S.S.a13:S.TT.,SS.14:S(.T)16:s.ST.T,S17:S(T).II:S,S.T.S18:TT,.SS-.aS-.aS.S.S6S(T)构造LR(O)分析表:状态ACTIONGOTOaA()9#ST0S2S3S411acc2r2r2r2r2r2r23r3r3r3r3r3r34S2S3S4655S8S76r6r6r6r6r6r67r4r4r4r4r4r48S2S3S499r5r5r5r5r5r5构造LR规范集族：10: S,.S,#12:S,a.,S-.a,n13:S.,#S-.A,#14:S(.T),S-.(T),#T.T,S,)11: S
25、,-S.,#T.S,)S-.a)S.,)S.(T),)113:S-XT.),)I14:S-(T).,)T-T.,S,)构造LR(I)分析表：第第15: S(T.),#TT.,S,)16: TS.,)17: S6(T)18: TT,.S,)S-.a,)S-.,)S今,)19:TT,S.,)I10:S-a.)IlkS-.,)I12:S-X.T),)T-.T,S,)-.s,)S-.a,)S-.A,s-.(T),)状态ACTIONGOTOa(9)#ST0S2S3S411acc2r23r34SlOSllS12655S8S76r67r48SlOSllS1299r510r211r312SlOSllS1213
26、13S8S1414R4参看LR(I)的规范集合，可以看到12和110、13和11h14和U2、15和H3、17和114是同心集。依此构造LALR(I)集合：状态ACTIONGOTOa()#ST0S2S3S411acc210r2r22311r3r3r3412SlOSllS1265513S8S76r6r6714r4r4r48SlOSllS1299r5r5分析对输入符号为(a#和(a,a#的LR(O),LR(1),LALR(I)分析过程:(a#的LR(O)分析过程，步骤状态栈符号栈输入串ACTIONGOTO10#(a#S4204#(a#S23042#(ar264042#(Sr655045#(TUER
27、ROR(a,a#的LR(O)分析过程:步骤状态栈符号栈输入串ACTIONGOTO10(a,a#S4204#(a,a#S23042#(a,a#r264046#(S,a#r655045#(TS860458#(T,A#S2704582#(T,ar29804589#(T,S#r559045#(T#ERROR(a#的LR(I)分析过程:步骤状态栈符号栈输入串ACTIONGOTO10(a#S4204#(A#SlO30410#(a#ERROR(a,a#的LR分析过程:步骤状态栈符号栈输入串ACTIONGOTO10(a,a#S4204#(a,a#SlO30410#(a,a#r264046#(S,a#r6550
28、45#(T,a#S860458#(T,a#SlO7045810#(T,aa#ERROR(a#的LALR分析过程:步骤状态栈符号栈输入串ACTIONGOTO10#(a#S4204#(A#SlO30410#(a#r264046#(SERROR(a,a#的LALR(I)分析过程:步骤状态栈符号栈输入串ACTIONGOTO10n(a,a#S4204#(a,a#SlO30410#(a,a#r264046#(Sa#r6513504513#(TS860458138#(T,a#SlO704513810#(T,aa#r2980451389#(T,S#ERROR(3)LR(I)分析表发现问题最早，LALR次之，L
29、R(O)最慢，发现位置相同。第8章8.1 (1)a*(-b+c)解：abc+*(为单目减)(2) -1AV-1(CV-D)解：AICD1V-V8.2 先将式子用树形表示出来：X+三元式表示：间接三元式表示:1(+,a,b)2(-,5(+,a,b)6(+,三元式表1 (+,a,b)2 (-,(1),-)3(+,c,d)4(,(2),(3)5(+,(1),c)6(-,(4),(5)四元式表示:1(+,a,b,tl)3(+,c,d,t3)5(+,a,b,t5)7(-,t4,t6,t7)(1),-)3(+,c,d)4(,(2),(3)(5),c)7(-(4),(6)间接三元式1：12：23：34：45
30、：56: 17: 62(一,tl,-t2)4(,t2,t3,t4)6(+,t5,c,t6)第9章1.分析所给出的代码的运行结果：OPqrStUVWfor循环是将buf数组依次赋值a-z,a-fwhile循环是在从buf+12开始的数组中找，X，如果没找到就打印当前字符。3 .答：运行时的存储区常分为：目标区、静态数据区、栈区和堆区。代码区用于存放目标代码，静态数据区用于存放编译时能确定所占空间的数据，堆栈区用于可变数据以及管理过程中的控制信息。全局变量在程序装入时就分配空间，而局部变量则在进入过程或分程序时进行分配空间。4 .答：静态绑定是在编译时就指定其相对位置。动态绑定是在运行过程中指定相
31、对位置。第10章6.(1)传值：a的输出值为2(2)传地址：a的输出值为8第11章ILl答：所谓代码优化即对代码进行等价变换，使得变换后的代码与变换前代码运行结果相同，而运行速度加快或占用存储空间少，或两者兼有。进行优化的基础是中间或目标代码生成，以及基本块的识别、控制流分析和数据流分析。2答：根据不同的阶段，分为中间代码优化和目标代码的优化。根据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化。3答：最常用的代码优化技术有：(1)删除多余运算(2)代码外提(3)强度削弱(4)变换循环控制条件(5)合并已知量和复写传播(6)删除无用赋值4答：(1) 1-4为第1块，5-8为第2块，9-12为第3块，13句为第4块，14-22为第5块,23-30句为第6块。流图如下：Bl(2) (14)和(16)都有4*i的运算，将(16)换成t7=t6(17)和(20)都有4*j的运算，将(20)换成tl=t8(23)和(25)都有4*i的运算，将(25)换成tl
