《编译原理chapter7》由会员分享，可在线阅读，更多相关《编译原理chapter7（39页珍藏版）》请在金锄头文库上搜索。
1、版权所有 计算机学院 闫健恩第七章第七章 运行时刻环境运行时刻环境1版权所有 计算机学院 闫健恩概概 述述静态存储管理静态存储管理栈式存储管理栈式存储管理堆式存储管理堆式存储管理2版权所有 计算机学院 闫健恩7.1 概述概述n运行时刻环境运行时刻环境n为数据分配安排存储位置为数据分配安排存储位置n确定访问变量时使用的机制确定访问变量时使用的机制n过程之间的连接过程之间的连接n参数传递参数传递n和操作系统、输入输出设备相关的其它接口和操作系统、输入输出设备相关的其它接口n目的目的 编译程序除了要关心目标代码生成问题外，编译程序除了要关心目标代码生成问题外，还必须要考虑程序运行时使用的数据区域的管
2、理还必须要考虑程序运行时使用的数据区域的管理问题。问题。3版权所有 计算机学院 闫健恩n为什么要使用数据区为什么要使用数据区 程序运行时各种数据必须放在内存中，程序运行时各种数据必须放在内存中，便于访问和使用。便于访问和使用。n数据区的管理数据区的管理n内存永远不能满足需要；内存永远不能满足需要；n必须找到存贮的数据；必须找到存贮的数据；n按照程序单位（过程、函数）分配和按照程序单位（过程、函数）分配和管理数据区。管理数据区。7.1 概述概述4版权所有 计算机学院 闫健恩n数据区存贮的内容数据区存贮的内容1.变量和常数（用户自己定义）变量和常数（用户自己定义）2.临时单元：源程序中没有，编译程
3、序在生临时单元：源程序中没有，编译程序在生成中间代码时建立和使用。成中间代码时建立和使用。3.形式单元：存放过程或函数间传递的参数；形式单元：存放过程或函数间传递的参数；4.返回地址：返回主调程序的入口。返回地址：返回主调程序的入口。5.保护区：保存主调程序的寄存器内容，恢保护区：保存主调程序的寄存器内容，恢复现场。复现场。6.数据访问控制信息数据访问控制信息7.1 概述概述5版权所有 计算机学院 闫健恩n主题主题n存储管理：栈分配、存储管理：栈分配、堆管理、垃圾回收堆管理、垃圾回收n对变量、数据的访问对变量、数据的访问本章核心问题本章核心问题如何访问到数据如何访问到数据7.1 概述概述6版权
4、所有 计算机学院 闫健恩1）存储分配的典型方式）存储分配的典型方式n目标程序的代码放置在目标程序的代码放置在代码代码区区n静态区、堆区、栈区分别放静态区、堆区、栈区分别放置不同类型生命期的数据值，置不同类型生命期的数据值，即即数据区数据区7版权所有 计算机学院 闫健恩2）静态和动态存储分配）静态和动态存储分配n静态分配静态分配n编译器在编译时刻就可以做出存储分配决编译器在编译时刻就可以做出存储分配决定，不需要考虑程序运行时刻的情形定，不需要考虑程序运行时刻的情形n不存在可变长的数组、可变长的字符串、不存在可变长的数组、可变长的字符串、指针；指针；n不存在函数或过程的嵌套和递归。不存在函数或过程
5、的嵌套和递归。n全局变量全局变量8版权所有 计算机学院 闫健恩n动态分配动态分配n栈式存储：和过程的调用栈式存储：和过程的调用/返回同步进行分返回同步进行分配和回收，值的生命期和过程生命期相同配和回收，值的生命期和过程生命期相同n有可变数组、有过程和函数的递归和嵌套。有可变数组、有过程和函数的递归和嵌套。n堆存储：生命期比相应过程调用的生命期更堆存储：生命期比相应过程调用的生命期更长的调用。长的调用。n有静态变量有静态变量(static)、指针、表单等。、指针、表单等。n手工进行回收手工进行回收n垃圾回收机制垃圾回收机制静态和动态存储分配静态和动态存储分配9版权所有 计算机学院 闫健恩7.2
6、静态存贮分配静态存贮分配n 分配方式分配方式 在符号表中按照对象属性顺序分配在符号表中按照对象属性顺序分配数据区，从而建立一个数据映像，运数据区，从而建立一个数据映像，运行时按照此映像分配实际的内存数据行时按照此映像分配实际的内存数据区。区。10版权所有 计算机学院 闫健恩符号表如下，符号表如下，DADA栏表示数据区编号，栏表示数据区编号，ADDRADDR栏是相对栏是相对地址地址7.2 静态存贮分配静态存贮分配11版权所有 计算机学院 闫健恩7.3 栈式分配栈式分配n内容：内容：n活动树活动树n活动记录活动记录n调用代码序列调用代码序列n栈中的变长数据栈中的变长数据12版权所有 计算机学院 闫
7、健恩7.3.1 活动树活动树n过程调用（过程活动）在时间上总是嵌套的：过程调用（过程活动）在时间上总是嵌套的：n后调用的先返回后调用的先返回n因此可以用栈式分配来处理过程活动所需要的因此可以用栈式分配来处理过程活动所需要的内存空间。内存空间。n程序运行的所有过程活动可以用树表示程序运行的所有过程活动可以用树表示n每个结点对应于一个过程活动每个结点对应于一个过程活动n根结点对应于根结点对应于main过程的活动过程的活动n过程过程p的某次活动对应的结点的子结点对应于的某次活动对应的结点的子结点对应于此次活动调用的各个过程活动（从左向右，表此次活动调用的各个过程活动（从左向右，表示调用的先后顺序）。
8、示调用的先后顺序）。13版权所有 计算机学院 闫健恩活动树的例子活动树的例子（1 1）n程序：程序：P277，图，图7-2n过程调用（返回）序过程调用（返回）序列和活动树的前序列和活动树的前序（后序）遍历对应（后序）遍历对应n假定当前活动对应结假定当前活动对应结点点N，那么所有尚未，那么所有尚未结束的结点对应于结束的结点对应于N及其祖先结点。及其祖先结点。14版权所有 计算机学院 闫健恩sq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)活动树的例子活
9、动树的例子（1 1）15版权所有 计算机学院 闫健恩7.3.2 活动记录活动记录n过程调用和返回由控制栈进行管理过程调用和返回由控制栈进行管理n每个活跃的活动对应于栈中的一个活动每个活跃的活动对应于栈中的一个活动记录记录n活动记录按照活动的开始时间，从栈底活动记录按照活动的开始时间，从栈底到栈顶排列到栈顶排列16版权所有 计算机学院 闫健恩一般的活动记录的布局一般的活动记录的布局实实 参参临临 时时 数数 据据返返 回回 值值可选的控制链可选的控制链可选的访问链可选的访问链保存的机器状态保存的机器状态局局 部部 数数 据据指向调用者的指向调用者的活动记录活动记录用来访问存于其用来访问存于其它活
10、动记录中的它活动记录中的非局部数据非局部数据17版权所有 计算机学院 闫健恩运行时刻栈的例子运行时刻栈的例子na11为全局变量为全局变量nmain没有局部变量没有局部变量nr有局部变量有局部变量Inq的局部变量的局部变量i，和参，和参数数m,n。18版权所有 计算机学院 闫健恩 运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录） sa : arrays运行时刻栈的例子运行时刻栈的例子19版权所有 计算机学院 闫健恩 运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的
11、所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录） si: integerra : arraysr运行时刻栈的例子运行时刻栈的例子20版权所有 计算机学院 闫健恩 运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录） sk: integerq (1, 9)a : arraysq(1,9)r运行时刻栈的例子运行时刻栈的例子21版权所有 计算机学院 闫健恩 运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活
12、动记录） sk: integerq (1, 9)a : arrayq (1, 3)k: integersq(1,9)rp(1,9) q(1,3)q(1,0)p(1,3)运行时刻栈的例子运行时刻栈的例子22版权所有 计算机学院 闫健恩7.3.3 调用代码序列调用代码序列n调用代码序列调用代码序列(calling sequence)为活动记为活动记录分配空间，填写记录中的信息；录分配空间，填写记录中的信息；n返回代码序列返回代码序列(return sequence)恢复及其恢复及其状态，是调用者继续运行。状态，是调用者继续运行。n调用代码序列会分割到调用者和被调用者调用代码序列会分割到调用者和被调
13、用者中。中。n根据源语言、目标机器、操作系统的限制，可根据源语言、目标机器、操作系统的限制，可以有不同的分割方案以有不同的分割方案n把代码尽可能放在被调用者中。把代码尽可能放在被调用者中。23版权所有 计算机学院 闫健恩调用调用/返回代码序列的要求返回代码序列的要求n数据方面数据方面n能够把参数正确地传递给被调用者能够把参数正确地传递给被调用者n能够把返回值传递给调用者能够把返回值传递给调用者n控制方面控制方面n能够正确转到被调用者的代码的开始位置能够正确转到被调用者的代码的开始位置n能够正确转会调用者的调用位置（的下一条指能够正确转会调用者的调用位置（的下一条指令）令）n调用代码序列和活动记
14、录的布局相关调用代码序列和活动记录的布局相关24版权所有 计算机学院 闫健恩调用代码序列的例子调用代码序列的例子nCalling sequencen调用这计算实在参数的值调用这计算实在参数的值n将返回地址和原将返回地址和原top_sp存放到被调用者的活动记录存放到被调用者的活动记录中。调用者增加中。调用者增加top_sp的值（越过了局部数据、临的值（越过了局部数据、临时变量、被调用者的参数、机器状态字段）时变量、被调用者的参数、机器状态字段）n被调用者保存寄存器值和其他状态字段被调用者保存寄存器值和其他状态字段n被调用者初始化局部数据、开始运行。被调用者初始化局部数据、开始运行。nReturn
15、 sequencen被调用者将返回值放到和参数相邻的位置被调用者将返回值放到和参数相邻的位置n恢复恢复top_sp和寄存器，跳转到返回地址。和寄存器，跳转到返回地址。25版权所有 计算机学院 闫健恩调用代码序列的例子调用代码序列的例子26版权所有 计算机学院 闫健恩7.3.4栈中的栈中的变长数据变长数据n如果数据对象如果数据对象的生命期局限的生命期局限于过程活动的于过程活动的生命期，就可生命期，就可以分配在运行以分配在运行时刻栈中。时刻栈中。ntop指向实际的指向实际的栈顶栈顶ntop_sp用于寻找用于寻找顶层记录的定顶层记录的定长字段长字段27版权所有 计算机学院 闫健恩7.4 非局部数据的
16、访问（无嵌套过程）非局部数据的访问（无嵌套过程）n没有嵌套过程时的数据访问没有嵌套过程时的数据访问nC语言中，每个函数能够访问的变量语言中，每个函数能够访问的变量n要么是这个函数的局部变量：就在当前活动记录内，要么是这个函数的局部变量：就在当前活动记录内，可以通过可以通过top_sp指针加上相对地址来访问变量指针加上相对地址来访问变量n要么是全局变量：在静态区，抵制在编译时刻可知要么是全局变量：在静态区，抵制在编译时刻可知n很容易将很容易将C语言的函数作为参数进行传递语言的函数作为参数进行传递n参数中只需要包括函数代码的开始地址。参数中只需要包括函数代码的开始地址。n在函数中访问变量的模式很简
17、单，不需要考虑过程在函数中访问变量的模式很简单，不需要考虑过程是如何激活的。是如何激活的。28版权所有 计算机学院 闫健恩nPASCAL中，如果过程中，如果过程A的声明中包含了过程的声明中包含了过程B的的声明，那么声明，那么B可以使用在可以使用在A中声明的变量。中声明的变量。n当当B的代码运行时，如果的代码运行时，如果它使用的是它使用的是A中的变量。中的变量。那么这个变量指向运行栈那么这个变量指向运行栈中最上层的同名变量。中最上层的同名变量。n但是，我们不能通过嵌套但是，我们不能通过嵌套层次直接得到层次直接得到A的活动记的活动记录的相对位置。录的相对位置。void A()intx,y;void
18、B()int b;x = b+y;voidC()B(); C();A的活动记录的活动记录C的活动记录的活动记录B的活动记录的活动记录当当A调用调用C，C又调用又调用B时时:7.4.1非局部数据的访问（无嵌套过程）非局部数据的访问（无嵌套过程）29版权所有 计算机学院 闫健恩7.4.2 嵌套深度嵌套深度n嵌套深度是正文概念，可以根据源程序静嵌套深度是正文概念，可以根据源程序静态地确定态地确定n不内嵌于任何其他过程中的过程，嵌套不内嵌于任何其他过程中的过程，嵌套深度为深度为1n嵌套在深度为嵌套在深度为i的过程中的过程，深度的过程中的过程，深度为为i+1.30版权所有 计算机学院 闫健恩深度为深度为
19、1sort深度为深度为2readArray，exchange，quicksort深度为深度为3partition31版权所有 计算机学院 闫健恩7.4.3 访问链访问链n访问链被用于访问非局部的数据访问链被用于访问非局部的数据n如果过程如果过程p在声明时嵌套在过程在声明时嵌套在过程q的声明中，的声明中，那么那么p的活动记录中的访问链指向最上层的的活动记录中的访问链指向最上层的q的活动记录。的活动记录。n从栈顶活动记录开始，访问链形成了一个从栈顶活动记录开始，访问链形成了一个链路，嵌套深度逐一递减。链路，嵌套深度逐一递减。32版权所有 计算机学院 闫健恩n设深度为设深度为np的过程的过程p访问变
20、量访问变量x，而变量，而变量x在在深度为深度为nq的过程中声明，那么的过程中声明，那么n从当前活动记录出发，沿访问链前进从当前活动记录出发，沿访问链前进np-nq次找到的活动记录中的次找到的活动记录中的x就是要找的变量位就是要找的变量位置置nx相对于活动记录的偏移量在编译时刻已知相对于活动记录的偏移量在编译时刻已知nnp-nq在编译时刻已知；在编译时刻已知；7.4.3 访问链访问链33版权所有 计算机学院 闫健恩访问链的例子访问链的例子34版权所有 计算机学院 闫健恩7.4.4 显示表显示表n用访问链访问数据时，如果嵌套深度大，则访用访问链访问数据时，如果嵌套深度大，则访问的效率差。问的效率差
21、。n显示表：使用数组显示表：使用数组d为每个嵌套深度保留一个为每个嵌套深度保留一个指针指针n指针指针di指向最高的深度为指向最高的深度为i的的活动记录。的的活动记录。n如果程序如果程序p中访问深度为中访问深度为i的过程的过程q的变量的变量x，那么，那么di直接指向相应的直接指向相应的q活动记录；活动记录；n显示表的维护显示表的维护n调用过程调用过程p时，在时，在p的活动记录中保留的活动记录中保留dnp的值，的值，并将并将dnp设置为当前活动记录。设置为当前活动记录。n从从p返回时，恢复返回时，恢复dnp的值。的值。35版权所有 计算机学院 闫健恩显示表的例子显示表的例子q(1,9)调用q(1,
22、3)时，q的深度为2q(1,3)调用p，p的深度为3q调用e，e的深度为236版权所有 计算机学院 闫健恩7.5 堆式存贮分配堆式存贮分配n含义含义 在编译时无法确定数据区的大小，在过在编译时无法确定数据区的大小，在过程的入口处也确定不了数据区的大小，程的入口处也确定不了数据区的大小，因此无法使用静态或栈式分配方法。因此无法使用静态或栈式分配方法。n条件条件 有有static类型、指针类型和表单类型、指针类型和表单(form)等等变量。变量。37版权所有 计算机学院 闫健恩存储管理器存储管理器n基本功能基本功能n分配：为每个内存请求分配一段连续的、适当大分配：为每个内存请求分配一段连续的、适当
23、大小的堆空间。首先从空闲的堆空间分配；如果不小的堆空间。首先从空闲的堆空间分配；如果不行则从操作系统中获取内存、增加堆空间。行则从操作系统中获取内存、增加堆空间。n回收：把被回收的空间返回空闲空间缓冲池，以回收：把被回收的空间返回空闲空间缓冲池，以满足其他的分配。满足其他的分配。n评价存储管理器的特性：评价存储管理器的特性：n空间效率：是程序需要的堆空间最小，即减小碎空间效率：是程序需要的堆空间最小，即减小碎片片n程序效率：充分运用内存系统的层次，提高效率程序效率：充分运用内存系统的层次，提高效率n低开销：使分配低开销：使分配/收回内存的操作尽可能高效收回内存的操作尽可能高效38版权所有 计算机学院 闫健恩n堆空间的分配及管理堆空间的分配及管理n固定长分块法：将堆空间分成大小相同的块，使用链固定长分块法：将堆空间分成大小相同的块，使用链表连接各个单元；适用于类型单一或长度一致的数据表连接各个单元；适用于类型单一或长度一致的数据类型。类型。n可变长分块法：将堆空间分成长度不同的块。可变长分块法：将堆空间分成长度不同的块。n 外部碎片和内部碎片问题外部碎片和内部碎片问题n堆空间使用应注意的问题堆空间使用应注意的问题n不可以随便释放不可以随便释放n释放的方法：参照计数法和无用单元敛集。释放的方法：参照计数法和无用单元敛集。39
