UJ P
6.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)前后活动记录的过程。
Demo的活动记录
(4) Demo→A 1→B→A 1→B 2 2
图6-3 运行栈及DISPLAY表示意图
第六章 运行时存储空间组织 (2) 由于一个过程在运行时所需的实际数据空间 的大小，除可变数据结构(可变数组)那些部分外，其 余部分在编译时是完全可以知道的。编译程序处理时 将过程运行时所需的数据空间分为两部分：一部分在 编译时可确定其体积，称为该过程的活动记录；另一
示表。
第六章 运行时存储空间组织
也即，每当进入一个过程后，在建立它的活动记录区的同时 也建立一张DISPLAY表，它自顶而下每个单元依次存放着现行层、
直接外层等，直至最外层(主程序层)等每一层过程的最新活动记
录的起始地址。 6.3 (1) 写出实现一般递归过程的活动记录结构以及过程 调用、过程进入与过程返回的指令； (2) 对以return(表达式)形式(这个表达式本身是一个递归 调用)返回函数值的特殊函数过程，给出不增加时间开销但能节省 存储空间的实现方法。假定语言中过程参数只有传值和传地址两
3[TOP]=SP+d 4[TOP]=n JSR P
第六章 运行时存储空间组织 过程进入指令为 SP=TOP+1 1[SP]=返回地址 TOP=TOP+L 建立DISPLAY
P；
返回指令为 TOP=SP-1 SP=0[SP] X=2[TOP] UJ 0[X]
/*执行P过程*/
第六章 运行时存储空间组织 (2) 对于return后的直接递归情况，可简化为 (i+3)[SP]=Ti 或 (i+3)[SP]=addr [Ti]
种形式，为便于理解，举下例说明这种特殊的函数调用：
第六章 运行时存储空间组织 int gcd (int p,int q) {
if (p % q ==0) return q;
else return gcd (q, p % q) } 【解答】 (1) 一般递归过程的活动记录如图6-1 所示。
第六章 运行时存储空间组织
请分别给出这四个时刻运行栈的布局和使用的 DISPLAY表； (2) 若该语言允许动态数组，编译程序应如何处 置？如过程B有动态局部数组R[m:n]，请给出B第一次 激活时相应的数据空间的情况。 【解答】 (1) 运行栈及使用的DISPLAY表如图6-3 所示。
第六章 运行时存储空间组织
B_sp
…
DISPLAY表 B_sp
A_sp Demo_sp
… …
…
B的活动记录
DISPLAY表 A_sp Demo_sp
A_sp Demo_sp
… …
A的活动记录
DISPLAY表 Demo的活动记录 A_sp
A_sp Demo_sp
… …
A的活动记录
Demo_sp (1) Demo→A
Demo的活动记录
(2) Demo→A→B
(i+1)* fact( )中的(i+1)值都后于fact计算。也即，第 一 次 递 归 调 用 得 到 (i+1)* fact ， 第 二 次 递 归 调 用 得 到 (i+1)*fact，第三次递归调用仍得到(i+1)*fact，…，直到 第五次递归调用还是得到(i+1)* fact，而此时fact为1，i为 0。因此，每次递归所求实际上都是1 * fact，最终得到输出 结果为1。
TOP 临时单元 内情向量 局部变量 DISPLAY表 形式单元 参数个数 全局DISPLAY地址 返回地址 SP TOP 老SP d个单元 L
图6-1 递归过程的活动记录
第六章 运行时存储空间组织 过程调用指令为 (i+4)[TOP]=Ti 或 (i+4)[TOP]=addr [Ti]
1[TOP]=SP
【解答】
按照嵌套过程语言栈式实现方法，ex
调用PP(a)前后活动记录的过程如图6-2所示。
第六章 运行时存储空间组织
PP_TOP PP_SP ex_SP PP的活动记录 (调用PP(a)之后)
DISPLAY表 形式参数X
参数个数：1 全局DISPLAY地址 返回地址 PP_SP ex_TOP ex_SP a DISPLAY表 ex_SP 参数个数：0 全局DISPLAY地址 返回地址 ex_SP ex_SP
第六章 运行时存储空间组织 (3) 堆 式 动 态 分 配 申 请 和 释 放 存 储 空 间 遵 守 原则。
a. 先请先放
c. 后请先放 作有 。
b. 先请后放
d. 任意
(4) 栈式动态分配与管理在过程返回时应做的工 a. 保护SP b. 恢复SP
c. 保护TOP
d. 恢复TOP
第六章 运行时存储空间组织 (5) 如果活动记录中没有DISPLAY表，则说明 a. 程序中不允许有递归定义的过程 。
部分(动态数组)的体积需在运行时动态确定，称为该
过程的可变辅助空间。当一个过程开始工作时，首先 在运行栈顶部建立它的活动记录，然后再在这个记录
之顶确定它所需的辅助空间。含有动态数组R的过程B
在第一次激活时，相应的数据空间情况如图6-4所示。
第六章 运行时存储空间组织
数组 R
…
B的可变辅助空间
运行中，一个过程Q可能引用它的任一外层过程P的最新活
动记录中的某些数据。因此，过程Q运行时必须知道它的 所有(静态)外层过程的最新活动记录的地址。由于允许递
归和可变数组，这些外层过程的活动记录的位置也往往是
变迁的。因此，必须设法跟踪每个(静态)外层的最新活动 记录的位置，而完成这一功能的就是DISPLAY嵌套层次显
b. 程序中不允许有嵌套定义的过程
c. 程序中既不允许有嵌套定义的过程，也不允许有递 归定义的过程 d. 程序中允许有递归定义的过程，也允许有嵌套定义 的过程 【解答】 (1) b (3) d (2) a (4) b (5) b
第六章 运行时存储空间组织 6.2 何谓嵌套过程语言运行时的DISPLAY表？它的作 当过程定义允许嵌套时，一个过程在运行 用是什么？ 【解答】 中应能够引用在静态定义时包围它的任一外层过程所定义 的变量或数组。也就是说，在栈式动态存储分配方式下的
static int i=5;
if (i==0){ return(1); } else { i=i-1; return((i+abs(1))*fact( ));} }
第六章 运行时存储空间组织 main( ) { printf ("factor or 5=%d\n",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。
第六章 运行时存储空间组织
第六章 运行时存储空间组织
6.1 完成下列选择题： (1) 过程的DISPLAY表中记录了 a. 过程的连接数据 。
b. 过程的嵌套层次
c. 过过程P1调用P2时，连接数据不包含 a. 嵌套层次显示表 c. 返回地址 b. 老SP d. 全局DISPLAY地址
第六章 运行时存储空间组织
将abs(1)改为1后，输出结果为1而不是120，这主要是与 编译的代码生成策略有关。对表达式(i + abs(1))* fact( )， 因为两个子表达式(i+abs(1))和fact( )都有函数调用，而编 译器的编译则是先产生左子表达式的代码，后产生右子表达 式的代码。也即，每次递归调用时，(i + abs(1))* fact( ) 中的(i+abs(1))的值都先于fact算出。但是，当abs(1)改为1 后，左子表达式就没有函数调用了，于是编译器就先产生右 子表达式的代码。每次递归调用时，
……
B2的活动记录
B1_sp DISPLAY表 A_sp Demo_sp B1_sp
… …
B1_sp A1_sp Demo_sp
……
B1的活动记录
DISPLAY表 A_sp Demo_sp
A_sp Demo_sp
…
A1_sp Demo_sp
…
A1的活动记录
Demo_sp (3) Demo→A→B 2 1→B
A_sp Demo_sp
…
A_sp Demo_sp
…
A的活动记录
Demo的活动记录
(a)
图6-4 带动态数组的运行栈示意 (a) 动态数组R空间分配之前；(b) 动态数组R空间分配之后
第六章 运行时存储空间组织 6.6 下 面 程 序 的 结 果 是 120 。 但 是 如 果 把 第 5 行 的 abs(1)改成1的话，则程序结果为1。试分析为什么会有这 种不同的结果。 int fact( ) {
数组R的 内情向量
…
数组 R 的 内情向量 B的活动记录 DISPLAY表 B_sp A的活动记录 DISPLAY表 Demo的活动记录 A_sp Demo_sp (b)