活动树 过程调用（过程活动）在时间上总是嵌套的 后调用的先返回 因此用栈来分配过程活动所需内存空间 ·程序运行的所有过程活动可以用树表示 每个结点对应于一个过程活动 根结点对应于main过程的活动 过程p的某次活动对应的结点的所有子结点 表示此次活动所调用的各个过程活动 从左向右，表示调用的先后顺序 6
活动树 • 过程调用 (过程活动) 在时间上总是嵌套的 – 后调用的先返回 – 因此用栈来分配过程活动所需内存空间 • 程序运行的所有过程活动可以用树表示 – 每个结点对应于一个过程活动 – 根结点对应于main过程的活动 – 过程p的某次活动对应的结点的所有子结点 • 表示此次活动所调用的各个过程活动 • 从左向右，表示调用的先后顺序 6 南大编译许畅
活动树的例子 enter main() 快速排序程序 enter readArray() 过程调用（返回）序列和活动 leave readArray() enter quicksort(1,9) 树的前序（后序）遍历对应 enter partition(1,9) leave partition(1,9) 假定当前活动对应结点N, enter quicksort(1,3) 那么所有尚未结束的活动对 leave quicksort(1,3) 应于N及其祖先结点 enter quicksort(5,9) leave quicksort(5,9) leave quicksort(1,9) 9(1,9) leave main() p(1,9) q(1,3) q(5,9) 图7-2中程序的可能的活动序列 p(1,3)q(1,0)q(2,3) p(5,9)q(5,5)q(7,9 p(2,3)q(2,1)q(3,3) p(7,9)q(7,7)g(9,9) 7
活动树的例子 • 快速排序程序 – 过程调用 (返回) 序列和活动 树的前序 (后序) 遍历对应 – 假定当前活动对应结点N， 那么所有尚未结束的活动对 应于N及其祖先结点 7 南大编译许畅
活动记录 过程调用和返回由控制栈 实在参数 进行管理 返回值 。 每个活跃的活动对应于栈 中的一个活动记录 控制链 访问链 ·活动记录按照活动的开始 时间，从栈底到栈顶排列 保存的机器状态 局部数据 临时变量 8
活动记录 • 过程调用和返回由控制栈 进行管理 • 每个活跃的活动对应于栈 中的一个活动记录 • 活动记录按照活动的开始 时间，从栈底到栈顶排列 8 南大编译许畅
运行时刻栈的例子 integer a11] integer a11 。说明 main main main main [11]为全局变量 main无局部变量 integer i b)r被激活 r有局部变量i g有局部变量i, integer all] integer a11] main main main main 和参数m,n integer m,n integer m:n q(1,9) q1,9) q(1,9) q(1,9) integer i integer t p(1,9)q(1,3) integer m,n p(1,3)q(1,0) q(1,3) integer i c)Y被弹出栈，q(1,9)被压栈 d)控制返回到q1,3) 9
运行时刻栈的例子 • 说明 – a[11]为全局变量 – main无局部变量 – r有局部变量i – q有局部变量i， 和参数m, n 9 r r 南大编译许畅
调用代码序列 调用代码序列(Calling sequence)为活动记录分配 空间，填写记录中的信息 返回代码序列(Return sequence)恢复机器状态， 使调用者继续运行 调用代码序列会分割到调用者和被调用者中 根据源语言、目标机器和操作系统的限制，可以有不 同的分割方案 把代码尽可能放在被调用者中 10
调用代码序列 • 调用代码序列 (Calling sequence) 为活动记录分配 空间，填写记录中的信息 • 返回代码序列 (Return sequence) 恢复机器状态， 使调用者继续运行 • 调用代码序列会分割到调用者和被调用者中 – 根据源语言、目标机器和操作系统的限制，可以有不 同的分割方案 – 把代码尽可能放在被调用者中 10 南大编译许畅