编译原理教程课后习题答案——第六章

《编译原理教程课后习题答案——第六章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章运行时存储空间组织6.1完成下列选择题：(1)过程的DISPLAY表中记录了。a.过程的连接数据b.过程的嵌套层次c.过程的返回地址d.过程的入口地址(2)过程P1调用P2时，连接数据不包含。a.嵌套层次显示表b.老SPc.返回地址d.全局DISPLAY地址(3)堆式动态分配申请和释放存储空间遵守原则。a.先请先放b.先请后放c.后请先放d.任意(4)栈式动态分配与管理在过程返回时应做的工作有。a.保护SPb.恢复SPc.保护TOPd.恢复TOP(5)如果活动记录中没有DISPLAY表，则说明。a.程序中不允许有递

2、归定义的过程b.程序中不允许有嵌套定义的过程c.程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程d.程序中允许有递归定义的过程，也允许有嵌套定义的过程【解答】(1)b(2)a(3)d(4)b(5)b6.2何谓嵌套过程语言运行时的DISPLAY表？它的作用是什么？【解答】当过程定义允许嵌套时，一个过程在运行中应能够引用在静态定义时包围它的任一外层过程所定义的变量或数组。也就是说，在栈式动态存储分配方式下的运行中，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据。因此，过程Q运行时必须知道它的所有(静态

3、)外层过程的最新活动记录的地址。由于允许递归和可变数组，这些外层过程的活动记录的位置也往往是变迁的。因此，必须设法跟踪每个(静态)外层的最新活动记录的位置，而完成这一功能的就是DISPLAY嵌套层次显示表。也即，每当进入一个过程后，在建立它的活动记录区的同时也建立一张DISPLAY表，它自顶而下每个单元依次存放着现行层、直接外层等，直至最外层(主程序层)等每一层过程的最新活动记录的起始地址。6.3(1)写出实现一般递归过程的活动记录结构以及过程调用、过程进入与过程返回的指令；(2)对以return(表达式)形式(这个表达

4、式本身是一个递归调用)返回函数值的特殊函数过程，给出不增加时间开销但能节省存储空间的实现方法。假定语言中过程参数只有传值和传地址两种形式，为便于理解，举下例说明这种特殊的函数调用：intgcd(intp,intq){if(p%q==0)returnq;elsereturngcd(q,p%q)}【解答】(1)一般递归过程的活动记录如图6-1所示。图6-1递归过程的活动记录过程调用指令为(i+4)[TOP]=Ti或(i+4)[TOP]=addr[Ti]1[TOP]=SP3[TOP]=SP+d4[TOP]=nJSRP过程进入指

5、令为SP=TOP+11[SP]=返回地址TOP=TOP+L建立DISPLAYP；/*执行P过程*/返回指令为TOP=SP-1SP=0[SP]X=2[TOP]UJ0[X](2)对于return后的直接递归情况，可简化为(i+3)[SP]=Ti或(i+3)[SP]=addr[Ti]UJP6.4有一程序如下：programex;a:integer;procedurePP(x:integer);begin:x:=5;x:=a+1end;begina:=2;PP(a);write(a)end.试用图表示ex调用PP(a)前后活动记

6、录的过程。【解答】按照嵌套过程语言栈式实现方法，ex调用PP(a)前后活动记录的过程如图6-2所示。图6-2ex调用PP(a)前后的活动记录6.5类PASCAL结构(嵌套过程)的程序如下，该语言的编译器采用栈式动态存储分配策略管理目标程序数据空间。programDemoprocedureA;procedureB;begin(*B*)…ifdthenBelseA;…end;(*B*)begin(*A*)Bend;(*A*)begin(*Demo*)Aend.(1)若过程调用序列为①Demo→A；②Demo→A→B；③Dem

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

8、，称为该过程的活动记录；另一部分(动态数组)的体积需在运行时动态确定，称为该过程的可变辅助空间。当一个过程开始工作时，首先在运行栈顶部建立它的活动记录，然后再在这个记录之顶确定它所需的辅助空间。含有动态数组R的过程B在第一次激活时，相应的数据空间情况如图6-4所示。图6-4带动态数组的运行栈示意(a)动态数组R空间分