第十章 目标程序运行时的组织
10.1 概述
10,2数据表示
10.3目标程序运行时的栈式存储组织
10.4 参数传递
10.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,段结构
B,过程定义不嵌套，只允许过程递归调用
C,分程序结构分程序嵌套过程定义嵌套
4存储类别的多少 Global
Static
Local
dynamic
术语
静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是
“静态”确定的。
动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。
例 procedure A(m,n:integer);
begin real z;
array B[m:n];
begin
·
·
·
end;
end;
声明的作用域 词法作用域动态作用域例,（ 1 ） p r o g ra m dyn a m ic(i,0);
(2) v a r r:rea l
(3) pro cedu re sho w;
(4) beg in wri te( r:5:3 ) end ;
(5) pro cedru e sm a ll;
(6) va r r,real ;
(7) beg in r,=0,12 5 ; sho w e nd;
(8) beg in
(9) r,=0,25 ;
(10 ) sho w; sm a ll ; wri te/n ;
(11 ) sho w; sm a ll ; wri te/n ;
(12 ) end.
lex ica l sco pe
0,25 0 0,25 0
0,25 0 0,25 0
dy na mic scop e
0,25 0 0,12 5
0,25 0 0,12 5
数据表示 各种数据对象的存储分配数据对象的属性
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)存放在一块连续的存储区对象：类的实例变量象结构的域一样存放在一块连续的存储区，
但方法（成员函数）不存在该对象里指令：
例：按行 A 是 10? 20 的二维数组
A [ 1,1]
A [ 1,2]
.,第一行
.,
A [ 1,2 0 ]
A [ 2,1 ]
.,第二行
.,
.,
.,
.,
A [ 1 0,2 0 ] 第十行数组元素的地址计算设 A [ 1,1] 的地址为 a,每个元素占一个字
A[ i,j] 的地址,a + （ i - 1 ）? 2 0 + （ j-1 ）
= （ a - 2 1 ） + （ 2 0 i + j ）
一般,a r r a y A [ l
1
,u
1
,l
2
,u
2
，,l
n
,u
n
]
令 d
i
=u
i
-l
i
+1
元素 A [ i
1
,i
2
，,i
n
] 的地址 D
D = a + （ i
1
-l
1
） d
2
d
3
d
n
+ （ i
2
-l
2
） d
3
d
4
d
n
+ + （ i
n - 1
-l
n - 1
） d
n
+ （ i
n
- l
n
）
经因子分解后得 D = C O N S PA R T+V A R PA R T
其中 C O N S PA R T = a - C
C = （ （ （ l
1
d
2
+l
2
） d
3
+ l
3
） d
4
+ + l
n - 1
） d
n
+ l
n
V A R PA R T= （ （ （ i
1
d
2
+i
2
） d
3
+ i
3
） d
4
+ + i
n - 1
） d
n
+ i
n
四元式 两组 V A R PA R T? T
C O N S PA R T? T
1
T
1
[ T] 表示数组元素的地址数组元素引用,X,=T
1
[ T]
对数组元素赋值,T
1
[ T],=X
l
可变 (动态 )数组,若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变 (动态 )数组 。
数组内情向量：,
编译将数组的有关信息记录在一些单元中，称为数组的,内情向量,
A[l 1:u 1,l 2:u 2,,ln,un]
l1 u1
l2 u2
:
:
type a（首地址）
n C
目标程序运行时的存储组织存储分配策略：
简单的栈式分配方案嵌套过程的栈式分配方案分程序结构的存储分配方案静态存储分配动态存储分配 ——栈式堆式
l
术语 -过程活动记录 AR:
为说明方便，假定程序是由过程组成，过程区分为源文本，
运行时称作过程的激活。
一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区 （块）叫做一个活动记录或 frame（ 帧 ）
一般这个段要记录：
l临时值，如计算表达式时的中间工作单元。
l局部变量 （数据）
l保存运行过程前的状态 （返回地址，寄存器值 …… ）
l存取链 （可选） 对于非局部量的引用。
l控制链 （可选） 指向调用者的活动记录，释放栈。
l实参 （形式单元）
l返回值 （对函数） （有时可使用寄存器存放返回值）
简单的栈式分配方案
程序结构特点,过程定义不嵌套，过程可递归调用，含可变数组 ;
例,main
全局变量的说明
proc R
……
end R;
proc Q
……
end Q;
主程序执行语句
end main
Main ----> Q--- -> R Main ---> Q--- -> Q
T O P -----> R 的活动记录 Q 的活动记录
S P - - - - - - >
Q 的活动记录 Q 的活动记录主程序全局 主程序全局数据区 数据区
T O P - - - - > 临时工作单元局部简单变量局部数组的内情向量保存运 行过程前的状态 （返回地址，寄存器值）
实参 （形式单元）和参数个数
S P - - - - - > 控制链 （老 SP ）
TO P 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 ain (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 ain */
用 Display表的方案
(1)主程序 --->(2)P--->(3)Q--->(4)R
P 的活动记录主程序的活动记录
d[1]
d[0]
display sp
top
主程序的活动记录d[0] sp
display
top
（ 1）（ 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表的维护和建立
DISPLAY表 d 运行栈
0 主程活动记录地址
1 R活动记录地址
..,
0 老 SP
1 返回地址
2 全局 D ISP LAY
地址
3 参数个数
4 形式单元
,
,
,
d DI SP LAY
,
,
,
简单变量数组内情向量临时变量
当过程的层次为 n，
它的 display为 n+1个值。
一个过程被调用时，
从调用过程的
DISPLAY表中自下向上抄录 n个 SP值，再加上本层的 SP值。
全局 DISPLAY地址分程序结构
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 O P
数 组 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,指 向 活 动 记 录 之 顶
B 的 内 情 向 量
Z
B
1
的 T O P
D I S P L A Y D I S P L A Y
形式单元
m,n
2
形式单元
m,n
2
连 接 数 据 连 接 数 据
A 的 T O P A 的 T O P
∶
∶
∶
∶
( a ) ( b)
( a ) 到 达 标 号 B
1
处 ; ( b) 进 入 分 程 序 B
1;
B
Z
B1 TO
数 组 B 数 组 B
e
d
B22 的 T O P
B 的 内 情 向 量 B 的 内 情 向 量
z z
B1 的 T O P B1 的 T O P
D I S P L A Y D I S P L A Y
形式单元
m,n
2
形式单元
m,n
2
连 接 数 据 连接 数 据
A 的 T O P A 的 T O P
∶
∶
∶
∶
(c) (d)
(c )数组 B 分配之后； （ d）进入分程序 B22;
数 组 C 数 组 C
数 组 B 数 组 B
C 的 向 量 内 情
e
B
5
的 T O P
C 的 内 情 向 量
B
4
的 T O P
B4 的 T O P
B 的 内 情 向 量
B 的 内 情 向 量 z
Z B
1
的 T O P
B
1
的 T O P D I S P L A Y
D I S P L A Y
形式单元
m,n
2
形式单元
m,n
2
连接数据连 接 数 据 A 的 T O P
A 的 T O P
∶
∶
∶
∶
( e ) ( f)
( e ) 进入分程序 B
4
分配数组 C 之后； ( f ) 进入分程序 B
5 。
参数传递
(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( 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)S? call id(<arglist>){for 队列 <arglist>.q的每一项 P do {gen(par,-,-,p);n:=n+1};
gen(call,-,-,entry(id))}
(2)<arglist>? <arglist>1,E{把 E.place排在
<arglist>.q
的末端；
(3)<arglist>? E
过程作为参数传递三种环境：词法环境传递环境活动环境
program param(input,output);
procedure b(function h(n:integer):integer);
(*) var m:integer;
begin m:=3; writeln(h(2)) end{b};
procedure c;
(*) var m:integer;
function f(n:integer):integr;
(&) begin f:=m+n end{f};
begin m:=0; b(f) end {c}
begin
c
end.
(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
图 10-27 嵌套过程作为参数传递
p ar am
c
存取链
m
b
<f,>
存取链图 10- 28 连同存取链一起传递过程实参值结果传递除了未建立真正的别名之外,这个机制得到的结果与引用传递类似：在过程中复制和使用自变量的值,然后当过程退出时,再将参数的最终值复制回自变量的地址 。 因此,这个方法有时也被称为复制进,复制出,或复制存储 。
值结果传递与引用传递的唯一区别在于别名的表现不同 。 例如,在以下的代码中 （ C语法 ）,void p (int x,int y)
{++x;
++y;
}
main()
{int a=1;
p(a,a);
return 0;
}
在调用 p之后,若使用了引用传递,则 a的值为 3；若使用了值结果传递,则 a
的值为 2。
名字传递这是传递机制中最复杂的参数了 。 由于名字传递的思想是直到在被调用的程序真正使用了自变量 （ 作为一个参数 ） 之后才对这个自变量赋值,所以它还称作延尽赋值 （ delayed evaluation） 。 因此,自变量的名称或是它在调用点上的结构表示取代了它对应的参数的名字 。 例如在代码
void p (int x)
{++x;}
中，若做了一个如 p(a[i])的调用时，其结果是计算
++(a[i])。因此，若在 p中使用 x之前改变 i，那么它的结果就与在引用传递或在值结果传递中的不同
int i;
int a [10];
void p (int x)
{++i;
++x;
}
main ()
{i=1;
a[1]=1;
a[2]=2;
p(a[i]);
return 0;
}
对 p的调用的结果是将 a[2]设置为 3并保持 a[1]不变 。
名字传递的解释如下：在调用点上的自变量的文本被看作是它自己右边的函数，
生当在被用的过程的代码中到达相应的参数名时，就要计算它。我们总是在调用程序的环境中计算自变，而总是在过程的定义环境中执行过程。
建立内情向量，分配内存的目标代码
（ n维 可变数组,type--每个元素占一个字）
begin k:=1;n:=1;c:=0;
while k<=n do
begin di:=ui-li+ 1;
m:=m*di;
c:=c*di+li;
把 li,ui和 di填进内情向量表区；
k:=k+1
end;
申请 m个空间,令首地址为 a;把 n,c,type,a填进内情向量表区
end
赋值中数组元素的翻译
A? V:=E
V? id[<elist>] | id
<elist>? <elist>,E | E
V? <elist>] | id
<elist>? <elist>,E | id [E
结构（记录），抽象数据类型对象类实例变量的存储结构 (CIR)
class parent { | class parent{
public int a,b,c; | public a,b,c;
public void draw() {..}; | public virtual void draw()
}; |,..
class child:public parent{ |
public d,e; |
public void sift(){…}; | void draw(){…}
};
堆式动态存储分配堆变量堆空间的管理策略减少碎片的技术空间的释放
C++的堆变量
Int *Ptr;
Ptr=new int(5)；
Int *ptr= new int [10]
Delete ptr
Delete[ ] ptr
堆变量是可以在程序运行时根据需要随时创建或删除的变量
C++的堆对象
#include<iostream.h>
Class Myclass{
Public:
Myclass();
Myclass(int k,int j);
void Set(int,int){m=k;n=j;}
Myclass();
Private:
int m,n;
};
Myclass::Myclass(){
Set(0,0);
Cout<<Default<<endl;
}
Myclass::Myclass(int k,int j) {
Set(k,j);
Cout<<―m=―<<m<<endl;
}
Myclass:,?Myclass() {
Cout<<―Destructor‖<<endl;
}
使用 new和 delete的示例
#include<iostream.h>
Int main()
{
Cout<<―one‖<<endl;
Myclass *ptr1=new Myclass;
Delete ptr1;
Cout<<―two‖<<endl;
Ptr1=new Myclass(5,10);
Delete ptr1;
Return 0;
}
one
Defalt
Destructor
two
m=5
Destructor
堆式动态存储分配
Const int ArraySize=24;//default size
Class IntArray{
Public:
//operations performed on arrays
IntArray(int sz=ArraySize);
IntArray(const IntArray&);
~IntArray(){delete ia;}
IntArray& operator= (const
IntArray&);
int& operator[] (int);
int getSize() {return size;}
protected:
//internal data representation
int size;
int * ia;
};
IntArray()函数的实现,引入新的运算符 new
IntArray::IntArray （ int sz)
{
size= sz;
// allocate an integer array of
size
// and set ia to point to it
ia= new int [size];
// initialize array
for (int i=0;i<sz;++i)
ia[i]=0;
}
C++语言中 new操作符施加在一个类型标识符上 （ 包括类名 ）
Pascal语言中,标准过程 new能够动态建立存储空间并相应地置上指针 。 标准过程
dispose是释放空间,
new与 dispose不断改变着堆存储器的使用情况 。
C语言中有这些操作的若干个版本,但最基本的是 malloc 和 free,它们都是标准库
（ stdlib.h） 的一部分堆式动态存储分配需求：
一个程序语言允许用户自由地申请数据空间和退还数据空间,或者不仅有过程而且有进程 （ process）
的程序结构,
操作：
堆提供两个操作,分配操作和释放操作情况,
经一段运行时间之后，这个大空间就必定被分划成许多块块，
有些占用，有些无用（空闲） --碎片问题堆式动态储分配当运行程序要求一块体积为 N的空间时，我们应该分配哪一块给它呢？
运行程序要求一块体积为 N的空间，但发现没有比 N大的空闲块了，然而所有空闲块的总和却要比 N大得多如果运行程序要求一块积为 N的空间，但所有空闲块的总和也不够 N，那又应怎么办呢？有的管理系统采用一种叫做垃圾回收的办法来对付这种局面。即寻找那些运行程序业己无用但尚未释放的占用块堆管理堆空间的管理策略减少碎片的技术空间的释放堆空间的管理策略
1 定长块管理
2 变长块管理堆式动态储分配的实现
1 定长块管理堆式动态储分配最简单的实现是按定长块进行 。
初始化时,将堆存储空间分成长度相等的若干块,每块中指定一个链域,按照邻块的顺序把所有块链成一个链表,用指针 available指向链表中的第一块 。
分配时每次都分配指针 available所指的块,然后
available指向相邻的下一块 。 归还时,把所归还的块插入链表 。 考虑插入方便,可以把所归还的 块 插 在 available 所 指 的块 之 前,然后
available指向新归还的块 。
2 变长块管理除了按定长块进行分配之外，还可以根据需要分配长度不同的存储块，可以随要求而变。按这种方法，初始化时存储空间是一个整块。按照用户的需要，分配时先是从一个整块里分割出满足需要的一小块，以后，归还时，如果新归还的块和现有的空间能合并，则合并成一块；
如果不能和任何空闲块合并，则可以把空闲块链成一个链表。再进行分配时，从空闲块链表中找出满足需要的一块，或者整块分配出去，
或者从该块上分割一小块分配出去。若空闲块表中有若干个满足需要的空闲块时，该分配哪一块呢？通常有三种不同的分配策略不同的情况应采用不同的方法。通常在选择时需考虑下列因素：用户的要求； 请求分配量的大小分布；分配和释放的频率以及效率对系统的重要等等。
（ 1） 首次满足法：只要在空闲块链表中找到满足需要的一块,
就进行分配 。
（ 2） 最优满足法：将空闲块链表中一个不小于申请块且最接近于申请块的空闲块分配给用户,则系统在分配前首先要对空闲块链表从头至尾描一遍,然后从中找出一块,为避免每次分配都要扫描整个链表,通常将空闲块链表空间的大小从小到大排序 。
（ 3） 最差满足法：将空闲块表中不小于申请块且是最大的空闲的一部全分配给用户 。 此时的空闲块链表按空闲的块的大小从大到小排序 。 只需从链表中删除第一个结点,并将其中一部分分配给用户,而其它部分作为一个新的结点插入到空闲块表的适当置上去 。
减少碎片的技术
1分配时，找最小的足够大的块 ---需保持空闲块的大小排序
2 释放时，合并任何相邻的块 ---搜索全部空闲块表，或其它算法
3 将堆变量紧缩在一起空间的释放
1显式释放
2隐式（自动）释放显式释放程序设计语言提供机制如,pascal 的 dispose
C 的 free
程序员必须编写分配和释放存储的明确的调用注意的问题 1 堆变量是不可访问的（垃圾）
2 悬挂（不安全）指针堆式分配和释放的 C语言描述
#define NULL 0
# define MEMSIZE 8096 /* change for different sizes */
typedef fdouble Align;
typedef unionheader
{struct {union header *next;
unsigned usedsize;
unsigned freesize;
}s;
Align a;
}Header;//数据类型 Header保存每个存储块的簿记信息
static Header mem [MEMSIZE];
static Header *memptr= NULL;
void *malloc (unsigned nbytes)
{Header *p,*newp;
unsigned nunits;
nunits= (nbytes+sizeof(Header)-1/ sizeof (Header)+1;
if (memptr == NULL)
{memptr->s.next = memptr = mem;
memptr->s.usedsize = 1;
memptr->s.freesize = MEMSIZE-1;
}
for (p=memptr;
(p->s,next!= memptr) &&(p->s,freesize < nunits);
p=p->s,next);
if (p->s,freesize <> nunits) return NULL;
/* no block big enough */
newp = p+p->s,usedsize;
newp->s,usedsize= nunits;
newp->s,freesize = p->s,freesize-nunits;
newp->s.next = p->s,next;
p->s,freesize=0;
p->s,next= newp;
memptr=newp;
return (void *)(newp+1);
}
void free (void *ap)
{Header * bp,*p,*prev;
bp=(Header *) ap –1;
for (prev= memptr,p=memptr->s,next;
(p!=bp) &&(p!= memptr); prev=p,p=p->s,next);
if (p!=bp) return;
/* corrupted list,do nothing*/
prev->s,freesize += p->s,usedsize + p->s,freesize;
prev->s,next = p->s,next;
memptr = prev;
}
堆的自动管理 -----隐式存储回收在一种需要完全动态的运行时环境的语言
（ OO语言,函数式语言 Lisp,ML)中,堆也必须类似地自动管理 。 自动存储器管理涉及到了前面分配的但不再使用的存储器的回收,可能是在它被分配的很久以后,
而没有明确的对 free的调用 。 这个过程称作垃圾回收 （ grabage collection） 。
垃圾回收垃圾回收程序 ---寻找可被引用的所有存储器并释所有未引用的存储器。
在存储块不再引用时，无论是直接还是通过指针间接的引用，识别这些存储块是一项比维护堆存储 的列表复杂得多的任务。
方法 ---对 malloc的调用失败，激活垃圾回收程序垃圾回收算法 mark and sweep
隐式存储回收 —mark and sweep算法隐式存储回收要求用户程序和支持运行的回收子程序并行工作，因为回收程序需要知道分配给用户程序的存储块何时不再使用。为了实现并行工作，在存储块中要设置回收子程序访问的信息。
存储块格式：
块长度访问计数标记指针用户使用空间回收过程分为两个阶段 。
（ 1） 第一个阶段为标记阶段,对已分配的块跟踪程序中各指针的访问路径 。 如果某个块被访问过,就给这个块加一个标记 。
（ 2） 第二个阶段为回收阶段,所有未加标记的存储块回收到一起,并插入空闲块链表中,然后消除在存储块中所加的全部标记 。
面向对象的语言中的动态存储器面向对象的语言在运行时环境中要求特殊的机制以完成其增添的特性：对象,方法,
继承以及动态联编 。
面向对象语言在对运行时方面的要求差异很大 。
Smalltalk要求与 LISP相似的完全动态环境
C＋＋则保持 C的基于栈的环境实现对象实现对象的一个简单机制是，初始化代码将所有当前的继承特征（和方法）直接地复制到记录结构中（将方法当作代码指针）。但这样做极浪费空间。
另外一种方法是在执行时将类结构的一个完整的描述保存在每个点的存储器中，并由超类指针维护继承性（有时这也称作继承图
（ inheritance graph））。接着同用于它的实例变量的域一起，每个对象保持一个指向其定义类的指针，通过这个类就可找到所有（局部和继承的）的方法。此时，只记录一次方法指针（在类结构中），而且对于每个对象并不将其复制到存储器中。由于是通过类继承的搜索来找到这个机制的，所以该机制还实现继承性与动态联编。其缺 在于：
虽然实例变量具有可预测的偏移量（正如在标准环境中的局部变量一样），方法却没有，而且它们必须由带有查询功能的符号表结构中的名字维护。这是对于诸如 Smalltalk的高度动态语言的合理的结构，因为类结构可以在执行中改变。
C++中选择的方法将整个类结构保存在环境中,计算出每个类的可用方法的代码指针列表,并将其作为一个虚拟函数表 （ virtual function table） 而存放在
（ 静态 ） 存储器 。 它的优点在于：可做出安排以使每个方法都有一个可预测的偏移量,
而且也不再需要用一系列表查询遍历类的层次结构 。 现在每个对象都包括了一个指向相应的虚拟函数表而不是类结构的指针 （ 当然,
这个指针的位置必须也有可预测的偏移量 ） 。
例 C++类声明：
class A
{public:
double x,y;
void f();
virtual void g();
};
class B:public A
{public:
double z;
void f();
virtual void h();
};
类 A的一个对象应出现在存储器中 （ 带有它的虚拟函数表 ）
而类 B的一个对象则应如下所示：
x
y
vtp A::g
B::h
A::g
X
Y
vtp
z
10.1 概述
10,2数据表示
10.3目标程序运行时的栈式存储组织
10.4 参数传递
10.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,段结构
B,过程定义不嵌套，只允许过程递归调用
C,分程序结构分程序嵌套过程定义嵌套
4存储类别的多少 Global
Static
Local
dynamic
术语
静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是
“静态”确定的。
动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。
例 procedure A(m,n:integer);
begin real z;
array B[m:n];
begin
·
·
·
end;
end;
声明的作用域 词法作用域动态作用域例,（ 1 ） p r o g ra m dyn a m ic(i,0);
(2) v a r r:rea l
(3) pro cedu re sho w;
(4) beg in wri te( r:5:3 ) end ;
(5) pro cedru e sm a ll;
(6) va r r,real ;
(7) beg in r,=0,12 5 ; sho w e nd;
(8) beg in
(9) r,=0,25 ;
(10 ) sho w; sm a ll ; wri te/n ;
(11 ) sho w; sm a ll ; wri te/n ;
(12 ) end.
lex ica l sco pe
0,25 0 0,25 0
0,25 0 0,25 0
dy na mic scop e
0,25 0 0,12 5
0,25 0 0,12 5
数据表示 各种数据对象的存储分配数据对象的属性
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)存放在一块连续的存储区对象：类的实例变量象结构的域一样存放在一块连续的存储区，
但方法（成员函数）不存在该对象里指令：
例：按行 A 是 10? 20 的二维数组
A [ 1,1]
A [ 1,2]
.,第一行
.,
A [ 1,2 0 ]
A [ 2,1 ]
.,第二行
.,
.,
.,
.,
A [ 1 0,2 0 ] 第十行数组元素的地址计算设 A [ 1,1] 的地址为 a,每个元素占一个字
A[ i,j] 的地址,a + （ i - 1 ）? 2 0 + （ j-1 ）
= （ a - 2 1 ） + （ 2 0 i + j ）
一般,a r r a y A [ l
1
,u
1
,l
2
,u
2
，,l
n
,u
n
]
令 d
i
=u
i
-l
i
+1
元素 A [ i
1
,i
2
，,i
n
] 的地址 D
D = a + （ i
1
-l
1
） d
2
d
3
d
n
+ （ i
2
-l
2
） d
3
d
4
d
n
+ + （ i
n - 1
-l
n - 1
） d
n
+ （ i
n
- l
n
）
经因子分解后得 D = C O N S PA R T+V A R PA R T
其中 C O N S PA R T = a - C
C = （ （ （ l
1
d
2
+l
2
） d
3
+ l
3
） d
4
+ + l
n - 1
） d
n
+ l
n
V A R PA R T= （ （ （ i
1
d
2
+i
2
） d
3
+ i
3
） d
4
+ + i
n - 1
） d
n
+ i
n
四元式 两组 V A R PA R T? T
C O N S PA R T? T
1
T
1
[ T] 表示数组元素的地址数组元素引用,X,=T
1
[ T]
对数组元素赋值,T
1
[ T],=X
l
可变 (动态 )数组,若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变 (动态 )数组 。
数组内情向量：,
编译将数组的有关信息记录在一些单元中，称为数组的,内情向量,
A[l 1:u 1,l 2:u 2,,ln,un]
l1 u1
l2 u2
:
:
type a（首地址）
n C
目标程序运行时的存储组织存储分配策略：
简单的栈式分配方案嵌套过程的栈式分配方案分程序结构的存储分配方案静态存储分配动态存储分配 ——栈式堆式
l
术语 -过程活动记录 AR:
为说明方便，假定程序是由过程组成，过程区分为源文本，
运行时称作过程的激活。
一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区 （块）叫做一个活动记录或 frame（ 帧 ）
一般这个段要记录：
l临时值，如计算表达式时的中间工作单元。
l局部变量 （数据）
l保存运行过程前的状态 （返回地址，寄存器值 …… ）
l存取链 （可选） 对于非局部量的引用。
l控制链 （可选） 指向调用者的活动记录，释放栈。
l实参 （形式单元）
l返回值 （对函数） （有时可使用寄存器存放返回值）
简单的栈式分配方案
程序结构特点,过程定义不嵌套，过程可递归调用，含可变数组 ;
例,main
全局变量的说明
proc R
……
end R;
proc Q
……
end Q;
主程序执行语句
end main
Main ----> Q--- -> R Main ---> Q--- -> Q
T O P -----> R 的活动记录 Q 的活动记录
S P - - - - - - >
Q 的活动记录 Q 的活动记录主程序全局 主程序全局数据区 数据区
T O P - - - - > 临时工作单元局部简单变量局部数组的内情向量保存运 行过程前的状态 （返回地址，寄存器值）
实参 （形式单元）和参数个数
S P - - - - - > 控制链 （老 SP ）
TO P 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 ain (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 ain */
用 Display表的方案
(1)主程序 --->(2)P--->(3)Q--->(4)R
P 的活动记录主程序的活动记录
d[1]
d[0]
display sp
top
主程序的活动记录d[0] sp
display
top
（ 1）（ 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表的维护和建立
DISPLAY表 d 运行栈
0 主程活动记录地址
1 R活动记录地址
..,
0 老 SP
1 返回地址
2 全局 D ISP LAY
地址
3 参数个数
4 形式单元
,
,
,
d DI SP LAY
,
,
,
简单变量数组内情向量临时变量
当过程的层次为 n，
它的 display为 n+1个值。
一个过程被调用时，
从调用过程的
DISPLAY表中自下向上抄录 n个 SP值，再加上本层的 SP值。
全局 DISPLAY地址分程序结构
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 O P
数 组 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,指 向 活 动 记 录 之 顶
B 的 内 情 向 量
Z
B
1
的 T O P
D I S P L A Y D I S P L A Y
形式单元
m,n
2
形式单元
m,n
2
连 接 数 据 连 接 数 据
A 的 T O P A 的 T O P
∶
∶
∶
∶
( a ) ( b)
( a ) 到 达 标 号 B
1
处 ; ( b) 进 入 分 程 序 B
1;
B
Z
B1 TO
数 组 B 数 组 B
e
d
B22 的 T O P
B 的 内 情 向 量 B 的 内 情 向 量
z z
B1 的 T O P B1 的 T O P
D I S P L A Y D I S P L A Y
形式单元
m,n
2
形式单元
m,n
2
连 接 数 据 连接 数 据
A 的 T O P A 的 T O P
∶
∶
∶
∶
(c) (d)
(c )数组 B 分配之后； （ d）进入分程序 B22;
数 组 C 数 组 C
数 组 B 数 组 B
C 的 向 量 内 情
e
B
5
的 T O P
C 的 内 情 向 量
B
4
的 T O P
B4 的 T O P
B 的 内 情 向 量
B 的 内 情 向 量 z
Z B
1
的 T O P
B
1
的 T O P D I S P L A Y
D I S P L A Y
形式单元
m,n
2
形式单元
m,n
2
连接数据连 接 数 据 A 的 T O P
A 的 T O P
∶
∶
∶
∶
( e ) ( f)
( e ) 进入分程序 B
4
分配数组 C 之后； ( f ) 进入分程序 B
5 。
参数传递
(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( 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)S? call id(<arglist>){for 队列 <arglist>.q的每一项 P do {gen(par,-,-,p);n:=n+1};
gen(call,-,-,entry(id))}
(2)<arglist>? <arglist>1,E{把 E.place排在
<arglist>.q
的末端；
(3)<arglist>? E
过程作为参数传递三种环境：词法环境传递环境活动环境
program param(input,output);
procedure b(function h(n:integer):integer);
(*) var m:integer;
begin m:=3; writeln(h(2)) end{b};
procedure c;
(*) var m:integer;
function f(n:integer):integr;
(&) begin f:=m+n end{f};
begin m:=0; b(f) end {c}
begin
c
end.
(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
图 10-27 嵌套过程作为参数传递
p ar am
c
存取链
m
b
<f,>
存取链图 10- 28 连同存取链一起传递过程实参值结果传递除了未建立真正的别名之外,这个机制得到的结果与引用传递类似：在过程中复制和使用自变量的值,然后当过程退出时,再将参数的最终值复制回自变量的地址 。 因此,这个方法有时也被称为复制进,复制出,或复制存储 。
值结果传递与引用传递的唯一区别在于别名的表现不同 。 例如,在以下的代码中 （ C语法 ）,void p (int x,int y)
{++x;
++y;
}
main()
{int a=1;
p(a,a);
return 0;
}
在调用 p之后,若使用了引用传递,则 a的值为 3；若使用了值结果传递,则 a
的值为 2。
名字传递这是传递机制中最复杂的参数了 。 由于名字传递的思想是直到在被调用的程序真正使用了自变量 （ 作为一个参数 ） 之后才对这个自变量赋值,所以它还称作延尽赋值 （ delayed evaluation） 。 因此,自变量的名称或是它在调用点上的结构表示取代了它对应的参数的名字 。 例如在代码
void p (int x)
{++x;}
中，若做了一个如 p(a[i])的调用时，其结果是计算
++(a[i])。因此，若在 p中使用 x之前改变 i，那么它的结果就与在引用传递或在值结果传递中的不同
int i;
int a [10];
void p (int x)
{++i;
++x;
}
main ()
{i=1;
a[1]=1;
a[2]=2;
p(a[i]);
return 0;
}
对 p的调用的结果是将 a[2]设置为 3并保持 a[1]不变 。
名字传递的解释如下：在调用点上的自变量的文本被看作是它自己右边的函数，
生当在被用的过程的代码中到达相应的参数名时，就要计算它。我们总是在调用程序的环境中计算自变，而总是在过程的定义环境中执行过程。
建立内情向量，分配内存的目标代码
（ n维 可变数组,type--每个元素占一个字）
begin k:=1;n:=1;c:=0;
while k<=n do
begin di:=ui-li+ 1;
m:=m*di;
c:=c*di+li;
把 li,ui和 di填进内情向量表区；
k:=k+1
end;
申请 m个空间,令首地址为 a;把 n,c,type,a填进内情向量表区
end
赋值中数组元素的翻译
A? V:=E
V? id[<elist>] | id
<elist>? <elist>,E | E
V? <elist>] | id
<elist>? <elist>,E | id [E
结构（记录），抽象数据类型对象类实例变量的存储结构 (CIR)
class parent { | class parent{
public int a,b,c; | public a,b,c;
public void draw() {..}; | public virtual void draw()
}; |,..
class child:public parent{ |
public d,e; |
public void sift(){…}; | void draw(){…}
};
堆式动态存储分配堆变量堆空间的管理策略减少碎片的技术空间的释放
C++的堆变量
Int *Ptr;
Ptr=new int(5)；
Int *ptr= new int [10]
Delete ptr
Delete[ ] ptr
堆变量是可以在程序运行时根据需要随时创建或删除的变量
C++的堆对象
#include<iostream.h>
Class Myclass{
Public:
Myclass();
Myclass(int k,int j);
void Set(int,int){m=k;n=j;}
Myclass();
Private:
int m,n;
};
Myclass::Myclass(){
Set(0,0);
Cout<<Default<<endl;
}
Myclass::Myclass(int k,int j) {
Set(k,j);
Cout<<―m=―<<m<<endl;
}
Myclass:,?Myclass() {
Cout<<―Destructor‖<<endl;
}
使用 new和 delete的示例
#include<iostream.h>
Int main()
{
Cout<<―one‖<<endl;
Myclass *ptr1=new Myclass;
Delete ptr1;
Cout<<―two‖<<endl;
Ptr1=new Myclass(5,10);
Delete ptr1;
Return 0;
}
one
Defalt
Destructor
two
m=5
Destructor
堆式动态存储分配
Const int ArraySize=24;//default size
Class IntArray{
Public:
//operations performed on arrays
IntArray(int sz=ArraySize);
IntArray(const IntArray&);
~IntArray(){delete ia;}
IntArray& operator= (const
IntArray&);
int& operator[] (int);
int getSize() {return size;}
protected:
//internal data representation
int size;
int * ia;
};
IntArray()函数的实现,引入新的运算符 new
IntArray::IntArray （ int sz)
{
size= sz;
// allocate an integer array of
size
// and set ia to point to it
ia= new int [size];
// initialize array
for (int i=0;i<sz;++i)
ia[i]=0;
}
C++语言中 new操作符施加在一个类型标识符上 （ 包括类名 ）
Pascal语言中,标准过程 new能够动态建立存储空间并相应地置上指针 。 标准过程
dispose是释放空间,
new与 dispose不断改变着堆存储器的使用情况 。
C语言中有这些操作的若干个版本,但最基本的是 malloc 和 free,它们都是标准库
（ stdlib.h） 的一部分堆式动态存储分配需求：
一个程序语言允许用户自由地申请数据空间和退还数据空间,或者不仅有过程而且有进程 （ process）
的程序结构,
操作：
堆提供两个操作,分配操作和释放操作情况,
经一段运行时间之后，这个大空间就必定被分划成许多块块，
有些占用，有些无用（空闲） --碎片问题堆式动态储分配当运行程序要求一块体积为 N的空间时，我们应该分配哪一块给它呢？
运行程序要求一块体积为 N的空间，但发现没有比 N大的空闲块了，然而所有空闲块的总和却要比 N大得多如果运行程序要求一块积为 N的空间，但所有空闲块的总和也不够 N，那又应怎么办呢？有的管理系统采用一种叫做垃圾回收的办法来对付这种局面。即寻找那些运行程序业己无用但尚未释放的占用块堆管理堆空间的管理策略减少碎片的技术空间的释放堆空间的管理策略
1 定长块管理
2 变长块管理堆式动态储分配的实现
1 定长块管理堆式动态储分配最简单的实现是按定长块进行 。
初始化时,将堆存储空间分成长度相等的若干块,每块中指定一个链域,按照邻块的顺序把所有块链成一个链表,用指针 available指向链表中的第一块 。
分配时每次都分配指针 available所指的块,然后
available指向相邻的下一块 。 归还时,把所归还的块插入链表 。 考虑插入方便,可以把所归还的 块 插 在 available 所 指 的块 之 前,然后
available指向新归还的块 。
2 变长块管理除了按定长块进行分配之外，还可以根据需要分配长度不同的存储块，可以随要求而变。按这种方法，初始化时存储空间是一个整块。按照用户的需要，分配时先是从一个整块里分割出满足需要的一小块，以后，归还时，如果新归还的块和现有的空间能合并，则合并成一块；
如果不能和任何空闲块合并，则可以把空闲块链成一个链表。再进行分配时，从空闲块链表中找出满足需要的一块，或者整块分配出去，
或者从该块上分割一小块分配出去。若空闲块表中有若干个满足需要的空闲块时，该分配哪一块呢？通常有三种不同的分配策略不同的情况应采用不同的方法。通常在选择时需考虑下列因素：用户的要求； 请求分配量的大小分布；分配和释放的频率以及效率对系统的重要等等。
（ 1） 首次满足法：只要在空闲块链表中找到满足需要的一块,
就进行分配 。
（ 2） 最优满足法：将空闲块链表中一个不小于申请块且最接近于申请块的空闲块分配给用户,则系统在分配前首先要对空闲块链表从头至尾描一遍,然后从中找出一块,为避免每次分配都要扫描整个链表,通常将空闲块链表空间的大小从小到大排序 。
（ 3） 最差满足法：将空闲块表中不小于申请块且是最大的空闲的一部全分配给用户 。 此时的空闲块链表按空闲的块的大小从大到小排序 。 只需从链表中删除第一个结点,并将其中一部分分配给用户,而其它部分作为一个新的结点插入到空闲块表的适当置上去 。
减少碎片的技术
1分配时，找最小的足够大的块 ---需保持空闲块的大小排序
2 释放时，合并任何相邻的块 ---搜索全部空闲块表，或其它算法
3 将堆变量紧缩在一起空间的释放
1显式释放
2隐式（自动）释放显式释放程序设计语言提供机制如,pascal 的 dispose
C 的 free
程序员必须编写分配和释放存储的明确的调用注意的问题 1 堆变量是不可访问的（垃圾）
2 悬挂（不安全）指针堆式分配和释放的 C语言描述
#define NULL 0
# define MEMSIZE 8096 /* change for different sizes */
typedef fdouble Align;
typedef unionheader
{struct {union header *next;
unsigned usedsize;
unsigned freesize;
}s;
Align a;
}Header;//数据类型 Header保存每个存储块的簿记信息
static Header mem [MEMSIZE];
static Header *memptr= NULL;
void *malloc (unsigned nbytes)
{Header *p,*newp;
unsigned nunits;
nunits= (nbytes+sizeof(Header)-1/ sizeof (Header)+1;
if (memptr == NULL)
{memptr->s.next = memptr = mem;
memptr->s.usedsize = 1;
memptr->s.freesize = MEMSIZE-1;
}
for (p=memptr;
(p->s,next!= memptr) &&(p->s,freesize < nunits);
p=p->s,next);
if (p->s,freesize <> nunits) return NULL;
/* no block big enough */
newp = p+p->s,usedsize;
newp->s,usedsize= nunits;
newp->s,freesize = p->s,freesize-nunits;
newp->s.next = p->s,next;
p->s,freesize=0;
p->s,next= newp;
memptr=newp;
return (void *)(newp+1);
}
void free (void *ap)
{Header * bp,*p,*prev;
bp=(Header *) ap –1;
for (prev= memptr,p=memptr->s,next;
(p!=bp) &&(p!= memptr); prev=p,p=p->s,next);
if (p!=bp) return;
/* corrupted list,do nothing*/
prev->s,freesize += p->s,usedsize + p->s,freesize;
prev->s,next = p->s,next;
memptr = prev;
}
堆的自动管理 -----隐式存储回收在一种需要完全动态的运行时环境的语言
（ OO语言,函数式语言 Lisp,ML)中,堆也必须类似地自动管理 。 自动存储器管理涉及到了前面分配的但不再使用的存储器的回收,可能是在它被分配的很久以后,
而没有明确的对 free的调用 。 这个过程称作垃圾回收 （ grabage collection） 。
垃圾回收垃圾回收程序 ---寻找可被引用的所有存储器并释所有未引用的存储器。
在存储块不再引用时，无论是直接还是通过指针间接的引用，识别这些存储块是一项比维护堆存储 的列表复杂得多的任务。
方法 ---对 malloc的调用失败，激活垃圾回收程序垃圾回收算法 mark and sweep
隐式存储回收 —mark and sweep算法隐式存储回收要求用户程序和支持运行的回收子程序并行工作，因为回收程序需要知道分配给用户程序的存储块何时不再使用。为了实现并行工作，在存储块中要设置回收子程序访问的信息。
存储块格式：
块长度访问计数标记指针用户使用空间回收过程分为两个阶段 。
（ 1） 第一个阶段为标记阶段,对已分配的块跟踪程序中各指针的访问路径 。 如果某个块被访问过,就给这个块加一个标记 。
（ 2） 第二个阶段为回收阶段,所有未加标记的存储块回收到一起,并插入空闲块链表中,然后消除在存储块中所加的全部标记 。
面向对象的语言中的动态存储器面向对象的语言在运行时环境中要求特殊的机制以完成其增添的特性：对象,方法,
继承以及动态联编 。
面向对象语言在对运行时方面的要求差异很大 。
Smalltalk要求与 LISP相似的完全动态环境
C＋＋则保持 C的基于栈的环境实现对象实现对象的一个简单机制是，初始化代码将所有当前的继承特征（和方法）直接地复制到记录结构中（将方法当作代码指针）。但这样做极浪费空间。
另外一种方法是在执行时将类结构的一个完整的描述保存在每个点的存储器中，并由超类指针维护继承性（有时这也称作继承图
（ inheritance graph））。接着同用于它的实例变量的域一起，每个对象保持一个指向其定义类的指针，通过这个类就可找到所有（局部和继承的）的方法。此时，只记录一次方法指针（在类结构中），而且对于每个对象并不将其复制到存储器中。由于是通过类继承的搜索来找到这个机制的，所以该机制还实现继承性与动态联编。其缺 在于：
虽然实例变量具有可预测的偏移量（正如在标准环境中的局部变量一样），方法却没有，而且它们必须由带有查询功能的符号表结构中的名字维护。这是对于诸如 Smalltalk的高度动态语言的合理的结构，因为类结构可以在执行中改变。
C++中选择的方法将整个类结构保存在环境中,计算出每个类的可用方法的代码指针列表,并将其作为一个虚拟函数表 （ virtual function table） 而存放在
（ 静态 ） 存储器 。 它的优点在于：可做出安排以使每个方法都有一个可预测的偏移量,
而且也不再需要用一系列表查询遍历类的层次结构 。 现在每个对象都包括了一个指向相应的虚拟函数表而不是类结构的指针 （ 当然,
这个指针的位置必须也有可预测的偏移量 ） 。
例 C++类声明：
class A
{public:
double x,y;
void f();
virtual void g();
};
class B:public A
{public:
double z;
void f();
virtual void h();
};
类 A的一个对象应出现在存储器中 （ 带有它的虚拟函数表 ）
而类 B的一个对象则应如下所示：
x
y
vtp A::g
B::h
A::g
X
Y
vtp
z
