《编译原理简明教程》21世纪高等学校计算机学科系列教材---太原理工大学---计算机科学与技术学院---冯秀芳第一章 引言第二章 形式语言理
论基础第三章 自动机理论基础第四章 词法分析第五章 语法分析—自顶向下分析方法第六章 语法分析—自底向上分析方法第七章 语义分析及
中间代码的生成第八章 代码优化第九章 目标代码的生成第十章 符号表第十一章 目标程序运行时的存储组织与分配第十二章 出错处理第十三
章 编译程序自动生成工具简介第十四章 面向对象语言的编译第十五章 并行编译技术目 录第十一章 目标程序运行时的存储组织与分配
学习目标了解和掌握程序运行时的存储组织了解和掌握静态存储分配 了解和掌握栈式动态存储分配
了解和掌握堆式动态存储分配 了解和掌握参数传递机制11.1 程序运行时的存储组织11.2 静态
存储分配11.3 栈式动态存储分配11.4 堆式动态存储分配11.5 过程的调用与返回11.6 参数传递机制目 录11.1 程序
运行时的存储组织程序在运行时，系统将为其分配一块存储空间，该空间需容纳程序生成的目标代码以及目标代码运行时的各种数据。从用途上来看
，这块存储空间可以划分为 ：① 目标程序区，用来存放目标代码。② 静态数据区，用来存放编译时就能确定存储空间的数据。③ 运行栈区，
用来存放运行时才能确定存储空间的数据。④ 运行堆区，用来存放运行时用户动态申请存储空间的数据。 11.1 程序运行时的存储组织动态
存储分配方式有两种：栈式和堆式。栈式：主要采用一个栈作为动态分配的存储空间，当调用一个过程时，过程中各数据项所需的存储空间就动态地
分配于栈顶，当过程工作结束时，就释放这部分存储空间。堆式：主要通过给运行程序分配一个大的存储空间(称为堆)，每当运行需要时就从这片
空间中借用一块，用过之后再退还给堆。 11.2 静态存储分配静态存储分配就是在编译时对所有的数据项分配固定的存储单元，且在运行时始
终保持不变。适用于静态存储分配的程序设计语言必须满足下列条件：? 不允许过程的递归调用；? 不允许含可变体积的数据；? 不允
许用户动态地建立数据实体 例如，FORTRAN语言(FORTRAN 90除外)。11.2 静态存储分配静态存储分配策略：编译程序
在对源程序正文进行处理时，对每个变量均建立一个符号表项目，并填入相应的属性(包括填入目标地址)。 例如，FORTRAN程序段如下：
REAL S1,S2REAL A (5),B (5,10)11.3 栈式动态存储分配栈式存储分配策略是将整个程序的数据
空间设计为一个栈，每当程序调用一个过程时，就在栈顶为其分配数据空间，当调用结束时，就释放这部分空间。 这种方式适用于C、Pasca
l、ALOGOL、PL/I等语言。 11.3 栈式动态存储分配为了管理一个过程在一次执行时所需要的信息，常使用一段连续的存贮区，这
个存贮区称为活动记录。活动记录一般包含以下内容。? 局部数据区：用于存放局部变量、内情向量和临时工作单元(存放中间结果)；?
参数区：用于保存实在参数的地址或值；? 地址区：用于存放与该过程有关的一些地址信息。如返回地址、控制链、存取链。11.3.1
简单的栈式存储分配有一些语言允许过程递归调用，但是不允许过程嵌套定义，也没有分程序结构，这些语言可以采用简单的栈式存储分配方式。
例11.1】 一个C语言的程序结构如下：extern float scale；/全局变量说明/ …main (
){ int n；float m； /局部变量说明/ …}void P1 ( ){ int i
； /局部变量说明/ …}void P2 (float a){ int i，j；)
/局部变量说明/ …} 11.3.1 简单的栈式存储分配若主程序调用了过程P1，P1又调用了P2，那么P2进
入运行后的存储结构如图所示；若主程序调用了过程P2，P2又递归调用自己，P2过程第二次进入运行后的存储结构如图所示。11.3.2嵌
套过程语言的栈式存储分配 程序设计语言的程序结构中允许过程嵌套定义，存储分配不能运用简单的栈式办法来实现。【例11.2】 一个省略
的Pascal程序。 11.3.2嵌套过程语言的栈式存储分配内层过程在运行时必须知道其所有外层过程的最新活动记录的地址，以便在活
动记录中查找非局部量所对应的存储空间，所以必须设法跟踪每个外层过程的最新活动记录的位置。跟踪的方法主要有两种方法：一种是在过程活动
记录中增设存取链，指向包含该过程的直接外层过程的最新活动记录的地址，其过程活动记录的内容如图所示。第二种是在建立过程活动记录的同时
建立一张嵌套层次显示表display，该表记录着每一层过程的最新活动记录的地址，display表的内容如图所示。11.3.2嵌套过
程语言的栈式存储分配例如，假定例11.2中Pascal程序的某次执行顺序为：aaa→A→B→C→…即程序的执行从主程序aaa开始，
aaa调用了过程A和B，而B又调用了过程C……，图11.7给出了进入过程C之后运行栈的情况示意。 11.4 堆式动态存储分配程序
设计语言允许动态申请和释放存储空间，那么运行时的存储管理通常采用堆式动态存储策略。堆式存储分配在运行时动态地进行。假设程序运行时有
一个大的存储空间，每当需要时就从这片空间中申请一块，不用时再释放给它。对于堆式存储分配来说，需要解决两方面的问题：堆空间的分配，即
当运行程序需要一块空间时，应该分配哪一块给它；分配空间的解除，由于返回给堆的不用空间是按任意次序进行的，所以需专门研究解除分配的策
略。 11.4 堆式动态存储分配当运行程序要求一块体积为N的空间时，应该如何分配？可以采取多种策略进行堆式动态存储管理，如：可
利用空间表边界标志法、伙伴系统、无用单元收集和存储压缩等策略。这里仅介绍一种使用可利用空间表进行动态分配的方法。 可利用空间表是指
将所有空闲块用一张表记录下来，表的结构可以是目录表，也可以是链表。动态存储分配的方法使用可利用空间表进行动态存储分配的方法又可分为
如下两种：定长块的管理:是最简单的堆式存储管理方法，即将堆存储空间在初始化时就划分成大小相同的若干块，将各个块通过链表链接起来形成
一个单向线性链表。 变长块的管理 :是常用的堆式存储管理方法，即可以根据需要分配给用户长度不同的存储块。 动态存储分配的方法由于可
利用空间表中的结点大小不同，当可利用空间表有若干个满足需要(大于等于申请块)的空闲块时，可采用下列三种方法进行存储分配：首次满足法
：从表头开始查找可利用空间表，将找到的第一个满足需要的空闲块或空闲块的一部分分配给用户。最优满足法：系统首先对可利用空间表从头至尾
扫描一遍，然后从中找出一块不小于申请块且最接近于申请块的空间块分配给用户。最差满足法：系统将可利用空间表中不小于申请块且是链表中最
大空闲块的一部分分配给用户。11.5 过程调用与返回 当出现过程调用时，编译程序必须为活动记录分配存储空间，计算并存储参数值，为
调用分配相应的存储器等。过程调用完成的工作有：分配被调过程的活动记录并填入相关信息，然后将程序控制转移到被调过程入口。 过程返回主
要完成的工作有：回收分配的被调过程活动记录所占用的空间，并将程序控制转移回调用过程继续执行。11.6 参数传递机制过程(或函数)
是结构化程序设计的主要手段，当一个过程调用另一个过程时，不同的参数传递机制可能会产生不同的结果，主要有四种常见的参数传递机制：值传
递；引用传递；值-结果传递；名字传递。11.6 参数传递机制值传递是最简单的参数传递机制，在调用时计算实参所代表的表达式，其值就
是被调用过程运行时形参的值。值传递的实现如下：① 把形参当做过程的局部变量，即在被调用过程的活动记录中开辟形参的存储空间；② 调用
过程计算实参的值，并将它们的值放在形参开辟的存储空间中；③ 被调用过程执行时，就像使用局部变量一样使用这些形式单元。11.6 参
数传递机制在引用传递中，实参必须是分配了存储单元的变量，调用过程把实参的地址传给被调用过程，使得形参成为实参的别名，因而对形参的任
何改变也同时体现在实参中。当采用引用传递时：① 如果实参是有左值的名字或表达式，则传递这个左值本身；如果实参是没有左值的表达式，则
计算表达式的值并存入新的存储单元，然后传递这个新单元的地址。(注意：左值指的是表达式所表示的存储单元)。② 在被调用过程的目标代码
中，对形参的任何引用都是通过形参存储的地址来间接引用实参的。 11.6 参数传递机制在值-结果传递中，每个形参对应两个单元，第一
个单元存放实参的地址；第二个单元存放实参的值。任何对形参的引用或者赋值都看成对它的第二个单元的直接访问，但在返回调用过程前必须把第二个单元的内容存放到第一个单元所指的实参单元中。 名字传递是最复杂的一种参数传递机制。在名字传递中，通常每个实参对应一个子程序，称为形、实替换程序(thunk)。当调用时，若实参不是变量，那么thunk就计算实参，并送回计算值所在的地址。在过程体中每当引用形参时，就调用相应的thunk，然后利用thunk返回的地址引用该值。 |
|
