第八章 目标程序运行时的组织
8.1 概述
8.2 数据表示
8.3 目标程序运行时的栈式存储组织
8.4 参数传递
8.5 堆式存储概述概述 -代码生成解决语义 gap
高级语言支持的概念
Type value expression
Variable procedure
Function parameters
目标机支持的概念
bits bytes words
Registers
Stack address
Routine(sub routine)
概述代码生成前如何安排目标机资源运行时组织的几个问题数据表示 -如何在目标机中表示每个源语言类型的值表达式求值 -如何组织表达式的计算存储分配 -如何组织不同作用域变量的存储过程实现 -如何以例程实现过程，函数，参数传递概述任务：编译程序对目标程序运行时的组织（设计运行环境和分配存储） 如 通常存储区布局可为：
目标代码区静态数据区
Stack
heap
运行环境和存储分配设计分析逻辑阶段：在目标代码生成前，作准备实质：
关联（ Binding）
将源程序的文本? 程序运行动作的实现源文件中的名字 N? 运行时的存储 S
在语义学中，使用术语 environment函数表示
env,N→S (N 到 S的映射 )
静态文本中 运行时动作及为实现其动作的准备
（与运行时数据对象的表示有关）
过程定义过程名 执行过程体过程体 控制数据对象的分配，为执行过程体使用源文本中同样的名字 目标程序中不同的数据空间因为一个过程可以是递归的，
这时同一个名字在不同的时间可能代表不同的存储单元决定运行管理复杂程度的因素 ——源语言本身
1,允许的数据类型的多少
2．语言中允许的数据项是 静态确定动态确定
3．程序结构 决定名字的作用域的规则和结构
A,段结构 (Fortran)
B,过程定义不嵌套，只允许过程递归调用
C,分程序结构分程序嵌套过程定义嵌套
4存储类别的多少 Global
Static
Local
dynamic
术语
静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是
“静态”确定的。
动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。
例 procedure A(m,n:integer);
begin real z;
array B[m:n];
begin
·
·
·
end;
end;
数据表示 各种数据对象的存储分配数据对象的属性
name 名字，名称
type 类型
location 内存地址
value 值
component 成分数据表示简单变量：
char,1 byte
integers,2 or 4 bytes
floats,4 to 16 bytes
booleans,1 bit (but usually 1 byte)
指针,unsigned integers
一维数组：一块连续的存储区多维数组：一块连续的存储区，按行存放结构（记录）：把所有域（ field)存放在一块连续的存储区对象：类的实例变量象结构的域一样存放在一块连续的存储区，
但方法（成员函数）不存在该对象里指令：
目标程序运行时的存储组织存储分配策略：
简单的栈式分配方案嵌套过程的栈式分配方案分程序结构的存储分配方案堆式存储静态存储分配动态存储分配 ——栈式堆式术语 -过程活动记录 AR:
为说明方便，假定 源 程序是由过程组成,运行时称作过程的激活。
一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区 （块）叫做一个活动记录 AR或 frame 帧一般这个段要记录：
l临时值，如计算表达式时的中间工作单元。
l局部变量 （数据）
l保存运行过程前的状态 （返回地址，寄存器值 …… ）
l存取链 （可选） 对于非局部量的引用。
l控制链 （可选） 指向调用者的活动记录，释放栈。
l实参 （形式单元）
l返回值 （对函数） （有时可使用寄存器存放返回值）
简单的栈式分配方案
程序结构特点,过程定义不嵌套，过程可递归调用，含可变数组 ;
例,main
全局变量的说明
proc R
……
end R;
proc Q
……
end Q;
主程序执行语句
end main
Mai n----> Q----> R Mai n---> Q----> Q
T O P -----> R 的活动记录 Q 的活动记录
S P - - - - - - >
Q 的活动记录 Q 的活动记录主程序全局 主程序全局数据区 数据区
T O P - - - - > 临时工作单元局部简单变量局部数组的内情向量保存运 行过程前的状态 （返回地址，寄存器值）
实参 （形式单元）和参数个数
S P - - - - - > 控制链 （老 SP ）
TOP R 的数组区
SP R 的活动记录
Q 的活动记录主程序全局数据区嵌套过程语言的栈式分配方案
l主要特点,
（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，
数组或过程等）。
（实现）一个过程执行时可以引用它的任一外层过程的最新活动记录中的某些数据。
关键技术：解决对非局部量的引用（存取）。
设法跟踪每个外层过程的最新活动记录
AR的位置。
跟踪办法：
1,用静态链（如 PL/0的 SL）。
2,用嵌套层次显示表 DISPLAY。
const a=10;
var b,c;
procedure p;
begin
c:=b+a;
end;
begin
read(b);
while b#0 do
begin
call p;
write(2*c);
read(b);
end
end.
( 0) jmp 0 8 转向 主程序入口
( 1) jmp 0 2 转向 过程 p入口
( 2) int 0 3 过程 p入口,为过程 p开辟空间
( 3) lod 1 3 取变量 b的值到栈顶
( 4) lit 0 10 取常数 10到栈顶
( 5) opr 0 2 次栈顶与栈顶相加
( 6) sto 1 4 栈顶值送变量 c中
( 7) opr 0 0 退栈并返回调用点 (16)
( 8) int 0 5 主程序入口开辟 5个栈空间
( 9) opr 0 16 从命令行读入值置于栈顶
(10) sto 0 3 将栈顶值存入变量 b中
(11) lod 0 3 将变量 b的值取至栈顶
(12) lit 0 0 将常数值 0进栈
(13) opr 0 9 次栈顶与栈顶是否不等
(14) jpc 0 24 等时转 (24)（ 条件不满足转 ）
(15) cal 0 2 调用过程 p
(16) lit 0 2 常数值 2进栈
(17) lod 0 4 将变量 c的值取至栈顶
(18) opr 0 4 次栈顶与栈顶相乘 (2*c)
(19) opr 0 14 栈顶值输出至屏幕
(20) opr 0 15 换行
(21) opr 0 16 从命令行读取值到栈顶
(22) sto 0 3 栈顶值送变量 b中
(23) jmp 0 11 无条件转到循环入口 (11)
(24) opr 0 0 结束退栈目标代码解释执行时数据栈的布局（运行栈的存储分配）
每个过程的 AR有
3个联系单元：
– SL,静态链,指向 定义 该过程的 直接外过程
（或主程序）运行时 最新 数据段的基地址 。
– DL,动态链,指向 调用 该过程前正在运行过程的数据段基地址。
– RA,返回地址,记录调用该过程时 目标程序的 断点,即调用过程指令的下一条指令的地址。
局部变量中间结果目标代码的解释执行 运行栈
S
M调用过程 P
RA
DL
SLb
.
,
t
t
b
P
M
解决对非局部量的引用（存取）
用 Display表
Display表 ---嵌套层次显示表当前激活过程的层次为 K，它的 Display表含有 K+1个单元，依次存放着现行层，直接外层 … 直至最外层的每一过程的最新活动记录的基地址例：
pro gr am m ai n(i,0); 程序结构图
pro c R ( c,d);
R
end /* R */
pro c P (a) ; 主
p ro c Q (b);
P Q ca ll R
R( x,y);
end /* Q* / ca ll Q
Q(z ); ca ll P
end /* P*/
ca ll R
P （ W ）；
R （ U,V ）；
end /* m ai n*/
用 Display表的方案
(1)主程序 --->(2)P--->(3)Q--->(4)R
主程序的活动记录d[0] sp
display
top
（ 1）
P 的活动记录主程序的活动记录
d[1]
d[0]
display sp
top
（ 2）
用 Display表的方案
主程序 --->P--->Q--->R
R 的活动记录
Q 的活动记录
P 的活动记录主程序的活动记录
Q 的活动记录
P 的活动记录主程序的活动记录
display
d[2]
d[1]
d[0]
d[1]
d[0]
display
sp
top
top
sp
（ 3） （ 4）
DISPLAY表的维护和建立
不放在过程的活动记录中
放在过程的活动记录中
,
,
,
临时变量数组内情向量临时变量
d DISPL AY
4 形式单元
,
,
,
3 参数个数
2 全局 DISPLAY
地址
1 返回地址
0 老 SP
当过程的层次为 n，
它的 display为 n+1个值。
一个过程被调用时，
从调用过程的
DISPLAY表中自下向上抄录 n个 SP值，再加上本层的 SP值。
全局 DISPLAY地址栈式存储组织 review
数据空间的存储管理：栈式存储分配
– 过程 (函数 )的活动记录：是一段连续的存储区，存放过程 (函数 )的一次执行所需要的信息。
– 过程 (函数 )活动记录的内容：联系单元（静态链,动态链和返回地址）、局部变量和临时变量栈式存储分配的实现：
设置两个指针：栈顶指针 Top和当前活动记录指针 SP；
调用一个过程 (函数 )前，先把过程 (函数 )的参数压入数据栈；
在数据栈中为过程 (函数 )的活动记录分配空间；
填写联系单元内容；
执行过程 (函数 )代码；
过程 (函数 )返回前，根据当前 SP恢复 Top指针，根据动态链恢复 SP为外层过程 (函数 )的活动记录起始地址，根据返回地址得到下一条指令地址；
继续执行外层过程 (函数 )代码。
过程的活动记录 (AR)
C PL0
临时工作单位 √ √
局部变量 √ √
机器状态信息存取链 √
控制链 √ √
实参 √
返回地址 √ √
过程 R的活动记录过程 Q的活动记录过程 P的活动记录主程序全局数据区分程序结构
Procedure A(m,n); integer m,n;
B1:begin real z; array B[m:n];
B2:begin real d,e;
L3,2
end;
B4:begin array C[1:m]; 1
B5:begin real e;
L6,5 4
end;
end;
L8:end;
分程序结构的存储分配方案处理分程序结构存储分配方案的一种简单办法是，把分程序看成,无名无参过程”，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。
一则，每逢进入 一个分程序，就照样建立连接数据和 DISPLAY表,这是不必要的。
二则,当从内层分程序向外层转移时，可能同时要结束若干个分程序。
按照过程处理办法，意味着必须一层一层地通过“返回” 来恢复所要到达的那个分程序的数据区，但不能直接到达。
例如：如果有一个从第 5层分程序转出到达第 1层分程序的标号 L，虽然在第 5层分程序工作时知道 L所属的层数，我们极易从
DISPLAY中获得第 1层分程序的活动记录基址（ SP），但是怎么知道第 1层分程序进入时的 TOP呢？唯一的办法是从
5,4,3和 2各层顺序退出。但这种办法是很浪费时间的。
为了解决上述问题，可采取两种措施。第一，对每个过程或分程序都建立有自己的栈顶指示器 TOP，代替原来仅有过程的栈顶指示器,每个 TOP的值保存在各自活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作“无参过程”，每个分程序享用包围它的那个最近过程的 DISPLAY。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。
：
每个过程被当作是 0层分程序。而过程体分程序（假定是一个分程序）当作是它所管辖的第 1层分程序。
这样，每个过程的活动记录所含的内容有：
1.过程的 TOP值，它指向过程活动记录的栈顶位置。
2.连接数据，共四项：
（ 1)老 SP值；
（ 2)返回地址；
(3)全局 DISPAY地址；
（ 4)调用时的栈顶单元地址，老 TOP。
3,参数个数和形式单元
4,DISPAY表。
5,过程所辖的各分程序的局部数据单元。
对于每个分程序来说，它们包括：
（ 1)分程序的 TOP值。当进入分程序时它含现行栈顶地址，以后，用来定义栈的新高度（分程序的 TOP值）；
（ 2)分程序的局部变量,数组内情向量和临时工作单元。
变 量 e
B
5
的 T O P
数 组 C 的 内 情 向 量变 量 e 和 d
B
4
的 T O P B
2
的 T OP
数 组 B 的 内 情 向 量变 量 z
K B
1
的 T O P
D D I S P L A Y
6 形 式 单 元 m,n
5 参 数 个 数,2
4 调 用 时 的 栈 顶 地 址 （老 T O P ）
3 全 局 D I S P L A Y 地 址
2 返 回 地 址
1 老 S P
0 过 程 的 T O P,指 向 活 动 记 录 之 顶
D I S P L A Y
形式单元
m,n
2
连 接 数 据
A 的 T O P
∶
∶
(a) 到 达 标 号 B
1
处 ;
B 的 内 情 向 量
Z
B
1
的 T O P
D I S P L A Y
形式单元
m,n
2
连 接 数 据
A 的 T O P
∶
∶
( b) 进 入 分 程 序 B
1;
数 组 B
B 的 内 情 向 量
B
1
的 T o p
D i s p l a y
z
形 式 单 元
m,n
2
A 的 T o p
连 接 数 据
( c ) 数 组 B 分 配 之 后数 组 B
e
d
B
2
的 T o p
B 的 内 情 向 量
B
1
的 T o p
D i s p l a y
z
形 式 单 元
m,n
2
A 的 T o p
连 接 数 据
( d ) 进 入 分 程 序 B
2
数 组 C
数 组 B
C 的 内 情 向 量
B
4
的 T o p
B 的 内 情 向 量
B
1
的 T o p
D i s p l a y
z
形 式 单 元
m,n
2
A 的 T o p
连 接 数 据
( e ) 进 入 分 程 序 B 4 分 配数 组 C 之 后数 组 C
数 组 B
e
B
5
的 T o p
C 的 内 情 向 量
B
4
的 T o p
B 的 内 情 向 量
B
1
的 T o p
D i s p l a y
z
形 式 单 元
m,n
2
A 的 T o p
连 接 数 据
( f ) 进 入 分 程 序 B
参数传递
(1)procedure exchangel(i,j:integer);
(2) var x:integer;
(3) begin;
(4) x:=a[i]; a[i]:=a[j]; a[j]:=x
(5) end;
带有非局部变量和形参的 PASCAL过程非局变量 a[i]和 a[j]的 值进行交换,i,j为形参（在这里是传值）
(1)program reference(input,output);
(2)var a,b:integer;
(3)procedure swap({var} x,y:integer);
(4) var temp:integer;
(5) begin
(6) temp:=x;
(7) x:=y;
(8) y:=temp
(9) end;
(10)begin
(11) a:=1; b:=2;
(12) swap(a,b);
(13) writeln(?a=?,a);writeln(?b=?,b)
(14)end.
带有过程 swap的 PASCAL程序
传地址（变量参数）
例如：过程 swap(var x,y:integer);
swap(a,b）；（ a,b为 调用时的 实参 ）
调用结果 a,b的值被改变。
传值（值调用）
特点是对形式参数的任何运算不影响实参的值。
例如：过程 swap(x,y:integer);
swap(a,b）； 其结果,a,b调用前的值不改变。
传值 的实现
1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。
2.调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。
3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。
procedure swap( x,y:integer);
var temp:integer;
begin temp:=x; x:=y； y:=temp
end；
调用 swap(a,b) 过程将不会影响 a和 b的值。
其结果等价于执行下列运算：
x,=a；
y,=b；
temp,=x；
x,=y；
y,=temp
传地址 的实现
（ call- by- reference )(call-by-address)(call-by-
location)
把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：
1实在参数是一个名字，或具有左值的表达式 ----
传递左值
2实在参数是无左值的表达式 ----计算值，放入一存储单元，传此存储单元地址
3目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用
procedure swap( var x,y:integer);
var temp:integer;
begin temp:=x; x:=y； y:=temp
end；
调用 swap(i,a[i]) 其结果等价于执行下列运算：
1把 i和 a[i]的地址分别放到 x和 y相应的单元 a1,a2
2( temp,=x； )temp的内容置为 a1所指单元中存的内容
3 (x,=y;) a1所指单元 的内容置为 a2所指单元值
4( y,=temp) a2所指单元 的内容置为 temp的 值
(1)swap(x,y)
(2)int *x,*y;
(3){ int temp;
(4) temp=*x; *x=*y; *y=temp;
(5)}
(6)main( )
(7){ int a=1,b=2;
(8) swap(&a,&b);
(9) printf(“a is now %d,b is now %d \n”,a,b);
(10)}
在一个值调用过程中使用指针的 C程序在 C程序中无传地址所以用指针实现。
过程调用的四元式序列
S? call id(<arglist>)
<arglist>? <arglist>,E
<arglist>? E
par T1
par T2
par Tn
call id,n
过程作为参数传递三种环境：词法环境传递环境活动环境
(1)program param(input,output);
(2)procedure b(function h(n:integer):integer);
(3) begin writeln(h(2)) end{b};
(4)procedure c;
(5) var m:integer;
(6) function f(n:integer):integr;
(7) begin f:=m+n end{f};
(8)begin m,= 0; b(f) end {c};
(9)begin
(10) c
(11)end
嵌套过程作为参数传递
p a r a m
c
存取链
m
b
< f,>
存取链连同存取链一起传递过程实参堆式动态存储分配
需求：
– 一个程序语言允许用户自由地申请数据空间和退还数据空间
操作：
– 堆提供两个操作，分配操作和释放操作
情况,
– 经一段运行时间之后，这个大空间就必定被分划成许多块块，有些占用，有些无用（空闲） --碎片问题程序语言允许用户自由地申请数据空间和退还数据空间
C++语言中 new操作符施加在一个类型标识符上 （ 包括类名 ）
Pascal语言中,标准过程 new能够动态建立存储空间并相应地置上指针 。 标准过程 dispose是释放空间,new与 dispose不断改变着堆存储器的使用情况 。
C语言中有这些操作的若干个版本,但最基本的是 malloc和 free,它们都是标准库 （ stdlib）
的一部分面向对象的语言的动态存储面向对象的语言在运行时环境中要求特殊的机制以完成其增添的特性：对象,方法,
继承以及动态联编 。
面向对象语言在对运行时方面的要求差异很大 。
Smalltalk要求与 LISP相似的完全动态环境
C＋＋则保持 C的基于栈的环境实现对象实现对象的一个简单机制是，初始化代码将所有当前的继承特征
（属性和方法）直接地复制到记录结构中（将方法当作代码指针）。但这样做极浪费空间。
另外一种方法是在执行时将类结构的一个完整的描述保存在每个类的存储中，并由超类指针维护继承性（有时这也称作继承图
（ inheritance graph））。每个对象保持一个指向其定义类的指针，
作为一个附加的域和它的实例变量放在一起，通过这个类就可找到所有（局部和继承的）的方法。此时，只记录一次方法指针
（在类结构中），而且对于每个对象并不将其复制到存储器中。
由于是通过类继承的搜索方法的，所以该机制还实现继承性与动态联编。其缺点在于：虽然实例变量具有可预测的偏移量（正如在标准环境中的局部变量一样），方法却没有，而且它们必须由带有查询功能的符号表结构中的名字维护。这对于诸如 Smalltalk
的高度动态语言是合理的结构，因为类结构可以在执行中改变。
折衷方法将整个类结构保存在存储中,计算出每个类的可用方法的代码指针列表 (称为方法索引表,
如,C++的 virtual function table） 。 它的优点在于：可做出安排以使每个方法都有一个可预测的偏移量,而且也不再需要用一系列表查询遍历类的层次结构 。 现在每个对象不仅包括实例变量还包括了一个相应的方法索引表的指针而不是类结构的指针 （ 当然,这个指针的位置必须也有可预测的偏移量 ） 。
class A { int m1; void f1(){…} }
class B extends A {void f2(){…} }
class C entends B {void f2(){…} }
class D extends C{bool m2; void f1(){…}}
class A a; class B b; class C c; class D d1,d2;
m1 m1
m2
对象 c 对象 d1 对象 d2
m1
m2
m1
对象 b
m1
对象 a
A_f1
类 A
B_f2
A_f1
类 B
C_f2
A_f1
类 C
C_f2
D_f1
类 D
某个单继承 O-O语 言的对象存储示意某个 O-O语 言的程序例子
string day;
class Fruit
{
int price;
string name;
void init(int p,string s){price=p;
name=s;}
void print(){
Print("On ",day,",the price of
",name,
" is ",price,"\n");}
}
class Apple extends Fruit
{
string color;
void setcolor(string c){color=c;}
void print(){
Print("On ",day,",the price of
",color,
" ",name," is ",price,"\n");}
}
void main()
{
class Apple a;
a=New (Apple);
a.init(100,"apple");
a.setcolor("red");
day="Tuesday";
a.print();
}
它 的运行时存储组织临时变量局部变量控制链 (EBP)
返回地址 (EIP)
实参
……
Apple的实例
……
……
Vtable of Fruit
Vtable of Apple
……
vtable
int price(100)
string name
string color
……
Fruit.init
Fruit.print
Fruit.init
Apple.print
Apple.setcolor
……
栈区 堆区
8.1 概述
8.2 数据表示
8.3 目标程序运行时的栈式存储组织
8.4 参数传递
8.5 堆式存储概述概述 -代码生成解决语义 gap
高级语言支持的概念
Type value expression
Variable procedure
Function parameters
目标机支持的概念
bits bytes words
Registers
Stack address
Routine(sub routine)
概述代码生成前如何安排目标机资源运行时组织的几个问题数据表示 -如何在目标机中表示每个源语言类型的值表达式求值 -如何组织表达式的计算存储分配 -如何组织不同作用域变量的存储过程实现 -如何以例程实现过程，函数，参数传递概述任务：编译程序对目标程序运行时的组织（设计运行环境和分配存储） 如 通常存储区布局可为：
目标代码区静态数据区
Stack
heap
运行环境和存储分配设计分析逻辑阶段：在目标代码生成前，作准备实质：
关联（ Binding）
将源程序的文本? 程序运行动作的实现源文件中的名字 N? 运行时的存储 S
在语义学中，使用术语 environment函数表示
env,N→S (N 到 S的映射 )
静态文本中 运行时动作及为实现其动作的准备
（与运行时数据对象的表示有关）
过程定义过程名 执行过程体过程体 控制数据对象的分配，为执行过程体使用源文本中同样的名字 目标程序中不同的数据空间因为一个过程可以是递归的，
这时同一个名字在不同的时间可能代表不同的存储单元决定运行管理复杂程度的因素 ——源语言本身
1,允许的数据类型的多少
2．语言中允许的数据项是 静态确定动态确定
3．程序结构 决定名字的作用域的规则和结构
A,段结构 (Fortran)
B,过程定义不嵌套，只允许过程递归调用
C,分程序结构分程序嵌套过程定义嵌套
4存储类别的多少 Global
Static
Local
dynamic
术语
静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是
“静态”确定的。
动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。
例 procedure A(m,n:integer);
begin real z;
array B[m:n];
begin
·
·
·
end;
end;
数据表示 各种数据对象的存储分配数据对象的属性
name 名字，名称
type 类型
location 内存地址
value 值
component 成分数据表示简单变量：
char,1 byte
integers,2 or 4 bytes
floats,4 to 16 bytes
booleans,1 bit (but usually 1 byte)
指针,unsigned integers
一维数组：一块连续的存储区多维数组：一块连续的存储区，按行存放结构（记录）：把所有域（ field)存放在一块连续的存储区对象：类的实例变量象结构的域一样存放在一块连续的存储区，
但方法（成员函数）不存在该对象里指令：
目标程序运行时的存储组织存储分配策略：
简单的栈式分配方案嵌套过程的栈式分配方案分程序结构的存储分配方案堆式存储静态存储分配动态存储分配 ——栈式堆式术语 -过程活动记录 AR:
为说明方便，假定 源 程序是由过程组成,运行时称作过程的激活。
一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区 （块）叫做一个活动记录 AR或 frame 帧一般这个段要记录：
l临时值，如计算表达式时的中间工作单元。
l局部变量 （数据）
l保存运行过程前的状态 （返回地址，寄存器值 …… ）
l存取链 （可选） 对于非局部量的引用。
l控制链 （可选） 指向调用者的活动记录，释放栈。
l实参 （形式单元）
l返回值 （对函数） （有时可使用寄存器存放返回值）
简单的栈式分配方案
程序结构特点,过程定义不嵌套，过程可递归调用，含可变数组 ;
例,main
全局变量的说明
proc R
……
end R;
proc Q
……
end Q;
主程序执行语句
end main
Mai n----> Q----> R Mai n---> Q----> Q
T O P -----> R 的活动记录 Q 的活动记录
S P - - - - - - >
Q 的活动记录 Q 的活动记录主程序全局 主程序全局数据区 数据区
T O P - - - - > 临时工作单元局部简单变量局部数组的内情向量保存运 行过程前的状态 （返回地址，寄存器值）
实参 （形式单元）和参数个数
S P - - - - - > 控制链 （老 SP ）
TOP R 的数组区
SP R 的活动记录
Q 的活动记录主程序全局数据区嵌套过程语言的栈式分配方案
l主要特点,
（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，
数组或过程等）。
（实现）一个过程执行时可以引用它的任一外层过程的最新活动记录中的某些数据。
关键技术：解决对非局部量的引用（存取）。
设法跟踪每个外层过程的最新活动记录
AR的位置。
跟踪办法：
1,用静态链（如 PL/0的 SL）。
2,用嵌套层次显示表 DISPLAY。
const a=10;
var b,c;
procedure p;
begin
c:=b+a;
end;
begin
read(b);
while b#0 do
begin
call p;
write(2*c);
read(b);
end
end.
( 0) jmp 0 8 转向 主程序入口
( 1) jmp 0 2 转向 过程 p入口
( 2) int 0 3 过程 p入口,为过程 p开辟空间
( 3) lod 1 3 取变量 b的值到栈顶
( 4) lit 0 10 取常数 10到栈顶
( 5) opr 0 2 次栈顶与栈顶相加
( 6) sto 1 4 栈顶值送变量 c中
( 7) opr 0 0 退栈并返回调用点 (16)
( 8) int 0 5 主程序入口开辟 5个栈空间
( 9) opr 0 16 从命令行读入值置于栈顶
(10) sto 0 3 将栈顶值存入变量 b中
(11) lod 0 3 将变量 b的值取至栈顶
(12) lit 0 0 将常数值 0进栈
(13) opr 0 9 次栈顶与栈顶是否不等
(14) jpc 0 24 等时转 (24)（ 条件不满足转 ）
(15) cal 0 2 调用过程 p
(16) lit 0 2 常数值 2进栈
(17) lod 0 4 将变量 c的值取至栈顶
(18) opr 0 4 次栈顶与栈顶相乘 (2*c)
(19) opr 0 14 栈顶值输出至屏幕
(20) opr 0 15 换行
(21) opr 0 16 从命令行读取值到栈顶
(22) sto 0 3 栈顶值送变量 b中
(23) jmp 0 11 无条件转到循环入口 (11)
(24) opr 0 0 结束退栈目标代码解释执行时数据栈的布局（运行栈的存储分配）
每个过程的 AR有
3个联系单元：
– SL,静态链,指向 定义 该过程的 直接外过程
（或主程序）运行时 最新 数据段的基地址 。
– DL,动态链,指向 调用 该过程前正在运行过程的数据段基地址。
– RA,返回地址,记录调用该过程时 目标程序的 断点,即调用过程指令的下一条指令的地址。
局部变量中间结果目标代码的解释执行 运行栈
S
M调用过程 P
RA
DL
SLb
.
,
t
t
b
P
M
解决对非局部量的引用（存取）
用 Display表
Display表 ---嵌套层次显示表当前激活过程的层次为 K，它的 Display表含有 K+1个单元，依次存放着现行层，直接外层 … 直至最外层的每一过程的最新活动记录的基地址例：
pro gr am m ai n(i,0); 程序结构图
pro c R ( c,d);
R
end /* R */
pro c P (a) ; 主
p ro c Q (b);
P Q ca ll R
R( x,y);
end /* Q* / ca ll Q
Q(z ); ca ll P
end /* P*/
ca ll R
P （ W ）；
R （ U,V ）；
end /* m ai n*/
用 Display表的方案
(1)主程序 --->(2)P--->(3)Q--->(4)R
主程序的活动记录d[0] sp
display
top
（ 1）
P 的活动记录主程序的活动记录
d[1]
d[0]
display sp
top
（ 2）
用 Display表的方案
主程序 --->P--->Q--->R
R 的活动记录
Q 的活动记录
P 的活动记录主程序的活动记录
Q 的活动记录
P 的活动记录主程序的活动记录
display
d[2]
d[1]
d[0]
d[1]
d[0]
display
sp
top
top
sp
（ 3） （ 4）
DISPLAY表的维护和建立
不放在过程的活动记录中
放在过程的活动记录中
,
,
,
临时变量数组内情向量临时变量
d DISPL AY
4 形式单元
,
,
,
3 参数个数
2 全局 DISPLAY
地址
1 返回地址
0 老 SP
当过程的层次为 n，
它的 display为 n+1个值。
一个过程被调用时，
从调用过程的
DISPLAY表中自下向上抄录 n个 SP值，再加上本层的 SP值。
全局 DISPLAY地址栈式存储组织 review
数据空间的存储管理：栈式存储分配
– 过程 (函数 )的活动记录：是一段连续的存储区，存放过程 (函数 )的一次执行所需要的信息。
– 过程 (函数 )活动记录的内容：联系单元（静态链,动态链和返回地址）、局部变量和临时变量栈式存储分配的实现：
设置两个指针：栈顶指针 Top和当前活动记录指针 SP；
调用一个过程 (函数 )前，先把过程 (函数 )的参数压入数据栈；
在数据栈中为过程 (函数 )的活动记录分配空间；
填写联系单元内容；
执行过程 (函数 )代码；
过程 (函数 )返回前，根据当前 SP恢复 Top指针，根据动态链恢复 SP为外层过程 (函数 )的活动记录起始地址，根据返回地址得到下一条指令地址；
继续执行外层过程 (函数 )代码。
过程的活动记录 (AR)
C PL0
临时工作单位 √ √
局部变量 √ √
机器状态信息存取链 √
控制链 √ √
实参 √
返回地址 √ √
过程 R的活动记录过程 Q的活动记录过程 P的活动记录主程序全局数据区分程序结构
Procedure A(m,n); integer m,n;
B1:begin real z; array B[m:n];
B2:begin real d,e;
L3,2
end;
B4:begin array C[1:m]; 1
B5:begin real e;
L6,5 4
end;
end;
L8:end;
分程序结构的存储分配方案处理分程序结构存储分配方案的一种简单办法是，把分程序看成,无名无参过程”，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。
一则，每逢进入 一个分程序，就照样建立连接数据和 DISPLAY表,这是不必要的。
二则,当从内层分程序向外层转移时，可能同时要结束若干个分程序。
按照过程处理办法，意味着必须一层一层地通过“返回” 来恢复所要到达的那个分程序的数据区，但不能直接到达。
例如：如果有一个从第 5层分程序转出到达第 1层分程序的标号 L，虽然在第 5层分程序工作时知道 L所属的层数，我们极易从
DISPLAY中获得第 1层分程序的活动记录基址（ SP），但是怎么知道第 1层分程序进入时的 TOP呢？唯一的办法是从
5,4,3和 2各层顺序退出。但这种办法是很浪费时间的。
为了解决上述问题，可采取两种措施。第一，对每个过程或分程序都建立有自己的栈顶指示器 TOP，代替原来仅有过程的栈顶指示器,每个 TOP的值保存在各自活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作“无参过程”，每个分程序享用包围它的那个最近过程的 DISPLAY。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。
：
每个过程被当作是 0层分程序。而过程体分程序（假定是一个分程序）当作是它所管辖的第 1层分程序。
这样，每个过程的活动记录所含的内容有：
1.过程的 TOP值，它指向过程活动记录的栈顶位置。
2.连接数据，共四项：
（ 1)老 SP值；
（ 2)返回地址；
(3)全局 DISPAY地址；
（ 4)调用时的栈顶单元地址，老 TOP。
3,参数个数和形式单元
4,DISPAY表。
5,过程所辖的各分程序的局部数据单元。
对于每个分程序来说，它们包括：
（ 1)分程序的 TOP值。当进入分程序时它含现行栈顶地址，以后，用来定义栈的新高度（分程序的 TOP值）；
（ 2)分程序的局部变量,数组内情向量和临时工作单元。
变 量 e
B
5
的 T O P
数 组 C 的 内 情 向 量变 量 e 和 d
B
4
的 T O P B
2
的 T OP
数 组 B 的 内 情 向 量变 量 z
K B
1
的 T O P
D D I S P L A Y
6 形 式 单 元 m,n
5 参 数 个 数,2
4 调 用 时 的 栈 顶 地 址 （老 T O P ）
3 全 局 D I S P L A Y 地 址
2 返 回 地 址
1 老 S P
0 过 程 的 T O P,指 向 活 动 记 录 之 顶
D I S P L A Y
形式单元
m,n
2
连 接 数 据
A 的 T O P
∶
∶
(a) 到 达 标 号 B
1
处 ;
B 的 内 情 向 量
Z
B
1
的 T O P
D I S P L A Y
形式单元
m,n
2
连 接 数 据
A 的 T O P
∶
∶
( b) 进 入 分 程 序 B
1;
数 组 B
B 的 内 情 向 量
B
1
的 T o p
D i s p l a y
z
形 式 单 元
m,n
2
A 的 T o p
连 接 数 据
( c ) 数 组 B 分 配 之 后数 组 B
e
d
B
2
的 T o p
B 的 内 情 向 量
B
1
的 T o p
D i s p l a y
z
形 式 单 元
m,n
2
A 的 T o p
连 接 数 据
( d ) 进 入 分 程 序 B
2
数 组 C
数 组 B
C 的 内 情 向 量
B
4
的 T o p
B 的 内 情 向 量
B
1
的 T o p
D i s p l a y
z
形 式 单 元
m,n
2
A 的 T o p
连 接 数 据
( e ) 进 入 分 程 序 B 4 分 配数 组 C 之 后数 组 C
数 组 B
e
B
5
的 T o p
C 的 内 情 向 量
B
4
的 T o p
B 的 内 情 向 量
B
1
的 T o p
D i s p l a y
z
形 式 单 元
m,n
2
A 的 T o p
连 接 数 据
( f ) 进 入 分 程 序 B
参数传递
(1)procedure exchangel(i,j:integer);
(2) var x:integer;
(3) begin;
(4) x:=a[i]; a[i]:=a[j]; a[j]:=x
(5) end;
带有非局部变量和形参的 PASCAL过程非局变量 a[i]和 a[j]的 值进行交换,i,j为形参（在这里是传值）
(1)program reference(input,output);
(2)var a,b:integer;
(3)procedure swap({var} x,y:integer);
(4) var temp:integer;
(5) begin
(6) temp:=x;
(7) x:=y;
(8) y:=temp
(9) end;
(10)begin
(11) a:=1; b:=2;
(12) swap(a,b);
(13) writeln(?a=?,a);writeln(?b=?,b)
(14)end.
带有过程 swap的 PASCAL程序
传地址（变量参数）
例如：过程 swap(var x,y:integer);
swap(a,b）；（ a,b为 调用时的 实参 ）
调用结果 a,b的值被改变。
传值（值调用）
特点是对形式参数的任何运算不影响实参的值。
例如：过程 swap(x,y:integer);
swap(a,b）； 其结果,a,b调用前的值不改变。
传值 的实现
1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。
2.调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。
3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。
procedure swap( x,y:integer);
var temp:integer;
begin temp:=x; x:=y； y:=temp
end；
调用 swap(a,b) 过程将不会影响 a和 b的值。
其结果等价于执行下列运算：
x,=a；
y,=b；
temp,=x；
x,=y；
y,=temp
传地址 的实现
（ call- by- reference )(call-by-address)(call-by-
location)
把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：
1实在参数是一个名字，或具有左值的表达式 ----
传递左值
2实在参数是无左值的表达式 ----计算值，放入一存储单元，传此存储单元地址
3目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用
procedure swap( var x,y:integer);
var temp:integer;
begin temp:=x; x:=y； y:=temp
end；
调用 swap(i,a[i]) 其结果等价于执行下列运算：
1把 i和 a[i]的地址分别放到 x和 y相应的单元 a1,a2
2( temp,=x； )temp的内容置为 a1所指单元中存的内容
3 (x,=y;) a1所指单元 的内容置为 a2所指单元值
4( y,=temp) a2所指单元 的内容置为 temp的 值
(1)swap(x,y)
(2)int *x,*y;
(3){ int temp;
(4) temp=*x; *x=*y; *y=temp;
(5)}
(6)main( )
(7){ int a=1,b=2;
(8) swap(&a,&b);
(9) printf(“a is now %d,b is now %d \n”,a,b);
(10)}
在一个值调用过程中使用指针的 C程序在 C程序中无传地址所以用指针实现。
过程调用的四元式序列
S? call id(<arglist>)
<arglist>? <arglist>,E
<arglist>? E
par T1
par T2
par Tn
call id,n
过程作为参数传递三种环境：词法环境传递环境活动环境
(1)program param(input,output);
(2)procedure b(function h(n:integer):integer);
(3) begin writeln(h(2)) end{b};
(4)procedure c;
(5) var m:integer;
(6) function f(n:integer):integr;
(7) begin f:=m+n end{f};
(8)begin m,= 0; b(f) end {c};
(9)begin
(10) c
(11)end
嵌套过程作为参数传递
p a r a m
c
存取链
m
b
< f,>
存取链连同存取链一起传递过程实参堆式动态存储分配
需求：
– 一个程序语言允许用户自由地申请数据空间和退还数据空间
操作：
– 堆提供两个操作，分配操作和释放操作
情况,
– 经一段运行时间之后，这个大空间就必定被分划成许多块块，有些占用，有些无用（空闲） --碎片问题程序语言允许用户自由地申请数据空间和退还数据空间
C++语言中 new操作符施加在一个类型标识符上 （ 包括类名 ）
Pascal语言中,标准过程 new能够动态建立存储空间并相应地置上指针 。 标准过程 dispose是释放空间,new与 dispose不断改变着堆存储器的使用情况 。
C语言中有这些操作的若干个版本,但最基本的是 malloc和 free,它们都是标准库 （ stdlib）
的一部分面向对象的语言的动态存储面向对象的语言在运行时环境中要求特殊的机制以完成其增添的特性：对象,方法,
继承以及动态联编 。
面向对象语言在对运行时方面的要求差异很大 。
Smalltalk要求与 LISP相似的完全动态环境
C＋＋则保持 C的基于栈的环境实现对象实现对象的一个简单机制是，初始化代码将所有当前的继承特征
（属性和方法）直接地复制到记录结构中（将方法当作代码指针）。但这样做极浪费空间。
另外一种方法是在执行时将类结构的一个完整的描述保存在每个类的存储中，并由超类指针维护继承性（有时这也称作继承图
（ inheritance graph））。每个对象保持一个指向其定义类的指针，
作为一个附加的域和它的实例变量放在一起，通过这个类就可找到所有（局部和继承的）的方法。此时，只记录一次方法指针
（在类结构中），而且对于每个对象并不将其复制到存储器中。
由于是通过类继承的搜索方法的，所以该机制还实现继承性与动态联编。其缺点在于：虽然实例变量具有可预测的偏移量（正如在标准环境中的局部变量一样），方法却没有，而且它们必须由带有查询功能的符号表结构中的名字维护。这对于诸如 Smalltalk
的高度动态语言是合理的结构，因为类结构可以在执行中改变。
折衷方法将整个类结构保存在存储中,计算出每个类的可用方法的代码指针列表 (称为方法索引表,
如,C++的 virtual function table） 。 它的优点在于：可做出安排以使每个方法都有一个可预测的偏移量,而且也不再需要用一系列表查询遍历类的层次结构 。 现在每个对象不仅包括实例变量还包括了一个相应的方法索引表的指针而不是类结构的指针 （ 当然,这个指针的位置必须也有可预测的偏移量 ） 。
class A { int m1; void f1(){…} }
class B extends A {void f2(){…} }
class C entends B {void f2(){…} }
class D extends C{bool m2; void f1(){…}}
class A a; class B b; class C c; class D d1,d2;
m1 m1
m2
对象 c 对象 d1 对象 d2
m1
m2
m1
对象 b
m1
对象 a
A_f1
类 A
B_f2
A_f1
类 B
C_f2
A_f1
类 C
C_f2
D_f1
类 D
某个单继承 O-O语 言的对象存储示意某个 O-O语 言的程序例子
string day;
class Fruit
{
int price;
string name;
void init(int p,string s){price=p;
name=s;}
void print(){
Print("On ",day,",the price of
",name,
" is ",price,"\n");}
}
class Apple extends Fruit
{
string color;
void setcolor(string c){color=c;}
void print(){
Print("On ",day,",the price of
",color,
" ",name," is ",price,"\n");}
}
void main()
{
class Apple a;
a=New (Apple);
a.init(100,"apple");
a.setcolor("red");
day="Tuesday";
a.print();
}
它 的运行时存储组织临时变量局部变量控制链 (EBP)
返回地址 (EIP)
实参
……
Apple的实例
……
……
Vtable of Fruit
Vtable of Apple
……
vtable
int price(100)
string name
string color
……
Fruit.init
Fruit.print
Fruit.init
Apple.print
Apple.setcolor
……
栈区 堆区
