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

'附录部分习题参考答案第1章参考答案：1，2，3，4，5，6，7解答：略！第2章参考答案：1，2，3：解答：略！4.解答： A：① B：③ C：① D：② 5.解答：用E表示<表达式>，T表示<项>，F表示<因子>，上述文法可以写为：E→T|E+TT→F|T*FF→(E)|i最左推导：E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+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=>E+F*i=>E+i*i=>T+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} 非终结符号为：{bexpr,bterm,bfactor}开始符号为：bexpr(2)句子not(trueorfalse)的语法树为：7.解答：(1)把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S→ABA→aAb|abB→cB|e(2)令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S→aE|Ea|bSS|SbS|SSbE→aEbE|bEaE|e(3)设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式（其中B产生1到2个b）：S→aSBS|BSaSB→b|bb(4)解法一：S→〈奇数头〉〈整数〉〈奇数尾〉     |〈奇数头〉〈奇数尾〉     |〈奇数尾〉 〈奇数尾〉→1|3|5|7|9 〈奇数头〉→2|4|6|8|〈奇数尾〉 〈整数〉→〈整数〉〈数字〉|〈数字〉 〈数字〉→0|〈奇数头〉解法二：文法G=({S,A,B,C,D},{0,1,2,3,4,5,6,7,8,9},P,S)S→AB|BA→AC|DB→1|3|5|7|9D→2|4|6|8|B C→0|D(5)文法G=({N,S,N,M,D},{0,1,2,3,4,5,6,7,8,9},S,P)S→N0|N5N→MD|eM→1|2|3|4|5|6|7|8|9D→D0|DM|e(6)G[S]：S→aSa|bSb|cSc|a|b|c|e8.解答：(1)句子abab有如下两个不同的最左推导：S=>aSbS=>abS=>abaSbS=>ababS=>abab  S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab  所以此文法是二义性的。(2)句子abab的两个相应的最右推导：  S=>aSbS=>aSbaSbS=>aSbaSb=>aSbab=>abab  S=>aSbS=>aSb=>abSaSb=>abSab=>abab(3)句子abab的两棵分析树：(a)(b)(4)此文法产生的语言是：在{a，b}上由相同个数的a和b组成的字符串。9，10：解答：略！第3章习题解答：1.解答：(1)  √  (2) √  (3)  ×(4)  ×  (5) √  (6)√2.[分析]   有限自动机分为确定有限自动机和非确定有限自动机。确定有限自动机的确定性表现在映射d：Q×VT-->q是单值函数，也就是说，对任何状态q∈Q和输入字符串a∈VT，d(q,a)唯一确定下一个状态。显然，本题给出的是一个确定的有限自动机，它的状态转换图是C中的②。    它所接受的语言可以用正则表达式表示为00(0|1)*，表示的含义为由两个0开始的后跟任意个（包含0个）0或1组成的符号串的集合。2.解答：A:④  B:③  C:②  D:②  E:④3，4．解答：略！5．解答： 6．解答：(1)(0|1)*01(2)((1|2|…|9)(0|1|2|…|9)*|e)(0|5)(3)(0|1)*(011)(0|1)*(4)1*|1*0(0|10)*(1|e)(5)a*b*c*…z*(6)(0|10*1)*1(7)(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*(8)[分析]设S是符合要求的串，|S|=2k+1(k≥0）。则S→S10|S21，|S1|=2k(k>0），|S2|=2k(k≥0）。且S1是{0,1}上的串，含有奇数个0和奇数个1。 S2是{0,1}上的串，含有偶数个0和偶数个1。考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规式，即S1为：((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规式，即S2为：((00|11)|(01|10)(00|11)*(01|10))*因此，S为：((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0|((00|11)|(01|10)(00|11)*(01|10))*17．解答：(1) 以0开头并且以0结尾的，由0和1组成的符号串。(2) {a|a∈{0,1}*}(3) 由0和1组成的符号串，且从右边开始数第3位为0。(4) 含3个1的由0和1组成的符号串。{a|a∈{0,1}+，且a中含有3个1}(5) 包含偶数个0和1的二进制串，即{a|a∈{0,1}*，且a中有偶数个0和1}8.解答： 01Q0*Q1Q2Q3Q2Q3Q0Q1Q1Q0Q3Q29.解答：(1)DFA M=({0，1}，{q0，q1，q2}，q0，{q2}，d)其中d定义如下:d(q0，0)=q1    d(q0，1)=q0d(q1，0)=q2    d(q1，1)=q0d(q2，0)=q2    d(q2，1)=q0状态转换图为：(2)正规式:1*01*01*01*DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，d)，其中d定义如下：d(q0，0)=q1    d(q0，1)=q0d(q1，0)=q2    d(q1，1)=q1d(q2，0)=q3    d(q2，1)=q2d(q3，1)=q3    状态转换图为：10.解答：(1) DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，d)，其中d定义如下：d(q0，0)=q1    d(q0，1)=q2d(q1，0)=q1    d(q1，1)=q3d(q2，0)=q3    d(q2，1)=q1状态转换图为： (2)DFA M=({0，1}，{q0}，q0，{q0}，d)，其中d定义如下:d(q0，0)=q0    d(q0，1)=q0状态转换图为：11解答：(1)(a|b)*a(a|b)①求出NFAM:②确定化，得到DFAM:③化简: 在第②步中求出的DFAM中没有等价状态，因此它就是最小化的DFAM。(2)(a)b)*a(a|b)(a|b)①求NFAM：②确定化，得到DFAM： ③化简，在第②步中求出的DFAM中没有等价状态，因此它已经是最小化的DFAM了。12.解答：对应的NFA为：增加状态X、Y，再确定化：IIaIb{x,5}{A,T,Y}{}{A,T,Y}{A,T,Y}{B}{B}{}{B,T,Y}{B,T,Y}{}{T,Y}{T,Y}{}{}得到的DFA为：最小化：该自动机已经是最小化的DFA了。13．解答：其中a代表1元硬币，b代表5角硬币14．解答：正规式为：(0|1)*(00|01)化简：(0|1)*0(0|1)不确定的有穷自动机为： 确定化，并最小化得到：正规文法为：S→1S|0AA→0B|0|1C|1B→0B|0|1C|1C→1S|0A15.解答：①正规式：(dd*:|e)dd*(.dd*|e)，d代表a~z的字母②NFA为：③DFA为：16.解答：词法分析器对源程序采取非常局部的观点，因此象C语言的语句fi(a==f(x))…中，词法分析器把fi当作一个普通的标识符交给编译的后续阶段，而不会把它看成是关键字if的拼写错。PASCAL语言要求作为实型常量的小数点后面必须有数字，如果程序中出现小数点后面没有数字情况，它由词法分析器报错。17.解答：此时编译器认为/*thenpartreturnqelse/*elsepart*/是程序的注释，因此它不可能再发现else前面的语法错误。分析这是注释用配对括号表示时的一个问题。注释是在词法分析时忽略的，而词法分析器对程序采取非常局部的观点。当进入第一个注释后，词法分析器忽略输入符号，一直到出现注释的右括号为止，由于第一个注释缺少右括号，所以词法分析器在读到第二个注释的右括号时，才认为第一个注释处理结束。 为克服这个问题，后来的语言一般都不用配对括号来表示注释。例如Ada语言的注释始于双连字符（--），随行的结束而终止。如果用Ada语言的注释格式，那么上面函数应写成longgcd(p,q)longp,q;{if(p%q==0)--thenpartreturnqelse--elsepartreturngcd(q,p%q);}18.解答：略！第4章习题解答：1，2，3，4解答略！5.解答：(1)×(2)√(3)×(4)√(5)√(6)√(7)×(8)×6.解答：(1)A：④B：③C：③D：④E：②(2)A：④B：④C：③D：③E：②7.解答：(1)消除给定文法中的左递归，并提取公因子：bexpr→bterm{orbterm}bterm→bfactor{andbfactor}bfactor→notbfactor|(bexpr)|true|false(2)用类C语言写出其递归分析程序:   voidbexpr();{  bterm();  WHILE(lookahead=="or"){      match("or");      bterm();   }}voidbterm();{  bfactor();  WHILE(lookahead=="and"){    match("and");    bfactor();  }voidbfactor();{  if(llokahead=="not")then{     match("not");     bfactor(); }elseif(lookahead=="(")then{        match(‘(");        bexpr();        match(")");      } elseif(lookahead=="true")then match("true) elseif(lookahead=="false")          thenmatch("false");  elseerror; }}8.解答：消除所给文法的左递归，得G"：        S→(L)|a        L→SL"        L"→,SL"|e实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法G"有：First(S)={(,a)Follow(S)={),,,#}First(L)={(,a)Follow(L)={)}First(L")={,}Follow(L")={)}按以上结果，构造预测分析表M如下：文法G"是LL(1)的，因为它的LL(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→SL"5#)L"aa,(a,a))#S→a6#)L",(a,a))#7#)L"S,,(a,a))#L"→,SL"8#)L"S(a,a))#9#)L")L((a,a))#S→(L)10#)L")La,a))#11#)L")L"Sa,a))#L→SL"12#)L")L"aa,a))#S→a13#)L")L",a))#14#)L")L"S,,a))#L"→,SL"15#)L")L"Sa))#16#)L")L"aa))#S→a17#)L")L"))#18#)L")))#L"→e19#)L")#20#))#L"→e21##   9.解答： 各非终结符的First集：First(S)={First(A){e}}∪{First(B){e}}∪{e}∪{b}={a,b,e}First(A)={b}∪{e}={b,e}First(B)＝{e}∪{a}={a,e}First(C)={First(A){e}}∪First(D)∪First(b)={a,b,c}First(D)={a}∪{c}={a,c}各个候选式的First集为：First(AB)={a,b,e}First(bC)={b}First(e)＝{e}First(b)＝{b}First(aD)={a}First(AD)={a,b,c}First(b)={b}First(aS)={a}First(c)={c}各非终结符的Follow集的计算：Follow(S)={#}∪Follow(D)={#}Follow(A)=(First(B){e})∪Follow(S)∪First(D)={a,#,c}Follow(B)=Follow(S)={#}Follow(C)=Follow(S)={#}Follow(D)=Follow(B)∪Follow(C)={#}10．解答：(1)求First和Follow集First(E)=First(T)={(,a,b,∧}⑦First(E")={+,e}⑥First(T)=First(F)={(,a,b,∧}④First(T")=｛(,a,b,∧,e｝⑤First(F)=First(P)={(,a,b,∧}③First(F")=｛*，e｝②First(P)={(,a,b,∧}①（计算顺序）Follow(E)={#,)}Follow(E")=Follow(E)={#，)}(1)（使用的产生式）Follow(T)=First(E")＼{e}∪Follow(T")(1,2)={+}∪{),#}={+,),#}Follow(T")=Follow(T)={+,},#}(3)Follow(F)=First(T")＼{e}∪Follow(T)(3,4)={(,a,b,∧,+,),#}Follow(F")=Follow(F)(5)={(,a,b,∧,+,),#}Follow(P)=First(F")＼{e}∪Follow(F)(5,6)={*,(,a,b,∧,+,),#}(2)证明:∵a.文法不含左递归；b.每个非终结符的各个侯选式的First集不相交；c.First(E")∩Follow(E")={+,e}∩{#,),}=FFirst(T")∩Follow(T")={(,a,b,∧,e}∩{+,)}=F First(F")∩Follow(F")={*,e}∩{,a,(∧,+,},#}=F∴改造后的文法满足LL(1)文法的三个条件，是LL(1)文法。(3)预测分析表如下所示。ab*+∧()#EE→TE"E→TE"E→TE"E"E"→+EE"→eE"→eTT→FT"T→FT"T→FT"T→FT"T"T"→TT"→TT"→TT"→TT"→eT"→eFF→PF"F→PF"F→PF"F→PF"F"F"→eF"→eF"→*F"F"→eF"→eF"→eF"→eF"→ePP→aP→bP→∧P→(E)11.解答：(1)S→AbcA→a│eB→b│ea.文法不含左递归；b.S,A,B各候选式的First集不相交；c.First(A)∩Follow(A)={a,e}∩{b}=FFirst(B)∩Follow(B)={b,e}∩F=F∴该文法为LL(1)文法。(2)S→AbA→a│B│eB→b│ea.文法不含左递归；b.S,A,B各候选式的First集不相交；c.First(A)∩Follow(A)={a,b,e}∩{b}={b}≠F∴该文法不是LL(1)文法。12.解答：①最右推导：E=>T=>F=>(E)=>(E＋T)=>(E＋F)=>(E＋i)=>(T＋i)=>(T*F＋i)语法树：图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集为：FirstVT(S)={a,(}FirstVT(T)={,,a,(}lastVT(S)={a,）}lastVT(T)={,,a,)}  文法G[S]的算符优先关系表：根据优先关系表，对每个终结符或#建立符号f与g，把f(和g)分成一组。根据G[S]的算符优先关系表，画出如下的有向图。优先函数如下：用算符优先分析法分析句子(a,(a,a))。 给定的输入符号串是文法的一个句子。14.解答：(1)该文法的拓广文法G"为0．S"→S1．S→aSAB2．S→BA3．A→aA4．A→B5．B→b其LR(0)项目集规范族和识别活前缀的DFA如下:I0={S"→·S,S→·aSAB,S→·BA,B→·b}I1={S"→S·}I2={B→b·}I3={S→a·SAB,S→·aSAB,S→·BA,B→·b}I4={S→B·A,A→·aA,A→·B,B→·b}I5={S→aS·AB,A→·aA,A→·B,B→·b}I6={S→aSA·B,B→·b}I7={A→a·A,A→·aA,A→·B,B→·b}I8={A→B·}I9={S→BA·}I10={S→aSAB·}I11={A→aA·} 显然，上述状态中没有出现冲突。显然，该文法是LR(0)的文法，因此也是SLR(1)的。求各个非终结符的Follow集，以便构造分析表：Follow(S")={#}    Follow(S)={a,b,#}    Follow(A)={a,b,#}    Follow(B)={a,b,#}构造的SLR(1)分析表如下：(2)该文法的拓广文法G"为0．S"→S1．S→Sab2．S→bR3．R→S4．R→a其LR(0)项目集规范族和识别活前缀的DFA如下:I0={S"→·S,S→·Sab,S→·bR}I1={S"→S·,S→S·ab}I2={S→b·R,R→·S,R→·a,S→·Sab,S→·bR}I3={S→Sa·b}I4={S→bR·}I5={R→S·,S→S·ab}I6= {R→a·}I7={S→Sab·}显然，I1和I5存在移进-归约冲突。求S"和R的Follow集：    Follow(S")={#}    Follow(R)=Follow(S)={a,#}在I5中，出现的移进－归约冲突，且Follow(R)∩{a}={a}，不能用SLR(1)方法解决。因此，此文法不是SLR(1)文法。15.解答：(1)构造其拓广文法G"的产生式为0．S"→S1．S→A2．A→BA3．A→e4．B→aB5．B→b构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0={[S"→·S,#],[S→·A,#],[A→·BA,#,[A→·,#],        [B→·aB,a/b/#],[B→·b,a/b/#]}I1={[S"→S·,#]}I2={[S→A·,#]}I3={[A→B·A,#],[A→·BA,#],[A→·,#],        [B→·aB,a/b/#],[B→·b,a/b/#]}I4={[B→b·,a/b/#]}I5={[B→a·B,a/b/#],[B→·aB,a/b/#],        [B→·b,a/b/#]}I6={[A→BA·,#]}I7={[B→aB·,a/b/#]}该文法的LR(1)项目集规范族中没有冲突，所以该文法是LR(1)文法。构造LR(1)分析表如下： 以上分析表无多的定义入口，所以该文法为LR(1)文法。(3)对于输入串abab，其分析过程如下：16.解答：(1)对于产生式S→AaAb|BbBa来说First(AaAb)∩First(BbBa)={a}∩{b}=FA，B∈VN仅有一条候选式。因此，这个文法是LL(1)的。(2)下面构造这个文法的识别活前缀的DFA。I0={S"→·S,S→·AaAb,S→·BbBa,A→·,B→·}I1={S"→S·}I2={S→A·aAb}I3={S→B·bBa}I4={S→Aa·Ab,A→·}I5={S→Bb·Ba,B→·}I6={S→AaA·b}I7= {S→BbB·a}I8={S→AaAb·}I9={S→BbBa·}由于Follow(A)=Follow(B)={a,b},因此项目集I0中存在归约-归约冲突。在I0状态下，当输入符号是a或是b时，不知用A→e还是B→e进行归约。故此文法不是SLR(1)的。但是，此文法时LR(1)的。17.解答：该文法的拓广文法G"为0．S"→S1．S→(SR2．S→a3．R→,SR4．R→)构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0={S"→·S,S→·(SR,S→·a}I1={S"→S·}I2={S→(·SR,S→·(SR,S→·a}I3={S→a·}I4={S→(S·R,R→·,SR,R→·)}I5={S→(SR·}I6={R→)·}I7={R→,·SR,S→·(SR,S→·a}I8={R→,S·R,R→·,SR,R→·)}I9={R→,SR·} 每个LR(0)项目集中没有冲突。因此，此文法是LR(0)文法。其分析表如下：18．解答：略！第5章习题解答：1，2，3解答：略！4.解答：(1)设S，L，B的值的属性用val表示：S"→S{printf(S.val)}S→L1.L2{S.val:=L1.Val+L2.val/2L2.length}S→L{S.val:=L.val}L→L1B{L.val:=L1.val*2+B.val，L.length=L1.length+1}L→B{L.val:=B.val),L.length:=2}B→0{B.val:=0}B→1{B.val:=1}(2)为S，L引入属性h，用来记录配对的括号个数：S"→S{printf(S.h)}S→a{S.h:=0}S→(L){S.h:=S.h+1}L→L(1),S{S.h:=L(1).h+S.h}L→S{L.h:=S.h)}(3)为D引入一个综合属性h，用来记录D中含id的个数：P→D{printf(D.h)}D→D1;D2{D.h:=D1.h+D2.h}D→id:T{D.h:=1}D→procid;D1;S{D.h:=D1.h+1}5.解答：输入串为bcccaadadadb时的语法树为： 采用修剪语法树的方法，按句柄方式自下而上归约该语法树，在归约时调用相应的语义规则，由此得到最终的翻译结果为：34242421.6.解答：(a+b)+(c+d/(e-3))*87.解答：(1)ab-c+*(2)AnotCDnotornotor(3)abcde/+*+(4)ABandCnotDoror(5)a-bc-d+*+(6)ABorCDnotEandorand8.解答：三元式四元式①(+,a,b)1.(+,a,b,T1)②(-,1,-)2.(-,T,-,T2)③(+,c,d)3.(+,c,d,T3)④(*,2,3)4.(*,T2,T3,T4)⑤(+,a,b)5.(+,a,b,T5)⑥(+,c,5)6.(+,T5,c,T6)⑦(-,4,6)7.(-,T4,,T6,T7)9.解答：四元式代码为：1.(jnz，A，_，x)2.(j，_，_，3)3.(jnz，B，_，5)4.(j，_，_，y)5.(jnz，C，_，y)6.(j，_，_，7)7.(jnz，D，_，y) 8.(j，_，_，x)10.解答：11.解答：(1)四元式序列为：1．（j<,A,C,3）8.(:=,T,-,C)2.(j,-,-,14)9.(j,-,-,14)3.(j<,B,D,5)11.(j,-,-,14)4.(j,-,-,14)12.(+,A,2,T2)5.(j=,A,1,7)13.(:=,T2,-,A)6.(j,-,-,10)14.7.(+,c,1,T1)(2)四元式序列为：1.(j＞0，x，0，3)7.(j，_，_，12)2.(j，_，_，8)8.(＋，x，2，T2)3.(j＞，y，0，5)9.(:＝，T2，_，x)4.(j，_，_，8)10.(＋，y，3，T3)5.(＋，x，y，T1)11.(:＝，T3，_，y)6.(:＝，T1，_，z)12.(3)四元式序列为：0.(+，A，3，t0)1.(:=，t0，，t1)2.(*，C，A，t2)3.(*，t2，2，t3)4.(:=，t3，，B)5.(j<，X，0，7)6.(j，，，0)7.(4)四元式序列为：0.(*,b,2,t0)1.(:=,t0,,i)2.(:=,100,,t1)3.(j,,,6)4.(+,i,1,t2)5.(:=,t2,,i)8.(+,c,d,t4)9.(*,t3,t4,t5)10.(+,a,b,t6)11.(+,t6c,t7)12.(-,t5,t7,t8)13.(:=,t8,,x) 6.(j>,i,t1,15)7.(+,a,b,t3)14.(j,,,4)15.12.解答：略！第6章习题解答：1，2，3，4，5解答：略！6.解答：本题考查的要点是掌握栈式动态存储分配策略中运行的布局，填充过程活动记录display表的内容。运行栈的布局遵循“先进后出”原则，即一个过程调用另一个过程时，被调用过程则在调用过程的栈顶构筑自己的数据区，形成自己的活动记录，包括自己的display表。而display表内容的项数与过程的嵌套层次有关，一般比过程的嵌套层数大1。(1)demo→A此时的运行栈只有主程序demo和过程A的2个数据区，过程A只引用主程序demo全局数据和其自身的局部数据，因此其display表内容有2项，即主程序数据区首址和过程A的主程序数据区首址。(2)demo→A→B 此时的运行栈只有主程序demo、过程A和过程B的3个数据区，过程B嵌套定义在过程A中，要引用主程序demo全局数据、过程A的数据和其自身的局部数据，因此其display表内容有3项，即主程序数据区首址、过程A的主程序数据区首址和过程B本身的数据区首址。(3)demo→A→B→B此时的运行栈包括主程序demo、过程A和2个过程B的实例的4个数据区，过程B要引用的数据区还是3个：主程序demo全局数据、过程A的数据和当前活跃过程B的局部数据（栈顶数据项），因此其display表内容还是有3项，即主程序数据区首址、过程A的主程序数据区首址和当前活跃过程B本身的数据区首址。(4)demo→A→B→B→A此时的运行栈包括主程序demo、2个过程A和2个过程B的实例的5个数据区，但过程A只引用主程序demo全局数据和其自身的局部数据，因此其display表内容只有2项，即主程序数据区首址和过程A的主程序数据区首址。各个运行时刻运行栈的布局和使用的display表如图。第7章习题解答：1.解答：A：局部B：全局C：代码外提D：削减运算强度E：删除归纳变量2，3.解答：略！4.解答：程序流图如下：回边为：B4→B3，循环L={B3,B4}5.解答：各结点n的必经结点集D(n)如下：       D(n0)={n0}       D(n1)={n0,n1}       D(n2)={n0,n1,n2}       D(n3)={n0,n1,n2,n3 }       D(n4)={n0,n1,n2,n4}       D(n5)={n0,n1,n2,n5}       D(n6)={n0,n1,n2,n5,n6}       D(n7)={n0,n1,n2,n5,n6,n7}   回边和循环：   因为D(n5)={n0,n1,n2,n5}，且n5→n2，所以n5→n2为一条回边。根据它求出的循环L1={n2,n5,n3,n4}。    因为D(n6)={n0,n1,n2,n5,n6}，且n6→n1，所以n6→n1为一条回边。根据这条回边，求出的循环L2={n6,n1,n5,n3,n4,n2}。6.解答：(1)首先划分基本块并画出其程序流图，其中有三个基本块B1，B2，B3，有一条回边B2→B2，相应的循环是{B2}。(2)强度削弱：在B2中A和B为乘法运算，可以削弱它们的运算强度，变乘法为加法。优化结果如下图。 (3)删除归纳变量：在循环中，i是循环的基本归纳变量，A，B是同族的归纳变量，且有线性关系，变换循环控制条件，流图如下。(4)代码外提：由于删除归纳变量后有R:=K*100，是循环不变运算，可以提到前置结点B2"中。7.解答：8.解答：(1)DAG如下：(2)优化后的三地址代码为：T3:＝S－RT4:＝S＋RA:＝5*T4B:＝T3＋T49.解答：(本题中假设采用字节地址，两个字节作为一个机器字。)(1)程序的中间代码如下：            B1:readN             /*置初值*/               i:=2           B2:ifi>NgotoB4   /*第一个for语句*/           B3:T1:=i               T2:=addr(A)      /*数组A的基地址*/               T1:=2*T1               T2[T1]:=true               i:=i+1               gotoB2           B4:i:=2               T3:=N**0.5               T3:=[T3]+1     /*[T3]是对T3的值取整*/           B5:ifi>T3gotoB12           B6:T4:=i               T5:=addr(A)               T4:=2*T4                ifT5[T4]gotoB8           B7:gotoB11           B8:j:=2*i           B9:ifj>NgotoB11  /*第三个for语句*/           B10:T6:=j               T7:=addr(A)               T6:=2*T6               T7[T6]=false               j:=j+i               gotoB9           B11:i:=i+1               gotoB5           B12:(2)根据上述中间代码，可划分成基本块B1，B2，B3，B4，B5，B6，B7，B8，B9，B10，B11。其程序流图如下： 考查上面的程序流图：D(B3)={B1,B2,B3}，又有B3→B2，因此B3→B2是一条回边。根据它找到的循环L1={B2,B3}。   D(B10)={B1,B2,B4,B5,B6,B9,B10}，又有B10→B9，所以B10→B9是一条回边。根据这条回边找到循环L2={B9,B10}。   D(B11)={B1,B2,B4,B5,B6,B9,B11}，又有B11→B5，因此B11→B5是一条回边。根据这条回边找到循环L3={B11,B9,B10,B8,B7,B6,B5}(3)进行代码外提把在循环中不随循环变化的操作提到循环外的前置结点中，且在基本块中作复写传播和删除无用赋值。结果程序流图如图1。(4)进行强度削弱和删除归纳变量后，其程序流图如图2。 图1代码外提、复写传播和删除无用赋值后的流图图2强度削弱和删除归纳变量后的流图10.解答：略！第8章习题解答：1，2.解答：略！3.解答：设所有变量均用名字表示地址，寄存器名字用R0、R1和R2表示。目标代码如下：(1)MOV x，#1(2)MOV  x，y(3)ADD  x，#1(4)MOV  R1，bMUL  R1(5)MOV  R0，bADD  R0，cMOV  R1，aDIV  R1，R0MOV  R2 ，cADD  R1，aMOV  x，R1，eADD  R2，fMUL R2，dSUB  R1，R2MOV  x，R14.解答：MOV  R0，ASUB  R0，BMOV  R1，CADD  R1，DMOVS， R1MOV  R1，ESUB  R1，FDIV  R1，R0MUL  R1，SMOVV， R15.解答：(1)MOVR0,bMULR0,cADDR0,aMOVx,R0(2)MOVR0,aDIVR0,bSUBR0,cDIVR0,dMOVx,R0(3)MOVR0,#0SUBR0,bMULR0,aMOVR1,dADDR1,eMOVR2,cSUBR2,R1ADDR0,R2MOVx,R06.解答：略！'