1
编译原理第六章运行时存储空间管理上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 5月
2
第六章 运行时存储空间管理
§ 6.1 变量及存储分配一个用高级语言写的程序要投入运行，首先要有一组可运行的代码，这组代码应与高级语言的程序等价；
其次还需要一个运行环境，对程序中的变量作存储分配，提供各种运行信息。前者涉及程序语言的编译系统，我们已在前几章中作了概要介绍。后者涉及变量以及变量的存储分配和存储管理的问题。本章主要讨论运行时的存储管理问题，也涉及了符号表的组织与管理。
3
一、程序的存储空间一个程序要运行,至少应有这样两个存储空间：
(1) 代码空间 这是经翻译后生成的目标代码的存储区域,
线性存放着目标指令序列 。 对三地址代码来说,当前执行的指令位置由指令指针 ip指示 。 因此,只要将 ip指向程序的第一个语句,程序便处于开始执行的状态,以后每执行一个语句,ip便加 4(我们约定,三地址代码的每个语句占 4个字节 ),指向下个语句 。 要改变程序控制顺序,只要将转向点赋给 ip即可 。
4
(2) 数据空间 每个程序都定义一定数量的各种类型的变量和常数,翻译程序必须为之分配相应的存储空间 。 初等类型的数据,如逻辑,整型,实型变量,通常以存储器的基本存储单元如字节,字,双字来存储 。 集合数据,如数组,
串,记录结构等,一般用若干个连续的字节或字来存储 。
这便使变量绑定 (Biding)于一个存储区域 。 变量获得存储区的这种活动称为分配 (Allocation)。 一个变量一旦被建立,
就获得了相应的存储区,完成了存储区与变量的绑定 。 除了这些变量与常数外,数据空间还保存了程序的一些控制和管理信息 (例如,反映程序间调用关系的控制链,反映程序间变量引用关系的引用链等 ),说明程序实体的绑定信息的描述符以及其他等等 。
5
对一个程序来说,它的代码长度可以在编译时刻完全确定下来,因此,编译时便可安排代码空间 。 但对数据空间来说,不仅程序实体的属性影响了存储分配 (例如变量类型影响了每个数据元素的存储长度,作用域决定了变量绑定于某存储区的空间范围,生存期决定了这种约束的时间范围 )，
而且语言的运行特性也决定了数据空间的分配和管理应采用的方法和策略 。 有的语言在运行前就能确定数据空间的大小,因而在编译时刻就能进行存储分配,这种分配策略称之为静态分配 (Static Allocation),有的语言则必须在运行时刻才能作分配,称之为动态分配 (Dynamic Allocation)。
有的语言因变量生存期具嵌套特性而采用栈分配 (Stack
Allocation)策略,有的语言因生存期的随机交叉特性而采用堆分配 (Heap Allocation)策略 。
6
二,活动记录一个程序单元 (Program Unit,以下简称单元 )的一次激活所需的信息管理是通过相应的活动记录 (Activation Record)来实施的 。 一个单元的每次激活,都应建立相应的活动记录,
它是单元实例的一部分 。
一个活动记录是一连续存储区 。 通常,它的内容如图 6.1所示 。
当单元 A调用单元 B时,应中断 A的活动,建立 B的活动记录,将调用的实在参数传递给 B的活动记录,将控制转移至
B,使 B处于活动状态 。 因此,活动记录中应包含如下内容：
7
返回指针
returned pointer
动态链
dynamic link
静态链
static link
保存的机器状态
saved machine states
参数单元
parameters
局部变量
local variables
临时变量
temporaries
图 6.1活动记录
8
(1) 分配给形式参数的存储单元,这是实参传递的存储区 。
(2) A被中断时的状态以及中断结束后的返回点,以便 B的活动结束后能返回被中断的 A,使 A继续活动起来 。
(3) B的局部变量或它们的描述符,以及临时变量 。
(4) 记录动态调用关系的动态链及记录静态嵌套关系的静态链 。 静态链用以实施静态作用域规则,动态链除记录了调用控制关系外,也是动态作用域实施的依据 。
显然,除了变量存储区外 。 活动记录的其他部分的存储长度都是编译时可确定的 。 如果一个单元不含动态数组和动态类型数据,这个单元的活动记录的长度在编译时便可确定 。 对活动记录中某元素 i的访问,可通过该元素在活动记录中的位移 offset(i)来表示,一旦活动记录被分配在存储位置 D,则 i的地址为
D+offset(i)
9
三,变量的存储分配由上可见,局部变量的存储分配对活动记录的建立有着主要影响 。 从存储分配角度看,变量有四种类型 。
(1) 静态变量 (Static Variable) 如果每个单元的活动记录,
以及每个变量的存储位置,在编译时均可确定,在运行时不会变化,那么存储分配可在编译时完成,这便是所说的静态分配 。 静态分配是在编译时将变量绑定于一个存储区,
不管在程序单元的哪一次活动中,这些变量都绑定于相同的存储位置 。 这类变量称为静态变量 。
10
(2) 半静态变量 (Semistatic Variable) 如果一个语言允许单元的递归调用,一个单元可递归地被多次激活,这就会为一个单元建立起多个活动记录 。 变量是在单元每次激活时,
动态地绑定于刚建立的活动记录 。 这类变量的长度必须是编译时可确定的,因而活动记录的长度,变量 x在活动记录中的相对位置 (即位移 offset(x)),都是编译时可确定的 。 运行时,一旦该单元被激活,相应活动记录便获得物理存储区 D,变量 x便被定于 D+offset(x)。 这类变量称为半静态变量 。 虽然每个活动记录的长度,每个变量在活动记录中的相对位移,如同静态变量那样在编译时可知 （ 称为静态可确定 ） 但这样的活动记录的个数却依赖于该单元的递归调用深度,这是运行时可知 （ 动态可确定 ） 的 。
11
(3) 半动态变量 (Semidynamic Variable) 如在单元 U中,有
ALGOL 68的说明：
[l,m] int a；
[l,n] real b
它定义了体积为 m的整型数组 a和体积为 n的实型数组 b。 如果 m和 n都不是常量,它们的值只有当 U被激活时才能确定,
那么编译时不可能为它们作存储分配 。 即使在活动记录中为它们的存储作安排也不可能 。 虽然在本例中,数组 a相对于活动记录的位移有可能在编译时确定,但它的长度在编译时是不能确定的,因此紧接着要作存储分配的数组 b在活动记录中的相对位移,在编译时也不能确定了 。 因此,动态数组不可能绑定于活动记录的常量位移 。 像动态数组这一类变量,称为半动态变量 。
12
对于半动态变量,在编译时可以在活动记录中为它们安排描述符 。 描述符是数据对象的属性集,记录着程序实体的约束信息 。 对上例中的动态数组 a和 b来说,它们的描述符包含两个元素：一个元素是指向 a或 b在活动记录中的首址的指针,另一个元素则记录了动态数组每一维的上下界 。
很明显,数组的维数是静态可知的,因此描述符的长度也是静态可知的,所以它们在活动记录中的位移也是可确定的 。 只是描述符的内容,即数组在活动记录中的首址和每一维的上,下界,在编译时是不可知的,需待 U被激活并运行至动态数组说明时,方可确定每一维的上,下界,将它们记入描述符的第二个元素中,并据此算出数组的体积 D，
在刚建立起来的 U的活动记录顶端,为数组分配一个大小为
D的存储区,将数组描述符的第一个元素指向该存储区 。 以后对该数组的任一元素的访问,可通过描述符计算出该数组元素对数组起始元素的位移而获得访问地址 。
13
(4) 动态变量 (Dynamic Variable) 有一类数据对象，即使到它所在单元被激活时，其活动记录的长度仍不能确定，因为这类数据对象的存储区域的大小在运行时仍有可能发生变化。例如 APL的变量可以是动态类型的，它不是显式说明，而是由运行时当前值隐式确定，并随运行路径的变化而变化着。又例如 ALGOL 68的灵活数组 (Flexible Array)，
它的界是可变的，在运行中可能是二维的，也可能是三维的。再如 PL/1和 Pascal等语言中，允许数据的动态扩大和压缩，由一组结点构成的数据结构，结点可以动态加入，也可以动态删除。像链表和树就是这样的数据结构，结点由指针来连接，结点在程序运行时分配。对于这些在运行时可能改变变量类型和变量结构的，不仅数据对象本身不能静态分配，而且它们的描述符的内容，甚至描述符的长度都不是静态可确定的，这类变量称为动态变量。总之，动态变量表示的数据对象的长度和个数，以及它们的描述符的内容和长度，都可能在它的生存期中改变。
14
四,存储分配模式根据以上讨论,存储分配可采取静态,栈式和堆三种方式 。
1,静态分配如果程序语言只允许静态变量,那么变量与存储区域的绑定关系在编译时便可建立,并完成存储分配 。 这一类语言便是静态语言 。 它们不允许递归调用,不允许动态数组,
不允许动态类型的数据对象,即不允许有非静态变量 。
FORTRAN,COBOL便是静态语言 。
15
2,栈式分配凡不满足静态分配条件的语言,自然归入了动态分配类 。
但对半静态变量和半动态变量来说,所有局部变量在单元激活时隐式建立,活动记录长度或者静态可确定,或者在单元被激活时确定 。 同时,各单元之间的调用关系遵循
,后进先出,模式,即单元 A被激活,建立起一个单元实例,
分配了 A的活动记录 。 执行中 A调用了单元 B,于是 A的活动暂中断 (A的活动记录并未撤消,仍保留着 ),为激活了的
B建立一个单元实例,分配 B的活动记录 。 随着 B运行结束,
完成了 B的当前实例,释放 B的活动记录,返回到被暂时中断的单元 A,继续 A的活动,直至 A的活动结束时,才撤消
A的活动记录 。 这表明单元 B的生存期嵌套在 A的生存期中,
即它们之间存在着动态嵌套的关系,相应的活动记录的建立和撤消满足后进先出的模式 。 因此,我们选择栈来分配活动记录是十分自然的 。 由于这个原因,半静态变量和半动态变量也称为栈变量 (StackVariable)。
16
应该指出,栈并不是栈式语言语义的一部分 。 这类语言的语义仅要求每激活一个单元,其局部变量应绑定于这个刚激活单元的活动记录,并遵循作用域的规则 。 而栈是实现这种语义的有效模型 。
虽然半静态变量和半动态变量都是栈式分配的,但半静态变量绑定于活动记录的常数位移,即它可在编译时分配于活动记录中 。 而半动态变量则在编译时只在活动记录中分配了它的描述符,需待所有单元 U被激活后,在新建立的 U
的活动记录顶端 (即栈顶 )按描述符信息,分配半动态变量的存储空间 。
基于栈的存储分配也完全适用于静态语言，栈式分配也被许多静态语言的实现所采用。
17
3,堆分配由于动态变量表示的数据对象,它的长度,个数都有可能在执行中改变,即在其生存期中动态改变,就不可能在栈上为这样的对象作分配 。 例如在 Pascal中,每个指针只能指向一种类型的对象 。 假定 P在 A中已被说明为类型 t的指针,
B动态嵌套在 A中,B中包含了一个分配语句,New (P)
...
代码
code
静态数据
static data
栈
stack
堆
heap
图 6.2 存储组织
18
它建立一个类型为 t的对象,并将对象的地址赋于 P。 当 B执行到这个分配语句时,B的活动记录在栈顶,而 A的活动记录在 B的活动记录下面 。 这个 A中定义的,B中分配的 P指向的对象,不能在 B的活动记录中分配 。 因为 B的活动结束时,
它的活动记录就得释放,但 P所指向的这个对象的生存期并未结束,不应该释放 。 可是将这个对象分配在 A的活动记录中也是行不通的 。 因为如果 P所指的这个对象是个灵活数组,
这就无疑要重新构造栈了 。 所以对这样的对象可另辟一个并非栈模式的存储区进行分配,这个存储区称为堆 。 一般而言,出现下列情况：
(1) 单元活动结束后,局部变量的值还需保留 。
(2) 调用单元与被调用单元的生存期不满足嵌套关系,即出现交叉现象,那么后进先出的模式是不合适的,必须用堆模式分配 。
因此运行时,常把目标代码与全局变量,静态数据安排在存储空间的底端 。 在静态空间之上为栈空间,堆则安排在存储空间的另一端,栈和堆可动态的迎面增长,如图 6.2所示 。
19
§ 6.2 静态分配如前所述,一个语言如果不允许递归调用,动态数组和动态类型时,便可采用静态分配模式 。 FORTRAN是一种典型的静态语言 。 下面讨论它的静态分配 。
一,FORTRAN 程序的运行时结构一个 FORTRAN程序由一组程序单元,即一个主程序,若干个子程序或者函数组成 。 每个单元可独立编译,绑定于一个活动记录 。 活动记录及变量在运行前便可建立,其生存期延续到整个程序执行结束 。 变量的作用域局部于它被说明的那个单元,而 COMMON语句说明的变量是全局于各单元的全局变量,分配在全局数据活动记录中 。
对于 FORTRAN来说,本章第一节中提到的动态链和静态链,动态变量及半动态变量的描述符不会出现在活动记录中 。 如果只关心存储分配,则一个 FORTRAN程序的编译要经过三个步骤 。
20
(1) 编译时，变量约束于活动记录的常量位移，因此每一个变量的引用都可用二元式 (单元名，位移 )表示。而转换控制语句中对指令的引用也可翻译成二元式 (单元名，指令在代码段中的位移 )。
(2) 连接时，须将程序所有单元连接起来。每连接一个单元，
将它的代码段分配到代码区，活动记录分配到数据区。
这时，翻译后的所有引用活动记录和代码段的二元式都可转换成一个单一的存储地址。例如单元 i的活动记录从
1000存储单元开始分配，则二元 (i,6)表示的数据单元引用地址为 D[1006]。同样，单元 i的代码段从 2000存储单元开始分配，则 (i,5)表示的指令地址为 C[2005]。当然，实际的连接器应将各单元的代码段连接成一个可重定位
(Relocatable)代码，只是我们关心连接过程，所以避开了它。
(3) 装入时，将连接后的可重定位代码程序装入主存储器并定位，成为可直接执行的机器代码，并将 ip指向程序第一条指令，使程序处于可执行状态。
21
经过上述编译过程，一个 FORTRAN程序的存储结构如图
6.3所示。
ip 单元 1代码段单元 2代码段单元 n代码段
…
单元 1活动记录全局数据活动记录单元 2活动记录单元 n活动记录
…
图 6.3 FORTRAN程序的存储结构
22
二,运行环境的转换由于这一章的主题是存储分配,我们将对引起控制转换的语句的编译感兴趣,因为两个单元之间的控制转换,将引起环境的变换 。
为叙述方便,我们约定：单元 i的活动记录中位移为 j的存储单元内容记为 d[i,j],单元 i的代码段中位移为 j的语句记为
c[i,j],它们经连接后的实际存储地址记为 D[m],C[m]。 X
的地址记为 &X,X可为 d[i,j]或 c[i,j]。
1,GOTO X语句编译器将标号 X编译成二元式 [i,j]。 GOTO X的语义是使转移的目标地址成为指令指针的当前内容,即
ip:=& c[i,j]
23
2,过程调用语句 CALLP
过程调用时,编译器为之实现的语义为
(1) 在单元 P的活动记录位移为 0的存储单元中存放调用后返回的指令地址 。 因为调用语句翻译成两个语句,每个语句占 4字节,故返回地址为 ip+8。
D[P,0]:= ip+8
(2) 单元 P的代码段的第一个语句地址为 & c[P,0],将它置于
ip中,实现将控制转移到 P。
ip:= & c[P,0]
经连接后为
D[m]:= ip+8
ip:= n
其中 m为 P活动记录的首址,n为 P代码首址 。
24
3,返回语句 RETURN
其语义为将所在单元 P的活动记录位移为 0的存储单元中的返回地址置于 ip中,实现返回 。 即
ip:= d[P,0]
连接后为
ip:= D[m]
m是单元 P的活动记录的首址 。
25
§ 6.3 栈式分配类 ALGOL语言是由 ALGOL 60派生的一类语言,
它们都允许递归调用一个单元,有的允许动态数组,
有的允许动态建立数据对象,它们的调用关系是后进先出的栈模型,因此采用动态的栈式存储分配 。
这类语言的另一个特点是静态嵌套的程序结构,采用静态作用域规则 。 这些特性对于存储分配都有影响 。
26
一、只含半静态变量的栈式分配这里实际指的是只允许递归调用的栈式分配 。 在这种情况下,每个变量的长度,以及整个活动记录的长度在编译时就可以确定 。 但由于递归调用,一个单元可多次激活而有多个实例,每个活动记录是在单元每次激活时动态建立并与代码段建立绑定关系的 。 在编译时,变量 X绑定于它在活动记录中的常数位移 i,所以单元一旦被激活,相应活动记录便在数据存储器的栈顶获得分配,当前栈指针 current便是活动记录的开始位置,释放指针 free指向数据存储器下一可用单元,因此变量 X的地址为 D[current+i]。 对于数组元素来说,数组 a的初始元素的位移为 offset(a),栈当前指针为 current,则数组元素 a[i]的地址为：
current + offset(a) + i
27
单元 A调用了单元 B,使 B激活,从 A的活动记录的栈顶之上 (由 free指示 )建立起绑定于 B的当前实例的活动记录 。 为了能使 B返回 A,B的活动记录应保存返回地址和 A的活动记录地址,我们称它为动态连接 (Dynamic Link),由它组成了一个调用链,称为动态链 (Dynamic Chain)。 单元 B的当前实例一旦结束,绑定于它的局部变量的生存期也告终结,相应的活动记录便可自栈顶撤消,由动态链可将当前指针 current调整指向 A的活动记录,使之处于栈顶位置,A的这个实例又处于活动之中 。 如果以后 A又调用 C,则 C的活动记录又可分配于 A的活动记录栈顶之上,即原行 B的活动记录位置 。 很显然,活动记录的分配与释放是后进先出的 。
28
因此,将调用语句 CALLP编译成下列五个语句：
(1) 调用语句之后的第 5个语句位置为返回地址,新的活动记录将建在 free所指的栈顶之上,故有
D[free],= ip + 20
(2) 将建立的新的活动记录的动态连接就是当前活动记录
D[free + 4],= current
(3) 当前活动记录指针 current调整至新建的活动记录,即
current:=free
(4) 释放指针调整至新的活动记录之上,即
free:=free+L
其中 L为 P的活动记录的长度,是静态可确定的 。
(5) 使 P的实例处于活动状态,指令指针指向 P的代码：
ip:=P的代码段首地址 。
29
单元 P当前实例结束时,返回调用单元是由下列三个语句实现的：
(1) 删除当前的活动记录,使 free指向当前的 current,即
free:=current
(2) 根据动态连接,使 current指向调用单元的活动记录,即
current:=D[current+4]
(3) 实现控制转移,按返回指针返回调用单元,即
ip:=D[free]
30
[例 6.2]基于上述管理方法,调用序列
A Call E
E Call F
F Call G
G Call F
的活动记录栈的状态如图 6.5所示 。 图中只表示了动态链,current及 free
两指针
A
E
F
G
F
curren
t
free
动态链图 6.5 例 6.2的活动记录栈
31
二,半动态变量的栈式分配如果语言不只允许递归调用,而且还允许像动态数组这样的半动态变量,则由于变量长度动态确定,
将导致活动记录的长度也得推迟到单元激活时才能确定 。 因此变量不可能绑定于常量位移,为此,翻译时只能在活动记录中为半动态变量设置描述符
(或称内情向量 )。 以数组 a为例,它应包含如下信息：
(1) 动态数组在存储区的首址 a0（ 或第五章讨论的虚首址 a0-C） 。
(2) 数组的维数 n和数组元素的类型 。
(3) 每一维的上,下界 ui,li(甚至它们的界差 di=ui –
li +1),i＝ 1,2,3…,n。
32
显然描述符的信息长度依赖于数组的维数 。 由于维数静态可知,故描述符的长度也是静态可确定的 。 而描述符的内容,如数组存储首址和每一维的上,下界需待运行时才能确定,进而数组的长度才能确定 。 因此含动态数组的单元,
它的活动记录由两部分组成,一部分如同本章第三节的活动记录内容,只是半动态变量的描述符取代了半动态变量,
显然这一部分的长度是静态可确定的；另一部分是分配给动态数组存储区 。 一个单元激活后,首先在栈顶分配活动记录的第一部分,如同上一节所述那样,分配后 free指向栈顶之上 。 然后在每遇到一个动态数组说明时,将当时应确定的数组每一维的上,下界连同维数,类型记入描述符,
并计算出数组长度 L,自 free所指单元 (即数组首址 )开始分配该数组,free:=free + L,使 free指向该数组后的下一可用存储单元,并将数组首址记入描述符 。 直至所有动态数组分配完 。
33
如果一个单元含有本章第一节所述的半动态变量的数组说明：
[1:m]int a；
[1:n]real b；
的话,则相应建立的活动记录如图 6-6所示 。 活动记录中在分配给临时变量存储区之上是分配给动态数组的存储区 。
以后对数组元素 a[i1,i2,…,in]的访问,由 a的描述符查有关信息,计算该数组元素相对于数组首址的位移 K。 例如对二维数组元素 a[i,j],假定数组按行存放,有
K=(i-l1)*d2+j-l2
其中 l1,l2分别为第一,二维的下界,d2为第二维的界差 。 因此 a[i,j]的地址为 D[a0+k*W],其中 W为每个数组元素的长度,如整型元素为 4字节,实型为 8字节等 。
由于是动态分配,上述活动都在运行时进行,因此相应的运行代码应在编译时生成 。 鉴于为此生成的运行代码总量不小；不同的数组规律却相同,因此,通常引进运行子程序以减少生成的代码总量 。
34
返回指针动态链静态链保存的机器状态参数单元局部变量临时变量数组 a的存储区
|---------------------------------
数组 b的存储区
current
free
图 6.6含动态数组的活动记录
35
三,动态变量的存储分配如本章第一节所述,动态变量所表示的数据对象的长度,元素个数等,都可能在生存期中动态变化,
因此只能在堆上进行存储分配,这类分配将在第四节专门进行讨论 。
36
四,非局部环境上述讨论都只涉及对局部环境的引用 。 非局部环境的引用必须考虑变量的作用域 。 有两种作用域规则,即静态作用域规则和动态作用域规则 。
1,静态作用域规则这是一种最近嵌套规则,也称为词法作用域规则 。 类
ALGOL语言的特点是分程序结构,两个元或者是分离的 (无公共部分 ),或者是嵌套的,(单元 B完全被包围在单元 A中 )。
图 6-7(a)给出了静态嵌套的示意性例子,这种嵌套结构用相应的树结构表示 (参见图 6-7(b))相当直观 。
37
unit A;
y,int;
unit B;
y,int;
unit C;
unit D;
...
end D;
end C;
...
end B;
unit E;
x,int;
unit F;
x,y,int;
...
...
z:=x+y;
...
end F;
unit G;
...
end G;
end A;
z,int;
(a)
A
B E
C F G
D
(b)
图 6.7 (a)类 ALGOL的静态嵌套 (b)相应的嵌套树
...
end E;
...
38
为了表示嵌套的层次性,我们设最外层的单元 (嵌套树的根单位 )A为 0层,直接嵌套在它内部的单元 B和 E为 1层,直接嵌套在 1层内的单元 C,F和 G为 2层,等等 。 每一个单元的嵌套深度 ni是静态可知的,从嵌套树看,ni就是 i在树中所处的层次 。 虽然 C,F和 G都是第 2层的,但 C的直接外层是 B，
F和 G的直接外层均为 E。
最近嵌套规则是指：
(1) 变量 x在单元 U1中被说明,则 x的作用域局部于 U1,或称
x在 U1中是可见的 。
(2) 变量 x在 U1中没有被说明,则必然在包围 U1的某个单元中被说明,并且是处在包围 U1并说明了 x的那些外层单位中,
嵌套深度 ni为最大的单元 (即最靠近 U1的单元 ) i的作用域中 。
39
换言之,如果一个变量 x在 U0中说明,而嵌套在 U0中的 U1对它没有另作说明,则 U0中说明的 x的作用域包含了 U1,x在
U1中是非局部可见的,U1中引用的 x为 U0中说明的 x。 如果 x
在 U1中另有说明,则 U1中引用 x为 U1中说明的 x,U0中说明的 x只在 U0中扣除了 U1的区域中可见 。 需提醒的是,有名单元 U1的名如果是在单元 U0中定义的,则 U1的名与 U0中说明的局部变量有相同的作用域 。 在图 6-7的例子中,语句
z:=x+y中的 z是局部于 F的,x是在 E中定义的,y是 A中定义的 。 同样的原因,在 F或 G中可调用 B,因为 B与 A中定义的 y
一样是局部于 A的,在 F和 G中是可见的 。 但是 F或 G不能调用 C或 D,因为 C或 D没有在 F或 G中定义,也没有在包围它们的外层 E和 A中定义 。 因此 C,D对 F和 G是不可见的,对 E
也是不可见的 。
40
2,动态作用域规则这是一种最近活动规则,对非局部变量,引用的应是最近外层中说明的 。 静态作用域的最近外层是静态嵌套外层,而动态作用域的最近外层是指动态调用外层,这也是一种嵌套,只不过是生存期的嵌套 。
因此在 A-E-F-G-F的调用序列中,当前活动 F的调用外层为 G,因此 F中的 z是 F中说明的,而 x和 y则都是 G中说明的 。
如前所说,一个单元可能有多个实例,在活动记录栈中可能建立起多个活动记录 。 在这种情况下,动态作用域规则的最近外层是指最近外层的最新活动记录 。
41
五,对非局部环境的引用
1,静态作用域规则在这种情况下,我们引入静态连接 (Static Link)的概念,它是指向嵌套直接外层的最新活动记录的指针,它处于活动记录位移为 8的存储单元中 。 各嵌套程序单元的活动记录中,静态连接的序列构成一个静态链 (Static Chain)。 因此对于 A-E-F-G-F的调用序列,如果只关心静态链,则活动记录栈如图 6-
8所示 (为了便于比较,图中也画出了动态链 ),并示意性地列出了每个单元及所说明的变量 。
42
A:y
E:x
F:z
G:x,y
F:z
current
free
动态链图 6.8 动态链和静态链静态链
43
在嵌套深度为 np的单元 p中,引用了在嵌套深度为 nt
的单元 t中说明的变量 x,我们将 x约束于一个二元式 (d,offset),其中 d=np – nt,offset是指 x在 t的活动记录中的位移 。 因此在 p中引用 x,可以从 p的活动记录开始,沿静态链在栈中向下搜索 d步,到达 t的最新活动记录 Dt。 如果定义成递归函数：
f(d) = if d = 0 then current else D[f(d-1) +8]
则 Dt = f(d)。 对于半静态变量,Dt + offset为 x的地址 。 对于半动态变量,则 Dt + offset为 x的描述符的地址,它的元素指向动态数组 x在活动记录中首址 。
如果 d = 0,则 x为 p中的局部变量 。
44
为了设置活动记录中的静态连接,调用语句的操作语义应作修改 。 单元 A调用了单元 B,则 B在 A中是可见的：或 B是 A的外层,或 A与 B有相同的外层,
或 A是 B的直接外层 。 因此,对 B设置的静态连接,
应为沿 A的静态链在栈中向下搜索 nA-nB +1步所指向的活动记录 。
调用语句的语义由下列六条指令实现：
(1) D[free]:= ip+24
(2) D[free+4]:= current
(3) D[free+8]:= f(d+1)
(4) current:=free
(5) free:=free+L
(6) ip:=B的代码段首址返回语句的语义实现与本节第一部分相同 。
45
2,动态作用域规则在这种情况下,活动记录中位移为 8的静态连接是一指针,它应指向动态调用直接外层的活动记录 。
显然它与动态链是一致的,可以合并 。 从图 6.8中也可以看出动态作用域的引用关系,因此调用语句的返回语句的操作语义如本节第一部分所述 。
46
§ 6.4 堆分配动态语言采用动态规则,通常指动态类型规则和动态域规则 。 如 APL,LISP和 SMOBOL4。 动态变量因其类型,访问方法,使用的操作,都不能在编译时确定,因此动态变量的描述符的长度也是动态可变的 。 所以在活动记录中为动态变量安排了指向描述符和指向变量存储区的二个指针,而在堆上对描述符和变量作存储分配 。
47
此外，单元之间的调用关系如果并不遵循后进先出原则，某些单元在运行具备后被激活了，与当前活动单元不存在嵌套调用关系，二个单元的生存期就可能是交叉的。一个单元的存储空间的申请和释放可能是随机的，在这种情况下，也只能在堆上作存储分配。我们只讨论动态变量的堆分配问题。
作为堆的存储空间可以由固定长度的存储块组成,
也可以由可变长度的存储块组成 。 在堆中可随机申请一个或几个存储块,活动结束时可随机释放,因此经过一段时间后,堆空间可能被划分成如图 6.9所示的状态 。
48
P Q R S
Q
P
R
S
free
图 6.9 堆分配的存储空间组织使用块记录
49
在这些存储块中,有些正在使用,由使用块记录指出各使用块的开始位置及块的大小等有送信息；有些则空闲,称为自由块 。 所有自由块均被链接起来 。
由指针 free指向其起始块,每个自由块都有一指针指向下一自由块 。 当有一使用块被释放时,该块连接到 free链中,并从使用块记录中撤消该块的记录项 。 设自由块总长度为 N,从中申请长度为 n的新的使用块时,会出现下列几种可能：
50
(1) 有若干个自由块,其大小均大于等于 n,则采用首次拟合法：搜索 free链,寻找第一个满足其长度
1≥n的自由块 。 该块分成长度 n的使用块和长度为 l-
n的自由块,分别加入使用块记录和自由块链 free。
除首次拟合法外,还可采用最优满足法和最差满足法 。 最优满足法是从 free链中寻找一块 ≥n的最小自由块,最差满足法则从 free链中寻找 ≥n的最大自由块,与首次拟合法各有优缺点 。
51
(2) 若每个自由块的长度都小于 n,但这些自由块的总度 N却大于等于 n,将这些碎片形成一个连续空间后再对 n进行分配是一种解决办法 。 这时需将使用块移位搬家,程序各引用点都得调整 。 其中,对引用堆对象的指针的调整比较困难 。
52
(3) 若 N<n,空闲区已不敷分配,这时需调用无用单元回收器 (Garbage Collector)来隐式释放,没有使用,的使用块 。
方法之一是标记法：首先把所有从栈出发可到达堆数据对象的引用都作出标记,或称着色 。 每个堆对象都有一个指针,它指向栈的下一个引用堆对象的存储单元 。 接着穿过该存储单元的指针而到达另一堆对象,对它也作出标记或着色 。 重复这一过程,直至所有栈到堆的引用对象都作出了标记为止 。 从概念上看,通过这些指针给堆着色了的是正在使用的块,其余的为没有使用的块,可以释放 。 方法之二为引用计数法,每个数据块都记录其它数据对象对它的引用跟踪,如果引用数降为 0,那么该块可以释放 。 但这种方法只有在块之间的指针不出现环时才有效 。
堆的管理在时间和空间上都需额外开销,高效率的堆管理问题是数据结构理论中的专门问题 。 以上只是堆分配的简述,以便与栈式分配作一比较 。
53
§ 6.5 参数传递程序单元之间的通信可以通过非局部环境来进行,也可以通过参数传递来实现 。 但参数传递允许每欠调用时传递不同的数据,既灵活,又有较高的可读性和可修改性 。 例 6.3
中,a和 b是形式参数 (Formal Parameter),是 swap与它的调用者之间信息交换的媒介 。 调用语句 swap (m,n)按位置对应关系将实在参数 (actual parameter)m和 n依次传递给形式参数 a 和 b。
[例 6.3] 下列程序作参数传递用例 。
Procedure swap(a,b,intger)；
Var temp,intger；
begin temp:=a；
a:=b；
b:=temp
end swap
实参与形参之间的参数传递有三种类型：数据参数传递,
过程参数传递和类型参数传递 。 这里只介绍前两种 。
54
一,数据参数传递数据参数有引用调用 (call by reference),值调用
(call by value)和名调用 (call by name)三种传递方式 。
不同的语言有不同的约定 。 FORTRAN以引用调用为标准传递方法,ALGOL 60为名调用,也可指定值调用,Pascal 可指定值调用或引用调用,
SIMULA 67则提供值调用,引用调用和名调用三种形式 。 如何选择参数的传递方式将影响语言的语义,
同一程序采用不同的传递方式,将导致不同的结果 。
55
1,引用调用将调用环境中实参地址传递给形参的参数传递方式称为引用调用 。 如实参是常数或表达式,则将它的值存放在一中间存储单元 (或称临时变量 )中,将中间存储单元地址传递给形参 。 有些语言不允许向赋值左部的形参传送常数或表达式的实参,一旦出现这种情况,就作错误处理 。 被调用程序单元对形参的引用,被理解为对形参单元中实参地址的间接引用 。 被调用单元通过形参可对实参作修改,因此实参的存储单元为调用程序单元的被调用程序单元共享 。
引用调用的实现方法是,向被调用过程的活动记录中的形参单元传送实参变量的地址,或传送存放实参值的临时变量的地址 。
56
2,值调用形参只起局部变量作用,实参存储单元也不能为形参共享,
不能对调用程序单元的参数随意修改 。 形参和实参之间的值的传递有下列三种方式：
(1) 传值 调用程序单元将实参的值传递给形参,作为形参这一局部变量的初始化 。 被调用程序单元对形参的赋值不影响调用程序单元的环境 。 这是实参向形参的值的单向传递 。
(2) 结果调用 (call by result) 被调用程序单元在被调用时,
形参仅作局部变量,实参不向形参传值,形参也不引用实参 。 而被调用单元在结束活动时,将形参的值复制到调用环境的实参单元中 。 这是形参向实参单向传递结果值 。
(3) 传值得结果 (call by value-result)也称复写入复写出 (copy-
in and copy-out)。 调用单元以实参值初始化形参,被调用单元在结束活动时将形参的值复制至实参 。
57
值调用的实现方法：通常为一形参设两个存储单元,
其中一个值单元和一个地址单元 。 传值时,将实参的值传递给形参的值单元；得结果时将实参的地址
(或存放实参的值的临时变量的地址 )传递给形参的地址单元 。 被调用单位结束活动时,若为得结果,
将形参单元中的值,按形参地址单元中实参地址,
向实参传递 。
58
3,名调用这是由 ALGOL 60定义的一种特殊的参数传递方式,根据它的复制规则 (copy-rule)定义：
(1) 过程调用的作用相当于把被调用过程的过程体复制到调用处,但把其中任一出现的形式参数文字上替换成相应的实在参数 。 这种文字上替换称为宏扩展 (Marcro Expansion)。
(2) 被调用过程中的局部名如果与过程调用处的名发生冲突,
则在宏扩展前对被调用过程中的这些局部名重新命名,以避免重名冲突 。
(3) 为了表现实在参数的整体性,必要时在替换前把实在参数用括号括起来 。
59
对例 6.3给出的过程,swap(a,b)是将 a,b的值互换,但根据换名规则,调用语句
swap(i,a[i])
在 swap执行中为
temp:=i；
i:=a[i]；
a[i],= temp
调用前若 i=3,a[3]=4,则调用后为 i=4,a[4]=3,而不是想像中的 i=4,a[3]=3。
名调用这种参数传递方式使程序难读,也难于实现 。
名调用的基本实现技术是把实在参数处理成一个子程序,
对形式参数的每次引用就调用这个实参子程序 (也称为
Thunk)。 因此并不是在进入被调用过程前先计算实在参数,
而是在进入被调用过程后每次引用形参就每次调用 thunk。
60
二,过程参数的传递数据参数是常见的,大量的,但也有将过程 (子程序 )作为参数进行传递的情况 。 例如,一个问题的求解方法可能有好几个,如排序与检索,每一种方法对应于一个子程序 。 如果想评价各种方法的优劣,如占用空间的大小,运行时间的长短等,就需要设计一个测试 S程序性能的测试程序,它将 S作为形式参数,当测试某个方法所对应的子程序为 T时,
便可将实在参数 T传递给 S。 因此过程作为参数传递的这种方式是有实用价值的,为一些语言所采用 。
程序单元 P将实在过程 T作为参数传递给程序单元 Q,这意味着在单元 P中有过程调用语句 CALLQ(T)：
Unit P
…
CALL Q(T)；
…
end P
61
而单元 Q中存在着被区分为过程的形式参数,不妨记为 S。
显然,在单元 Q中,应有关于 S的调用语句：
Unit Q(S:procedure)
…
CALL S；
…
end Q
在这种情况下,CALL S实际上就是 CALL T。 因此需向形参 S传递 T的代码首址以及 T的引用环境,以便在 CALL S时可转而调用 T过程,并在 T的环境下引用 T的局部变量和非局部变量 。 但由于静态作用域规则和动态作用域规则的不同,在 CALLS处 T的引用环境也是不同的 。
62
在静态作用域规则下,CALL S处 T的局部环境,应由单元 P
中 CALL Q(T)处 T的静态非局部环境,即 T的静态连接指出,
并传递给 S,在 CALL S时便可获得 T的静态非局部环境 。 因此对区分为过程的形参 S设置二个指针,一个指向实参过程
T的代码段首址,另一个存放实参 T的静态连接 。 对静态嵌套语言来说,它们都是静态可确定的 。 当在单元 Q中调用形参过程 S时,执行形参单元中指向的 T代码,将形参单元中的实在过程 T的静态连接记入活动记录,建立起 T的非局部环境 。
在动态作用域规则下,CALL S处于 Q中,不管在栈顶上将建立的实参过程是什么,它的动态外层都是 Q,实参过程 T
只需向 S传递 T代段的首址即可 。 非局部引用环境由动态链给出 。
63
§ 6.6 符号表在程序中,用户用标识符定义了不少名字来代表不同的数据对象,编译程序将这些名字保存在符号表中 。 符号表除了记录名字本身而外,还记录了与名字关联的各种属性信息,例如名字的种属 (常量,变量,数组,过程等 ),名字的数据类型 (整型,实型,布尔型,字符型等 ),为名字分配的数据空间的存储地址以及编译过程中的一些特征标志和其他有关信息 。 在词法分析阶段,当识别出一个新的名字时,
便将此名字登入符号表 。 与之关联的其他属性值,可在词法分析,语法分析,语义分析及中间代码生成等各阶段陆续填入 。 总之,符号表的登记工作应在准确获得相关信息后即时完成 。 随之,在编译各阶段每当需要引用名字及其有关信息时,只要查询符号表便可获得 。 因此,在编译中对符号表的访问相当频繁,所需的时间开销占了编译时间的不小的比例 。 如何组织好符号表,为符号表上的操作选择好的算法,是提高编译效率的不可忽视的问题 。
64
一,符号表的组织在符号表中为每一个名字设立一个表项,每一个表项是一个记录,通常有两个域构成,一个是名字域,一个是信息域 。 信息域通常设若干子域及标志位 。 不同种属的名字的信息是不同的,因此信息域的构成也不同 。 但不管怎样,
名字的存储分配信息 (名字的绑定信息 )始终是信息域中的一个重要组成部分 。
名字的长度、信息域的组成及长度可能是各不相同的。除非给出某种约定，否则符号表项各域的长度很难一致，因此常采用间接表技术。
65
以名字域为例，如果约定名字域长度为 10，图 6-10(a)给出了四个名字在符号表中的登记状况。如果在符号表外另设一字符串数组，每个名字的字符串记录在字符串数组中，每个字符串以 EOW作为结束标志，而符号表的名字域中为一指针，它指向该名字在字符串数组中的开始位置，于是图 6-10(a)的内容就可以用图 6-10(b)来表示。不难发现，这种间接表方式使符号表长度一致，存储空间使用得更有效。信息域各子域也可仿此组织。
名字信息名字 信息
sort
a
readarray
...
(a)
sorteowaeowreada r r a g eow ieow
(b)
图 6.10 名字的存储技术 (a)名字的直接存储 (b)间接表技术
66
如何确定名字的存储分配信息呢？ 编译程序在编译时刻确定名字运行时刻的存储分配信息,并将它填入符号表中 。
如果生成的目标代码是汇编语言的,由于汇编程序具有管理不同名字的存储分配功能,所以在由源程序生成汇编代码后,需扫描符号表,为每一名字生成汇编语言的数据定义并提供给汇编程序,汇编程序据此对名字作存储分配 。
如果生成的目标代码是机器代码,则每个数据目标的存储位置与一个固定的起始地址 (如活动记录的开始地址 )相关 。
单独的数据模块中的数据目标位置也是如此 。 Fortran的
COMMON区是单独存放的,其起始位置是确定的,其中的数据目标的位置与该起始位置相关 。
动态栈式分配时,每一名字对过程活动记录中某一位置 (如
current指的位置 )的位移量,即相对地址是可知的,它就是符号表中名字的存储信息 。 运行时,当过程活动的位置确定后,这些名字的真正地址也就确定了 。
67
二,常用的符号表结构在一个源程序中,有可能定义了上百个名字,并对它们引用了上千次,因此这些操作的总代价在编译时是不可忽视的 。 通常可以用插入 n个名字和进行 e次查找所需的总时间来评价各种符号表结构的优劣 。
(1) 线性表 这种表格结构简单而自然 。 用 N个数组 A1，
A2,…,AN来存放符号表的 N个子域,其中的一个数组,
如 A1相应于名字域 。 显然,确定下标 i,便可知道名字为
A1[i]的各信息子域 A2[i],…,AN[i]。 符号表当前位置由指针 P指示,它指出了下一个符号表项将要存放的位置 。 如果一个符号表已经包含了 n个名字,则 P指向 n+1项 。
插入一个新名字时,首先要查符号表以确定这名字是否已在符号表中,其代价与 n成正比 。 而查询某个名字的信息,
其代价也与 n成正比 。 因此插入 n个名字并在 n个名字上作 e
次查找所需的总代价与 cn(n+e)成正比,其中 c是一个常数,
它与实现符号表操作的一组指令的执行时间是相关的 。
68
(2) 散列表 (Hash Table) 它在编译中广泛使用 。 它将所有名字分成 m组,由 hash函数 (其值为 0,…,m-1)
来计算一个名字 S应属的组号 hash(S)。 具有相同
hash值的同一组名字形成一个链表,其链头位置记录在长度为 m的 hash表的 hash(s)项 。 因此散列表是由长度为 m的指针数组构成,如图 6-11所示 。 其中设名字 cp和 n的 hash值均为 9,match的 hash值为 20，
而 last,action,ws均为 32,斜线 /表示链尾 。 这种形式的散列表是一种开放散列表 。
…
…
…
…
图 6.11 长度为 256的散列表
0
9
20
32
25
5
cp n
action
match
last ws
69
在这种结构的表中插入 n个名字,并在 n个名字上进行 e次查找所需的总代价,与 n(n+e)/m成正比 。 很明显,其效率比线性表高,因为 m并不小 。 特别当 m取值为 n时,总代价是 n+e
的线性函数 。 然而开放散列表的空间开销随 m的增大而增加,
因此这是一种以空间换取时间的方法 。 m取多大为宜？ 符号表使用频度高,时间矛盾突出时 m宜大 。 对中等规模的程序,
m取几百,查表可以说是即查即得,这时查表时间相对说来是一个小量 。 如果空间不富裕,则 m宜小 。
开放散列表的一个要点是设计一个好的 hash函数,一要计算速度快,二要把所有的名字均匀地分布到 m个链表中去,
这样有利于提高速度 。
70
[例 6.4] 如果将每个标识符记录在 character string中,每个字母或数字占一个字节,用 EOW作为标识符结束标志,它也占一个字节 。 符号表采用上述 hash表结构,设 hash函数将 a,…,z,0,…,9对应于 1,…,26,27,…,36,然后将标识符的每个字母或数字对应的数值相加得 Sum,以 Sum mod 5作为该标识符的 hash值 。 Hash表中为相应 hash链的指针,最新出现的标识符总是处于 hash链的链头 。 如果在词法分析时依次遇到下列标识符,temp,swap,grammar5,show5,
v3rd,reference1,exchange6,则相应的符号表如图 6.12所示 。
其中 hash链中元素的名字域是指向名字在 character string中起始位置的指针,第二元为信息域,第三元为链接元 。
71
0
2
4
图 6-12 例 6.4的符号表示意图
1
3
P7
P6
P2 P1
P3
P5
P4
P1? P2? P3? P4?
t e m p EOW S W a p EOW g r a m m a r 5 EOW s h o w
P5? P6? P7?
5 EOW v 3 r d EOW r e f e r e n c e 1 EOW e x c h a
n g e 6 EOW
编译原理第六章运行时存储空间管理上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 5月
2
第六章 运行时存储空间管理
§ 6.1 变量及存储分配一个用高级语言写的程序要投入运行，首先要有一组可运行的代码，这组代码应与高级语言的程序等价；
其次还需要一个运行环境，对程序中的变量作存储分配，提供各种运行信息。前者涉及程序语言的编译系统，我们已在前几章中作了概要介绍。后者涉及变量以及变量的存储分配和存储管理的问题。本章主要讨论运行时的存储管理问题，也涉及了符号表的组织与管理。
3
一、程序的存储空间一个程序要运行,至少应有这样两个存储空间：
(1) 代码空间 这是经翻译后生成的目标代码的存储区域,
线性存放着目标指令序列 。 对三地址代码来说,当前执行的指令位置由指令指针 ip指示 。 因此,只要将 ip指向程序的第一个语句,程序便处于开始执行的状态,以后每执行一个语句,ip便加 4(我们约定,三地址代码的每个语句占 4个字节 ),指向下个语句 。 要改变程序控制顺序,只要将转向点赋给 ip即可 。
4
(2) 数据空间 每个程序都定义一定数量的各种类型的变量和常数,翻译程序必须为之分配相应的存储空间 。 初等类型的数据,如逻辑,整型,实型变量,通常以存储器的基本存储单元如字节,字,双字来存储 。 集合数据,如数组,
串,记录结构等,一般用若干个连续的字节或字来存储 。
这便使变量绑定 (Biding)于一个存储区域 。 变量获得存储区的这种活动称为分配 (Allocation)。 一个变量一旦被建立,
就获得了相应的存储区,完成了存储区与变量的绑定 。 除了这些变量与常数外,数据空间还保存了程序的一些控制和管理信息 (例如,反映程序间调用关系的控制链,反映程序间变量引用关系的引用链等 ),说明程序实体的绑定信息的描述符以及其他等等 。
5
对一个程序来说,它的代码长度可以在编译时刻完全确定下来,因此,编译时便可安排代码空间 。 但对数据空间来说,不仅程序实体的属性影响了存储分配 (例如变量类型影响了每个数据元素的存储长度,作用域决定了变量绑定于某存储区的空间范围,生存期决定了这种约束的时间范围 )，
而且语言的运行特性也决定了数据空间的分配和管理应采用的方法和策略 。 有的语言在运行前就能确定数据空间的大小,因而在编译时刻就能进行存储分配,这种分配策略称之为静态分配 (Static Allocation),有的语言则必须在运行时刻才能作分配,称之为动态分配 (Dynamic Allocation)。
有的语言因变量生存期具嵌套特性而采用栈分配 (Stack
Allocation)策略,有的语言因生存期的随机交叉特性而采用堆分配 (Heap Allocation)策略 。
6
二,活动记录一个程序单元 (Program Unit,以下简称单元 )的一次激活所需的信息管理是通过相应的活动记录 (Activation Record)来实施的 。 一个单元的每次激活,都应建立相应的活动记录,
它是单元实例的一部分 。
一个活动记录是一连续存储区 。 通常,它的内容如图 6.1所示 。
当单元 A调用单元 B时,应中断 A的活动,建立 B的活动记录,将调用的实在参数传递给 B的活动记录,将控制转移至
B,使 B处于活动状态 。 因此,活动记录中应包含如下内容：
7
返回指针
returned pointer
动态链
dynamic link
静态链
static link
保存的机器状态
saved machine states
参数单元
parameters
局部变量
local variables
临时变量
temporaries
图 6.1活动记录
8
(1) 分配给形式参数的存储单元,这是实参传递的存储区 。
(2) A被中断时的状态以及中断结束后的返回点,以便 B的活动结束后能返回被中断的 A,使 A继续活动起来 。
(3) B的局部变量或它们的描述符,以及临时变量 。
(4) 记录动态调用关系的动态链及记录静态嵌套关系的静态链 。 静态链用以实施静态作用域规则,动态链除记录了调用控制关系外,也是动态作用域实施的依据 。
显然,除了变量存储区外 。 活动记录的其他部分的存储长度都是编译时可确定的 。 如果一个单元不含动态数组和动态类型数据,这个单元的活动记录的长度在编译时便可确定 。 对活动记录中某元素 i的访问,可通过该元素在活动记录中的位移 offset(i)来表示,一旦活动记录被分配在存储位置 D,则 i的地址为
D+offset(i)
9
三,变量的存储分配由上可见,局部变量的存储分配对活动记录的建立有着主要影响 。 从存储分配角度看,变量有四种类型 。
(1) 静态变量 (Static Variable) 如果每个单元的活动记录,
以及每个变量的存储位置,在编译时均可确定,在运行时不会变化,那么存储分配可在编译时完成,这便是所说的静态分配 。 静态分配是在编译时将变量绑定于一个存储区,
不管在程序单元的哪一次活动中,这些变量都绑定于相同的存储位置 。 这类变量称为静态变量 。
10
(2) 半静态变量 (Semistatic Variable) 如果一个语言允许单元的递归调用,一个单元可递归地被多次激活,这就会为一个单元建立起多个活动记录 。 变量是在单元每次激活时,
动态地绑定于刚建立的活动记录 。 这类变量的长度必须是编译时可确定的,因而活动记录的长度,变量 x在活动记录中的相对位置 (即位移 offset(x)),都是编译时可确定的 。 运行时,一旦该单元被激活,相应活动记录便获得物理存储区 D,变量 x便被定于 D+offset(x)。 这类变量称为半静态变量 。 虽然每个活动记录的长度,每个变量在活动记录中的相对位移,如同静态变量那样在编译时可知 （ 称为静态可确定 ） 但这样的活动记录的个数却依赖于该单元的递归调用深度,这是运行时可知 （ 动态可确定 ） 的 。
11
(3) 半动态变量 (Semidynamic Variable) 如在单元 U中,有
ALGOL 68的说明：
[l,m] int a；
[l,n] real b
它定义了体积为 m的整型数组 a和体积为 n的实型数组 b。 如果 m和 n都不是常量,它们的值只有当 U被激活时才能确定,
那么编译时不可能为它们作存储分配 。 即使在活动记录中为它们的存储作安排也不可能 。 虽然在本例中,数组 a相对于活动记录的位移有可能在编译时确定,但它的长度在编译时是不能确定的,因此紧接着要作存储分配的数组 b在活动记录中的相对位移,在编译时也不能确定了 。 因此,动态数组不可能绑定于活动记录的常量位移 。 像动态数组这一类变量,称为半动态变量 。
12
对于半动态变量,在编译时可以在活动记录中为它们安排描述符 。 描述符是数据对象的属性集,记录着程序实体的约束信息 。 对上例中的动态数组 a和 b来说,它们的描述符包含两个元素：一个元素是指向 a或 b在活动记录中的首址的指针,另一个元素则记录了动态数组每一维的上下界 。
很明显,数组的维数是静态可知的,因此描述符的长度也是静态可知的,所以它们在活动记录中的位移也是可确定的 。 只是描述符的内容,即数组在活动记录中的首址和每一维的上,下界,在编译时是不可知的,需待 U被激活并运行至动态数组说明时,方可确定每一维的上,下界,将它们记入描述符的第二个元素中,并据此算出数组的体积 D，
在刚建立起来的 U的活动记录顶端,为数组分配一个大小为
D的存储区,将数组描述符的第一个元素指向该存储区 。 以后对该数组的任一元素的访问,可通过描述符计算出该数组元素对数组起始元素的位移而获得访问地址 。
13
(4) 动态变量 (Dynamic Variable) 有一类数据对象，即使到它所在单元被激活时，其活动记录的长度仍不能确定，因为这类数据对象的存储区域的大小在运行时仍有可能发生变化。例如 APL的变量可以是动态类型的，它不是显式说明，而是由运行时当前值隐式确定，并随运行路径的变化而变化着。又例如 ALGOL 68的灵活数组 (Flexible Array)，
它的界是可变的，在运行中可能是二维的，也可能是三维的。再如 PL/1和 Pascal等语言中，允许数据的动态扩大和压缩，由一组结点构成的数据结构，结点可以动态加入，也可以动态删除。像链表和树就是这样的数据结构，结点由指针来连接，结点在程序运行时分配。对于这些在运行时可能改变变量类型和变量结构的，不仅数据对象本身不能静态分配，而且它们的描述符的内容，甚至描述符的长度都不是静态可确定的，这类变量称为动态变量。总之，动态变量表示的数据对象的长度和个数，以及它们的描述符的内容和长度，都可能在它的生存期中改变。
14
四,存储分配模式根据以上讨论,存储分配可采取静态,栈式和堆三种方式 。
1,静态分配如果程序语言只允许静态变量,那么变量与存储区域的绑定关系在编译时便可建立,并完成存储分配 。 这一类语言便是静态语言 。 它们不允许递归调用,不允许动态数组,
不允许动态类型的数据对象,即不允许有非静态变量 。
FORTRAN,COBOL便是静态语言 。
15
2,栈式分配凡不满足静态分配条件的语言,自然归入了动态分配类 。
但对半静态变量和半动态变量来说,所有局部变量在单元激活时隐式建立,活动记录长度或者静态可确定,或者在单元被激活时确定 。 同时,各单元之间的调用关系遵循
,后进先出,模式,即单元 A被激活,建立起一个单元实例,
分配了 A的活动记录 。 执行中 A调用了单元 B,于是 A的活动暂中断 (A的活动记录并未撤消,仍保留着 ),为激活了的
B建立一个单元实例,分配 B的活动记录 。 随着 B运行结束,
完成了 B的当前实例,释放 B的活动记录,返回到被暂时中断的单元 A,继续 A的活动,直至 A的活动结束时,才撤消
A的活动记录 。 这表明单元 B的生存期嵌套在 A的生存期中,
即它们之间存在着动态嵌套的关系,相应的活动记录的建立和撤消满足后进先出的模式 。 因此,我们选择栈来分配活动记录是十分自然的 。 由于这个原因,半静态变量和半动态变量也称为栈变量 (StackVariable)。
16
应该指出,栈并不是栈式语言语义的一部分 。 这类语言的语义仅要求每激活一个单元,其局部变量应绑定于这个刚激活单元的活动记录,并遵循作用域的规则 。 而栈是实现这种语义的有效模型 。
虽然半静态变量和半动态变量都是栈式分配的,但半静态变量绑定于活动记录的常数位移,即它可在编译时分配于活动记录中 。 而半动态变量则在编译时只在活动记录中分配了它的描述符,需待所有单元 U被激活后,在新建立的 U
的活动记录顶端 (即栈顶 )按描述符信息,分配半动态变量的存储空间 。
基于栈的存储分配也完全适用于静态语言，栈式分配也被许多静态语言的实现所采用。
17
3,堆分配由于动态变量表示的数据对象,它的长度,个数都有可能在执行中改变,即在其生存期中动态改变,就不可能在栈上为这样的对象作分配 。 例如在 Pascal中,每个指针只能指向一种类型的对象 。 假定 P在 A中已被说明为类型 t的指针,
B动态嵌套在 A中,B中包含了一个分配语句,New (P)
...
代码
code
静态数据
static data
栈
stack
堆
heap
图 6.2 存储组织
18
它建立一个类型为 t的对象,并将对象的地址赋于 P。 当 B执行到这个分配语句时,B的活动记录在栈顶,而 A的活动记录在 B的活动记录下面 。 这个 A中定义的,B中分配的 P指向的对象,不能在 B的活动记录中分配 。 因为 B的活动结束时,
它的活动记录就得释放,但 P所指向的这个对象的生存期并未结束,不应该释放 。 可是将这个对象分配在 A的活动记录中也是行不通的 。 因为如果 P所指的这个对象是个灵活数组,
这就无疑要重新构造栈了 。 所以对这样的对象可另辟一个并非栈模式的存储区进行分配,这个存储区称为堆 。 一般而言,出现下列情况：
(1) 单元活动结束后,局部变量的值还需保留 。
(2) 调用单元与被调用单元的生存期不满足嵌套关系,即出现交叉现象,那么后进先出的模式是不合适的,必须用堆模式分配 。
因此运行时,常把目标代码与全局变量,静态数据安排在存储空间的底端 。 在静态空间之上为栈空间,堆则安排在存储空间的另一端,栈和堆可动态的迎面增长,如图 6.2所示 。
19
§ 6.2 静态分配如前所述,一个语言如果不允许递归调用,动态数组和动态类型时,便可采用静态分配模式 。 FORTRAN是一种典型的静态语言 。 下面讨论它的静态分配 。
一,FORTRAN 程序的运行时结构一个 FORTRAN程序由一组程序单元,即一个主程序,若干个子程序或者函数组成 。 每个单元可独立编译,绑定于一个活动记录 。 活动记录及变量在运行前便可建立,其生存期延续到整个程序执行结束 。 变量的作用域局部于它被说明的那个单元,而 COMMON语句说明的变量是全局于各单元的全局变量,分配在全局数据活动记录中 。
对于 FORTRAN来说,本章第一节中提到的动态链和静态链,动态变量及半动态变量的描述符不会出现在活动记录中 。 如果只关心存储分配,则一个 FORTRAN程序的编译要经过三个步骤 。
20
(1) 编译时，变量约束于活动记录的常量位移，因此每一个变量的引用都可用二元式 (单元名，位移 )表示。而转换控制语句中对指令的引用也可翻译成二元式 (单元名，指令在代码段中的位移 )。
(2) 连接时，须将程序所有单元连接起来。每连接一个单元，
将它的代码段分配到代码区，活动记录分配到数据区。
这时，翻译后的所有引用活动记录和代码段的二元式都可转换成一个单一的存储地址。例如单元 i的活动记录从
1000存储单元开始分配，则二元 (i,6)表示的数据单元引用地址为 D[1006]。同样，单元 i的代码段从 2000存储单元开始分配，则 (i,5)表示的指令地址为 C[2005]。当然，实际的连接器应将各单元的代码段连接成一个可重定位
(Relocatable)代码，只是我们关心连接过程，所以避开了它。
(3) 装入时，将连接后的可重定位代码程序装入主存储器并定位，成为可直接执行的机器代码，并将 ip指向程序第一条指令，使程序处于可执行状态。
21
经过上述编译过程，一个 FORTRAN程序的存储结构如图
6.3所示。
ip 单元 1代码段单元 2代码段单元 n代码段
…
单元 1活动记录全局数据活动记录单元 2活动记录单元 n活动记录
…
图 6.3 FORTRAN程序的存储结构
22
二,运行环境的转换由于这一章的主题是存储分配,我们将对引起控制转换的语句的编译感兴趣,因为两个单元之间的控制转换,将引起环境的变换 。
为叙述方便,我们约定：单元 i的活动记录中位移为 j的存储单元内容记为 d[i,j],单元 i的代码段中位移为 j的语句记为
c[i,j],它们经连接后的实际存储地址记为 D[m],C[m]。 X
的地址记为 &X,X可为 d[i,j]或 c[i,j]。
1,GOTO X语句编译器将标号 X编译成二元式 [i,j]。 GOTO X的语义是使转移的目标地址成为指令指针的当前内容,即
ip:=& c[i,j]
23
2,过程调用语句 CALLP
过程调用时,编译器为之实现的语义为
(1) 在单元 P的活动记录位移为 0的存储单元中存放调用后返回的指令地址 。 因为调用语句翻译成两个语句,每个语句占 4字节,故返回地址为 ip+8。
D[P,0]:= ip+8
(2) 单元 P的代码段的第一个语句地址为 & c[P,0],将它置于
ip中,实现将控制转移到 P。
ip:= & c[P,0]
经连接后为
D[m]:= ip+8
ip:= n
其中 m为 P活动记录的首址,n为 P代码首址 。
24
3,返回语句 RETURN
其语义为将所在单元 P的活动记录位移为 0的存储单元中的返回地址置于 ip中,实现返回 。 即
ip:= d[P,0]
连接后为
ip:= D[m]
m是单元 P的活动记录的首址 。
25
§ 6.3 栈式分配类 ALGOL语言是由 ALGOL 60派生的一类语言,
它们都允许递归调用一个单元,有的允许动态数组,
有的允许动态建立数据对象,它们的调用关系是后进先出的栈模型,因此采用动态的栈式存储分配 。
这类语言的另一个特点是静态嵌套的程序结构,采用静态作用域规则 。 这些特性对于存储分配都有影响 。
26
一、只含半静态变量的栈式分配这里实际指的是只允许递归调用的栈式分配 。 在这种情况下,每个变量的长度,以及整个活动记录的长度在编译时就可以确定 。 但由于递归调用,一个单元可多次激活而有多个实例,每个活动记录是在单元每次激活时动态建立并与代码段建立绑定关系的 。 在编译时,变量 X绑定于它在活动记录中的常数位移 i,所以单元一旦被激活,相应活动记录便在数据存储器的栈顶获得分配,当前栈指针 current便是活动记录的开始位置,释放指针 free指向数据存储器下一可用单元,因此变量 X的地址为 D[current+i]。 对于数组元素来说,数组 a的初始元素的位移为 offset(a),栈当前指针为 current,则数组元素 a[i]的地址为：
current + offset(a) + i
27
单元 A调用了单元 B,使 B激活,从 A的活动记录的栈顶之上 (由 free指示 )建立起绑定于 B的当前实例的活动记录 。 为了能使 B返回 A,B的活动记录应保存返回地址和 A的活动记录地址,我们称它为动态连接 (Dynamic Link),由它组成了一个调用链,称为动态链 (Dynamic Chain)。 单元 B的当前实例一旦结束,绑定于它的局部变量的生存期也告终结,相应的活动记录便可自栈顶撤消,由动态链可将当前指针 current调整指向 A的活动记录,使之处于栈顶位置,A的这个实例又处于活动之中 。 如果以后 A又调用 C,则 C的活动记录又可分配于 A的活动记录栈顶之上,即原行 B的活动记录位置 。 很显然,活动记录的分配与释放是后进先出的 。
28
因此,将调用语句 CALLP编译成下列五个语句：
(1) 调用语句之后的第 5个语句位置为返回地址,新的活动记录将建在 free所指的栈顶之上,故有
D[free],= ip + 20
(2) 将建立的新的活动记录的动态连接就是当前活动记录
D[free + 4],= current
(3) 当前活动记录指针 current调整至新建的活动记录,即
current:=free
(4) 释放指针调整至新的活动记录之上,即
free:=free+L
其中 L为 P的活动记录的长度,是静态可确定的 。
(5) 使 P的实例处于活动状态,指令指针指向 P的代码：
ip:=P的代码段首地址 。
29
单元 P当前实例结束时,返回调用单元是由下列三个语句实现的：
(1) 删除当前的活动记录,使 free指向当前的 current,即
free:=current
(2) 根据动态连接,使 current指向调用单元的活动记录,即
current:=D[current+4]
(3) 实现控制转移,按返回指针返回调用单元,即
ip:=D[free]
30
[例 6.2]基于上述管理方法,调用序列
A Call E
E Call F
F Call G
G Call F
的活动记录栈的状态如图 6.5所示 。 图中只表示了动态链,current及 free
两指针
A
E
F
G
F
curren
t
free
动态链图 6.5 例 6.2的活动记录栈
31
二,半动态变量的栈式分配如果语言不只允许递归调用,而且还允许像动态数组这样的半动态变量,则由于变量长度动态确定,
将导致活动记录的长度也得推迟到单元激活时才能确定 。 因此变量不可能绑定于常量位移,为此,翻译时只能在活动记录中为半动态变量设置描述符
(或称内情向量 )。 以数组 a为例,它应包含如下信息：
(1) 动态数组在存储区的首址 a0（ 或第五章讨论的虚首址 a0-C） 。
(2) 数组的维数 n和数组元素的类型 。
(3) 每一维的上,下界 ui,li(甚至它们的界差 di=ui –
li +1),i＝ 1,2,3…,n。
32
显然描述符的信息长度依赖于数组的维数 。 由于维数静态可知,故描述符的长度也是静态可确定的 。 而描述符的内容,如数组存储首址和每一维的上,下界需待运行时才能确定,进而数组的长度才能确定 。 因此含动态数组的单元,
它的活动记录由两部分组成,一部分如同本章第三节的活动记录内容,只是半动态变量的描述符取代了半动态变量,
显然这一部分的长度是静态可确定的；另一部分是分配给动态数组存储区 。 一个单元激活后,首先在栈顶分配活动记录的第一部分,如同上一节所述那样,分配后 free指向栈顶之上 。 然后在每遇到一个动态数组说明时,将当时应确定的数组每一维的上,下界连同维数,类型记入描述符,
并计算出数组长度 L,自 free所指单元 (即数组首址 )开始分配该数组,free:=free + L,使 free指向该数组后的下一可用存储单元,并将数组首址记入描述符 。 直至所有动态数组分配完 。
33
如果一个单元含有本章第一节所述的半动态变量的数组说明：
[1:m]int a；
[1:n]real b；
的话,则相应建立的活动记录如图 6-6所示 。 活动记录中在分配给临时变量存储区之上是分配给动态数组的存储区 。
以后对数组元素 a[i1,i2,…,in]的访问,由 a的描述符查有关信息,计算该数组元素相对于数组首址的位移 K。 例如对二维数组元素 a[i,j],假定数组按行存放,有
K=(i-l1)*d2+j-l2
其中 l1,l2分别为第一,二维的下界,d2为第二维的界差 。 因此 a[i,j]的地址为 D[a0+k*W],其中 W为每个数组元素的长度,如整型元素为 4字节,实型为 8字节等 。
由于是动态分配,上述活动都在运行时进行,因此相应的运行代码应在编译时生成 。 鉴于为此生成的运行代码总量不小；不同的数组规律却相同,因此,通常引进运行子程序以减少生成的代码总量 。
34
返回指针动态链静态链保存的机器状态参数单元局部变量临时变量数组 a的存储区
|---------------------------------
数组 b的存储区
current
free
图 6.6含动态数组的活动记录
35
三,动态变量的存储分配如本章第一节所述,动态变量所表示的数据对象的长度,元素个数等,都可能在生存期中动态变化,
因此只能在堆上进行存储分配,这类分配将在第四节专门进行讨论 。
36
四,非局部环境上述讨论都只涉及对局部环境的引用 。 非局部环境的引用必须考虑变量的作用域 。 有两种作用域规则,即静态作用域规则和动态作用域规则 。
1,静态作用域规则这是一种最近嵌套规则,也称为词法作用域规则 。 类
ALGOL语言的特点是分程序结构,两个元或者是分离的 (无公共部分 ),或者是嵌套的,(单元 B完全被包围在单元 A中 )。
图 6-7(a)给出了静态嵌套的示意性例子,这种嵌套结构用相应的树结构表示 (参见图 6-7(b))相当直观 。
37
unit A;
y,int;
unit B;
y,int;
unit C;
unit D;
...
end D;
end C;
...
end B;
unit E;
x,int;
unit F;
x,y,int;
...
...
z:=x+y;
...
end F;
unit G;
...
end G;
end A;
z,int;
(a)
A
B E
C F G
D
(b)
图 6.7 (a)类 ALGOL的静态嵌套 (b)相应的嵌套树
...
end E;
...
38
为了表示嵌套的层次性,我们设最外层的单元 (嵌套树的根单位 )A为 0层,直接嵌套在它内部的单元 B和 E为 1层,直接嵌套在 1层内的单元 C,F和 G为 2层,等等 。 每一个单元的嵌套深度 ni是静态可知的,从嵌套树看,ni就是 i在树中所处的层次 。 虽然 C,F和 G都是第 2层的,但 C的直接外层是 B，
F和 G的直接外层均为 E。
最近嵌套规则是指：
(1) 变量 x在单元 U1中被说明,则 x的作用域局部于 U1,或称
x在 U1中是可见的 。
(2) 变量 x在 U1中没有被说明,则必然在包围 U1的某个单元中被说明,并且是处在包围 U1并说明了 x的那些外层单位中,
嵌套深度 ni为最大的单元 (即最靠近 U1的单元 ) i的作用域中 。
39
换言之,如果一个变量 x在 U0中说明,而嵌套在 U0中的 U1对它没有另作说明,则 U0中说明的 x的作用域包含了 U1,x在
U1中是非局部可见的,U1中引用的 x为 U0中说明的 x。 如果 x
在 U1中另有说明,则 U1中引用 x为 U1中说明的 x,U0中说明的 x只在 U0中扣除了 U1的区域中可见 。 需提醒的是,有名单元 U1的名如果是在单元 U0中定义的,则 U1的名与 U0中说明的局部变量有相同的作用域 。 在图 6-7的例子中,语句
z:=x+y中的 z是局部于 F的,x是在 E中定义的,y是 A中定义的 。 同样的原因,在 F或 G中可调用 B,因为 B与 A中定义的 y
一样是局部于 A的,在 F和 G中是可见的 。 但是 F或 G不能调用 C或 D,因为 C或 D没有在 F或 G中定义,也没有在包围它们的外层 E和 A中定义 。 因此 C,D对 F和 G是不可见的,对 E
也是不可见的 。
40
2,动态作用域规则这是一种最近活动规则,对非局部变量,引用的应是最近外层中说明的 。 静态作用域的最近外层是静态嵌套外层,而动态作用域的最近外层是指动态调用外层,这也是一种嵌套,只不过是生存期的嵌套 。
因此在 A-E-F-G-F的调用序列中,当前活动 F的调用外层为 G,因此 F中的 z是 F中说明的,而 x和 y则都是 G中说明的 。
如前所说,一个单元可能有多个实例,在活动记录栈中可能建立起多个活动记录 。 在这种情况下,动态作用域规则的最近外层是指最近外层的最新活动记录 。
41
五,对非局部环境的引用
1,静态作用域规则在这种情况下,我们引入静态连接 (Static Link)的概念,它是指向嵌套直接外层的最新活动记录的指针,它处于活动记录位移为 8的存储单元中 。 各嵌套程序单元的活动记录中,静态连接的序列构成一个静态链 (Static Chain)。 因此对于 A-E-F-G-F的调用序列,如果只关心静态链,则活动记录栈如图 6-
8所示 (为了便于比较,图中也画出了动态链 ),并示意性地列出了每个单元及所说明的变量 。
42
A:y
E:x
F:z
G:x,y
F:z
current
free
动态链图 6.8 动态链和静态链静态链
43
在嵌套深度为 np的单元 p中,引用了在嵌套深度为 nt
的单元 t中说明的变量 x,我们将 x约束于一个二元式 (d,offset),其中 d=np – nt,offset是指 x在 t的活动记录中的位移 。 因此在 p中引用 x,可以从 p的活动记录开始,沿静态链在栈中向下搜索 d步,到达 t的最新活动记录 Dt。 如果定义成递归函数：
f(d) = if d = 0 then current else D[f(d-1) +8]
则 Dt = f(d)。 对于半静态变量,Dt + offset为 x的地址 。 对于半动态变量,则 Dt + offset为 x的描述符的地址,它的元素指向动态数组 x在活动记录中首址 。
如果 d = 0,则 x为 p中的局部变量 。
44
为了设置活动记录中的静态连接,调用语句的操作语义应作修改 。 单元 A调用了单元 B,则 B在 A中是可见的：或 B是 A的外层,或 A与 B有相同的外层,
或 A是 B的直接外层 。 因此,对 B设置的静态连接,
应为沿 A的静态链在栈中向下搜索 nA-nB +1步所指向的活动记录 。
调用语句的语义由下列六条指令实现：
(1) D[free]:= ip+24
(2) D[free+4]:= current
(3) D[free+8]:= f(d+1)
(4) current:=free
(5) free:=free+L
(6) ip:=B的代码段首址返回语句的语义实现与本节第一部分相同 。
45
2,动态作用域规则在这种情况下,活动记录中位移为 8的静态连接是一指针,它应指向动态调用直接外层的活动记录 。
显然它与动态链是一致的,可以合并 。 从图 6.8中也可以看出动态作用域的引用关系,因此调用语句的返回语句的操作语义如本节第一部分所述 。
46
§ 6.4 堆分配动态语言采用动态规则,通常指动态类型规则和动态域规则 。 如 APL,LISP和 SMOBOL4。 动态变量因其类型,访问方法,使用的操作,都不能在编译时确定,因此动态变量的描述符的长度也是动态可变的 。 所以在活动记录中为动态变量安排了指向描述符和指向变量存储区的二个指针,而在堆上对描述符和变量作存储分配 。
47
此外，单元之间的调用关系如果并不遵循后进先出原则，某些单元在运行具备后被激活了，与当前活动单元不存在嵌套调用关系，二个单元的生存期就可能是交叉的。一个单元的存储空间的申请和释放可能是随机的，在这种情况下，也只能在堆上作存储分配。我们只讨论动态变量的堆分配问题。
作为堆的存储空间可以由固定长度的存储块组成,
也可以由可变长度的存储块组成 。 在堆中可随机申请一个或几个存储块,活动结束时可随机释放,因此经过一段时间后,堆空间可能被划分成如图 6.9所示的状态 。
48
P Q R S
Q
P
R
S
free
图 6.9 堆分配的存储空间组织使用块记录
49
在这些存储块中,有些正在使用,由使用块记录指出各使用块的开始位置及块的大小等有送信息；有些则空闲,称为自由块 。 所有自由块均被链接起来 。
由指针 free指向其起始块,每个自由块都有一指针指向下一自由块 。 当有一使用块被释放时,该块连接到 free链中,并从使用块记录中撤消该块的记录项 。 设自由块总长度为 N,从中申请长度为 n的新的使用块时,会出现下列几种可能：
50
(1) 有若干个自由块,其大小均大于等于 n,则采用首次拟合法：搜索 free链,寻找第一个满足其长度
1≥n的自由块 。 该块分成长度 n的使用块和长度为 l-
n的自由块,分别加入使用块记录和自由块链 free。
除首次拟合法外,还可采用最优满足法和最差满足法 。 最优满足法是从 free链中寻找一块 ≥n的最小自由块,最差满足法则从 free链中寻找 ≥n的最大自由块,与首次拟合法各有优缺点 。
51
(2) 若每个自由块的长度都小于 n,但这些自由块的总度 N却大于等于 n,将这些碎片形成一个连续空间后再对 n进行分配是一种解决办法 。 这时需将使用块移位搬家,程序各引用点都得调整 。 其中,对引用堆对象的指针的调整比较困难 。
52
(3) 若 N<n,空闲区已不敷分配,这时需调用无用单元回收器 (Garbage Collector)来隐式释放,没有使用,的使用块 。
方法之一是标记法：首先把所有从栈出发可到达堆数据对象的引用都作出标记,或称着色 。 每个堆对象都有一个指针,它指向栈的下一个引用堆对象的存储单元 。 接着穿过该存储单元的指针而到达另一堆对象,对它也作出标记或着色 。 重复这一过程,直至所有栈到堆的引用对象都作出了标记为止 。 从概念上看,通过这些指针给堆着色了的是正在使用的块,其余的为没有使用的块,可以释放 。 方法之二为引用计数法,每个数据块都记录其它数据对象对它的引用跟踪,如果引用数降为 0,那么该块可以释放 。 但这种方法只有在块之间的指针不出现环时才有效 。
堆的管理在时间和空间上都需额外开销,高效率的堆管理问题是数据结构理论中的专门问题 。 以上只是堆分配的简述,以便与栈式分配作一比较 。
53
§ 6.5 参数传递程序单元之间的通信可以通过非局部环境来进行,也可以通过参数传递来实现 。 但参数传递允许每欠调用时传递不同的数据,既灵活,又有较高的可读性和可修改性 。 例 6.3
中,a和 b是形式参数 (Formal Parameter),是 swap与它的调用者之间信息交换的媒介 。 调用语句 swap (m,n)按位置对应关系将实在参数 (actual parameter)m和 n依次传递给形式参数 a 和 b。
[例 6.3] 下列程序作参数传递用例 。
Procedure swap(a,b,intger)；
Var temp,intger；
begin temp:=a；
a:=b；
b:=temp
end swap
实参与形参之间的参数传递有三种类型：数据参数传递,
过程参数传递和类型参数传递 。 这里只介绍前两种 。
54
一,数据参数传递数据参数有引用调用 (call by reference),值调用
(call by value)和名调用 (call by name)三种传递方式 。
不同的语言有不同的约定 。 FORTRAN以引用调用为标准传递方法,ALGOL 60为名调用,也可指定值调用,Pascal 可指定值调用或引用调用,
SIMULA 67则提供值调用,引用调用和名调用三种形式 。 如何选择参数的传递方式将影响语言的语义,
同一程序采用不同的传递方式,将导致不同的结果 。
55
1,引用调用将调用环境中实参地址传递给形参的参数传递方式称为引用调用 。 如实参是常数或表达式,则将它的值存放在一中间存储单元 (或称临时变量 )中,将中间存储单元地址传递给形参 。 有些语言不允许向赋值左部的形参传送常数或表达式的实参,一旦出现这种情况,就作错误处理 。 被调用程序单元对形参的引用,被理解为对形参单元中实参地址的间接引用 。 被调用单元通过形参可对实参作修改,因此实参的存储单元为调用程序单元的被调用程序单元共享 。
引用调用的实现方法是,向被调用过程的活动记录中的形参单元传送实参变量的地址,或传送存放实参值的临时变量的地址 。
56
2,值调用形参只起局部变量作用,实参存储单元也不能为形参共享,
不能对调用程序单元的参数随意修改 。 形参和实参之间的值的传递有下列三种方式：
(1) 传值 调用程序单元将实参的值传递给形参,作为形参这一局部变量的初始化 。 被调用程序单元对形参的赋值不影响调用程序单元的环境 。 这是实参向形参的值的单向传递 。
(2) 结果调用 (call by result) 被调用程序单元在被调用时,
形参仅作局部变量,实参不向形参传值,形参也不引用实参 。 而被调用单元在结束活动时,将形参的值复制到调用环境的实参单元中 。 这是形参向实参单向传递结果值 。
(3) 传值得结果 (call by value-result)也称复写入复写出 (copy-
in and copy-out)。 调用单元以实参值初始化形参,被调用单元在结束活动时将形参的值复制至实参 。
57
值调用的实现方法：通常为一形参设两个存储单元,
其中一个值单元和一个地址单元 。 传值时,将实参的值传递给形参的值单元；得结果时将实参的地址
(或存放实参的值的临时变量的地址 )传递给形参的地址单元 。 被调用单位结束活动时,若为得结果,
将形参单元中的值,按形参地址单元中实参地址,
向实参传递 。
58
3,名调用这是由 ALGOL 60定义的一种特殊的参数传递方式,根据它的复制规则 (copy-rule)定义：
(1) 过程调用的作用相当于把被调用过程的过程体复制到调用处,但把其中任一出现的形式参数文字上替换成相应的实在参数 。 这种文字上替换称为宏扩展 (Marcro Expansion)。
(2) 被调用过程中的局部名如果与过程调用处的名发生冲突,
则在宏扩展前对被调用过程中的这些局部名重新命名,以避免重名冲突 。
(3) 为了表现实在参数的整体性,必要时在替换前把实在参数用括号括起来 。
59
对例 6.3给出的过程,swap(a,b)是将 a,b的值互换,但根据换名规则,调用语句
swap(i,a[i])
在 swap执行中为
temp:=i；
i:=a[i]；
a[i],= temp
调用前若 i=3,a[3]=4,则调用后为 i=4,a[4]=3,而不是想像中的 i=4,a[3]=3。
名调用这种参数传递方式使程序难读,也难于实现 。
名调用的基本实现技术是把实在参数处理成一个子程序,
对形式参数的每次引用就调用这个实参子程序 (也称为
Thunk)。 因此并不是在进入被调用过程前先计算实在参数,
而是在进入被调用过程后每次引用形参就每次调用 thunk。
60
二,过程参数的传递数据参数是常见的,大量的,但也有将过程 (子程序 )作为参数进行传递的情况 。 例如,一个问题的求解方法可能有好几个,如排序与检索,每一种方法对应于一个子程序 。 如果想评价各种方法的优劣,如占用空间的大小,运行时间的长短等,就需要设计一个测试 S程序性能的测试程序,它将 S作为形式参数,当测试某个方法所对应的子程序为 T时,
便可将实在参数 T传递给 S。 因此过程作为参数传递的这种方式是有实用价值的,为一些语言所采用 。
程序单元 P将实在过程 T作为参数传递给程序单元 Q,这意味着在单元 P中有过程调用语句 CALLQ(T)：
Unit P
…
CALL Q(T)；
…
end P
61
而单元 Q中存在着被区分为过程的形式参数,不妨记为 S。
显然,在单元 Q中,应有关于 S的调用语句：
Unit Q(S:procedure)
…
CALL S；
…
end Q
在这种情况下,CALL S实际上就是 CALL T。 因此需向形参 S传递 T的代码首址以及 T的引用环境,以便在 CALL S时可转而调用 T过程,并在 T的环境下引用 T的局部变量和非局部变量 。 但由于静态作用域规则和动态作用域规则的不同,在 CALLS处 T的引用环境也是不同的 。
62
在静态作用域规则下,CALL S处 T的局部环境,应由单元 P
中 CALL Q(T)处 T的静态非局部环境,即 T的静态连接指出,
并传递给 S,在 CALL S时便可获得 T的静态非局部环境 。 因此对区分为过程的形参 S设置二个指针,一个指向实参过程
T的代码段首址,另一个存放实参 T的静态连接 。 对静态嵌套语言来说,它们都是静态可确定的 。 当在单元 Q中调用形参过程 S时,执行形参单元中指向的 T代码,将形参单元中的实在过程 T的静态连接记入活动记录,建立起 T的非局部环境 。
在动态作用域规则下,CALL S处于 Q中,不管在栈顶上将建立的实参过程是什么,它的动态外层都是 Q,实参过程 T
只需向 S传递 T代段的首址即可 。 非局部引用环境由动态链给出 。
63
§ 6.6 符号表在程序中,用户用标识符定义了不少名字来代表不同的数据对象,编译程序将这些名字保存在符号表中 。 符号表除了记录名字本身而外,还记录了与名字关联的各种属性信息,例如名字的种属 (常量,变量,数组,过程等 ),名字的数据类型 (整型,实型,布尔型,字符型等 ),为名字分配的数据空间的存储地址以及编译过程中的一些特征标志和其他有关信息 。 在词法分析阶段,当识别出一个新的名字时,
便将此名字登入符号表 。 与之关联的其他属性值,可在词法分析,语法分析,语义分析及中间代码生成等各阶段陆续填入 。 总之,符号表的登记工作应在准确获得相关信息后即时完成 。 随之,在编译各阶段每当需要引用名字及其有关信息时,只要查询符号表便可获得 。 因此,在编译中对符号表的访问相当频繁,所需的时间开销占了编译时间的不小的比例 。 如何组织好符号表,为符号表上的操作选择好的算法,是提高编译效率的不可忽视的问题 。
64
一,符号表的组织在符号表中为每一个名字设立一个表项,每一个表项是一个记录,通常有两个域构成,一个是名字域,一个是信息域 。 信息域通常设若干子域及标志位 。 不同种属的名字的信息是不同的,因此信息域的构成也不同 。 但不管怎样,
名字的存储分配信息 (名字的绑定信息 )始终是信息域中的一个重要组成部分 。
名字的长度、信息域的组成及长度可能是各不相同的。除非给出某种约定，否则符号表项各域的长度很难一致，因此常采用间接表技术。
65
以名字域为例，如果约定名字域长度为 10，图 6-10(a)给出了四个名字在符号表中的登记状况。如果在符号表外另设一字符串数组，每个名字的字符串记录在字符串数组中，每个字符串以 EOW作为结束标志，而符号表的名字域中为一指针，它指向该名字在字符串数组中的开始位置，于是图 6-10(a)的内容就可以用图 6-10(b)来表示。不难发现，这种间接表方式使符号表长度一致，存储空间使用得更有效。信息域各子域也可仿此组织。
名字信息名字 信息
sort
a
readarray
...
(a)
sorteowaeowreada r r a g eow ieow
(b)
图 6.10 名字的存储技术 (a)名字的直接存储 (b)间接表技术
66
如何确定名字的存储分配信息呢？ 编译程序在编译时刻确定名字运行时刻的存储分配信息,并将它填入符号表中 。
如果生成的目标代码是汇编语言的,由于汇编程序具有管理不同名字的存储分配功能,所以在由源程序生成汇编代码后,需扫描符号表,为每一名字生成汇编语言的数据定义并提供给汇编程序,汇编程序据此对名字作存储分配 。
如果生成的目标代码是机器代码,则每个数据目标的存储位置与一个固定的起始地址 (如活动记录的开始地址 )相关 。
单独的数据模块中的数据目标位置也是如此 。 Fortran的
COMMON区是单独存放的,其起始位置是确定的,其中的数据目标的位置与该起始位置相关 。
动态栈式分配时,每一名字对过程活动记录中某一位置 (如
current指的位置 )的位移量,即相对地址是可知的,它就是符号表中名字的存储信息 。 运行时,当过程活动的位置确定后,这些名字的真正地址也就确定了 。
67
二,常用的符号表结构在一个源程序中,有可能定义了上百个名字,并对它们引用了上千次,因此这些操作的总代价在编译时是不可忽视的 。 通常可以用插入 n个名字和进行 e次查找所需的总时间来评价各种符号表结构的优劣 。
(1) 线性表 这种表格结构简单而自然 。 用 N个数组 A1，
A2,…,AN来存放符号表的 N个子域,其中的一个数组,
如 A1相应于名字域 。 显然,确定下标 i,便可知道名字为
A1[i]的各信息子域 A2[i],…,AN[i]。 符号表当前位置由指针 P指示,它指出了下一个符号表项将要存放的位置 。 如果一个符号表已经包含了 n个名字,则 P指向 n+1项 。
插入一个新名字时,首先要查符号表以确定这名字是否已在符号表中,其代价与 n成正比 。 而查询某个名字的信息,
其代价也与 n成正比 。 因此插入 n个名字并在 n个名字上作 e
次查找所需的总代价与 cn(n+e)成正比,其中 c是一个常数,
它与实现符号表操作的一组指令的执行时间是相关的 。
68
(2) 散列表 (Hash Table) 它在编译中广泛使用 。 它将所有名字分成 m组,由 hash函数 (其值为 0,…,m-1)
来计算一个名字 S应属的组号 hash(S)。 具有相同
hash值的同一组名字形成一个链表,其链头位置记录在长度为 m的 hash表的 hash(s)项 。 因此散列表是由长度为 m的指针数组构成,如图 6-11所示 。 其中设名字 cp和 n的 hash值均为 9,match的 hash值为 20，
而 last,action,ws均为 32,斜线 /表示链尾 。 这种形式的散列表是一种开放散列表 。
…
…
…
…
图 6.11 长度为 256的散列表
0
9
20
32
25
5
cp n
action
match
last ws
69
在这种结构的表中插入 n个名字,并在 n个名字上进行 e次查找所需的总代价,与 n(n+e)/m成正比 。 很明显,其效率比线性表高,因为 m并不小 。 特别当 m取值为 n时,总代价是 n+e
的线性函数 。 然而开放散列表的空间开销随 m的增大而增加,
因此这是一种以空间换取时间的方法 。 m取多大为宜？ 符号表使用频度高,时间矛盾突出时 m宜大 。 对中等规模的程序,
m取几百,查表可以说是即查即得,这时查表时间相对说来是一个小量 。 如果空间不富裕,则 m宜小 。
开放散列表的一个要点是设计一个好的 hash函数,一要计算速度快,二要把所有的名字均匀地分布到 m个链表中去,
这样有利于提高速度 。
70
[例 6.4] 如果将每个标识符记录在 character string中,每个字母或数字占一个字节,用 EOW作为标识符结束标志,它也占一个字节 。 符号表采用上述 hash表结构,设 hash函数将 a,…,z,0,…,9对应于 1,…,26,27,…,36,然后将标识符的每个字母或数字对应的数值相加得 Sum,以 Sum mod 5作为该标识符的 hash值 。 Hash表中为相应 hash链的指针,最新出现的标识符总是处于 hash链的链头 。 如果在词法分析时依次遇到下列标识符,temp,swap,grammar5,show5,
v3rd,reference1,exchange6,则相应的符号表如图 6.12所示 。
其中 hash链中元素的名字域是指向名字在 character string中起始位置的指针,第二元为信息域,第三元为链接元 。
71
0
2
4
图 6-12 例 6.4的符号表示意图
1
3
P7
P6
P2 P1
P3
P5
P4
P1? P2? P3? P4?
t e m p EOW S W a p EOW g r a m m a r 5 EOW s h o w
P5? P6? P7?
5 EOW v 3 r d EOW r e f e r e n c e 1 EOW e x c h a
n g e 6 EOW
