活动树 过程调用(过程活动)在时间上总是嵌套的: 后调用的先返回 因此用栈式分配來分配过程活动所需內存空间。 程序远行的所有过程活动可以用树表示 每个结点对应于一个过程活动 根结点对应于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)恢复机器状 态，使调用者继续运行。 • 调用代码序列会分割到调用者和被调用者 中。 – 根据源语言、目标机器、操作系统的限制，可 以有不同的分割方案 – 把代码尽可能放在被调用者中