南京大学：《编译原理》课程教学资源（PPT课件讲稿）第七章 运行时刻环境

第七章运行肘刻环境 赵建华 南京大学计算机系

第七章 运行时刻环境 赵建华 南京大学计算机系

运行附刻环境 运行时刻环境 为数捃分配安排存储位置 确定访问变量时使用的杋制 过程之间的连接 参数传递 和操作系统、输入输出设备相关的其它接口 主题 存储管理:栈分配、堆管理、垃圾回收 对变量、数据的访问

运行时刻环境 • 运行时刻环境 – 为数据分配安排存储位置 – 确定访问变量时使用的机制 – 过程之间的连接 – 参数传递 – 和操作系统、输入输出设备相关的其它接口 • 主题 – 存储管理：栈分配、堆管理、垃圾回收 – 对变量、数据的访问

存储分配的典型方式 目标程序的代码放置在代 代码区 码区 静态区 静态区、堆区、栈区分别 放置不同类型生命期的数 堆区 据值 空闲内存 栈区

存储分配的典型方式 • 目标程序的代码放置在代 码区 • 静态区、堆区、栈区分别 放置不同类型生命期的数 据值

静态和动态存储分配 ·静态分配 编译器在编译时刻就可以做出存储分配决定.不需 要考虑程序远行时刻的情形 全局变量 动恋分配 栈式存储:和过程的调用/返回同步进行分配和回收, 值的生命期和过程生命期相同 堆存储:数据对象比创建它的过程调用更长寿。 ·手工进行回收 垃圾回收机制

静态和动态存储分配 • 静态分配 – 编译器在编译时刻就可以做出存储分配决定，不需 要考虑程序运行时刻的情形 – 全局变量 • 动态分配 – 栈式存储：和过程的调用/返回同步进行分配和回收， 值的生命期和过程生命期相同 – 堆存储：数据对象比创建它的过程调用更长寿。 • 手工进行回收 • 垃圾回收机制

栈式分配 内容 活动树 活动记录 调用代码序列 栈中的变长数据

栈式分配 • 内容： – 活动树 – 活动记录 – 调用代码序列 – 栈中的变长数据

活动树 过程调用(过程活动)在时间上总是嵌套的: 后调用的先返回 因此用栈式分配來分配过程活动所需內存空间。 程序远行的所有过程活动可以用树表示 每个结点对应于一个过程活动 根结点对应于main过程的活动 过程p的某次活动对应的结点的所有子结点:此次 活动所调用的各个过程活动(从左向右,表示调用 的先后顺序)

活动树 • 过程调用（过程活动）在时间上总是嵌套的： – 后调用的先返回 – 因此用栈式分配来分配过程活动所需内存空间。 • 程序运行的所有过程活动可以用树表示 – 每个结点对应于一个过程活动 – 根结点对应于main过程的活动 – 过程p的某次活动对应的结点的所有子结点：此次 活动所调用的各个过程活动（从左向右，表示调用 的先后顺序）

活动树的例子(1) 程序:P277,图7-2 过程调用(返回)序列和活动 enter main( 树的前序(后序)遍历对应 enter readArrayo) leave readArrayo 假定当前活动对应结点N.那 enter quicksort(1, 9) enter partition(1, 9) 么所有尚未结束的活动对应于 leave partition(1, 9) N及其祖先结点。 enter quicksort(1, 3) leave quicksort(1, 3) enter quicksort(5, 9) p(1,9) q(1,3 (5,9) p(1,3)q(1,0)q(2,3) leave quicksort(5, 9) (5,9)q(5,5)q(7,9 leave quicksort(1, 9) p(2,3)q(2,1)q(3,3) p(7, 9)q(7. 7)q(9, leave main() 图7-2中程序的可能的活动序列

活动树的例子（1） • 程序：P277，图7-2 • 过程调用（返回）序列和活动 树的前序（后序）遍历对应 • 假定当前活动对应结点N，那 么所有尚未结束的活动对应于 N及其祖先结点

话动记录 过程调用和返回由 实在参数 控制栈进行管理 返回值 每个活跃的活动对 应于栈中的一个活 控制链 动记录 访问链 活动记录按照活动 保存的机器状态 的开始时间,从栈 局部数据 底到栈顶排列 临时变量

活动记录 • 过程调用和返回由 控制栈进行管理 • 每个活跃的活动对 应于栈中的一个活 动记录 • 活动记录按照活动 的开始时间，从栈 底到栈顶排列

运行射刻栈的例子 er o[lll integer a[1]为全局变 main m07 nain nain 7-----,- integer mai没有局部 a)Y被弹出栈 b)y被激活 变量 integer a[lll integer a 11]1 nain nain nain nain r有局部变量1 integer m, n integer m, n (1,9) q(1,9 q(1,9 的局部变量1 integer t integer i p(1,9)q(1,3) Integer m,n 和参数mn。 p(1,3)q(1,0) g(1,3) integer 2 c)y被弹出栈,q(1,9)被压栈 d)控制返回到q(1,3)

运行时刻栈的例子 • a[11]为全局变 量 • main没有局部 变量 • r有局部变量i • q的局部变量i， 和参数m,n

调用代码序列 调用代码序列 calling sequence)为活动记录 分配空间,填写记录中的信息; 返回代码序列( return sequence)恢复机器状 态。使调用者继续运行 调用代码序列会分割到调用者和被调用者 中 根据源语言、目标机器、操作系统的限制, 以有不同的分割方案 把代码尽可能放在被调用者中

调用代码序列 • 调用代码序列(calling sequence)为活动记录 分配空间，填写记录中的信息； • 返回代码序列(return sequence)恢复机器状 态，使调用者继续运行。 • 调用代码序列会分割到调用者和被调用者 中。 – 根据源语言、目标机器、操作系统的限制，可 以有不同的分割方案 – 把代码尽可能放在被调用者中