7编译原理之运行时刻环境.pptx

第七章 运行时刻环境湖南大学计算机与通信学院（软件学院）编译器的一些问题变量的存储位置如何分配？名字的作用域如何实现？过程调用如何实现？参数传递如何实现？……这些问题需要依靠运行时环境来辅助解决。运行时刻环境运行时刻环境为数据分配安排存储位置确定访问变量时使用的机制过程之间的连接参数传递和操作系统、输入输出设备相关的其它接口主题存储管理：栈分配、堆管理、垃圾回收对变量、数据的访问存储分配的典型方式0X00H目标程序的代码放置在代码区，通常位于存储的低端静态区、堆区、栈区分别放置不同类型生命期的数据值,实践中栈向较低地址方向增长堆向较高方向增长。编译的结果全局/静态变量……共享*从现在开始要注意，为使我们能在所有的例子中方便地使用正的偏移量,栈向较高地址方向增长，即顶是在最下端。...图7-10XFFFFH静态和动态存储分配静态分配编译器在编译时刻就可以做出存储分配决定，不需要考虑程序运行时刻的情形，如：静态变量（ｃ语言中static变量）全局变量动态分配栈式存储：过程的局部名字采用栈式存储和过程的调用/返回同步进行分配和回收，值的生命期和过程生命期相同堆heap存储：有些数据生命期比相应过程调用的生命期更长，常分配在一个可重用存储的“堆”中。堆和垃圾回收堆是虚拟内存的一个区域，它允许对象或其他数据元素在被创建时获得存储空间，并在数据变得无效时释放该存储空间垃圾回收：检测出堆中无用的数据元素，释放它们的空间手工进行回收（程序员）垃圾回收机制，如：Ｊａｖａ栈式分配内容：活动树活动记录调用(代码)序列栈中的变长数据活动树过程调用（过程活动）在时间上总是嵌套的：后调用的先返回(LIFO)因此可以用栈式分配来处理过程活动所需要的内存空间。程序运行的所有过程活动可以用树表示每个结点对应于一个过程活动根结点对应于main过程的活动过程p的某次活动对应的结点的子结点对应于此次活动调用的各个过程活动（从左向右，表示调用的先后顺序）活动树的例子－快速排序（1）活动树的例子－快速排序（２）程序：P260，图7-2过程调用（返回）序列和活动树的前序（后序）遍历对应假定当前活动对应结点N，那么所有尚未结束的结点对应于N及其祖先结点。活动记录过程调用和返回由控制栈进行管理过程活动记录：当调用过程或函数时，为其局部数据动态分配的存储区活动记录按照活动的开始时间，从栈底到栈顶排列局部变量计算中间结果图７－５活动记录框架活动记录控制链：指向调用者的活动记录（固定长度部分）访问链：活动记录中指向上一级活动记录(包含嵌套的环境定义的活动记录)的指针保存的机器状态：此次调用前的机器状态信息，如：返回地址及一些寄存器的值运行时刻栈的例子例：快速排序a[11]为全局变量main没有局部变量r有局部变量iq的局部变量i，和参数m,n。Main的活动记录调用序列调用序列(calling sequence)为活动记录分配空间，填写记录中的信息；返回序列(return sequence)恢复机器状态，使调用者继续运行。调用序列会分割到调用者和被调用者中。根据源语言、目标机器、操作系统的限制，可以有不同的分割方案把代码尽可能放在被调用者中。调用/返回序列的要求数据方面能够把参数正确地传递给被调用者能够把返回值传递给调用者控制方面能够正确转到被调用者的代码的开始位置能够正确转回调用者的调用位置（的下一条指令）调用序列和活动记录的布局相关活动记录的布局原则调用者和被调用者之间传递的值放在被调用者记录的开始位置固定长度的项放在中间位置控制链、访问链、机器状态字段早期不知道大小的项在活动记录尾部（干脆将固定长度的局部变量也放入该段）栈顶指针通常指向固定长度字段的末端top_sp调用代码序列的例子Calling sequence（调用序列）调用者计算实在参数的值将返回地址和原top_sp（控制链）存放到被调用者的活动记录中。调用者增加top_sp的值（越过了调用者的局部数据、临时变量、被调用者的参数、机器状态字段）被调用者保存寄存器值和其他状态字段被调用者初始化局部数据、开始运行。Return sequence （返回序列）被调用者将返回值放到和参数相邻的位置恢复top_sp和寄存器，跳转到返回地址。栈中的变长数据如果数据对象的生命期局限于过程活动的生命期，就可以分配在运行时刻栈中。top指向实际的栈顶top_sp用于寻找顶层记录的定长字段（框架指针）gcd(15,10)gcd(10,5)gcd(5,0)例 利用Euclid算法的简单递归算法，计算两个非负整数的最大公约数。程序清单 C代码???#include stdio.hint x, y;int gcd(int u, int v){ if (v==0) return u; else return gcd(v, u%v);}main(