8目标程序运行时的存储组织解析.ppt

（ａ） 图8.7 简单栈式存储分配 void p(int m) { …… if (m 1) { q(m-1); x- -; p(m-1); } …… } main() { p(x); } int x = 2; void p(int); void q(int n) { …… p(n); …… } 考虑下面的一种简单的C程序结构： 8.3.1 简单栈式存储分配 （ａ） 图8.7 简单栈式存储分配 （ｃ）第三次对p进行调用时的环境 自由空间 p的活动记录 main的活动记录 全局 / 静态数据区 SP TOP 主函数main第一次调用p的情况 main() { p(x); } 8.3.1 简单栈式存储分配 （ａ） 图8.7 简单栈式存储分配 SP TOP 在主函数调用p，在p中调用函数q,函数q再调用函数p的情况 自由空间 p的活动记录 q的活动记录 p的活动记录 main的活动记录 全局 / 静态数据区 8.3.1 简单栈式存储分配 （ａ） 图8.7 简单栈式存储分配 void p(int m) { …… if (m 1) { q(m-1); x- -; p(m-1); } …… } main() { p(x); } int x = 2; void p(int); void q(int n) { …… p(n); …… } 8.3.1 简单栈式存储分配 （ａ） 图8.7 简单栈式存储分配 SP TOP 函数q执行完毕后，函数p对自己调用的情况 自由空间 p的活动记录 p的活动记录 main的活动记录 全局 / 静态数据区 注意：在函数中定义的静态变量必须存放在全局／静态区中，不能在函数的活动记录中分配。 8.3.1 简单栈式存储分配 8.3.2 嵌套过程语言的栈式存储分配 如果在语言中允许过程嵌套定义(如Pascal语言)，因为没有提供非局部变量的引用，所以前面所说的两种存储分配策略都不能使用了。这时我们需要设计一种新的存储分配策略。 8.3.2 嵌套过程语言的栈式存储分配 现在我们分析的对象是允许过程嵌套定义的语言，因此会常常用到过程定义的层数，我们始终假定主程序的层数为，因此主程序为第０层过程。 如过程Ｑ是在层数为i的过程Ｐ内定义，并且Ｐ是包围Ｑ的最小过程，那么Ｑ的层数就为i+1。这时我们把Ｐ称为Ｑ的直接外层过程，而Ｑ称为Ｐ的内层过程。 8.3.2 嵌套过程语言的栈式存储分配 由于过程的定义是嵌套的，一个过程可以引用包围它的任一外层过程所定义的变量，又由于过程允许递归调用，因此一个过程在引用非局部变量时必须清楚地知道它的每个外层过程的最新活动记录的位置。 8.3.2 嵌套过程语言的栈式存储分配 跟踪外层活动记录的方法有很多，这里我们介绍一种常用的办法：通过嵌套层次显示表进行跟踪。 嵌套层次显示表(Display)实质上是一个指针数组，也可以看作是一个小栈，自顶向下依次存放着现行层、直接外层、……、第０层的最新活动记录的基地址，它是建立过程的活动记录的同时建立起来的。 8.3.2 嵌套过程语言的栈式存储分配 例如，令过程R的外层为Q, Q的外层为主程序P，则在过程R运行时的Display表的内容为： R的现行活动记录始址(SP的现行值) Q的最新活动记录的地址 P的活动记录的地址 2 1 0 8.3.2 嵌套过程语言的栈式存储分配 由于过程的层数也可以静态确定，因此每个过程的Display表的大小在编译时就可以确定。这样，由一个非局部变量说明所在的静态层数和相对于活动记录的相对地址，就可以得到 绝对地址＝Display[静态层数]＋相对地址 8.3.2 嵌套过程语言的栈式存储分配 为了便于组织存取和简化处理手续， 通常把Display表作为活动记录的一部分置于形式单元的上端。见下图 8.3.2 嵌套过程语言的栈式存储分配 临时单元 内情向量 简单变量 Display 形式单元 参数个数 全局Display地址 返回地址 老SP d 3 2 1 0 第K层SP … 最外层过程SP 主程序SP d+0 1 k Sp Top program P; var a,b: integer; procedure Q(x:integer) var i:integer; procedure R(y:integer) var c,d:integer; begin: …… if y0 then R(y-1); c=