《编译原理实践及应用》习题的参考答案.pdf

《《编译原理实践及应用》习题的参考答案.pdf》由会员分享，可在线阅读，更多相关《《编译原理实践及应用》习题的参考答案.pdf（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、附录部分习题参考答案第1章参考答案：1,2,3,4,5,6,7 解答：略！第2章参考答案：b 2,3：解答：略！4.解答：A：B：C：D：5.解答：用E表示v表达式，T表示v项，F表示 因子，上述文法可以写为:E T|E+TT t F|T*FF-(E)|i最左推导：E=E+T=E+T+T=T+T+T=F+T+T=i+T+T=i+F4-T=i+i+T=i+i+F=i+i+iE=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i最右推导：E=E+T=E+F=E+i=E+T+i=E+F+i=E+i+i=T+i+i=F+i+i=i+i+iE=E+T=E+T*F=E+T*i=

2、E+F*i=E+i*i=T4-i*i=F+i*i=i+i*ii+i+i和i+i*i的语法树如下图所示。i+i+i、i+i*i的语法树6.解答：(1)终结符号为：or,and,not,(,),true,false非终结符号为：b e xpr,b te rm,b f ac tor)开始符号为：b e xpr(2)句子not(true or false)的语法树为：bexprIbtermbfactorbexpr or btermIIbterm bfactorIIbfactor falseItrue7.解答：(1)把an b n d分成a“b n和d两部分，分别由两个非终结符号生成，因此，生成此文法的

3、产生式为：S A BA aA b|abB CB|8(2)令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S -aE|Ea|b S S|S b S|S S bE aEb E|b EaE|e(3)设文法开始符号为S,产生的w中满足l al W l b l W 2l al。因此，可想到S有如下的产生式(其 中B产 生1到2个b)：S *aS B S|B S aSB t b|b b(4)解法一：ST 奇数头 整数 奇数尾I 奇数头 奇数尾I(奇数尾 奇数尾-1|3|5|7|9 奇数头-2|4|6|8|奇数尾)整数一 整数 数字I 数

4、字 数字-0|奇数头解法二：文法 G=(S,A,B,C,D,0,1,2,3,4,5,6,7,8,9 ,P,S)S A B I BAA C I DB-1 1 3 1 51 71 9D-2I4I6 I8 IBCOID(5)文法 G=(N,S,N,M,D,0,1,234,5,6,7,8,9,S,P)S-NO|N5N-M D|sM-1|2|3|4|5|6|7|8|9D-D0|DM|e(6)GS：SaSa I bSb I cSc I a I b I c Is8.解答：(1)句子abab有如下两个不同的最左推导：S=aSbS=abS=abaSbS=ababS=ababS=aSbS=abSaSbS=abaS

5、bS=ababS=abab所以此文法是二义性的。(2)句子abab的两个相应的最右推导：S=aSbS=aSbaSbS=aSbaSb=aSbab=ababS=aSbS=aSb=abSaSb=abSab=abab(3)句子abab的两棵分析树：(a)(b)(4)此文法产生的语言是：在 a,b 上由相同个数的a 和 b 组成的字符串。9,10：解答：略！第 3 章习题解答:1.解答：(1)V (2)V (3)X (4)X (5)4(6)V2.分析有限自动机分为确定有限自动机和非确定有限自动机。确定有限自动机的确定性表现在映射3：Q X%q是单值函数，也就是说，对任何状态q WQ和输入字符串a d%,

6、8 (q,a)唯一确定下一个状态。显然，本题给出的是一个确定的有限自动机，它的状态转换图是C中的。它所接受的语言可以用正则表达式表示为0 0(0 1)*,表示的含义为由两个。开始的后跟任意个(包含。个)0或1组成的符号串的集合。2.解答：A:B:C:D:E:(4)3,4.解答：略！5.解答：6.解答：(1)(0 1 1)*0 1(2)(1|2|9)(0|1|2|9)*1 )(0 1 5)(3)(0 1 1)*(0 1 1)(0 1 1)*(4)1*1 1*0(0 1 1 0)*(1 怆)(5)a*b*c*z*(6)(0 1 1 0*1)*1(7)(0 0 1 1 1 )*(0 1 1 1 0)

7、(0 0 1 1 1)*(0 1 I I 0)(0 0 1 1 1)*)*(8)分析设S是符合要求的串，|S|=2k+l (k 20)。则 S-S 0|S2l,|S j=2k (k 0),|S j=2k (k 20)。且 是 0,J上的小，含有奇数个d和奇数个1。0,1 上的串，含有偶数个。和偶数个1。考虑有一个自动机4 接受S 那么自动机.如下:0111000:11和L(4)等价的正规式，即1为：(0 0 1 1)|(0 1 1 0)(0 0 1 1)*(0 1 1 1 0)*(0 1 1 1 0)(0 0|1 1)*类似的考虑有个自动机M接受S ,那么自动机M如下:=01|10和 L(M)

8、等价的正规式,即S,为:(00|11)|(01|10)(00|11)-(01 10).因此，S 为：(00 11)(01 10)(00 11).(01110)*(01110)(00111).01(00 11)I(01 10)(00 11)(01110)47.解答：(1)以0 开头并且以0 结尾的，由0 和 1 组成的符号串。(2)alas 0,1)*(3)由0 和 1组成的符号串，且从右边开始数第3 位为0。(4)含 3 个 1的由0 和 1组成的符号串。alaG 0,l+,且 a 中含有3 个 1 (5)包含偶数个0 和 1 的二进制串,即alaGO,l*,且 a 中有偶数个0 和 18.解

9、答：9.解答：(l)DFA M=(0,1,a,q,q),%，%，8)其中3定义如下：s(%O)=q,s q,1)=4)8(q(O)=q2 3(q/1)=%S(q2，O)=q,8(q?l)=q)状态转换图为：DFAM=(。1,q(),qi(q2,q3,q。，以 ，)，其中6定义如下:8(q0 O f8(qi(O)=q2S(q2.O)=q33，I f状态转换图为：-6(%,1)=%8 (q,.l)=q,8(q2-l q21 0.解答:(1)D F A M=(。,3(%O f3(q1 o)=q(S(q2.0)=q3状态转换图为i q0 qj q2 q3 q0 q3l-6),其中B定义如下:8(q0-

10、D=q2(q,q3B。，I f D F A M=(。1 ,qj,q0，q。，8),其中B定义如下:8(%)=%8(q0-1)=%状态转换图为：1 1 解答：(1)(al b)*a(al b)求 出N F A M:(2)(a)b)*a(al b)(al b)求NF AM：确 定化，得到D F AM：化简，在第步中求出的D F AM中没有等价状态，因此它已经是最小化的D F AM 了。1 2.解答：对应的N FA 为：增加状态X、Y,再确定化:II1 x,5 A,T,Y)()(A,T,Y)A,T,Y)B(B)B,T,Y)B,T,Y)T,Y T,Y ()得到的DFA为:最小化：该自动机已经是最小化的

11、D F A 了。13 .解答：Aa其中a代 表1元硬币,b代表5角硬币1 4.解答：正规式为：(0 11)*(0 0 10 1)化简：(0正*0(0 11)不确定的有穷自动机为：0确定化，并最小化得到:正规文法为：S-1 S I 0 AA-*0 B I 0 I IC I 1B-0 B 10 1 IC I 1C-1 S I 0 A15.解答：正规式：(d d*:l )d d*(.d d*l e),d代表a z的字母 NF A为：D F A为:16.解答：词法分析器对源程序采取非常局部的观点，因此象C语言的语句fi(a=f(x)中，词法分析器把f i 当作一个普通的标识符交给编译的后续阶段，而不会

12、把它看成是关键字 if 的拼写错。PASCAL语言要求作为实型常量的小数点后面必须有数字，如果程序中出现小数点后面没有数字情况，它由词法分析器报错。1 7.解答：此时编译器认为/*then partreturn qelse/*else part*/是程序的注释，因此它不可能再发现else前面的语法错误。分 析 这是注释用配对括号表示时的一个问题。注释是在词法分析时忽略的，而词法分析器对程序采取非常局部的观点。当进入第一个注释后，词法分析器忽略输入符号，一直到出现注释的右括号为止，由于第一个注释缺少右括号，所以词法分析器在读到第二个注释的右括号时，才认为第一个注释处理结束。为克服这个问题，后来的

13、语言一般都不用配对括号来表示注释。例如A da语言的注释始于双连字符(-)，随行的结束而终止。如果用Ada语言的注释格式，那么上面函数应写成long gcd(p,q)long p,q;(if(p%q=0)-then partreturn qelse-else partreturn gcd(q,p%q);1 8.解答：略!第 4 章习题解答:1,2,3,4解 答 略!5 .解答：(1)X (2)V6.解答：(D A：(2)A：7.解答：X (4)V (5)V (6)VB：C：B：C：(7)X (8)XD：E：D：E：(1)消除给定文法中的左递归，并提取公因子:b e x p r b t e r

14、m o r b t e r m )b t e r m b f h c t o r a n d b f a c t o r b f a c t o r n o t b f a c t o r|(b e x p r)|t r u e|f a l s e(2)用类C语言写出其递归分析程序：消除所给文法的左递归，得G：void bcxpr();void bfactor();(bterm();if(llokahead=not)then WHILE(lookahead=or)match(not);match(or);bfactor();bterm();)1else if(lookahead=()then)

15、match C();bexpr();void bterm();match(),);(bfactor();else if(lookahead=,true,)WHILEdookahead=and)then match(true)match(and);else if(lookahead=false)bfactor();then match(false*);)else error;)8.解答：)S f(L)|aL -S L L -,S L|实现预测分析器的不含递归调用的种有效方法是使用张分析表和个栈进行联合控制，下面构造预测分析表：根据文法G有：F i r st(S)=(,a)F o l l o w(

16、S)=F i r st(L)=(,a)F o l l o w(L)=F i r st(L)=,F o l l o w (Lf)=按以上结果，构造预测分析表M如下：),#)m留 结 符输入符号()a#sS T(L)S aLL-SUL-SL,UL T ,SL文法G是L L(1)的，因为它的L L(1)分析表不含多重定义入口。预测分析器对输入符号串(a,(a,a)做出的分析动作如下：步骤栈剩余输入串输出1#s(a,(a,a)#2#)L(a,(a,a)#S-(L)3#)La,(a,a)#4#)L Sa,(a,a)#L S U5#)L aa,(a,a)#S a6#)L,(a,a)#7#)US,(a,a)

17、#L。,SL8#)L S(a,a)#9#)L)L(a,a)#S-(L)1 0#)L)La,a)#1 1#)U)L Sa,a)#L 一 S U1 2#)L)L aa,a)#S a1 3#)L)Lf,a)#1 4#)L)LS,a)#L-,SL!1 5#)L)L Sa)#1 6#)L)Lraa)#S a1 7#)L)Lr)#1 8#)U)#L r 1 9#)L)#2 0#)#L-2 1#9.解答：各非终结符的F i r st集：F i r st(S)=F i r st(A)8 U F i r st(B)8)U e U b=a,b,eF i r st(A)=b U s=b,eF i r st(B)=e

18、)U a=a,sF i r st(C)=F i r st(A)e U F i r st(D)U F i r st(b)=a,b,cF i r st(D)=a U c=a,c各个候选式的F i r st集 为:F i r st(A B)=a,b,8 F i r st()=eF i r st(aD)=aF i r st(b)=bF i r st(bC)=bF i r st(b)=bF i r st(A D)=a,b,cF i r st(aS)=aF i r st(c)=c各非终结符的F o l l o w集的计算:F o l l o w(S)=#UF o l l o w(D)=#F o l l o

19、 w(A)=(F i r st(B)U F o l l o w(S)U F i r st(D)=a,#,cF o l l o w(B)=F o l l o w(S)=#F o l l o w(C)=F o l l o w(S)=#F o l l o w(D)=F o l l o w(B)U F o l l o w(C)=#)10.解答：(1)求 F i r st 和 F o l l o w 集F i r st(E)=F i r st(T)=(,a,b,A F i r st(E )=+,8 F i r st(T)=F i r st(F)=(,a,b,A F i r st(T)=(,a,b,A,s

20、)F i r st(F)=F i r st(P)=(,a,b,AF i r st(F)=*,&F i r st(P)=(,a,b,A)（计算顺序）F o l l o w(E)=#,)F o l l o w(E )=F o l l o w(E)=#,)F o l l o w(T)=F i r st(E )E U F o l l o w(T)=+U ),#=+,),#F o l l o w(T)=F o l l o w(T)=+,#F o l l o w(F)=F i r st(T)UF o l l o w(T)=(,a,b,A,+,),#F o l l o w(F )=F o l l o w(F

21、)=(,a,b,A,+,),#F o l l o w(P)=F i r st(F )s U F o l l o w(F)=*,(,a,b,A,+,),#(2)证明：V a.文法不含左递归；(1,7)(1)(使用的产生式)(1,4)(3)(3,4)(5)(5,6)b.每个非终结符的各个侯选式的F i r st集不相交;c.F i r st(E )n F o l l o w(E )=+,E n#,),=F i r st(T)n F o l l o w(T)=(,a,b,A,C +,)=F i r st(F )DF o l l o w(F )=*,E n ,a,(八,+,#=改造后的文法满足LL(1

22、)文法的三个条件，是LL(1)文法。(3)预测分析表如下所示。ab*+A()#EETEETEETEETEEE J+EE fE fTT-FTT 一 FTT-FTT 一 FTTT J Tr TT J gT J Tr TT-eT-8FF-PFrFPFF-PFFPFFF fF fFF fFFfFfPP aPbPAP T E)11.解答:(1)ma.文法不含左递归；b.S,A,B各候选式的First集不相交；c.First(A)AFollow(A)=a,8 A b=(PFirst(B)n Follow(B)=b志 C T=F=(E)=(E+T)=(E+F)=(E+i)=(T+i)=(T*F+i)语法树：

23、E图4.1句型(T*F+i)的语法树 短语：(T*F+i),T*F+i,T*F,i素短语：T*F,i最左素短语：T*F 由于E=E+T=E+T*F,故 E+T*F为该文法的句型短 语:T*F、E+T*F直接短语：T*F句柄：T*F13.解答：最左推导：S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)最右推导：S=(T)=(T,S)=(T,(T)=(T,(T,S)=(T,(T.a)=(T,(T,a)=(T,(a,a)=(S,(a,a)=(a,(a,a)文法中S 和 T 的 FirstVT和 LastVT集为:Fi

24、rstVT(S)=a,(FirstVT(T)=,a,()lastVT(S)=a,)lastVT(T)=,a,)文法GS的算符优先关系表：a()1#a(工1#c(2).写出所有的项目1.S 9 S3.S 9 aS6.S 9 bS9.S 9 c2.S 9 S 4.S-a S7.S f b S10.S c 5.S f aS,8.Sf bS(3).求项目集规范族每个项目集中的各个项目不冲突,则是LR(0)文法。(4).构造LR(O)分析表状态A C TI ONG OTOabc#SS0s2S5s31S1accS2s2s5s34S3r3r3r3r3S4riririris5s2s5s36s6r2r2r2r2

25、1 5.解答：(1)该文法的拓广文法G为0.S，-S1.S f Sab2.S-bR3.R f S4.R f a其 LR(0)项目集规范族和识别活前缀的DFA如下：ST S,S fS ab,S fbR=SS-ab)I2=Sb R,RT S,R a,S Sab,S一 bR=S SabL=SbRI5=RS，SS abI6=R-a-I7=SSab-显然，L 和 4 存在移进-归约冲突。求早和R 的 Follow集：Follow(S)=#Folio w(R)=Follow(S)=a,#在 4 中，出现的移进一归约冲突，且 Follow(R)Aa二 a ,不能用SLR(l)方法解决。因此，此文法不是SLR

26、(l)文法。(2)该文法的拓广文法G为0.S-S1.S-aSAB2.S f BA3,A f aA4.A f B5.B f b其 LR(0)项目集规范族和识别活前缀的DFA如下：I()=S-S,S aSAB,S BA,B-bL=S JSI2=B-b-=S-a SAB,S-aSAB,S一 BA,B一 bI4=S B A,A*aA,A-B,B bI5=SaS AB,A-aA,A-B,B bI=S 一 aSAB,B f b6【7=A-a-A,A aA,A B,B b%=A-B9=S-B A Lo=SaSAB-显然，上述状态中没有出现冲突。显然，该文法是LR(O)的文法，因此也是SLR(l)的。求各个非

27、终结符的Follow集，以便构造分析表：Follow(S-)=#Fol low(S)=a,b,#Follow(A)=a,b,#Follow(B)=a,b,#构造的SLR(1)分析表如下：actiongotoab#sAB0S3S2141acc2r5r5r53S3S2544S7S2985S7S2686S2107S7S21188r4r4r49r2r2r210rir1r111r3r3r31 6.解答：(1)构造其拓广文法G的产生式为0.S-S1.S-*A2.A f B A3.A f4.B f aB5.B f b构造其LR(O)项目集规范族和go to 函数(识别活前缀的D F A)如下:I。=S,-S

28、,#,S fA,#,ATB A,#,AT,#,B aB,a/b/#,a/b/#1=SI2=SA-,#I3=A-B-A,#AT-BA,#,A-,#,BaB,a/b/#,B-b,a/b/#I4=Bb-,a/b/#5=B a-B,a/b/#,B-aB,a/b/#,B b,a/b/#I6=ABA.,#=B-aB:a/b/#该文法的LR(1)项目集规范族中没有冲突，所以该文法是LR(1)文法。构造LR(1)分析表如下：状态actiongotoab#sAB0S5S4r31231acc2r13S5S4r3634r5r5r575S5S46r27r4r4r4以上分析表无多的定义入口，所以该文法为LR(1)文法。

29、(3)对于输入串abab,其分析过程如下：步骤状态栈输入动作(1)0abab*移进(2)0a5babf移进(3)0A5b4ab用B-b 归约(4)0u5B7ab#用B f aB进行归约(5)0B3ab*移进(6)OB3a5b#移进(7)OB3a5b4用B-b 归约(8)0B3&5B7用B-a睫行归约(9)0B3B3*用A-进行归约(10)0B3B3A6用A-BA进行归约(11)0B3A6用A-BA进行归约(12)0/2用S-A进行归约(13)0S1接受1 7.解答：(1)对于产生式SAaAb|BbBa来说First(AaAb)A First(BbBa)=a A b=0A,BWVN仅有一条候选式

30、。因此，这个文法是LL(1)的。(2)下面构造这个文法的识别活前缀的DFA。1。=ST S,S AaAb,S-BbBa,A，B-L=STSI2=S-A-aAbI3=S_BbBaI=S-Aa-Ab,A-I5=S-Bb Ba,B-I6=SAaAbI7=S-BbBaI8=S-AaAb%=S_BbBa-由于Follow(A)=Follow(B)=a,b,因此项目集I。中存在归约-归约冲突。在 I。状态下，当输入符号是a 或是b 时，不知用AT还是BT进行归约。故此文法不是SLR的。但是，此文法时LR(1)的。1 8.解答:该文法的拓广文法G，为0.STS1.S 一(SR2.S-33.R 一,SR4.R

31、-)构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:10=S-S,S f(S R,S f aL=SJS-I，=S(SR,S(SR,S fa l3=S-a-I4=S-(S-R,R fS R,Rf)I5=S(S R)6=3 一)I7=R fS R,S(SR,S f aI8=R一,S-R,R、SR,R一”9=RT,SR每个LR(0)项目集中没有冲突。因此，此文法是LR(0)文法。其分析表如下:状态actiongotoa()9*sR0S3S211acc2S3S243r2r2r2r2r24S6S755r1r1r1r1r16而r5r5r5r57S2S288S6S799r4r4r4r4

32、r41 9.解答：略!第5章习题解答:(3)为 D 引入一个综合属性h,用来记录D 中含id 的个数:1,2,3 解答:略！4.解答：(1)设 S,L,B 的值的属性用val表示：S-S printf(S.val)S-U.L2 S.val:=L,.Val+L2.val/2L2-|ens,hS*L S.val:=L.valLL B L.val:=L1.val*2+B.vaLL.length=LLlengthH-1 L B L.val:=B.val),L.length:=2 B0 B.val:=OB-1 B.val:=l)(2)为 S,L 引入属性h,用来记录配对的括号个数：S-S printf(

33、S.h)S-a S.h:=OS-(L)S.h:=S.h+lLL,S S.h:=L(】).h+S.hLS L.h:=S.h)P一 Dprintf(D.h)D-D1;)D.h:=D.h+D2.hD-id:TD.h:=1D*proc id;D;SD.h:=D.h+l5.解答：输入串为bcccaadadadb时的语法树为:/|b Q b/c R/I、Q a d/c R/I、Q a d/c R/I、Q a d采用修剪语法树的方法，按句柄方式自下而上归约该语法树，在归约时调用相应的语义规则，由此得到最终的潮译结果为：34242421.6.解答：(a+b)+(c+d/(e-3)*87.解答：(1)ab-c+

34、*(2)A not C D not or not or(3)abcde/+*+(4)A B and C not D or or(5)a-bc-d+*+(6)A B or C D not E and or and8 .解答：三元式四元式(+,a,b)1.(+,a,b,T)(-1,-)2.(-,T,T)(+,c,d)3.(+,c,d,T )(*,2,3)4.(*,T T ,T)(+,a,b)5.(+,a,b,T)(+,C,5)6.(+,T,c,T.)(-,4,6)7.(-,T T ,T.)9.解答：四元式代码为：1.(jnz,A,x)2.(j,一,3)3.(jnz,B,5)4.(j，_，_，y)5

35、.(jnz,C,y)6.(j,_9 _9 7)7.(jnz,D,y)8.(j,x)1 0 .解答：1 1 .解答：(1)四元式序列为:1.(j,A,C,3)2.(j,-,-,1 4)8.(:=,T,-,C)9.0,-r,1 4)3.(j(2)四元式序列为：l.(j0,x,0,3)7.(j,_，1 2)2.(j，_，8)8.(+,x,2,T J3.(j,y,0,5)9.(:=,T2，x)4.(j,_，,8)1 0.(+,y：3,T3)5.(+,x,y,T)“.(：=，T3,y)6.(:=,T ,z)1 2.(3)四元式序列为：0.(+,A,3,t O)4.(:=,t 3,B)1.(:=,t O

36、.t l)5.(j,i,t l,1 5)1 4.7.(+,a,b,t 3 )1 5.1 2.解答：略!第6章习题解答:1,2,3,4,5 解答：略！6.解答：本题考查的要点是掌握栈式动态存储分配策略中运行的布局，填充过程活动记录d i s p l a y 表的内容。运行栈的布局遵循“先进后出”原则，即一个过程调用另一个过程时，被调用过程则在调用过程的栈顶构筑自己的数据区，形成自己的活动记录，包括自己的 d i s p l a y 表。而d i s p l a y 表内容的项数与过程的嵌套层次有关，一般比过程的嵌套层数大1。(1)demo A此时的运行栈只有主程序d e m o 和过程A的 2个

37、数据区，过程A只引用主程序d e m o 全局数据和其自身的局部数据，因此其d i s p l a y 表内容有2项，即主程序数据区首址和过程A的主程序数据区首址。过程B的数据区SP2-过村A的SPOSP3过程B的数据区(I)dento AfSP3SPISPOSP2SPISPOISPISPOdemo士程A的isplay Ha 过程display 表但 程B的_ display 代(3)demo A B(2)demo-ATB此时的运行栈只有主程序d e m o、过程A和过程B的 3个数据区，过程B嵌套定义在过程 A中，要引用主程序d e m o 全局数据、过程A的数据和其自身的局部数据，因此其d

38、 i s p l a y表内容有3 项，即主程序数据区首址、过程A的主程序数据区首址和过程B本身的数据区首t l l：o(3)demo TATB B此时的运行栈包括主程序d e m o、过程A和 2个过程B的实例的4个数据区，过程B要引用的数据区还是3个：主程序d e m o 全局数据、过程A的数据和当前活跃过程B的局部数据(栈顶数据项)，因此其d i s p l a y 表内容还是有3 项，即主程序数据区首址、过程A的主程序数据区首址和当前活跃过程B本身的数据区首址。(4)d e m o A B B-A此时的运行栈包括主程序d e m o、2个过程A和 2个过程B的实例的5 个数据区，但过程

39、A只引用主程序d e m o 全局数据和其自身的局部数据，因此其d i s p l a y 表内容只有2项，即主程序数据区首址和过程A的主程序数据区首址。各个运行时刻运行栈的布局和使用的d is p la y 表如图。第7章习题解答:1 .解答：A：局部 B：全局 C：代码外提D：削减运算强度 E：删除归纳变量2 ,3.解答：略！4.解答：程序流图如下:回边为：5 .解答：各结点n的必经结点集D(n)如下：。(%)=%D(n J=%,n JD(n J=n0,n JD(n3)=n0，n(,n2，n3D(%)=%,%,为 D(n5)=n0,n1,n2,n JD(n6)=n0，n|,n2,%n JD

40、(n )=n ,n n n n n )回边和循环：因 为 D(n J=n 0,n%,且 巴 n?,所 以%一*4 为一条回边。根据它求出的循环匕=%,%。因为DI%)=%,n*%,且唯一*、，所 以%-、为条回边。根据这条回边，求出的循环 L2=n6,nrn5,ny n4,n j6.解答：(1)首先划分基本块并画出其程序流图，其中有三个基本块耳，B2,B3,有一条回边B,-B,相应的循环是 B,。B,(2)强度削弱：在B,中A和B为乘法运算，可以削弱它们的运算强度，变乘法为加法。优化结果如下图。(3)删除归纳变量：在循环中，i是循环的基本归纳变量，A,B是同族的归纳变量，且有线性关系，变换循环

41、控制条件，流图如下。(4)代码外提：由于删除归纳变量后有R:=K*10。是循环不变运算，可以提到前置结点B中。7.解答:B,8.解答:(l)DAG 如下:(2)优化后的三地址代码为：T3：=S-RT，:=S+RA:=5*T，4B:=T+T3 49.解答：(本题中假设采用字节地址，两个字节作为一个机器字。)(1)程序的中间代码如下：BjreadN /*置初值*/i:=2B,:ifiN gotoB4/*第一个 for语句*/B：=iT,:=addr(A)/*数组A 的基地址*/L :=2*工TJTJ:=truei:=i+1goto B2B:i:=24T3:=N*0.5T:=T +1 /*T 是对T

42、 的值取整*/B5：ifi T3gotoB12B6：T4：=i:=addr(A)T-=2*T,4 4ifT5T4 goto B8B7：gotoBHB 8o:Jj:=2*iB9：ifj N goto Bu/*第三个 for 语句*/BH jT7:=addr(A)T：=2*T6 6T7T6=falsej：=j+igoto B9goto B5(2)根据上述中间代码,可划分成基本块4,B,B3,B4,B.,B6,B7,Bg,B9,B10,B 其程序流图如下：II。考查上面的程序流图：D(B.)=BI,B7,B J,又 有BB,因 此BB,是一条回边。根据它找到的循环L,=B2,B3。D(B|0)=Br

43、B2,B4,B5,B6,B9，B1O,又有 B p-B g,所以 B10 B9 是一条回边。根据这条回边找到循环L2=B9,B1O D(BN)=,又有 B u-B、，因此 B u-B、是一条回边。根据这条回边找到循环 L3=BH,B9,B1 0,B8,B7,B6,B5)(3)进行代码外提把在循环中不随循环变化的操作提到循环外的前置结点中，且在基本块中作复写传播和删除无用赋值。结果程序流图如图1。(4)进行强度削弱和删除归纳变量后，其程序流图如图2。:=addrt A)si:=2*i口 ;=2 Nif si n goto Bj*lsil：truesi:sj 2goto BI 1 :N*H Tj

44、r T T12goto Bn图 2 强度削弱和删除归纳变量后的流图值后的流图1 0.解答：略!第8章习题解答:。目标代码如下:1,2.解答：田各！3.解答：设所有变量均用名字表示地址，寄存器名字用R。、和 R2表(l)M OVx,#1(5)MOV Ro，b(2)MOV x,yADD R。，c(3)ADD x,#1MOV a(4)MOV R,bDIV R j R()MUL R1,cMOV R2，eADD R j aADD R2，fMOV x,RJMUL R2，dSUB R j R2MOV x,R|4.解答：MOV R。，ASUBR。，BMOV R j CADDRj,DMOVS,RMOV R j ESUBFDIV 1V RoMULSMOVV,R15.解答：(l)M OVRo，b(3)MOV R(),#0MUL Ro，cSUB R0,bADD R(),aMUL R0,aMOV x,R()MOV R/(2)MOV Ro，aADD R eDIV R0,bMOV R?,cSUB R(),cSUB R：R1DIV R0，dADD R(),R2MOV x,R0MOV x,R06.解答：略!