第三节 栈式分配
?语言特点：允许递归，允许动态数组，
允许过程嵌套定义
一, 只含半静态变量的栈式分配
1,特点,
?仅允许递归调用
?变量及活动记录长度可静态确定
?一个单元可多次激活而有多个实例,
每个活动记录是在单元每次激活时
动态建立并与代码段建立绑定关系
的
2,处理方法
(1)设置当前栈指针 current,表示当前活动
记录的开始位置
(2)指针 free表示数据存储器下一个可用单元
(3)变量绑定于它在活动记录中的常数位移 i,
变量通过 current变址访问
(4)A调用 B时, 在 A活动记录的栈顶之上建
立起绑定于 B的当前实例的活动记录
(5)从 B返回时, 释放其活动记录
3,动态连接和动态链
?动态连接,A调用 B时, B的活动记
录中保存的 A的活动记录地址
?动态链：由动态连接组成的一个调
用链
A
E
F
G
F
A call E; E call F; F call G; G call F;
..,
..,
..,
..,
..,
4,CALL P 的处理
(1)保存返回地址
D [ free ],= ip + 20
(2)保存主调过程的 current
D [free + 4],= current
(3)建立 P的 current
current,= free
(4)调整 free
free,= free + L
(5)转子
ip,= P的代码段首地址
返回地址
动态连接
返回地址
动态连接
A的活动记录
即将建立的
P的活动记录
current
free
过程 A中调用了 P
返回地址
动态链
返回地址
动态链
A的活动记录
P的活动记录
current
free
进入过程 P以后
5,RETURN语句的处理
(1)恢复 free
free,= current
(2)恢复主调过程的 current
current,= D[current + 4]
(3)返回
ip,= D [free]
二, 半静态变量的栈式分配
1,活动记录内容
返回地址
动态链
静态链
保护区
参数单元
局部变量
临时变量
数组存储区
其中，局部变量中包括数组的描述符
2,动态数组空间的分配
(1)编译时, 分配内情向量表区, 并产
生在运行时动态建立内情向量和分
配数组空间的指令 ;
(2)一个单元激活后 （ 进入该单元 ）,
遇到动态数组说明时, 调用上述指
令 （ 填内情向量, 分配数组空间 ）,
并调整 free,= free + L。
三, 动态变量的存储分配
在堆上进行存储分配
四, 非局部环境
非局部环境的引用必须考虑变量的作用
域
1,静态作用域规则 ——最近嵌套规则
(1)嵌套的层次
最外层单元为 0层，若 P是 Q的直接外
层，则 Q的层次 = P的层次 ＋ 1
unit A;
y,int;
unit B;
end B;
y,int;
unit C;
end D;
end C;
…..,
unit D;
……
…..,
end E;
z,int;
unit F;
end G;
unit G;
x,y,int;
…..,
……
…..,
unit E;
z:=x+y;
end F;
……
…..,
end A;
A
B
C
D
E
F G
x,int;
(2)最近嵌套规则
变量的作用域是指可访问该变量的
程序范围
(I)变量 x在单元 U1中被说明, 则 x的
作用域局部于 U1,或称 x在 U1中是
可见的 ;
(II)变量 x在 U1中没有被说明, 则 x的
作用域是包围 U1的说明了 x的最小外
层单元 。
2,动态作用域规则
这是一种最近活动规则, 对非局部
变量, 引用的应是最近外层中说明
的 。
动态作用域的最近外层指的是动态
调用外层, 如 A-E-F-G-F的调用序列：
当前 F的调用外层为 G。
五, 对非局部环境的引用
1,静态作用域规则
(1)静态连接和静态链
?静态连接：指向 嵌套直接外层 的最
新活动记录的指针，它处于活动记录位
移为 8的存储单元中。
?静态链：各嵌套程序单元的活动记
录中，静态连接的序列构成一个静态链。
(2)非局部变量 x的地址的求法
假设单元 p中引用了单元 t中的变量 x，
且 p,t的深度分别为 np,nt 。
设 d = np – nt,将 x约束于 （ d,offset）,
问题的关键是找 t的最新活动记录 Dt,
而 Dt＋ offset即为 x的地址 。
?np – nt = 0,x为 p中的局部变量
Dt = current
?np – nt = 1,t是 p的直接外层
Dt ＝ D[current + 8]
?np – nt = 2,t是 p的再外层
Dt = D[D[current + 8] + 8]
?np – nt = 3,t是 p的再外层的外层
Dt = D[D[D[current + 8] ＋ 8] ＋ 8]
令 np – nt = d,则
f(d) = if d = 0
then curent
else D[f(d-1)+8]
f(d) 表示沿 p的静态链在栈中向下搜索
d步。
(3)静态连接的确定
单元 A调用单元 B的几种情形,
(I)nA-nB=0 (II)nA-nB=-1 (III)nA-nB=1 (IV)nA-nB>1
B0 B0 B0 B0
B
A
call B
A
B
call B
B
A
call B
B
call B
A
P
P1
(I)nA - nB = 0,B的静态连接＝ f (1)
(II)nA - nB = -1,B的静态连接＝ f (0 )
(III)nA - nB = 1,B的静态连接＝ f (2)
(IV)nA - nB = d,B的静态连接＝ f (d ＋ 1)
(4)调用语句 call B 的处理
D[free],= ip + 24
D[free + 4],= current
D[free + 8],= f(d + 1)
current,= free
free,= free + L
ip,= B 的代码段首址
2,动态作用域规则
此时, 静态连接是一指针, 指向动
态调用直接外层的活动记录, 其实
与动态连接一致 。
第四节 堆分配
一, 进行堆分配的几种情形
1,动态变量的描述符和变量存储区均分
配在堆上
2,二个程序单元的生存期相互交叉时
3,允许动态申请内存时
二, 存储空间的组织
1,自由块处于 free指向的一个链表中
2,使用块的信息登记于使用块记录中，
释放时被连接到 free链中
三, 存储分配的几种情形
设自由块总长度为 N，申请长度为 n
1,有大于或等于 n的自由块，采用首次
拟合法
2,自由块的长度均小于 n，且 N ≥ n,
移动使用块
3,N < n，回收无用单元
第五节 参数传递
先看例子,
procedure swap (a,b, integer);
var temp, integer;
begin temp,= a;
a,= b;
b,= temp
end;
……
call swap(x,y);
…,.,
形式参数
实在参数
几点说明,
1,程序单元间通信方式有非局部环境
和参数传递
2,参数，形参，实参
3,参数传递的三种类型：数据参数传
递，过程参数传递，类型参数传递
一, 数据参数传递
以调用 swap ( i,a[i] )为例，且调用前
i = 3,a 的几个元素分别为 7,1,4,5,8
1,引用调用（传地址）
?将实参的地址传递给相应的形参
?在单元中对形参的引用，实际上是对形
式单元中实参地址的间接引用
swap(i,a[i]); 相当于执行,
a:=i的地址 ;
b:=a[3]的地址 ;
temp:=a?; (temp=3)
a?:=b?; (i=4)
b?:=temp; (a[3]=temp=3)
执行结果, i=4,a[3]=3
2,值调用
?形参只起局部变量作用
(1)传值,实参的值 ?形式单元
(2)结果调用,形参的结果值 ?实参单
(3)传值得结果：实参的值 ?形式单元
形参的结果值 ?实参单元
?实现技术：一个形参对应两个单元
对“传值得结果” swap(i,a[i]); 相当于执行,
a1:=i的地址 ; a2:=3;
b1:=a[3]的地址 ; b2:=4;
temp:=a2; (temp=a2=3)
a2:=b2; (a2=b2=4)
b2:=temp; (b2=temp=3)
a1?:=a2; (i=a2=4)
b1?:=b2; (a[3]=b2=3)
执行结果, i=4,a[3]=3
3,名调用
?用实参原样替换形参的出现
?若被调用单元中的局部名与调用处的名
发生冲突，则对局部名重新命名
?把实参用括号括起来
?实现技术：把实参处理成一个子程序
（ thunk,称为参数子程序），对形参的每
次引用就调用该子程序
swap(i,a[i]); 相当于执行,
temp:=i; (temp=i=3)
i:=a[i]; (i=a[3]=4)
a[i]:=temp; (a[i]=a[4]=temp=3)
执行结果, i=4,a[4]=3 (a[3]不变 )
二, 过程参数的传递
1,调用形式
P
……
call Q(T)
…..,
Q(S)
……
call S
…..,
其中,call S实际上就是 call T,因此需向
形参 S传递 T的代码首址以及 T的引用环境
P
T
call Q(T)
T T
P
T
P
Q(S)
call S
Q(S)
call S
Q(S)
call S
Q(S)
call S
P
call Q(T)
call Q(T)
call Q(T)
2,在静态作用域规则下
P,T,Q之间的关系
(1)可见,call S处 T的非局部环境，应
由单元 P中 call Q(T)处 T的非局部环境指
出，即 f (d + 1),d = nP -nT
(2)处理方法,
?为 S设置两个指针，一个是 T的代码段首
址，另一个是 T的静态连接
?执行 call S时，将静态连接记入 T的活动
记录，执行 T的代码
3,在动态作用域规则下
?call Q(T)时只向 S传递 T代码段首址
?非局部环境由动态链给出，即 T的动态外
层总是 Q
?语言特点：允许递归，允许动态数组，
允许过程嵌套定义
一, 只含半静态变量的栈式分配
1,特点,
?仅允许递归调用
?变量及活动记录长度可静态确定
?一个单元可多次激活而有多个实例,
每个活动记录是在单元每次激活时
动态建立并与代码段建立绑定关系
的
2,处理方法
(1)设置当前栈指针 current,表示当前活动
记录的开始位置
(2)指针 free表示数据存储器下一个可用单元
(3)变量绑定于它在活动记录中的常数位移 i,
变量通过 current变址访问
(4)A调用 B时, 在 A活动记录的栈顶之上建
立起绑定于 B的当前实例的活动记录
(5)从 B返回时, 释放其活动记录
3,动态连接和动态链
?动态连接,A调用 B时, B的活动记
录中保存的 A的活动记录地址
?动态链：由动态连接组成的一个调
用链
A
E
F
G
F
A call E; E call F; F call G; G call F;
..,
..,
..,
..,
..,
4,CALL P 的处理
(1)保存返回地址
D [ free ],= ip + 20
(2)保存主调过程的 current
D [free + 4],= current
(3)建立 P的 current
current,= free
(4)调整 free
free,= free + L
(5)转子
ip,= P的代码段首地址
返回地址
动态连接
返回地址
动态连接
A的活动记录
即将建立的
P的活动记录
current
free
过程 A中调用了 P
返回地址
动态链
返回地址
动态链
A的活动记录
P的活动记录
current
free
进入过程 P以后
5,RETURN语句的处理
(1)恢复 free
free,= current
(2)恢复主调过程的 current
current,= D[current + 4]
(3)返回
ip,= D [free]
二, 半静态变量的栈式分配
1,活动记录内容
返回地址
动态链
静态链
保护区
参数单元
局部变量
临时变量
数组存储区
其中，局部变量中包括数组的描述符
2,动态数组空间的分配
(1)编译时, 分配内情向量表区, 并产
生在运行时动态建立内情向量和分
配数组空间的指令 ;
(2)一个单元激活后 （ 进入该单元 ）,
遇到动态数组说明时, 调用上述指
令 （ 填内情向量, 分配数组空间 ）,
并调整 free,= free + L。
三, 动态变量的存储分配
在堆上进行存储分配
四, 非局部环境
非局部环境的引用必须考虑变量的作用
域
1,静态作用域规则 ——最近嵌套规则
(1)嵌套的层次
最外层单元为 0层，若 P是 Q的直接外
层，则 Q的层次 = P的层次 ＋ 1
unit A;
y,int;
unit B;
end B;
y,int;
unit C;
end D;
end C;
…..,
unit D;
……
…..,
end E;
z,int;
unit F;
end G;
unit G;
x,y,int;
…..,
……
…..,
unit E;
z:=x+y;
end F;
……
…..,
end A;
A
B
C
D
E
F G
x,int;
(2)最近嵌套规则
变量的作用域是指可访问该变量的
程序范围
(I)变量 x在单元 U1中被说明, 则 x的
作用域局部于 U1,或称 x在 U1中是
可见的 ;
(II)变量 x在 U1中没有被说明, 则 x的
作用域是包围 U1的说明了 x的最小外
层单元 。
2,动态作用域规则
这是一种最近活动规则, 对非局部
变量, 引用的应是最近外层中说明
的 。
动态作用域的最近外层指的是动态
调用外层, 如 A-E-F-G-F的调用序列：
当前 F的调用外层为 G。
五, 对非局部环境的引用
1,静态作用域规则
(1)静态连接和静态链
?静态连接：指向 嵌套直接外层 的最
新活动记录的指针，它处于活动记录位
移为 8的存储单元中。
?静态链：各嵌套程序单元的活动记
录中，静态连接的序列构成一个静态链。
(2)非局部变量 x的地址的求法
假设单元 p中引用了单元 t中的变量 x，
且 p,t的深度分别为 np,nt 。
设 d = np – nt,将 x约束于 （ d,offset）,
问题的关键是找 t的最新活动记录 Dt,
而 Dt＋ offset即为 x的地址 。
?np – nt = 0,x为 p中的局部变量
Dt = current
?np – nt = 1,t是 p的直接外层
Dt ＝ D[current + 8]
?np – nt = 2,t是 p的再外层
Dt = D[D[current + 8] + 8]
?np – nt = 3,t是 p的再外层的外层
Dt = D[D[D[current + 8] ＋ 8] ＋ 8]
令 np – nt = d,则
f(d) = if d = 0
then curent
else D[f(d-1)+8]
f(d) 表示沿 p的静态链在栈中向下搜索
d步。
(3)静态连接的确定
单元 A调用单元 B的几种情形,
(I)nA-nB=0 (II)nA-nB=-1 (III)nA-nB=1 (IV)nA-nB>1
B0 B0 B0 B0
B
A
call B
A
B
call B
B
A
call B
B
call B
A
P
P1
(I)nA - nB = 0,B的静态连接＝ f (1)
(II)nA - nB = -1,B的静态连接＝ f (0 )
(III)nA - nB = 1,B的静态连接＝ f (2)
(IV)nA - nB = d,B的静态连接＝ f (d ＋ 1)
(4)调用语句 call B 的处理
D[free],= ip + 24
D[free + 4],= current
D[free + 8],= f(d + 1)
current,= free
free,= free + L
ip,= B 的代码段首址
2,动态作用域规则
此时, 静态连接是一指针, 指向动
态调用直接外层的活动记录, 其实
与动态连接一致 。
第四节 堆分配
一, 进行堆分配的几种情形
1,动态变量的描述符和变量存储区均分
配在堆上
2,二个程序单元的生存期相互交叉时
3,允许动态申请内存时
二, 存储空间的组织
1,自由块处于 free指向的一个链表中
2,使用块的信息登记于使用块记录中，
释放时被连接到 free链中
三, 存储分配的几种情形
设自由块总长度为 N，申请长度为 n
1,有大于或等于 n的自由块，采用首次
拟合法
2,自由块的长度均小于 n，且 N ≥ n,
移动使用块
3,N < n，回收无用单元
第五节 参数传递
先看例子,
procedure swap (a,b, integer);
var temp, integer;
begin temp,= a;
a,= b;
b,= temp
end;
……
call swap(x,y);
…,.,
形式参数
实在参数
几点说明,
1,程序单元间通信方式有非局部环境
和参数传递
2,参数，形参，实参
3,参数传递的三种类型：数据参数传
递，过程参数传递，类型参数传递
一, 数据参数传递
以调用 swap ( i,a[i] )为例，且调用前
i = 3,a 的几个元素分别为 7,1,4,5,8
1,引用调用（传地址）
?将实参的地址传递给相应的形参
?在单元中对形参的引用，实际上是对形
式单元中实参地址的间接引用
swap(i,a[i]); 相当于执行,
a:=i的地址 ;
b:=a[3]的地址 ;
temp:=a?; (temp=3)
a?:=b?; (i=4)
b?:=temp; (a[3]=temp=3)
执行结果, i=4,a[3]=3
2,值调用
?形参只起局部变量作用
(1)传值,实参的值 ?形式单元
(2)结果调用,形参的结果值 ?实参单
(3)传值得结果：实参的值 ?形式单元
形参的结果值 ?实参单元
?实现技术：一个形参对应两个单元
对“传值得结果” swap(i,a[i]); 相当于执行,
a1:=i的地址 ; a2:=3;
b1:=a[3]的地址 ; b2:=4;
temp:=a2; (temp=a2=3)
a2:=b2; (a2=b2=4)
b2:=temp; (b2=temp=3)
a1?:=a2; (i=a2=4)
b1?:=b2; (a[3]=b2=3)
执行结果, i=4,a[3]=3
3,名调用
?用实参原样替换形参的出现
?若被调用单元中的局部名与调用处的名
发生冲突，则对局部名重新命名
?把实参用括号括起来
?实现技术：把实参处理成一个子程序
（ thunk,称为参数子程序），对形参的每
次引用就调用该子程序
swap(i,a[i]); 相当于执行,
temp:=i; (temp=i=3)
i:=a[i]; (i=a[3]=4)
a[i]:=temp; (a[i]=a[4]=temp=3)
执行结果, i=4,a[4]=3 (a[3]不变 )
二, 过程参数的传递
1,调用形式
P
……
call Q(T)
…..,
Q(S)
……
call S
…..,
其中,call S实际上就是 call T,因此需向
形参 S传递 T的代码首址以及 T的引用环境
P
T
call Q(T)
T T
P
T
P
Q(S)
call S
Q(S)
call S
Q(S)
call S
Q(S)
call S
P
call Q(T)
call Q(T)
call Q(T)
2,在静态作用域规则下
P,T,Q之间的关系
(1)可见,call S处 T的非局部环境，应
由单元 P中 call Q(T)处 T的非局部环境指
出，即 f (d + 1),d = nP -nT
(2)处理方法,
?为 S设置两个指针，一个是 T的代码段首
址，另一个是 T的静态连接
?执行 call S时，将静态连接记入 T的活动
记录，执行 T的代码
3,在动态作用域规则下
?call Q(T)时只向 S传递 T代码段首址
?非局部环境由动态链给出，即 T的动态外
层总是 Q
