编译原理 第六章运行时存储空间管理 上海交通大学 张冬茉 Email:Zhang-dm@cssjtu.edu.cn 2004年5月
1 编译原理 第六章运行时存储空间管理 上海交通大学 张冬茉 Email:zhang-dm@cs.sjtu.edu.cn 2004年5月
第六章运行时存储空间管理 §6.1变量及存储分配 个用高级语言写的程序要投入运行,首先要有一组 可运行的代码,这组代码应与高级语言的程序等价; 其次还需要一个运行环境,对程序中的变量作存储分 配,提供各种运行信息。前者涉及程序语言的编译系 统,我们已在前几章中作了概要介绍。后者涉及变量 以及变量的存储分配和存储管理的问题。本章主要讨 论运行时的存储管理问题,也涉及了符号表的组织与 管理。 2
2 第六章 运行时存储空间管理 §6.1 变量及存储分配 一个用高级语言写的程序要投入运行，首先要有一组 可运行的代码，这组代码应与高级语言的程序等价； 其次还需要一个运行环境，对程序中的变量作存储分 配，提供各种运行信息。前者涉及程序语言的编译系 统，我们已在前几章中作了概要介绍。后者涉及变量 以及变量的存储分配和存储管理的问题。本章主要讨 论运行时的存储管理问题，也涉及了符号表的组织与 管理。
、程序的存储空间 个程序要运行,至少应有这样两个存储空间: (1)代码空间这是经翻译后生成的目标代码的存储区域, 线性存放着目标指令序列。对三地址代码来说,当前执行 的指令位置由指令指针ip指示。因此,只要将印指向程序的 第一个语句,程序便处于开始执行的状态,以后每执行 个语句,i便加4(我们约定,三地址代码的每个语句占4个 字节),指向下个语句。要改变程序控制顺序,只要将转向 点赋给p即可。 3
3 一、程序的存储空间 一个程序要运行，至少应有这样两个存储空间： (1) 代码空间 这是经翻译后生成的目标代码的存储区域， 线性存放着目标指令序列。对三地址代码来说，当前执行 的指令位置由指令指针ip指示。因此，只要将ip指向程序的 第一个语句，程序便处于开始执行的状态，以后每执行一 个语句，ip便加4(我们约定，三地址代码的每个语句占4个 字节)，指向下个语句。要改变程序控制顺序，只要将转向 点赋给ip即可
(2)数据空间每个程序都定义一定数量的各种类型的变量 和常数,翻译程序必须为之分配相应的存储空间。初等类 型的数据,如逻辑、整型、实型变量,通常以存储器的基 本存储单元如字节、字、双字来存储。集合数据,如数组 串、记录结构等,一般用若干个连续的字节或字来存储 这便使变量绑定( Biding)于一个存储区域。变量获得存储区 的这种活动称为分配( Allocation)。一个变量一旦被建立, 就获得了相应的存储区,完成了存储区与变量的绑定。除 了这些变量与常数外,数据空间还保存了程序的一些控制 和管理信息(例如,反映程序间调用关系的控制链,反映程 序间变量引用关系的引用链等)、说明程序实体的绑定信息 的描述符以及其他等等。 4
4 (2) 数据空间 每个程序都定义一定数量的各种类型的变量 和常数，翻译程序必须为之分配相应的存储空间。初等类 型的数据，如逻辑、整型、实型变量，通常以存储器的基 本存储单元如字节、字、双字来存储。集合数据，如数组、 串、记录结构等，一般用若干个连续的字节或字来存储。 这便使变量绑定(Biding)于一个存储区域。变量获得存储区 的这种活动称为分配(Allocation)。一个变量一旦被建立， 就获得了相应的存储区，完成了存储区与变量的绑定。除 了这些变量与常数外，数据空间还保存了程序的一些控制 和管理信息(例如，反映程序间调用关系的控制链，反映程 序间变量引用关系的引用链等)、说明程序实体的绑定信息 的描述符以及其他等等
对一个程序来说,它的代码长度可以在编译时刻完全确定 下来,因此,编译时便可安排代码空间。但对数据空间来 说,不仅程序实体的属性影响了存储分配(例如变量类型影 响了每个数据元素的存储长度,作用域决定了变量绑定于 某存储区的空间范围,生存期决定了这种约束的时间范围), 而且语言的运行特性也决定了数据空间的分配和管理应采 用的方法和策略。有的语言在运行前就能确定数据空间的 大小,因而在编译时刻就能进行存储分配,这种分配策略 称之为静态分配( Static Allocation),有的语言则必须在运行 时刻才能作分配,称之为动态分配( Dynamic Allocation) 有的语言因变量生存期具嵌套特性而采用栈分配( Stack Allocation)策略,有的语言因生存期的随机交叉特性而采用 堆分配( Heap allocation)策略
5 对一个程序来说，它的代码长度可以在编译时刻完全确定 下来，因此，编译时便可安排代码空间。但对数据空间来 说，不仅程序实体的属性影响了存储分配(例如变量类型影 响了每个数据元素的存储长度，作用域决定了变量绑定于 某存储区的空间范围，生存期决定了这种约束的时间范围)， 而且语言的运行特性也决定了数据空间的分配和管理应采 用的方法和策略。有的语言在运行前就能确定数据空间的 大小，因而在编译时刻就能进行存储分配，这种分配策略 称之为静态分配(Static Allocation)，有的语言则必须在运行 时刻才能作分配，称之为动态分配(Dynamic Allocation)。 有的语言因变量生存期具嵌套特性而采用栈分配(Stack Allocation)策略，有的语言因生存期的随机交叉特性而采用 堆分配(HeapAllocation)策略
、活动记录 个程序单元( Program unit,以下简称单元)的一次激活所 需的信息管理是通过相应的活动记录( Activation record)来 实施的。一个单元的每次激活,都应建立相应的活动记录, 它是单元实例的一部分。 个活动记录是一连续存储区。通常,它的内容如图61所 小。 当单元A调用单元B时,应中断A的活动,建立B的活动记 录,将调用的实在参数传递给B的活动记录,将控制转移至 B,使B处于活动状态。因此,活动记录中应包含如下内容: 6
6 二、活动记录 一个程序单元(Program Unit，以下简称单元)的一次激活所 需的信息管理是通过相应的活动记录(Activation Record)来 实施的。一个单元的每次激活，都应建立相应的活动记录， 它是单元实例的一部分。 一个活动记录是一连续存储区。通常，它的内容如图6.1所 示。 当单元A调用单元B时，应中断A的活动，建立B的活动记 录，将调用的实在参数传递给B的活动记录，将控制转移至 B，使B处于活动状态。因此，活动记录中应包含如下内容：
返回指针 returned pointer 动态链 dynamic link 静态链 static link 保存的机器状态 saved machine states 参数单元 parameters 局部变量 local variables 临时变量 temporaries 图6.1活动记录 7
7 返回指针 returned pointer 动态链 dynamic link 静态链 static link 保存的机器状态 saved machine states 参数单元 parameters 局部变量 local variables 临时变量 temporaries 图6.1活动记录
(1)分配给形式参数的存储单元,这是实参传递的存储区。 (2)A被中断时的状态以及中断结束后的返回点,以便B的活 动结束后能返回被中断的A,使A继续活动起来。 (3)B的局部变量或它们的描述符,以及临时变量。 (4)记录动态调用关系的动态链及记录静态嵌套关系的静态 链。静态链用以实施静态作用域规则,动态链除记录了调 用控制关系外,也是动态作用域实施的依据。 显然,除了变量存储区外。活动记录的其他部分的存储长 度都是编译时可确定的。如果一个单元不含动态数组和动 态类型数据,这个单元的活动记录的长度在编译时便可确 定。对活动记录中某元素i的访问,可通过该元素在活动记 录中的位移 offset(.表示,一旦活动记录被分配在存储位 置D,则i地址为 D+offset(i) 8
8 (1) 分配给形式参数的存储单元，这是实参传递的存储区。 (2) A被中断时的状态以及中断结束后的返回点，以便B的活 动结束后能返回被中断的A，使A继续活动起来。 (3) B的局部变量或它们的描述符，以及临时变量。 (4) 记录动态调用关系的动态链及记录静态嵌套关系的静态 链。静态链用以实施静态作用域规则，动态链除记录了调 用控制关系外，也是动态作用域实施的依据。 显然，除了变量存储区外。活动记录的其他部分的存储长 度都是编译时可确定的。如果一个单元不含动态数组和动 态类型数据，这个单元的活动记录的长度在编译时便可确 定。对活动记录中某元素i的访问，可通过该元素在活动记 录中的位移offset(i)来表示，一旦活动记录被分配在存储位 置D，则i的地址为 D+offset(i)
变量的存储分配 由上可见,局部变量的存储分配对活动记录的建立有着主 要影响。从存储分配角度看,变量有四种类型 (1)静态变量( Static variable)如果每个单元的活动记录, 以及每个变量的存储位置,在编译时均可确定,在运行时 不会变化,那么存储分配可在编译时完成,这便是所说的 静态分配。静态分配是在编译时将变量绑定于一个存储区, 不管在程序单元的哪一次活动中,这些变量都绑定于相同 的存储位置。这类变量称为静态变量
9 三、变量的存储分配 由上可见，局部变量的存储分配对活动记录的建立有着主 要影响。从存储分配角度看，变量有四种类型。 (1) 静态变量(Static Variable) 如果每个单元的活动记录， 以及每个变量的存储位置，在编译时均可确定，在运行时 不会变化，那么存储分配可在编译时完成，这便是所说的 静态分配。静态分配是在编译时将变量绑定于一个存储区， 不管在程序单元的哪一次活动中，这些变量都绑定于相同 的存储位置。这类变量称为静态变量
(2)半静态变量( Semistatic variable)如果一个语言允许单 元的递归调用,一个单元可递归地被多次激活,这就会为 个单元建立起多个活动记录。变量是在单元每次激活时 动态地绑定于刚建立的活动记录。这类变量的长度必须是 编译时可确定的,因而活动记录的长度、变量x在活动记录 中的相对位置(即位移oset(x),都是编译时可确定的。运 行时,一旦该单元被激活,相应活动记录便获得物理存储 区D,变量x便被定于D+ofe(x)。这类变量称为半静态变 量。虽然每个活动记录的长度,每个变量在活动记录中的 相对位移,如同静态变量那样在编译时可知(称为静态可 确定)但这样的活动记录的个数却依赖于该单元的递归调 用深度,这是运行时可知(动态可确定)的。 10
10 (2) 半静态变量(Semistatic Variable) 如果一个语言允许单 元的递归调用，一个单元可递归地被多次激活，这就会为 一个单元建立起多个活动记录。变量是在单元每次激活时， 动态地绑定于刚建立的活动记录。这类变量的长度必须是 编译时可确定的，因而活动记录的长度、变量x在活动记录 中的相对位置(即位移offset(x))，都是编译时可确定的。运 行时，一旦该单元被激活，相应活动记录便获得物理存储 区D，变量x便被定于D+offset(x)。这类变量称为半静态变 量。虽然每个活动记录的长度，每个变量在活动记录中的 相对位移，如同静态变量那样在编译时可知（称为静态可 确定）但这样的活动记录的个数却依赖于该单元的递归调 用深度，这是运行时可知（动态可确定）的