一、概述
静态分配策略：
编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变
栈式存储分配：
运行时把存储器作为一个栈进行管理，每当调用一个过程，它所需的存储空间就动态地分配于栈顶，一旦退出，它所占空间就予以释放。
堆式存储分配：
在运行时把存储器组织为堆，允许用户动态申请和归还存储空间，凡申请者从堆中分给一块，凡释放者退回给堆。
二、栈式存储分配的实现
2.1 活动举例
float fac(int n){
float f;
if (n==0) f=1;
else f=n*fac(n-1);
return f;
}
void main( ){
int i=2;
printf(“%f”,fac(i));
} 复制
执行时过程调用的顺序：
2.2 一些定义
2.2.1 活动
一个过程的活动：是指该过程的一次执行，每次执行一个过程体，产生该过程体的一个活动
一个活动的生存期：是指从该过程体的第一步操作到最后一步操作之间的操作序，包括执行该过程时调用其它过程花费的时间
名字说明作用域：一个说明在程序里能起作用的范围
2.2.2 活动记录（AR）
含义：存储管理过程活动所 需信息的一块连续的存储空间
作用：当调用过程时，将在栈顶为过程此次活动分配活动记录
SP 指向现行过程（即最新进入工作的那个过程)的活动记录在栈里的首地址，用于访问局部数据。
2.3 简单栈式存储分配举例
对语言的限制：没有分程序结构、过程定义不许嵌套、允许过程的递归调用
全局数据说明
main（）
{ main中的数据说明
…Q();…}
void R()
{ R中的数据说明
…}
void Q()
{ Q中的数据说明
…R();…} 复制
2.4 嵌套过程语言的栈式实现
对语言的限制：允许嵌套定义、允许递归调用
program P；
var a,x:integer；
-----------------------------Q
procedure Q(b:integer);
var i:integer;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%R
procedure R(u:integer;var v:integer);
var c,d:integer;
begin … if u=l then R(u+1,v)Q // R调用R
v:=(a+c)*(b-d); …
end {R}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%R
begin … R(1,x);… end {Q} // Q调用R
------------------------------Q
*******************************S
procedure S;
var c,i:integer;
begin a:=1;Q(c);… end {S} //S调用Q
*******************************S
begin a:=0;S;… end {P} // P调用S 复制
执行顺序：P->S->Q->R->R(递归)
活动记录：
静态链举例：
主程序的静态链结点值为主程序AR的首地址SP。
存在问题：当过程的嵌套层数过多时，沿静态链要经过若干结点才可找所需的非局部量
2.5 display表
2.5.1 定义
为解决嵌套层数多时寻找效率低的问题，引入display表（过程嵌套层次显示表）的概念。
注意：
c
、
a
这些变量的所在层次以及偏移量（相对数）都在词法分析时存在符号表中，可以直接查询。
之所以要记录每一层的最新AR首地址，是因为，同一层的某个局部变量可能会被改变，只有最新的活动记录中的才是当前值。
2.5.2 实现
主要有两种方式，外置display表和内嵌display表。
内嵌display表：放入AR中，作为AR的一部分。
注意：主程序无 全局display ,其display表占用AR中 全局display 的位置,值为0(主程序AR首地址SP)
例： 现行过程中引用k层变量x，可用以下两条指令获得：
LD R1,(d+k)[SP]
获得k层AR首地址。
原理：首先获取当前AR中display的地址d，那么第k层AR首地址为d+k，加上基地址
[sp]
就是第k层AR首地址。
LD R2,x[R1]
把x值传递给R2。
2.5.3 举例
动态链： 调用者活动记录首地址，即栈中上一个活动记录首地址。
静态链： 直接外层最新AR的首地址（这里由于display表的存在，所以填全局display）。
全局display： 调用者活动记录 display表的首地址。
display表： 存放每一层最新活动记录的首地址 ，先获取调用者的活动记录display表，在此基础上进行更新，如果当前活动记录在第 i 层，则display有 i+1 层。
- P活动记录：
- 编号1：存动态链，由于是第一个活动记录，所以填0
- 编号2：返回地址
- 编号3：全局display，由于是主程序的活动记录，没有全局display，该位置填写display表，只有一项，即第0层活动记录首地址0。
- 编号4-5 ：当前活动记录的局部变量
- S活动记录：
- 编号5：动态链，上一个活动记录首地址，即P首地址 0 。
- 编号6：返回地址
- 编号7：全局display，填写调用者的display表地址，即P的display表地址0
- 编号9-10：S的display表，先调用P的display表，再更新，包括第0层和第1层最新活动记录首地址（0和5）
- Q活动记录：
- 编号13：动态链，填调用者活动记录首地址5。
- 编号15：全局display，填调用者display表首地址9。
- 编号16：填形参个数
- 编号17：填具体形参
- 编号18-19：Q的display表，先调用调用者S的display表，再进行更新，内容为每一层的最新活动记录首地址（0和13），因为第1层最新活动为Q自身，活动变量首地址为13。
- R1活动记录：
- 编号21：动态链，调用者Q活动变量首地址13。
- 编号23：全局display，填调用者Q的display表首地址18。
- 编号27-29：R1的display表，先获得Q的display表，再更新，由于R1在第2层，所以display表为0、13、21。
- 后面同上。