编译原理课后答案——第六章_运行时存储空间组织课件

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

2、a. 保护SP b. 恢复SP c. 保护TOP d. 恢复TOP第六章第六章 运行时存储空间组织运行时存储空间组织 (5) 如果活动记录中没有DISPLAY表，则说明 。a. 程序中不允许有递归定义的过程 b. 程序中不允许有嵌套定义的过程c. 程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程d. 程序中允许有递归定义的过程，也允许有嵌套定义的过程【解答】 (1) b (2) a (3) d (4) b (5) b第六章第六章 运行时存储空间组织运行时存储空间组织 6.2 何谓嵌套过程语言运行时的DISPLAY表？它的作用是什么？【解答】 当过程定义允许嵌套时，一个过程在运行中应能够

3、引用在静态定义时包围它的任一外层过程所定义的变量或数组。也就是说，在栈式动态存储分配方式下的运行中，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据。因此，过程Q运行时必须知道它的所有(静态)外层过程的最新活动记录的地址。由于允许递归和可变数组，这些外层过程的活动记录的位置也往往是变迁的。因此，必须设法跟踪每个(静态)外层的最新活动记录的位置，而完成这一功能的就是DISPLAY嵌套层次显示表。第六章第六章 运行时存储空间组织运行时存储空间组织 也即，每当进入一个过程后，在建立它的活动记录区的同时也建立一张DISPLAY表，它自顶而下每个单元依次存放着现行层、直接外层等，直至最外层

4、(主程序层)等每一层过程的最新活动记录的起始地址。6.3 (1) 写出实现一般递归过程的活动记录结构以及过程调用、过程进入与过程返回的指令；(2) 对以return(表达式)形式(这个表达式本身是一个递归调用)返回函数值的特殊函数过程，给出不增加时间开销但能节省存储空间的实现方法。假定语言中过程参数只有传值和传地址两种形式，为便于理解，举下例说明这种特殊的函数调用： 第六章第六章 运行时存储空间组织运行时存储空间组织 int gcd (int p,int q) if (p % q =0) return q; else return gcd (q, p % q) 【解答】 (1) 一般递归过程的

5、活动记录如图6-1所示。第六章第六章 运行时存储空间组织运行时存储空间组织 TOP SP临时单元内情向量局部变量形式单元参数个数老SPDISPLAY表TOPd个单元全局DISPLAY地址返回地址L图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过程*/返回指令为 TO

6、P=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; procedure PP(x: integer); begin: x:=5; x:=a+1第六章第六章 运行时存储空间组织运行时存储空间组织 end; begin a:= 2; PP(a); write(a) end.试用图表示ex调用PP(a)前后活动记录的过程。 【解答】 按照嵌套过程语言栈式实现方法，

7、ex调用PP(a)前后活动记录的过程如图6-2所示。第六章第六章 运行时存储空间组织运行时存储空间组织 PP_SPex_SPDISPLAY表形式参数X参数个数：1全局DISPLAY地址返回地址ex_SPaDISPLAY表ex_SP参数个数：0全局DISPLAY地址返回地址ex_SPPP_TOPPP_SPex_TOPex_SPPP的活动记录(调用PP(a)之后)ex的活动记录(调用PP(a)之前)图6-2 ex调用PP(a)前后的活动记录第六章第六章 运行时存储空间组织运行时存储空间组织 6.5 类PASCAL结构(嵌套过程)的程序如下，该语言的编译器采用栈式动态存储分配策略管理目标程序数据空间

8、。program Demo procedure A;procedure B; begin(*B*) 第六章第六章 运行时存储空间组织运行时存储空间组织 if d then B else A; end;(*B*)begin(*A*) Bend;(*A*) begin(*Demo*)A end.第六章第六章 运行时存储空间组织运行时存储空间组织 (1) 若过程调用序列为 DemoA； DemoAB； DemoABB； DemoABBA请分别给出这四个时刻运行栈的布局和使用的DISPLAY表；(2) 若该语言允许动态数组，编译程序应如何处置？如过程B有动态局部数组Rm:n，请给出B第一次激活时相应的

9、数据空间的情况。【解答】 (1) 运行栈及使用的DISPLAY表如图6-3所示。 第六章第六章 运行时存储空间组织运行时存储空间组织 Demo_spA_spB_spDemo_spA_spDemo_spA_spA的活动记录Demo的活动记录DISPLAY表B_spA_spDemo_spA_spDemo_spDISPLAY表DISPLAY表B的活动记录A的活动记录Demo的活动记录(1) DemoA(2) DemoABDemo_spDemo_spDISPLAY 表DISPLAY表A2_spB2_spA_spDemo_spA_spDemo_spA_spDemo_spDISPLAY表(3) DemoA

10、B1B2Demo_spDemo_spDemo_spDemo_spDISPLAY表DISPLAY表A2的活动记录A1的活动记录Demo的活动记录(4) DemoA1B1B2A2B2的活动记录B1的活动记录B2_spB1_spA1_spB2_spDISPLAY表DISPLAY表B1_spA_spB1的活动记录B2的活动记录A的活动记录Demo的活动记录B1_spB2_spB1_spA1_spA1_spA2_spA1_sp图6-3 运行栈及DISPLAY表示意图 第六章第六章 运行时存储空间组织运行时存储空间组织 (2) 由于一个过程在运行时所需的实际数据空间的大小，除可变数据结构(可变数组)那些部

11、分外，其余部分在编译时是完全可以知道的。编译程序处理时将过程运行时所需的数据空间分为两部分：一部分在编译时可确定其体积，称为该过程的活动记录；另一部分(动态数组)的体积需在运行时动态确定，称为该过程的可变辅助空间。当一个过程开始工作时，首先在运行栈顶部建立它的活动记录，然后再在这个记录之顶确定它所需的辅助空间。含有动态数组R的过程B在第一次激活时，相应的数据空间情况如图6-4所示。第六章第六章 运行时存储空间组织运行时存储空间组织 B的活动记录A_sp数组R的内情向量B_spA_spDemo_spA_spDemo_spA的活动记录Demo的活动记录DISPLAY表B_spDemo_sp数组R数

12、组R的内情向量B_spA_spDemo_spA_spDemo_spB的活动记录A的活动记录Demo的活动记录A_spB_spDemo_spB的可变辅助空间(a)(b) DISPLAY表DISPLAY表 图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=i-1; return(

13、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)改为1后，输出结果为1而不是120，这主要是与编译的代码生成策略有关。对表达式(i + abs(1)* fact( )，因为两个子表达式(i+abs(1)和fact( )都有函数调用，而编译器的编译则是先产生左子表达式的代码，后产生右子表达式的代码。也即，每次递归调用时，(i + abs(1)* fact( )中的(i+abs(1)的值都先于fact算出。但是，当abs(