编译原理-答案.ppt

《编译原理-答案.ppt》由会员分享，可在线阅读，更多相关《编译原理-答案.ppt（689页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理教程原理教程（第三版）（第三版）习题解析与上机指解析与上机指导 胡元义等胡元义等 编著编著 西安电子科技大学出版社西安电子科技大学出版社http:/普通高等院校普通高等院校计算机算机类专业系列教材系列教材目录第一章第一章 绪论绪论第二章第二章 词法分析词法分析第三章第三章 语法分析语法分析第四章第四章 语义分析和中间代码生成语义分析和中间代码生成第五章第五章 代码优化代码优化第六章第六章 运行时存储空间组织运行时存储空间组织第七章第七章 目标代码生成目标代码生成第八章第八章 符号表与错误处理符号表与错误处理第九章第九章 小型编译程序介绍小型编译程序介绍第十章第十章 上机实验内容上机实验

2、内容第十一章第十一章 小型编译程序小型编译程序第一章 绪论1.1完成下列选择题：(1)构造编译程序应掌握。a.源程序b.目标语言c.编译方法d.以上三项都是(2)编译程序绝大多数时间花在上。a.出错处理b.词法分析c.目标代码生成d.表格管理(3)编译程序是对。a.汇编程序的翻译b.高级语言程序的解释执行c.机器语言的执行d.高级语言的翻译【解答】(1)d(2)d(3)d 1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这

3、个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便

4、于程序调试。这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。1.3 请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】编译程序总框图如图1-1所示。图1-1编译程序总框图作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响等。第二章 词法分析 2

5、.1 完成下列选择题：(1)词法分析器的输出结果是 。a.单词的种别编码 b.单词在符号表中的位置 c.单词的种别编码和自身值 d.单词自身值(2)正规式M1和M2等价是指 。a.M1和M2的状态数相等 b.M1和M2的有向边条数相等 c.M1和M2所识别的语言集相等 d.M1和M2状态数和有向边条数相等(3)DFAM(见图2-1)接受的字集为。a.以0开头的二进制数组成的集合 b.以0结尾的二进制数组成的集合 c.含奇数个0的二进制数组成的集合 d.含偶数个0的二进制数组成的集合 【解答】(1)c (2)c (3)d 图2-1习题2.1的DFAM2.2 什么是扫描器？扫描器的功能是什么？【解

6、答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。2.3 设M=(x,y,a,b,f,x,y)为一非确定的有限自动机，其中f定义如下：f(x,a)=x,y fx,b=y f(y,a)=fy,b=x,y试构造相应的确定有限自动机M。【解答】对照自动机的定义M=(S,f,So,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。先画出

7、NFA M相应的状态图，如图2-2所示。图2-2习题2.3的NFAM用子集法构造状态转换矩阵，如表2-1所示。表2-1 状态转换矩阵将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到M=(0,1,2,a,b,f,0,1,2)，其状态转换图如图2-3所示。表2-2 状态转换矩阵将图2-3所示的DFA M最小化。首先，将M的状态分成终态组1,2与非终态组0。其次，考察1,2，由于1,2a=1,2b=21,2，所以不再将其划分了，也即整个划分只有两组：0和1,2。令状态1代表1,2，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图2-4所示的化简了的DFA M。图2-3

8、习题2.3的DFA M图2-4 图2-3化简后的DFA M2.4 正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。【解答】正规式(ab)*a对应的NFA如图2-5所示，正规式a(ba)*对应的NFA如图2-6所示。图2-5正规式(ab)*a对应的NFA图2-6正规式a(ba)*对应的DFA这两个正规式最终都可得到最简DFA，如图2-7所示。因此，这两个正规式等价。图2-7最简NFA2.5 设有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1)给出描述该语言的正规表达式；(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。【解答】该语言对应的正规表达式为a(a

9、a)*bb(bb)*a(aa)*，正规表达式对应的NFA如图2-8所示。图2-8习题2-5的NFA用子集法将图2-8确定化，如图2-9所示。由图2-9重新命名后的状态转换矩阵可化简为(也可由最小化方法得到)0,2 1 3,5 4,6 7按顺序重新命名为0、1、2、3、4后得到最简的DFA，如图2-10所示。图2-9习题2.5的状态转换矩阵图2-10习题2.5的最简DFA2.6 有语言L=w|w(0,1)+，并且w中至少有两个1，又在任何两个1之间有偶数个0，试构造接受该语言的确定有限状态自动机(DFA)。【解答】对于语言L，w中至少有两个1，且任意两个1之间必须有偶数个0；也即在第一个1之前和

10、最后一个1之后，对0的个数没有要求。据此我们求出L的正规式为0*1(00(00)*1)*00(00)*10*，画出与正规式对应的NFA，如图2-11所示。图2-11习题2.6的NFA用子集法将图2-11的NFA确定化，如图2-12所示。图2-12习题2.6的状态转换矩阵由图2-12可看出非终态2和4的下一状态相同，终态6和8的下一状态相同，即得到最简状态为0、1、2,4、3、5、6,8、7按顺序重新命名为0、1、2、3、4、5、6，则得到最简DFA，如图2-13所示。图2-13习题2.6的最简DFA2.7 已知正规式(a|b)*|aa)*b和正规式(a|b)*b。(1)试用有限自动机的等价性证

11、明这两个正规式是等价的；(2)给出相应的正规文法。【解 答】(1)正 规 式(a|b)*|aa)*b对应的NFA如图2-14所示。图2-14正规式(a|b)*|aa)*b对应的NFA用子集法将图2-14所示的NFA确定化为DFA，如图2-15所示。图2-15图2-14确定化后的状态转换矩阵由于对非终态的状态1、2来说，它们输入a、b的下一状态是一样的，故状态1和状态2可以合并，将合并后的终态3命名为2，则得到表2-3(注意，终态和非终态即使输入a、b的下一状态相同也不能合并)。由此得到最简DFA，如图2-16所示。正规式(a|b)*b对应的NFA如图2-17所示。表2-3 合并后的状态转换矩阵

12、图2-16习题2.7的最简DFA图2-17正规式(a|b)*b对应的NFA用子集法将图2-17所示的NFA确定化为如图2-18所示的状态转换矩阵。图2-18图2-17确定化后的状态转换矩阵比较图2-18与图2-15，重新命名后的转换矩阵是完全一样的，也即正规式(a|b)*b可以同样得到化简后的DFA如图2-16所示。因此，两个自动机完全一样，即两个正规文法等价。(2)对图2-16，令A对应状态1，B对应状态2，则相应的正规文法GA为GA：AaA|bB|b BaA|bB|bGA可 进 一 步 化 简 为 GS：SaS|bS|b(非终结符B对应的产生式与A对应的产生式相同，故两非终结符等价，即可合

13、并为一个产生式)。2.8 下列程序段以B表示循环体，A表示初始化，I表示增量，T表示测试：I=1;while(I0)a=i+e-b*d;else a=0;在 生 成 中 间 代 码 时，条 件“i0”为假的转移地址无法确定，而要等到处理“else”时方可确定，这时就存在一个地址返填问题。此外，按语义要 求，当 处 理 完(i0)后 的 语 句(即“i0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填问题。对于赋值语句a=i+e-b*d，其处理顺序(也即生成中间代码顺序)是先生成

14、i+e的代码，再生成b*d的中间代码，最后才产生“-”运算的中间代码，这种顺序不能颠倒。4.3 令S.val为文法GS生成的二进制数的值，例如对输入串101.101，则S.val=5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则，G(S)如下：GS:SL.L|L LLB|B B0|1 【解 答】计 算 S.val的 文 法GS及语义动作如下：产生式 语义动作 GS：SS print(S.val)SL1L2 S.val:=L1.val+L2.val/2L2.length SL S.val:=L.val LL1B L.val:=L1.val*2+B.val L.lengt

15、h:=L1.length+1 LB L.val:=B.val L.length:=2 B1 B.val:=1 B0 B.val:=04.4 下面的文法生成变量的类型说明：Did LL,id L|:TTinteger|real试构造一个翻译方案，仅使用综合属性，把每个标识符的类型填入符号表中(对所用到的过程，仅说明功能即可，不必具体写出)。【解答】此题只需要对说明语句进行语义分析而不需要产生代码，但要求把每个标识符的类型填入符号表中。对D、L、T，为其设置综合属性type，而过程enter(name,type)用来把名字name填入到符号表中，并且给出此名字的类型type。翻译方案如下：Did

16、Lenter(id.name,L.type);L,id L(1)enter(id.name,L(1).type);L.type=L(1).type;L:T L.type=T.type;TintegerT.type=integer;TrealT.type=real;4.5 写出翻译过程调用语句的语义子程序。在所生成的四元式序列中，要求在转子指令之前的参数四元式par按反序出现(与实现参数的顺序相反)。此时，在翻译过程调用语句时，是否需要语义变量(队列)queue？【解答】为使过程调用语句的语义子程序产生的参数四元式par按反序方式出现，过程调用语句的文法为 Scall i(arglist)arg

17、listE arglistarglist(1),E按照该文法，语法制导翻译程序不需要语义变量队列queue，但需要一个语义变量栈STACK，用来实现按反序记录每个实在参数的地址。翻译过程调用语句的产生式及语义子程序如下：(1)arglistE 建立一个arglist.STACK栈，它仅包含一项E.place(2)arglistarglist(1)，E 将E.place压入arglist(1).STACK栈，arglist.STACK=arglist(1).STACK(3)Scall i(arglist)while arglist.STACKnull do begin 将arglist.STAC

18、K栈顶项弹出并送入p单元之中；emit(par,_,_,p);end;emit(call,_,_,entry(i);4.6 设某语言的while语句的语法形式为S while E do S(1)其语义解释如图4-1所示。(1)写出适合语法制导翻译的产生式；(2)写出每个产生式对应的语义动作。图4-1 习题4.6的语句结构图【解答】本题的语义解释图已经给出了翻译后的中间代码结构。在语法制导翻译过程中，当扫描到while时，应记住E的代码地址；当扫描到do时，应对E的“真出口”进行回填，使之转到S(1)代码的入口处；当扫描到S(1)时，除了应将E的入口地址传给S(1).chain之外，还要形成一个

19、转向E入口处的无条件转移的四元式，并且将E.fc继续传下去。因此，应把Swhile E do S(1)改写为如下的三个产生式：WwhileAW E doSA S(1)每个产生式对应的语义子程序如下：Wwhile W.quad=nxq;AW E do Backpatch(E.tc,nxq);A.chain=E.fc;A.quad=W.quad;SA S(1)Backpatch(S(1).chain,A.quad);emit(j,_,_,A.quad);S.chain=A.chain;4.7 改写布尔表达式的语义子程序，使得i(1)rop i(2)不按通常方式翻译为下面的相继两个四元式：(jrop

20、,i(1),i(2),0)(j,_,_,0)而是翻译成如下的一个四元式：(jnrop,i(1),i(2),0)使得当i(1)rop i(2)为假时发生转移，而为真时并不发生转移(即顺序执行下一个四元式)，从而产生效率较高的四元式代码。【解答】按要求改造描述布尔表达式的语义子程序如下：(1)Ei E.tc=null;E.fc=nxq;emit(jez,entry(i),_,0);(2)Ei(1)rop i(2)E.tc=null;E.fc=nxq;emit(jnrop,entry(i(1),entry(i(2);)/*nrop表示关系运算符与rop相反*/(3)E(E(1)E.tc=E(1).t

21、c;E.fc=E(1).fc;(4)EE(1)E.fc=nxq;emit(j,_,_,0);Backpatch(E(1).fc,nxq);(5)EAE(1)EA.fc=E(1).fc;(6)EEAE(2)E.tc=E(2).tc;E.fc=merg(EA.fc,E(2).fc);(7)E0E(1)E0.tc=nxq;emit(j,_,_,0);Backpatch(E(1).fc,nxq);(8)EE0E(2)E.fc=E(2).fc;Backpatch(E0.tc,nxq);4.8 按照三种基本控制结构文法将下面的语句翻译成四元式序列：while(ACBD)if(A1)C=C+1;else w

22、hile(AD)A=A+2;【解答】该语句的四元式序列如下(其中E1、E2和E3分别对应ACBD、A1和AD，并且关系运算符优先级高)：100(j,A,C,102)101(j,_,_,113)/*E1为F*/102(j,B,D,104)/*E1为T*/103(j,_,_,113)/*E1为F*/104(j=,A,1,106)/*E2为T*/105(j,_,_,108)/*E2为F*/106(+,C,1,C)/*C:=C+1*/107(j,_,_,112)/*跳过else后的语句*/108(j,A,D,110)/*E3为T*/109(j,_,_,112)/*E3为F*/110(+,A,2,A)/

23、*A:=A+2*/111(j,_,_,108)/*转回内层while语句开始处*/112(j,_,_,100)/*转回外层while语句开始处*/1134.9 已知源程序如下：prod=0;i=1;while(i20)prod=prod+ai*bi;i=i+1;试按语法制导翻译法将上述源程序翻译成四元式序列(设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节)。【解答】源程序翻译为下列四元式序列：100(=,0,_,prod)101(=,1,_,i)102(j,i,20,104)103(j,_,_,114)104(*,4,i,T1)105(-,A,4,T2)1

24、06(=,T2,T1,T3)107(*,4,i,T4)108(-,B,4,T5)109(=,T5,T4,T6)110(*,T3,T6,T7)111(+,prod,T7,prod)112(+,i,1,i)113(j,_,_,102)1144.10 给出文法GS:SSaA|AAAbB|BBcSd|e (1)请证实AacAbcBaAdbed是文法GS的一个句型；(2)请写出该句型的所有短语、素短语以及句柄；(3)为文法GS的每个产生式写出 相 应 的 翻 译 子 程 序，使 句 型AacAbcBaAdbed经该翻译方案后，输出为131042521430。【解答】(1)根据文法GS画出AacAbcBa

25、Adbed对应的语法树如图4-2所示。由图4-2可知AacAbcBaAdbed是文法GS的一个句型。图4-2 AacAbcBaAdbed对应的语法树(2)由 图 4-2可 知，句 型AacAbcBaAdbed中的短语为B,BaA,cBaAd,AbcBaAd,e,cBaAdbe,cAbcBaAdbed,A,AacAbcBaAdbed从图4-2可看出，句型AacAbcBaAdbed中相邻终结符对应的优先关系如下(层次靠下的优先级高)：#acbcadbed#素短语为BaA和e。句柄(最左直接短语)为A。(3)采用修剪语法树的办法，按句柄方式自下而上归约，每当一个产生式得到匹配时，则按归约的先后顺序与

26、所给的输出131042521430顺序进行对应。如：第一个句柄为A，它所对应的产生式为 SA，所 以 它 的 语 义 动 作 应 为print(1)；修剪后第二次找到的句柄为B,它所对应的产生式为AB，此时它对应输出序列中的“3”，即它的语义动作为print(3)，依此类推，得到每个产生式相应的语义动作如下：SSaA print(0)SA print(1)AAbB print(2)AB print(3)BcSd print(4)Be print(5)第五章 代码优化 5.1 完成以下选择题：(1)优化可生成 的目标代码。a.运行时间较短 b.占用存储空间较小c.运行时间短但占用内存空间大 d.

27、运行时间短且占用存储空间小 (2)下列 优化方法不是针对循环优化进行的。a.强度削弱 b.删除归纳变量 c.删除多余运算 d.代码外提 (3)基本块内的优化为 。a.代码外提，删除归纳变量 b.删除多余运算，删除无用赋值c.强度削弱，代码外提 d.循环展开，循环合并(4)在程序流图中，我们称具有下述性质 的结点序列为一个循环。a.它们是非连通的且只有一个入口结点 b.它们是强连通的但有多个入口结点c.它们是非连通的但有多个入口结点 d.它们是强连通的且只有一个入口结点(5)关于必经结点的二元关系，下列叙述中不正确的是 。a.满足自反性 b.满足传递性 c.满足反对称性 d.满足对称性【解答】(

28、1)d (2)c (3)b (4)d (5)d5.2 何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行？【解答】优化根据涉及的程序范围可分为三种。(1)局部优化是指局限于基本块范围内的一种优化。一个基本块是指程序中一组顺序执行的语句序列(或四元式序列)，其中只有一个入口(第一个语句)和一个出口(最后一个语句)。对于一个给定的程序，我们可以把它划分为一系列的基本块，然后在各个基本块范围内分别进行优化。通常应用DAG方法进行局部优化。(2)循环优化是指对循环中的代码进行优化。例如，如果在循环语句中某些运算结果不随循环的重复执行而改变，那么该运算可以提到循环外，其运算结果仍保持不变，但

29、程序运行的效率却提高了。循环优化包括代码外提、强度削弱、删除归纳变量、循环合并和循环展开。5.3将下面程序划分为基本块并作出其程序流图。read(A,B)F=1C=A*AD=B*BifC100gotoL2haltL2:F=F-1gotoL1【解答】先求出四元式程序中各基本块的入口语句，即程序的第一个语句，或者能由条件语句或无条件转移语句转移到的语句，或者条件转移语句的后继语句。然后对求出的每一入口语句构造其所属的基本块，它是由该入口语句至下一入口语句(不包括该入口语句)或转移语句(包括该转移语句)或停语句(包括该停语句)之间的语句序列组成的。凡未被纳入某一基本块的语句都从程序中删除。要注意基本

30、块的核心只有一个入口和一个出口，入口就是其中第一个语句，出口就是其中最后一个语句。如果发现某基本块有两个以上的入口或两个以上的出口，则划分基本块有误。程序流图画法是当下述条件(1)和(2)有一个成立时，从结点i有一有向边引到结点j：(1)基本块j在程序中的位置紧跟在基本块i之后，并且基本块i的出口语句不是无条件转移语句goto(s)或停语句。(2)基本块i的出口语句是goto(s)或ifgoto(s)，并且(s)是基本块j的入口语句。应用上述方法求出本题所给程序的基本块及程序流图见图5-1，图中的有向边、实线是按流图画法(1)画出的，虚线是按流图画法(2)画出的。图5-1程序流图5.4 基本块

31、的DAG如图5-2所示。若：(1)b在该基本块出口处不活跃；(2)b在该基本块出口处活跃；请分别给出下列代码经过优化之后的代码：(1)a=b+c(2)b=a-d (3)c=b+c(4)d=a-d图5-2习题5.4的DAG图【解答】(1)当b在出口处不活跃时，生成优化后的代码为 a=b0+c0 d=a-d0 c=d+c0 (2)当b在出口活跃时，生成优化后的代码为 a=b0+c0 b=a-d0 d=b c=d+c05.5 对于基本块P：S0=2S1=3/S0S2=T-CS3=T+CR=S0/S3H=RS4=3/S1S5=T+CS6=S4/S5H=S6*S2(1)应用DAG对该基本块进行优化；(2

32、)假定只有R、H在基本块出口是活跃的，试写出优化后的四元式序列。【解答】(1)根据DAG图得到优化后的四元式序列为S0=2S4=2S1=1.5S2=T-CS3=T+CS5=S3R=2/S3S6=RH=S6*S2(2)若只有R、H在基本块出口是活跃的，优化后的四元式序列为S2=T-CS3=T+CR=2/S3H=R*S25.6 试画出如下中间代码序列的程序流图，并求出：(1)各结点的必经结点集合D(n)；(2)流图中的回边与循环。J=0L1：I=0if I 8 goto L3L2：A=B+CB=D*CL3：if B=0 goto L4writeBgotoL5L4：I=I+1ifI8gotoL2L5

33、：J=J+1ifJ=3gotoL1halt【解答】(1)各结点的必经结点集分别为D(n0)=n0D(n1)=n0,n1D(n2)=n0,n1,n2D(n3)=n0,n1,n3D(n4)=n0,n1,n3,n4D(n5)=n0,n1,n3,n5D(n6)=n0,n1,n3,n6D(n7)=n0,n1,n3,n6,n7程序流图如图5-3所示。图5-3习题5.6的程序流图由于有n5n2和n6n1，而n2不是n5的必经结点，n1是n6的必经结点，所以n6n1为回边；即该回边表示的循环为 n1,n2,n3,n4,n5,n6，入口结点为n1，出口结点为n6。5.7 证明：如果已知有向边nd是一回边，则由结

34、点d、结点n以及有通路到达n而该通路不经过d的所有结点组成一个循环。【解答】根据题意画出示意图，如图5-4所示。图5-4具有回边nd的流图证明过程如下：(1)令结点d、结点n以及有通路到达n而该通路不经过d的所有结点构成集合L(即图5-4中的全部结点)，则L必定是强连通的。为了证明这一点，令M=L-d,n。由L的组成成分可知M中每一结点ni都可以不经过d而到达n。又因d DOM n(已知nd为回边，由回边定义知必有d DOM n)，所以必有d DOM ni，如图5-4所示。如不然，则从首结点就可以不经过d而到达ni，从而也可以不经过d到达n，这与d DOM n矛盾。因d DOM ni所以d必有

35、通路到达M中任一结点ni，而M中任一结点又可以通过n到达d(nd为回边)，从而M中任意两个结点之间必有一通路，L中任意两个结点之间亦必有一通路。此外，由M中结点性质可知：d到M中任一结点ni的通路上所有结点都应属于M，ni到n的通路上所有结点也都属于M。因此，L中任意两结点间通路上所有结点都属于L，也即，L是强连通的。(2)因为对所有niL，都有d DOM ni，所以d必为L的一个入口结点。我们说d也一定是L的唯一入口结点。如不然，必有另一入口结点d1L且d1d。d1不可能是首结点，否则d DOM n不成立(因为有d DOM d1，如果d1是首结点，则d就是首结点d1的必经结点，则只能是d=d

36、1，与dd1矛盾)。现设d1不是首结点，且设d1在L之外的前驱是d2，那么，d2和n之间必有一条通路d2d1n，且该通路不经过d，从而d2应属于M，这与d2L矛盾。所以不可能存在上述结点d1，也即d是循环的唯一入口结点。至此，我们已经满足了循环的定义：循环是程序流图中具有唯一入口结点的强连通子图，也即，L是包含回边nd的循环，d是循环的唯一入口结点。5.8 对下面四元式代码序列：A=0 I=1 L1:B=J+1 C=B+I A=C+A if I=100 goto L2 I=I+1 goto L1 L2:write A halt(1)画出其控制流程图；(2)求出循环并进行循环的代码外提和强度削弱

37、优化。【解答】(1)在构造程序的基本块的基础上画出该程序的流图，如图5-5所示。图5-5习题5.8的程序流图(2)很容易看出，B3B2是流图中的一条有向边，并且有B2 DOM B3，故B3B2为流图中的一条回边。循环可通过回边求得，即找出由结点B2、结点B3以及有通路到达B3但不经过B2的所有结点。所以，由回边组成的B3B2循环是 B2，B3。进行代码外提就是将循环中的不变运算外提到循环入口结点前新设置的循环前置结点中。经检查，找出的不变运算为B2中的B=J+1。因此，代码外提后的程序流图如图5-6所示。图5-6习题5.8中代码外提后的程序流图我们知道，强度削弱不仅可对乘法运算进行，也可对加法

38、运算进行。由于本题中的四元式程序不存在乘法运算，所以只能进行加法运算的强度削弱。从图5-5中可以看到，B2中的C=B+I，变量B因代码外提其定值点已在循环之外，故相当于常数。而另一加数I值由B3中的I=I+1决定，即每循环一次I值增1；也即每循环一次，B2中的C=B+I其C值增量与B3中的I相同，即常数1。因此，我们可以对C进行强度削弱，即将B2中的四元式C=B+I外提到前置结点B2中，同时在B3中I=I+1之后给C增加一个常量1。进行强度削弱后的结果如图5-7所示。图5-7习题5.8中强度削弱后的程序流图5.9 某程序流图如图5-8所示。(1)给出该流图中的循环；(2)指出循环不变运算；(3

39、)指出哪些循环不变运算可以外提。图5-8习题5.9的程序流图【解答】(1)流图中的循环为B2,B3,B4。(2)B3中的i=2是循环不变运算。(3)循环不变运算外提的条件是：该不变运算所在的结点是循环所有出口结点的必经结点；当把循环不变运算A=B op C(B或op C可以没有)外提时，要求循环中其他地方不再有A的定值点；当把循环不变运算A=B op C外提时，要求循环中A的所有引用点都是而且仅仅是这个定值所能到达的。由于i=2所在的结点不是循环所有出口结点的必经结点，故不能外提。5.10 一程序流图如图5-9所示，试分别对其进行代码外提、强度削弱和删除归纳变量等优化。图5-9习题5.10的程

40、序流图【解答】由图5-9可知，B5B4与B6B2为流图的有向边，从而有D(B5)=B1，B2，B3，B4，B5D(B6)=B1，B2，B3，B4，B6故有B4 DOM B5和B2 DOM B6，因此B5B4和B6B2为回边(其余都不是回边)，即分别组成了循环B4，B5、B2，B3，B4，B5，B6。对循环B4，B5、B2，B3，B4，B5，B6进行代码外提、强度削弱和删除归纳变量等优化后，其优化后的程序流图如图5-10所示。图5-10习题5.10中优化后的程序流图第六章 运行时存储空间组织 6.1 完成下列选择题：(1)过程的DISPLAY表中记录了 。a.过程的连接数据 b.过程的嵌套层次

41、c.过程的返回地址 d.过程的入口地址(2)过程P1调用P2时，连接数据不包含 。a.嵌套层次显示表 b.老SP c.返回地址 d.全局DISPLAY地址(3)堆式动态分配申请和释放存储空间遵守 原则。a.先请先放 b.先请后放 c.后请先放 d.任意(4)栈式动态分配与管理在过程返回时应做的工作有 。a.保护SP b.恢复SP c.保护TOP d.恢复TOP(5)如 果 活 动 记 录 中 没 有DISPLAY表，则说明 。a.程序中不允许有递归定义的过程 b.程序中不允许有嵌套定义的过程c.程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程d.程序中允许有递归定义的过程，也允许有嵌套

42、定义的过程【解答】(1)b (2)a (3)d (4)b (5)b6.2 何谓嵌套过程语言运行时的DISPLAY表？它的作用是什么？【解答】当过程定义允许嵌套时，一个过程在运行中应能够引用在静态定义时包围它的任一外层过程所定义的变量或数组。也就是说，在栈式动态存储分配方式下的运行中，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据。因此，过程Q运行时必须知道它的所有(静态)外层过程的最新活动记录的地址。由于允许递归和可变数组，这些外层过程的活动记录的位置也往往是变迁的。因此，必须设法跟踪每个(静态)外层的最新活动记录的位置，而完成这一功能的就是DISPLAY嵌套层次显示表。也即，

43、每当进入一个过程后，在建立它的活动记录区的同时也建立一张DISPLAY表，它自顶而下每个单元依次存放着现行层、直接外层等，直至最外层(主程序层)等每一层过程的最新活动记录的起始地址。6.3 (1)写出实现一般递归过程的活动记录结构以及过程调用、过程进入与过程返回的指令；(2)对以return(表达式)形式(这个表达式本身是一个递归调用)返回函数值的特殊函数过程，给出不增加时间开销但能节省存储空间的实现方法。假定语言中过程参数只有传值和传地址两种形式，为便于理解，举下例说明这种特殊的函数调用：int gcd(int p,int q)if(p%q=0)return q;else return gc

44、d(q,p%q)【解答】(1)一般递归过程的活动记录如图6-1所示。图6-1递归过程的活动记录过程调用指令为 (i+4)TOP=Ti 或 (i+4)TOP=addr Ti 1TOP=SP 3TOP=SP+d 4TOP=n JSR P过程进入指令为 SP=TOP+1 1SP=返回地址 TOP=TOP+L 建立DISPLAY P；/*执行P过程*/返回指令为 TOP=SP-1 SP=0SP X=2TOP UJ 0X(2)对于return后的直接递归情况，可简化为 (i+3)SP=Ti 或 (i+3)SP=addr Ti UJ P6.4 有一程序如下：program ex;a:integer;pro

45、cedure PP(x:integer);begin:x:=5;x:=a+1 end;begin a:=2;PP(a);write(a)end.试用图表示ex调用PP(a)前后活动记录的过程。【解答】按照嵌套过程语言栈式实现方法，ex调用PP(a)前后活动记录的过程如图6-2所示。图6-2 ex调用PP(a)前后的活动记录6.5 类PASCAL结构(嵌套过程)的程序如下，该语言的编译器采用栈式动态存储分配策略管理目标程序数据空间。program Demo procedure A;procedure B;begin(*B*)if d then B else A;end;(*B*)begin(*A

46、*)Bend;(*A*)begin(*Demo*)A end.(1)若过程调用序列为 DemoA；DemoAB；DemoABB；DemoABBA请分别给出这四个时刻运行栈的布局和使用的DISPLAY表；(2)若该语言允许动态数组，编译程序应如何处置？如过程B有动态局部数组Rm:n，请给出B第一次激活时相应的数据空间的情况。【解答】(1)运行栈及使用的DISPLAY表如图6-3所示。图6-3运行栈及DISPLAY表示意图(2)由于一个过程在运行时所需的实际数据空间的大小，除可变数据结构(可变数组)那些部分外，其余部分在编译时是完全可以知道的。编译程序处理时将过程运行时所需的数据空间分为两部分：一

47、部分在编译时可确定其体积，称为该过程的活动记录；另一部分(动态数组)的体积需在运行时动态确定，称为该过程的可变辅助空间。当一个过程开始工作时，首先在运行栈顶部建立它的活动记录，然后再在这个记录之顶确定它所需的辅助空间。含有动态数组R的过程B在第一次激活时，相应的数据空间情况如图6-4所示。图6-4 带动态数组的运行栈示意(a)动态数组R空间分配之前；(b)动态数组R空间分配之后6.6 下面程序的结果是120。但是如果把第5行的abs(1)改成1的话，则程序结果为1。试分析为什么会有这种不同的结果。int fact()static int i=5;if(i=0)return(1);else i=

48、i-1;return(i+abs(1)*fact();main()printf(factor or 5=%dn,fact();解答】i是静态变量，所有对i的操作实际上都是对i所对应的存储单元进行操作，每次递归进入下一层fact函数后，上一层对i的赋值仍然有效。需要注意的是，每次递归调用时，(i+abs(1)*fact()中的(i+abs(1)的值都先于fact算出。因此，第一次递归调用所求得的值为5*fact，第二次递归调用所求得的值为4*fact，一直到第五次递归调用所求得的值为1*fact，而此时fact为1。也即实际上是求一个5*4*3*2*1的阶乘，由此得到结果为120。将abs(1)

49、改为1后，输出结果为1而不是120，这主要是与编译的代码生成策略有关。对表达式(i+abs(1)*fact()，因为两个子表达式(i+abs(1)和fact()都有函数调用，而编译器的编译则是先产生左子表达式的代码，后产生右子表达式的代码。也即，每次递归调用时，(i+abs(1)*fact()中的(i+abs(1)的值都先于fact算出。但是，当abs(1)改为1后，左子表达式就没有函数调用了，于是编译器就先产生右子表达式的代码。每次递归调用时，(i+1)*fact()中的(i+1)值都后于fact计算。也即，第一次递归调用得到(i+1)*fact，第 二 次 递 归 调 用 得 到(i+1)

50、*fact，第 三 次 递 归 调 用 仍 得 到(i+1)*fact，直到第五次递归调用还是得到(i+1)*fact，而此时fact为1，i为0。因此，每次递归所求实际上都是1*fact，最终得到输出结果为1。第七章 目标代码生成 7.1 对下列四元式序列生成目标代码：T=A-BS=C+DW=E-FU=W/TV=U*S其中，V是基本块出口的活跃变量，R0和R1是可用寄存器。【解答】简单代码生成算法依次对四元式进行翻译。我们以四元式T=a+b为例来说明其翻译过程。汇编语言的加法指令代码形式为ADD R,X其中，ADD为加法指令；R为第一操作数，第一操作数必须为寄存器类型；X为第二操作数，它可以