编译原理cmpl.pptVIP

第二章 高级语言及其语法描述 第二章 高级语言及其语法描述 第八章 运行时的存储组织与管理 【学习目标】 【学习指南】 概述 ★ 运行时存储区的划分 运行时的存储区常常划分成：目标代码区、静态数据区、栈区和堆区 栈 堆 ★活动记录 数据空间的三种不同使用方法和管理方法 §8.2 静态存储分配 【例】一个FORTRAN 77的例子 适于静态存储分配的语言必须满足以下条件 静态存储分配无法克服的问题 C 语言程序的外部变量和程序中出现的常量都可以静态分配。 §8.3栈式存储分配 过程所需的数据空间包括两部分： §8.3栈式存储分配 §8.3.1 简单的栈式存储分配的实现 【例】利用Euclid算法的简单递归实现，计算两个非负整数的最大公约数。 【例】 §8.3.2 嵌套过程语言的栈式实现 语言的作用域规则确定了如何处理非局部名字的访问 PASCAL程序中过程定义的嵌套情况如下： ★ 非局部名字访问的实现(跟踪办法) ★一种是在过程活动记录中增设存取链 【例】 如何访问 a 的存储单元？ ★另外一种：嵌套层次显示表(DISPLAY) 嵌套层次 display 是一个指针数组 词法作用域语言的作用域规则允许display 通过以下步骤维护 维护步骤的验证 §8.1.3 堆式存储分配 堆式存储分配示意 对于堆式存储分配，需要解决两个问题 堆式存储管理的方法 使用可利用空间表进行动态存储分配的方法又可分为如下两种： 1、定长块管理 2、变长块管理 若可利用空间表存在多个大于所要求空间的空闲块，可采取以下三种方法之一进行存储分配： 内存状态和可利用空间表 本章小节 由于借、还的时间先后不一，因而经过一段时间的运行后，这个大空间就必然被分割成的许多小块，这些块有些正在使用，有些则是空闲的(未被使用)。 假定程序运行时有一个大的存储空间，需要时就从这个空间中借用一块，不用时再退还给它。 一个问题是堆空间的分配，即当运行程序需要一块空间时应分配哪一块给它； 一个问题是分配空间的回收，由于返回堆的不用空间是按任意次序进行的，所以需要研究专门的回收分配策略。 在许多语言中都有显式的堆空间分配和回收语句或函数，如： PASCAL 语言中的 new 和 dispose C 语言中的 alloc 和 free 以及 C++语言中的 new 和 delete 当运行程序要求一块体积为 N 的存储空间时应如何分配？从理论上讲，这时应从比 N 稍大一些的空闲块中取出 N 个单元予以分配，这种做法的目的是保持较大的空闲块以备将来之需。 但这种方法实现起来难度较大，实际中采用的办法是： 扫描空闲块链并在首次遇到的比 N 大的空闲块中取出 N 个单元进行分配。 如果找不到一块比 N 大的空闲块，但所有空闲块的总和却比 N 大，这时就需要用某种方法使这些空闲块拼接在一起，形成一个可分配的连续空间。 如果所有空闲块的总和都不及 N 大，则需要采用更复杂的办法，如废品回收技术(即寻找那些运行程序已不使用但仍未释放的存储块或运行程序目前很少使用的存储块)，把这些存储块回收后再重新分配。 定长块的管理。划分成大小相同的若干块。 变长块的管理。根据实际需要来分配长度不同的空闲块。 首先从一种最简单的程序设计语言结构讲起：没有分程序结构，过程定义不嵌套，但允许过程递归调用。 全局变量或数组的说明；main() //主函数{ 主程序执行语句} R() //函数 R{ …}Q() //函数 Q{ …} 这种情况下，采用栈式动态分配策略， 即，运行时，每当进入一个过程，则为该过程分配一段存储区，当一个过程工作完毕返回时，它所占用的存储区可释放。 程序运行时的存储空间(栈)中在某一时刻可能会包含某个过程的几个活动记录（某个过程递归调用的情况）； 另外，同样的一个存储位置，在不同运行时刻可能分配给不同的数据对象。 若主函数调用了函数 Q，Q 又调用了 R，在 R 进入运行后的存储结构如图（a）所示。 若主函数调用了函数 Q，Q 递归调用自己，在 Q 第二次进入运行后的存储结构如图（b）所示。 若主程序先调用 Q，然后主函数接着调用 R，且 Q 不调用 Q 和 R，这时 Q 和 R 进入运行后的存储结构，先后分别如图（c）和（d）所示。 框架指针： 指向当前活动的指针通常称为框架指针(frame pointer)或 fp，且通常保存在寄存器中。 栈指针： 还有一个栈指针(stack pointer)或 sp，它通常指向调用栈上的最后位置，它有时称作栈顶指针(top of stack) 或 tos。 在每个新活动记录中，控制链指向先前活动记录的控制链。 fp 指向当前活动记录的控制链，下一个调用中当前的 fp