1、第8章 目标程序运行时的存储组织,编译程序需进行目标程序运行环境的设计和数据空间的分配。,本章主要介绍：,静态存储分配策略,动态存储分配策略,8.1 概述,我们知道，编译程序的最终目的是将源程序翻译成等价的目标程序，为了达到此目的，编译程序除了对源程序进行词法分析、语法分析和语义分析外，在生成目标代码之前，还必需进行目标程序运行环境的设计和数据空间的分配。,所谓运行时的环境是指目标计算机的寄存器和存储器的结构，以及用来管理存储器并保存指导执行过程所需要的信息。,一般来讲，如编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。,8.1
2、 概述,数据空间包括用户定义的各种类型的数据对象所需的存储空间、调用过程所需的连接单元和组织输入/输出所需的缓冲区及保留中间结果和传递参数所需的临时单元等。,因此运行时的存储空间通常被划分成：目标区、静态数据区、栈区和堆区，如下图所示。,8.1 概述,其中，目标代码区用于存放生成的目标代码，它的长度是固定的，即能在编译时确定，静态数据区用于存放编译时所能确定占用空间大小的数据，堆、栈区用于存放可变数据以及管理过程活动的控制信息。,8.1 概述,程序设计语言关于名字的作用域和生成期的定义规则决定了分配目标程序数据空间的基本策略。,在大部分现有编译中目标程序数据空间的分配策略有：,8.1 概述,静
3、态存储分配策略,分配策略,动态存储分配策略,栈式动态存储分配,堆式动态存储分配,8.1 概述,静态存储分配策略,编译时对源程序中各数据项分配固定的存储空间，运行时始终不变。,动态存储分配策略,运行阶段动态地为源程序中的数据项分配存储空间。,8.1 概述,(1) 栈式动态存储分配,用一个栈作为动态分配的存储空间。 运行时，每当调用一个子程序(过程)，所需存储空间就动态地分配于栈顶，退出时释放所占用的空间。,(2) 堆式动态存储分配,运行时把存储区组织成堆，以便用户动态地申请或释放存储空间。,8.1 概述,8.2 静态存储分配,静态存储分配,编译阶段对源程序中各数据项分配固定的存储空间，运行时始终
4、不变。,如果在编译时能确定目标程序运行中所需要的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，并确定每个数据项的存储位置（单元地址），则称这种分配策略为静态存储分配。,对语言要求,（1）程序中每一个数据对象的大小在编译阶段能够确定（即不允许有可变体积的数据如可变数组等）；,（2）程序运行过程中的给定时刻，每一个数据对象只允许存在一个实例（即不允许有递归等）；,8.2 静态存储分配,（3）所有数据的性质是完全确定（即不允许有须在运行时动态确定性质的名字）。,像FORTRAN77是满足上述特点的语言。,8.2 静态存储分配,FORTRAN77采用的是静态存储分配，它的程序是段结构的
5、，整个程序由主程序段和若干个子程序段组成，各程序段中定义的名字一般彼此独立，它的每个数据名所需的存储空间大小都是常量，并且不允许递归调用。这样，整个程序所需数据空间的总量在编译时就能完全确定，从而每个数据名的地址就可静态进行分配。,8.2 静态存储分配,下面给出一个FORTRAN77的程序例子,(1) PROGRAM CNSUME(2) CHARACTER * 50 BUF (3) INTEGER NEXT(4) CHARACTER C, PRDUCE(5) DATA NEXT / 1 /, BUF / /(6) 6 C=PRDUCE( )(7) BUF( NEXT : NEXT )=C(8)
6、 NEXT=NEXT+1(9) IF ( C .EN. ) GOTO 6(10) WRITE ( *, (A)BUF(11) END,8.2 静态存储分配,(12) CHARACTER FUNCTION PRDUCE( )(13) CHARACTER * 80 BUFFER (14) INTEGER NEXT(15) SAVE BUFFER , NEXT(16) DATA NEXT / 81 /(17) IF ( NEXT .GT. 80 ) THEN(18) READ ( *, (A)BUFFER(19) NEXT=1(20) END IF(21) PRDUCE=BUFFER( NEXT :
7、 NEXT )(22) NEXT=NEXT+1(23) END,8.2 静态存储分配,代码,静态数据,该图描述了程序中局部变量的静态存储位置。,8.2 静态存储分配,动态存储分配策略,运行阶段动态地为源程序中的数据项分配存储空间。,(1) 栈式动态存储分配,运行时，每当调用一个子程序(过程)，所需存储空间就动态地分配于栈顶，退出时释放所占用的空间。,用一个栈作为动态分配的存储空间。,8.2 静态存储分配,8.3 动态存储分配,(2) 堆式动态存储分配,运行时把存储区组织成堆，以便用户动态地申请或释放存储空间。,如果一个程序设计语言允许递归调用、可变数组或每次调用都要重新分配局部变量，那么，就需
8、要采用动态存储分配策略。因为对于这种情况，编译程序无法知道它在运行时需要多大的存储空间，它所需要的存储空间的大小需待运行时动态地确定。,8.3 动态存储分配,为讨论方便，引入术语活动记录。过程的活动记录是一段连续的存储区，用以存放过程的一次执行所需要的信息。,活动记录至少应该包括以下几个部分,8.3 动态存储分配,1. 返回地址保存该被调过程返回后的地址。,2. 动态链指向调用该过程前的最新活动记录地址(即前一个活动记录的地址)。,SP,TOP,8.3 动态存储分配,3. 静态链指向静态直接外层最新活动记录地址的指针，用来访问非局部数据。,SP,TOP,8.3 动态存储分配,4. 形式单元存放
9、相应的实在参数的地址或值。,5. 局部变量一个子程序(过程)的局部变量。,SP,TOP,8.3 动态存储分配,6. 临时变量比如计算表达式过 程中需存放中间结果 用的临时值单元。,SP,TOP,连接数据,8.3 动态存储分配,SP总是指向现行过程活动记录的起始地址,SP,TOP,TOP则始终指向已占用的栈顶单元。,8.3 动态存储分配,8.3.1 简单栈式存储分配,对于没有分程序结构，过程定义不允许嵌套但允许过程递归调用的语言，我们可以采用一种简单的栈式存储分配策略。,简单栈式存储分配,C语言就是满足上述特点的一种语言。,C语言其过程的活动记录一般采用如图所示结构。,图中使用两个指针( SP和
10、TOP)指示栈最顶端的数据区， SP总是指向现行过程活动记录的起点,SP,TOP,8.3.1 简单栈式存储分配,TOP则始终指向已占用的栈顶单元。,SP,TOP,8.3.1 简单栈式存储分配,SP,TOP,由图可知，过程的每一个局部变量或形参在活动记录中的相对地址是确定的，因此可以知道程序运行时，变量和形参在栈上的绝对地址是：,绝对地址 活动记录基地址(SP) 相对地址,8.3.1 简单栈式存储分配,SP,TOP,相对地址：相对于活动记录起点的地址，它在编译时可完全确定。,对任何局部变量x的引用可表示为变址访问xsp, 此处x为变量x的相对地址。xsp表示地址为x+sp即x所在地址),8.3.
11、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);,考虑下面的一种简单的C程序结构：,8.3.1 简单栈式存储分配,（）,图8.7 简单栈式存储分配,（）第三次对p进行调用时的环境,SP,TOP,主函数main第一次调用p的情况,main() p(x); ,8.3.1 简单栈式存储分配,（）,图8.7 简单栈式存储分配,SP,TOP,在主函数调用p，在p中调用函数q,函数q再调用函数p的情况,
12、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对自己调用的情况,注意：在函数中定义的静态变量必须存放在全局静态区中，不能在函数的活动记录中分配。,8.3.1 简单栈式存储分配,8.3.2 嵌套过程语言的栈式存储分配,如果在语言中允许过程嵌套定义(如Pascal语言)，因为没有提供
13、非局部变量的引用，所以前面所说的两种存储分配策略都不能使用了。这时我们需要设计一种新的存储分配策略。,8.3.2 嵌套过程语言的栈式存储分配,现在我们分析的对象是允许过程嵌套定义的语言，因此会常常用到过程定义的层数，我们始终假定主程序的层数为，因此主程序为第层过程。如过程是在层数为i的过程内定义，并且是包围的最小过程，那么的层数就为i+1。这时我们把称为的直接外层过程，而称为的内层过程。,8.3.2 嵌套过程语言的栈式存储分配,由于过程的定义是嵌套的，一个过程可以引用包围它的任一外层过程所定义的变量，又由于过程允许递归调用，因此一个过程在引用非局部变量时必须清楚地知道它的每个外层过程的最新活动
14、记录的位置。,8.3.2 嵌套过程语言的栈式存储分配,跟踪外层活动记录的方法有很多，这里我们介绍一种常用的办法：通过嵌套层次显示表进行跟踪。,嵌套层次显示表(Display)实质上是一个指针数组，也可以看作是一个小栈，自顶向下依次存放着现行层、直接外层、第层的最新活动记录的基地址，它是建立过程的活动记录的同时建立起来的。,8.3.2 嵌套过程语言的栈式存储分配,例如，令过程R的外层为Q, Q的外层为主程序P，则在过程R运行时的Display表的内容为：,2,1,0,8.3.2 嵌套过程语言的栈式存储分配,由于过程的层数也可以静态确定，因此每个过程的Display表的大小在编译时就可以确定。这样
15、，由一个非局部变量说明所在的静态层数和相对于活动记录的相对地址，就可以得到,绝对地址Display静态层数相对地址,8.3.2 嵌套过程语言的栈式存储分配,为了便于组织存取和简化处理手续， 通常把Display表作为活动记录的一部分置于形式单元的上端。见下图,8.3.2 嵌套过程语言的栈式存储分配,d,3,2,1,0,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);
16、c=d+y;end Rbeginif b 0 then R(b) else Q(b);end Q,procedure S;var i,c,d:integer;beginc:=a+i+d;Q(c);end S begina:=0;b:=2;S; end P,8.3.2 嵌套过程语言的栈式存储分配,对于这个程序，下面给出P S Q R 其运行时的Display的活动情况：,Display,8.3.2 嵌套过程语言的栈式存储分配,对于这个程序，下面给出 P S Q Q R 其运行时的Display 的活动情况：,Display,Display表依次指向现行层、直接外层、 、第层的最新活动记录的基地址
17、。,8.3.2 嵌套过程语言的栈式存储分配,对于这个程序，下面给出 P S Q R R 其运行时的Display 的活动情况：,Display,Display表依次指向现行层、直接外层、 、第层的最新活动记录的基地址。,本章小结,静态存储分配策略,分配策略,动态存储分配策略,栈式动态存储分配,堆式动态存储分配,1. 目标程序数据空间的分配策略,本章小结,静态存储分配策略,编译时对源程序中各数据项分配固定的存储空间，运行时始终不变。,动态存储分配策略,运行阶段动态地为源程序中的数据项分配存储空间。,本章小结,(1) 栈式动态存储分配,用一个栈作为动态分配的存储空间。 运行时，每当调用一个子程序(过程)，所需存储空间就动态地分配于栈顶，退出时释放所占用的空间。,(2) 堆式动态存储分配,运行时把存储区组织成堆，以便用户动态地申请或释放存储空间。,本章小结,嵌套层次显示表(Display)实质上是一个指针数组，也可以看作是一个小栈，自顶向下依次存放着现行层、直接外层、第层的最新活动记录的基地址，它是建立过程的活动记录的同时建立起来的。,2. 嵌套层次显示表和活动记录,本章小结,例如，令过程R的外层为Q, Q的外层为主程序P，则在过程R运行时的Display表的内容为：,2,1,0,含Display表的过程的活动记录如下图：,本章小结,d,3,2,1,0,d+0,1,k,Sp,Top,
