1. 核心动机 (Motivation)
编译器不仅要生成代码，还要规划程序在运行时的“生存环境”。核心要解决的问题是：
存储分配：变量和代码存在哪？
作用域实现：如何让函数访问到外层定义的变量？（嵌套定义）
过程连接：函数调用时如何传递参数、保存现场和返回结果？
2. 存储组织 (Storage Organization)
程序运行时，操作系统申请的内存空间通常划分为四个区域：
代码区 (Code)：存放目标机器指令，大小固定，静态分配。
静态数据区 (Static Data)：存放编译时确定大小的数据（如全局变量、静态变量）。
堆 (Heap)：用于动态申请内存（如 Pascal 的
new，C 的malloc），生命周期不由栈管理。控制栈 (Control Stack)：本章重点。用于管理过程的活动（Activity），支持递归调用。
3. 活动记录与控制栈 (Activation Records & Control Stack) —— 画图核心
这是考试中“画栈图”的基础单位。你需要把每一个活动的执行环境想象成一个标准的“盒子”。
3.1 活动记录的标准结构 (The “Block” Structure)
一个标准的活动记录（从栈顶到栈底/高地址到低地址）通常包含以下域：
| 区域名称 | 功能描述 | 画图要点 |
|---|---|---|
| 临时数据 (Temporaries) | 存放计算中间结果 | 通常画在最底部 |
| 局部数据 (Local Data) | 本次执行中声明的局部变量 | 填空题重点：每次递归的值可能不同 |
| 机器状态 (Machine Status) | 保存程序断点 (PC)、寄存器值 | 保证能“断点续传” |
| 访问链 (Access Link) | (重点) 指向定义该过程的直接外层过程的活动记录 | 静态链。用于查找非局部变量 (Static Scope) |
| 控制链 (Control Link) | (重点) 指向调用该过程的活动记录（即栈中前一个记录） | 动态链。用于函数返回时恢复栈顶 |
| 实参区域 (Parameters) | 调用者传递进来的参数 | 由调用者填入 |
| 返回值 (Return Value) | 存放被调用函数的计算结果 | 由被调用者填入 |
画图技巧：在简化的示意图中，通常只需要画出 参数、局部变量 以及两个关键指针：控制链 和 访问链。
3.2 控制链 vs 访问链 (关键区分)
这是最容易混淆的概念，请务必背下来：
控制链 (Dynamic Link) —— “谁调用了我？”
指向：物理栈中紧挨着它下面（或上一个压栈）的活动记录。
作用：物理回退。函数运行完后，顺着它找到回家的路，恢复栈指针 (
)。 画法：无脑指向栈中的前一个记录（串糖葫芦）。
访问链 (Static Link) —— “我在哪里被定义的？”
指向：代码文本中包裹它的那一层函数的最新活动记录。
作用：逻辑寻址。当程序引用了一个当前函数里没有的变量时，顺着访问链往上找（实现词法作用域）。
画法：需要根据嵌套深度规则来判断（见下文 4.2）。
4. 非局部名字的访问 (Access to Non-local Names)
4.1 嵌套深度 (Nesting Depth)
为了确定访问链，我们需要给每个过程标记深度：
主程序：深度 1
每进入一层过程定义：深度 + 1
变量的深度 = 声明它所在过程的深度
4.2 访问链的建立规则 (The 3 Rules) —— 解题算法
假设过程
设
情况 1：调用“儿子” (直接嵌套)
条件：
（ 定义在 内部） 指向：
的访问链 自己的活动记录。 理解：儿子找爸爸，爸爸就是当前的调用者。
情况 2：调用“兄弟”或“自己” (同级嵌套/递归)
条件：
（ 和 定义在同一个外层块中，或者 递归调用 ） 指向：
的访问链 复制 的访问链。 理解：哥哥调用弟弟，弟弟找爸爸的路径和哥哥是一样的。
情况 3：调用“叔叔/长辈” (外层嵌套)
条件：
（ 是 的外层或外层的外层） 指向：
的访问链 从 的活动记录开始，顺着 的访问链往回走 步。 理解：我在深层，调用了一个浅层的函数。那个浅层函数的环境在链条的更上方。
5. 参数传递机制 (Parameter Passing)
传值调用 (Call-by-value)
机制：计算实参的值（右值），拷贝到被调过程的形参槽中。
特点：过程内修改形参不影响外部实参（除非传的是指针）。
语言：C, Java, Pascal (缺省)。
引用调用 (Call-by-reference)
机制：传递实参的地址（左值）。形参成为实参的别名。
特点：过程内修改形参直接改变外部实参。
语言：Fortran, C++ (
&), Pascal (var).
复制恢复 (Copy-restore / Copy-in Copy-out)
机制：进入时拷贝值（Copy-in），返回时将形参的新值拷贝回实参地址（Copy-out）。
特点：大多数情况下效果同引用调用。
区别：当同一个变量通过多个参数传递时（别名问题），结果可能不同。
传名调用 (Call-by-name)
机制：类似宏替换。每次引用形参时，重新计算实参表达式。
特点：Algol 60 特有，现代少见。
6. 实战指南：如何画运行时栈 (Practical Guide)
遇到“画出某时刻控制栈”的题目，请按以下步骤操作：
Step 1: 标记深度
在源代码旁边标出每个函数的嵌套深度。
Step 2: 模拟压栈
按照代码执行顺序，每调用一个函数，画一个新的矩形框（活动记录）。
- 注意：如果是递归调用，会有多个同名函数的框，但局部变量的值不同。
Step 3: 填充内容
参数域：填入调用时传入的具体数值。
局部变量：填入当前执行状态下的值。
Step 4: 连线 (两条链)
控制链：从当前框伸出箭头，指向前一个框（刚才调用它的那个）。
访问链：
看被调用的函数定义在哪里。
如果定义在 Global
指向栈底/全局区。 如果定义在某个函数
内部 指向栈中最近的一个 的框。 或者直接套用 4.2 节的“三规则”。
示例：QuickSort 栈图解
假设调用顺序：sort quicksort(1,9) quicksort(1,3) partition。
Plaintext
|-----------------------------|
| sort (Main) | Depth 1
| [变量: a, x] |
| [Access: null] |
|-----------------------------|
^
| (Control)
|-----------------------------|
| quicksort(1,9) | Depth 2 (定义在 sort 里)
| [变量: k, v] |
| [Access: 指向 sort] | (规则1: nq=np+1, 指向调用者)
|-----------------------------|
^
| (Control)
|-----------------------------|
| quicksort(1,3) | Depth 2
| [变量: k, v] |
| [Access: 指向 sort] | (规则2: nq=np, 复制上一个Access)
|-----------------------------|
^
| (Control)
|-----------------------------|
| partition | Depth 3 (定义在 quicksort 里)
| [变量: i, j] |
| [Access: 指向 quicksort(1,3)]| (规则1: nq=np+1, 指向调用者)
|-----------------------------| 7. 典型例题详解：函数作为参数与 Display 表 (Advanced Example)
针对涉及“函数作为参数传递”和“Display 表更新”的复杂题目，请参考以下范例。
场景：main 定义了 b 和
c；c 定义了 f 和
r。调用顺序为 main -> c ->
r -> b(f) -> f。
深度 1:
main深度 2:
b,c深度 3:
f,r
7.1 复杂控制栈画法 (Control Stack Diagram)
当控制进入 f 时，栈的状态如下。注意参数符号
< > 的使用和 访问链
的跳跃性。
Plaintext
|-------------------------------------|
| (1) main 的活动记录 | Depth 1
|-------------------------------------| <--- AL(b) 指向这里 (b定义在main中)
| Access Link: null | <--- AL(c) 指向这里 (c定义在main中)
|-------------------------------------|
^
| CL
|-------------------------------------|
| (2) c 的活动记录 | Depth 2
|-------------------------------------| <--- AL(r) 指向这里 (r定义在c中)
| 变量 m = 0 | <--- AL(f) 指向这里 (f定义在c中)
| Access Link: 指向 (1) main |
|-------------------------------------|
^
| CL
|-------------------------------------|
| (3) r 的活动记录 | Depth 3
|-------------------------------------|
| 变量 m = 7 |
| Access Link: 指向 (2) c |
|-------------------------------------|
^
| CL
|-------------------------------------|
| (4) b 的活动记录 | Depth 2
|-------------------------------------|
| 变量 m = 3 |
| 参数 <f, 访问链指向c> | **(重点)**: 传入了 f 及其静态环境
| Access Link: 指向 (1) main | **(易错)**: b 定义在 main 中，不指向 r
|-------------------------------------|
^
| CL
|-------------------------------------|
| (5) f 的活动记录 | Depth 3
|-------------------------------------|
| 参数 <n=2> |
| Access Link: 指向 (2) c | **(重点)**: 从 b 的参数中获取，指向 c
|-------------------------------------| 画图规范总结：
< >：表示由调用者传递进来的参数（如<n=2>或<f, 环境指针>）。无括号：表示过程内部自己定义的局部变量（如
m=0）。
7.2 Display 表 (d表) 的特殊机制
Display 表用于加速访问，d[i]
始终指向当前静态环境中深度为 i
的最新活动记录。
规则：当函数 f (深度3)
被调用时，如果它需要的静态父环境（这里是 c，深度2）不是当前
Display 表里的那个（当前是
b，深度2），则必须保存旧值，更新新值。
控制处于 f 中时的 Display
表状态图：
Plaintext
Display 表 (d) 控制栈 (Stack)
+-----------------+ +--------------------------+
| d[1] |------->| (1) main 的活动记录 |
+-----------------+ +--------------------------+
| d[2] |---+ | (2) c 的活动记录 | <--- d[2] 强制指向这里!
+-----------------+ | | [深度 2] | (因为 f 需要访问 c)
| d[3] |--+|--->+--------------------------+
+-----------------+ || | (3) r 的活动记录 |
|| +--------------------------+
|| | (4) b 的活动记录 |
|| | [深度 2] | (b 在 d 表中被"屏蔽")
|| +--------------------------+
|+--->| (5) f 的活动记录 | <--- d[3] 指向这里
| | [深度 3] |
| |--------------------------|
| | *保存的 d[2]: 指向 b | **(重点)**:
+--------------------------+ 用于 f 返回时恢复 d[2] 解题口诀：
Display 表关注的是“定义层级”而非“调用顺序”。
当 f 运行时，世界必须是 main -> c -> f 的样子，中间那个调用者 b 对 f 来说是不可见的，所以 d[2] 必须从 b 换成 c。
如果您喜欢我的文章，可以考虑打赏以支持我继续创作.
