编译原理cmpl_08.ppt

1 第八章运行时的存储组织与管理 概述 8 1数据空间的三种不同使用方法和管理方法 8 2栈式存储分配 8 3参数传递 本章小节 2 学习目标 全面了解目标程序运行时存储区的整体布局 每种存储区的组织方式和管理方法 并通过实例着重掌握 对允许过程嵌套定义的情况 栈式动态存储分配的组织方式和运行时进栈退栈的活动实现方法 3 学习指南 在代码生成前 编译程序必须进行目标程序运行环境的配置和数据空间的分配 一般来讲 假如编译程序从操作系统中得到一块存储区以使目标程序在其上运行 该存储区需容纳生成的目标代码和目标代码运行时的数据空间 我们这里所说的运行时的存储区组织 是指目标程序运行时的数据空间的管理和组织 4 目标程序运行时 存储区域的整体布局 以及各区域的作用 各种不同类型的数据表示 允许过程嵌套定义的情况 栈式动态分配的组织管理 对过程的调用 进入和退出时 栈式动态分配的工作原理 过程活动纪录的各项内容和它们的作用 以及活动纪录的组织方式 过程参数传递的不同方式 难重点 6 概述 静态程序和运行时的活动联系起来 在代码生成前 需要把程序静态的正文和实现这个程序的运行时的活动联系起来 弄清楚将来再代码运行时刻 源代码中的各种变量 常量等用户定义的量是如何存放的 如何去访问它们 标识符和存储单元的联系 在程序的执行过程中 程序中数据的存取是通过与之对应的存储单元来进行的 在程序语言中 程序使用的存储单元都由标识符来表示 它们对应的内存地址都是由编译程序在编译时或由其生产目标代码程序运行时进行分配的 7 运行时存储区的划分 从逻辑上看 在代码生成前 编译程序必须进行目标程序运行环境的配置和数据空间的分配 假定编译程序从操作系统中得到一块存储区 用于目标程序的运行 该存储区需容纳生成的目标代码和目标代码运行时的数据空间 数据空间应包括 用户定义的各种类型的数据对象 变量和常数 所需的存储空间 作为保留中间结果和传递参数的临时工作单元 调用过程时所需的连接单元 以及组织输入 输出所需的缓冲区 8 运行时的存储区常常划分成 目标代码区 静态数据区 栈区和堆区 代码 code 区用以存放目标代码 这是固定长度的 即编译时能确定的 静态数据区 staticdata 用以存放编译时能确定所占用空间的数据 堆栈区 stackandheap 用于可变数据以及管理过程活动的控制信息 目标程序运行时存储区的典型划分 9 栈 Pascal和C这样的语言的实现使用拓广的控制栈来管理过程的活动 当调用出现时 一个活动的执行被中断 有关机器状态的信息 程序计数器 机器寄存器的值 就保存在这个栈中 当控制从调用中返回时 在恢复了有关寄存器的值和把程序计数器置到紧接该调用的下一个点后 该活动能够继续 10 堆 在运行存储空间中有一个单独的区域叫做堆 heap 留给存放动态数据 Pascal和c语言都允许数据对象在程序运行时分配空间以便建立动态数据结构 这样的数据存储空间可以分配在堆区 11 活动记录 为了管理过程的一次执行中所需要的信息 使用一个连续的存储块 引入一个术语 过程的活动记录AR ActivationRecord 如Pascal和C语言 当过程调用时 产生一个过程的新的活动 用一个活动记录表示该活动的相关信息 并将其压入栈 当过程返回时 活动结束 把这个活动记录从栈中弹出 临时工作单元 比如计算表达式过程中需存放中间结果用的临时值单元 局部变量 一个过程的局部变量 机器状态信息 保存该过程执行前关于机器状态的信息 诸如程序计数器 寄存器的值 这些值都需要在控制从该过程返回时给予恢复 存取链 访问链 用以存取非局部变量 这些变量存放于其它过程的活动记录中 并不是所有语言需要该信息 控制链 指向调用该过程的那个过程的活动记录 这也不是所有语言都需要的 实参 也称形式单元 由调用过程向该被调过程提供实参的值 或地址 当然在实际编译程序中 也常常使用寄存器传递实参 返回地址 保存该被调过程返回后的地址 13 几乎所有的这些域的大小在编译时是已知的 如果局部变量中包含有可变数组 那么则采用内情向量 将内情向量置于过程活动记录中 另外 有些语言的编译程序还将参数个数存放于活动记录中 以便进行参数个数的检查 注意 并不是所有语言的编译程序全部使用这些信息 局部数据区中的一个栈单元 活动记录 15 数据空间的三种不同使用方法和管理方法 静态存储分配对所有数据对象分配固定的存储单元 且在运行时始终保持不变 栈式存储分配在运行把存储器作为一个栈进行管理 运行时 每当调用一个过程 它所需要的存储空间就动态地分配在栈顶 一旦退出 它所占空间就予以释放 堆式存储分配在运行时把存储器组织成堆结构 以便用户关于存储空间地申请与释放 采用哪种分配策略是由源语言的语义决定的 16 8 2静态存储分配 如果在编译时能确定目标程序运行中所需的全部数据空间的大小 编译时安排好目标程序运行时的全部数据空间 确定每个数据对象的存储位置 称这种分配策略为静态存储分配 运行时不改变绑定 每次过程活动时 一个名字都绑定到同样的存储单元 这种性质允许局部名字的值在过程停止活动后仍然保持 即当控制再次进入过程时 局部名字的值同上一次控制离开时一样 17 程序是段结构的 即由主程序段和若干子程序段组成 程序 主程序段 若干子程序段各程序段中定义的名字一般是彼此独立的 除公共块和等价语句说明的名字以外 也即各段的数据对象名的作用域在各段中 同一个名字在不同的程序段表示不同的存储单元 不会在不同段间互相引用 赋值 每个数据名所需的存储空间大小都是常量 即不许含可变体积的数据 如可变数组 且所有数据名的性质是完全确定的 像FORTRAN这样的语言 18 这样 整个程序所需数据空间的总量在编译时完全确定 从而每个数据名的地址就可静态进行分配 换句话说 一旦存储空间的某个位置分配给了某个数据名 关联起来 之后 在目标程序的整个运行过程中 此位置 地址 就属于该数据名了 存储管理的静态性也使得FORTRAN程序中的各程序段均可独立地进行编译 19 例 一个FORTRAN77的例子 1 PROGRAMCNSUME 2 CHARACTER 50BUF 程序体所拥有的静态量BUF 3 INTEGERNEXT 程序体所拥有的静态量NEXT 4 CHARACTERC PRDUCE 程序体所拥有的静态量C 5 DATANEXT 1 BUF 6 6C PRDUCE 7 BUF NEXT NEXT C 8 NEXT NEXT 1 9 IF C EN GOTO6 10 WRITE A BUF 11 END 12 CHARACTERFUNCTIONPRDUCE 13 CHARACTER 80BUFFER 14 INTEGERNEXT 15 SAVEBUFFER NEXT PRDUCE函数体所拥有的静态量BUFFER NEXT 16 DATANEXT 81 17 IF NEXT GT 80 THEN 18 READ A BUFFER 19 NEXT 1 20 ENDIF 21 PRDUCE BUFFER NEXT NEXT 22 NEXT NEXT 1 23 END 20 consume的活动记录 produce的活动记录 21 名字在程序被编译时绑定到存储单元 不需要运行时的任何支持 绑定的生存期是程序的整个运行时间 控制再次进入该过程时 局部变量的值和控制上一次离开时的一样 每个活动记录的大小是固定的 过程调用时保存信息的地址在编译时也是已知的 特点 22 适于静态存储分配的语言必须满足以下条件 数组的上下界必须是常数 过程调用不允许递归 编译时刻无法预先确定哪些递归函数在运行时被激活 更难以确定它们的递归深度 不允许采用动态的数据结构 即在程序运行过程中申请和释放的数据结构 23 静态存储分配无法克服的问题 动态数组问题递归调用问题 栈式存储分配被调用者的生存期超过调用者 局部数据需要保留 save 堆式存储分配 24 满足这些条件的语言除了FORTRAN之外 还有BASIC等语言 在这些语言中 编译程序可以完全确定程序中数据项所在的地址 通常为相对于各数据区起始地址的位移量 由于过程调用不允许递归 因此数据项的存储地址就与过程相联系 过程调用所使用的局部数据区可以直接安排在过程的目标代码之后 并把各数据项的存储地址填入相关的目标代码中 以便在过程运行时访问这个局部数据区 在此 不存在对存储区的再利用问题 目标程序执行时不必进行运行时的存储空间管理 过程的进入和退出变得极为简单 25 C语言程序的外部变量和程序中出现的常量都可以静态分配 声明在函数外面外部变量静态外部变量声明在函数里面静态局部变量 26 8 3栈式存储分配 这种分配策略是将整个程序的数据空间设计为一个栈 在具有递归结构的语言程序中 每当调用一个过程时 它所需的数据空间就分配在栈顶 每当过程工作结束时就释放这部分空间 栈式动态存储分配策略适用于PASCAL C ALGOL之类具有递归结构的语言的实现 27 过程所需的数据空间包括两部分 一部分是生存期在本过程这次活动中的数据对象 如局部变量 参数单元 临时变量等等 另一部分则是用以管理过程活动的记录信息 即当一次过程调用出现时 调用该过程的那个过程的活动即被中断 当前机器的状态信息 诸如程序计数器 返回地址 寄存器的值等等 也都必须保留在栈中 当控制从调用返回时 便根据栈中记录的信息恢复机器状态 使该过程的活动继续进行 28 8 3栈式存储分配 8 2 1简单的栈式存储分配的实现 8 2 2嵌套过程语言的栈式实现 8 2 3分程序结构的存储管理 使用栈式存储分配策略意味着 运行时每当进入一个过程 就在栈顶为该过程的临时工作单元 局部变量 机器状态及返回地址等信息分配所需的数据空间 当一个过程工作完毕返回时 它在栈顶的数据空间也即释放 本节我们将以三种语言结构为例 详细讨论栈式存储分配的实现 29 8 3 1简单的栈式存储分配的实现 首先从一种最简单的程序设计语言结构讲起 没有分程序结构 过程定义不嵌套 但允许过程递归调用 全局变量或数组的说明 main 主函数 主程序执行语句 R 函数R Q 函数Q 30 这种情况下 采用栈式动态分配策略 即 运行时 每当进入一个过程 则为该过程分配一段存储区 当一个过程工作完毕返回时 它所占用的存储区可释放 程序运行时的存储空间 栈 中在某一时刻可能会包含某个过程的几个活动记录 某个过程递归调用的情况 另外 同样的一个存储位置 在不同运行时刻可能分配给不同的数据对象 若主函数调用了函数Q Q又调用了R 在R进入运行后的存储结构如图 a 所示 若主函数调用了函数Q Q递归调用自己 在Q第二次进入运行后的存储结构如图 b 所示 若主程序先调用Q 然后主函数接着调用R 且Q不调用Q和R 这时Q和R进入运行后的存储结构 先后分别如图 c 和 d 所示 32 框架指针 指向当前活动的指针通常称为框架指针 framepointer 或fp 且通常保存在寄存器中 栈指针 还有一个栈指针 stackpointer 或sp 它通常指向调用栈上的最后位置 它有时称作栈顶指针 topofstack 或tos 在每个新活动记录中 控制链指向先前活动记录的控制链 fp指向当前活动记录的控制链 下一个调用中当前的fp就会办成下一个活动记录的控制链 33 例 利用Euclid算法的简单递归实现 计算两个非负整数的最大公约数 includeintx y intgcd intu intv if v 0 returnu returngcd v u v main x 15 y 10 printf d n gcd x y return0 栈的生长方向 控制链 控制链 控制链 sp fp 例 intx 2 voidg int prototype voidf intn staticintx 1 g n x voidg intm inty m 1 if y 0 f y x g y main g x return0 控制链 控制链 控制链 sp fp 栈的生长方向 在第2次对g调用时 程序的运行环境 控制链 控制链 sp fp 栈的生长方向 在第3次对g调用时 程序的运行环境 38 8 3 2嵌套过程语言的栈式实现 PASCAL语言程序结构的特点是允许过程嵌套定义 一个过程可以引用包围它的任一外层过程所定义的标识 如变量 数组或过程等 若不考虑它的 文件 和 指针 类型 采用PASCAL的一个子集 它的存储分配也是采用栈式动态分配策略 只是它的过程活动记录中应增设一些内容 用以解决对非局部变量的引用问题 39 语言的作用域规则确定了如何处理非局部名字的访问 词法作用域规则 静态作用域规则 它仅仅根据程序正文即可确定用于名字的声明 如 Pascal C Ada动态作用域规则它在运行时根据当前的活动来决定用于名字的声明 如 Lisp APL和Snobol 1 programsort input output sort的过程头 2 vara array 0 10 ofinteger 3 x integer 4 procedurereadarray sort内嵌套定义的readarray的过程头 5 vari integer 6 begin a end readarray readarray的过程体 7 procedureexchange i j integer sort内嵌套定义的exchange的过程头 8 begin 9 x a i a i a j a j x exchange的过程体 10 end exchange 11 procedurequicksort m n integer sort内嵌套定义的quicksort的过程头 12 vark v integer 13 functionpartition y z integer integer quicksort内嵌套定义的partition的函数头 14 vari j integer 15 begin a partition的函数体 16 v 17 exchange i j 18 end partition 19 begin end quicksort quicksort的过程体 20 begin end sort sort的例程体 具有嵌套过程的PASCAL程序 41 PASCAL程序中过程定义的嵌套情况如下 sort1readarray2exchange2quicksort2partition3 这里将整个程序sort看成最外层的过程 过程readarray exchange和partition中引用的a均不是它们的局部变量 而是过程sort的局部变量 42 假如过程sort激活 调用 了过程quicksort 这时存储栈中的情形示意如图 其中在quicksort过程活动记录中有一 或一些 存储单元 用斜线描绘 用以记录过程quicksort可以引用sort中定义的变量a和x 也就是说 为了解决对非局部量的存取问题 必须设法跟踪每个外层过程的最新活动记录的位置 43 非局部名字访问的实现 跟踪办法 实现对非局部量的存取的方法 跟踪每个外层过程的最新活动记录AR的位置 跟踪办法 用静态链 如PL 0的SL 用DISPLAY表 44 一种是在过程活动记录中增设存取链 在过程活动记录中增设存取链 访问链 指向包含该过程的直接外层过程的最新一次活动的活动记录的访问链 在运行时栈上的数据区 活动记录 之间又拉出一条链 sp fp 45 例 如果该程序的某次执行顺序为 sort quicksort quicksort partition exchange 即主程序 最外层过程 sort开始执行 继而进入过程quicksort 而又一次进入过程quicksort 接着进入过程partition 进入过程exchange s q 1 9 s q 1 9 q 1 3 s q 1 9 q 1 3 p 1 3 s q 1 9 q 1 3 p 1 3 e 进入过程exchange之后运行栈的示意 过程exchange由过程 函数 partition调用 但exchange的直接外层过程是sort 所以过程exchange的活动记录的存取链指向sort的活动记录 另外 过程partition中引用了第 2 行说明的变量a 而partition的直接外层是quicksort quicksort的直接外层过程是sort partition对非局部量a的引用通过两次拉链实现 49 如何访问a的存储单元 从栈顶的活动记录开始 追踪访问链np na次 到达a的声明所在过程的活动记录 访问链的追踪用间接操作就可完成 假定过程p的嵌套深度为np 它引用嵌套深度为na的变量a na np 如何访问a的存储单元 过程p对变量a访问时 a的地址由下面的二元组表示 np na a在活动记录中的偏移 50 另外一种 嵌套层次显示表 DISPLAY 另外一种存取非局部变量的办法 也是常用的有效办法 即每进入一个过程后 在建立它的活动记录的同时建立一张嵌套层次显示表display 51 嵌套层次 这里所提到的 嵌套层次 是指过程定义的层数 始终假定主程序的层数为0 因此主程序称为0层过程 如某过程p是在层次为i的过程q内定义的 并且q是包围p的直接外层 那么p的过程层数为i 1 一般编译程序处理过程说明时 将把过程层数作为重要的属性登记在符号表中 计数过程的层数很容易实现 用一个计数器Level 初值为0 每遇到过程说明则增1 过程说明结束则减1 52 display是一个指针数组 display是一个指针数组d 也可看做是一个小栈 自顶向下每个单元依次存放着现行层 直接外层 直至最外层 0层 主程序层 等每一层过程的最新活动记录的地址 也即 嵌套层次i的过程的局部变量a是在由display元素d i 所指的那个活动记录中存放的 也就是说 嵌套层次i 1过程中的非局部变量可能在i i 1 0层 对它的存取是通过display元素d i d i 1 d 0 而获得的 53 假定现在进入的过程的层数为i 则它的display表含有i 1个元素 依次指向现行层 直接外层 直至最外层 0层 等每一层过程的最新活动记录的地址 假定有如下四种调用情况 a sort quicksort b sort quicksort quicksort c sort quicksort quicksort partition d sort quicksort quicksort partition exchange 当一个新的活动开始时 display表被改变 原有的值在新的活动记录中被保存 当控制权从新的活动中返回时 display表的状态必须被恢复 56 词法作用域语言的作用域规则允许display通过以下步骤维护 当一个嵌套深度为i的过程的新的活动开始时 在新的活动记录中保存d i 的当前值 同时使d i 指向新的活动记录 在活动结束前 d i 被恢复为已保存的值 57 维护步骤的验证 假设一个嵌套深度为j的过程调用一个嵌套深度为i的过程 根据源代码中被调用过程是否嵌套在调用过程中 j i情况 i j 1并且被调用过程嵌套在调用过程中 display表的前j个元素不需要进行改变 将d i 设为指向新的活动记录 j i情况 嵌套深度为1 2 i 1的调用和被调用的外围过程必须相同 在新的活动记录中保存d i 的旧值 然后将d i 指向新的活动记录 display表将被正确地维护 因为它的前i 1个元素 没有改变 P2的直接外层过程是P0 不是P1的直接外层 P0就是P1自身 是P2的直接外层 P0既是P1又是P2的直接外层 P2的直接外层过程是P0 59 Display本身的体积在编译时可确定 至于display本身作为单独的表分配存储 还是作为活动记录的一部分 比如置于实参 形式单元 的上端 则取决于编译程序的设计者 假定将display作为活动记录的一部分 由于每个过程的形式单元数目在编译时是知道的 那么display的相对地址d 相对于活动记录起点 在编译时也是完全确定的 因此 若现行过程中引用了某一外层过程的变量 则很容易生成相应的存取指令 60 8 1 3堆式存储分配 如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制 如 中的new delete PASCAL的new 等机制 或者不仅有过程而且有进程的程序结构的情况下 空间的使用未必服从 先申请后释放 后申请先释放 的原则 那么只有栈式的动态分配方案就不适用了 通常使用一种称为堆式的动态存储分配方案 局部名的值在活动结束时必须被保存 被调用者的活动生存期超过调用者 用活动树不能够正确描绘这种语言的过程之间的控制流 61 堆式存储分配示意 由于借 还的时间先后不一 因而经过一段时间的运行后 这个大空间就必然被分割成的许多小块 这些块有些正在使用 有些则是空闲的 未被使用 假定程序运行时有一个大的存储空间 需要时就从这个空间中借用一块 不用时再退还给它 62 对于堆式存储分配 需要解决两个问题 一个问题是堆空间的分配 即当运行程序需要一块空间时应分配哪一块给它 一个问题是分配空间的回收 由于返回堆的不用空间是按任意次序进行的 所以需要研究专门的回收分配策略 在许多语言中都有显式的堆空间分配和回收语句或函数 如 PASCAL语言中的new和disposeC语言中的alloc和free以及C 语言中的new和delete 63 堆式存储管理的方法 当运行程序要求一块体积为N的存储空间时应如何分配 从理论上讲 这时应从比N稍大一些的空闲块中取出N个单元予以分配 这种做法的目的是保持较大的空闲块以备将来之需 但这种方法实现起来难度较大 实际中采用的办法是 扫描空闲块链并在首次遇到的比N大的空闲块中取出N个单元进行分配 64 如果找不到一块比N大的空闲块 但所有空闲块的总和却比N大 这时就需要用某种方法使这些空闲块拼接在一起 形成一个可分配的连续空间 如果所有空闲块的总和都不及N大 则需要采用更复杂的办法 如废品回收技术 即寻找那些运行程序已不使用但仍未释放的存储块或运行程序目前很少使用的存储块 把这些存储块回收后再重新分配 65 使用可利用空间表进行动态存储