前段时间有读者问我前面词法、语法、语义分析都讲完了为什么还要单独拿一章讲“运行时存储空间管理”这个问题问到点子上了。前面所有分析工作都在编译期完成但程序真正跑起来之后源代码里的变量名到底落在内存的哪个位置、嵌套过程中怎么访问外层变量这些恰恰是很多人学编译原理时最迷糊的地方。这一章“变量访问环境”要解决的核心问题就是把“名字作用域”最终翻译成“地址生命周期”。我尽量用实际例子把这些概念串起来讲适合正在啃龙书、虎书的中级读者也适合想彻底搞懂函数调用栈和闭包实现原理的朋友。1. 从名字到地址三种存储分配策略决定了变量怎么活要理解变量访问环境不能只盯着“环境”得先看“存储”。编译器在处理变量时第一个要回答的问题就是这个变量的存储空间应该放在哪什么时候分配什么时候释放。1.1 静态分配、栈式分配、堆式分配分别解决什么问题我习惯把一个变量看作“有一段命名的内存”。命名是编译期的事内存是运行时的事。按照生存周期的不同存储分配可以分成三类静态分配变量地址在编译期就能确定整个程序运行期间不变。典型代表是全局变量和static变量。编译器直接把它们放到数据段生成代码时用绝对地址或者基址寄存器加固定偏移访问。栈式分配变量随着一个过程函数被调用而分配随着过程返回而释放。典型代表是局部变量。因为过程调用天然具有“先进后出”的嵌套结构用栈来管理最合适。堆式分配变量的生命周期不受过程调用的约束可以手动申请、手动释放或者交给垃圾回收器。典型代表是动态数组、对象、指针指向的数据。这三种策略并不是互斥的真实编译器通常三者混用。全局变量用静态分配局部变量用栈式分配动态数据结构用堆式分配。重点来了变量访问环境里说的“环境”并不是指这三类空间本身而是指“当前代码正处于哪个过程、哪个嵌套层级编译器该如何找到对应变量的存放位置”。1.2 为什么访问环境不是纯运行时问题很多人有一个误解觉得变量访问是靠运行时查表完成的。实际上对于编译型语言变量访问环境的大部分决策在编译期就确定了。语法分析阶段建立的符号表记录了每个变量的声明位置和可见作用域到中间代码生成和代码生成阶段编译器要针对每个变量访问点生成寻址代码。这时候编译器必须知道三件事当前变量声明在第几层——这决定了词法嵌套深度。当前访问点在第几层——这决定了从哪个活动记录出发。变量在当前层活动记录里的偏移——这决定了最终地址怎么算。我以前调试自己写的编译器时最常犯的错误就是把符号表和运行时环境混在一起。其实符号表是编译期概念活动记录链是运行时概念。变量访问环境可以理解成“符号表作用域信息在运行时的镜像”。它不是一个保存在内存里的字典而是通过栈帧、链指针、偏移量这些机制体现出来的。2. 活动记录栈帧里的每一位字段设计与调用约定栈式分配的单位不是单个变量而是“过程的一次活动”。每次过程调用都会在栈上压入一个活动记录有的教材叫栈帧。2.1 活动记录里到底放了什么东西一个典型的活动记录包含这些字段我列个表字段作用对应关系返回地址过程执行完后回到哪条指令调用者代码段位置动态链指向调用者的活动记录谁调用了我静态链指向词法外层过程的活动记录谁的代码文本包含了我的声明实参调用者传递的参数参数传递的载体局部变量本过程声明的变量编译期已确定偏移临时变量表达式计算产生的中间结果编译器分配时复用保存的寄存器恢复调用者现场的寄存器值调用约定决定“动态链”和“静态链”这两个名字特别容易搞混我重点说一下。动态链解决的是“调用返回问题”它把当前活动记录和调用者的活动记录串起来形成一个按时间顺序排列的链表。静态链解决的是“变量访问问题”它把当前活动记录和词法上嵌套的外层活动记录串起来形成一个按源码嵌套结构排列的链表。如果一段代码里只有一个全局过程、根本没有嵌套过程那么静态链这个字段可以省略但 Pascal、Ada、JavaScript 这些语言有嵌套函数就必须考虑它。2.2 调用者和被调用者各自负责什么活动记录不是一次性压栈的调用者和被调用者必须按约定分工这个约定就叫调用约定。以经典的 x86 调用序列为例调用者的职责是计算实参值并按约定压栈。执行call指令把返回地址压栈并跳转到被调用者入口。取得返回值后清理参数如果调用者负责清理。被调用者的职责是保存旧基址把上一个活动记录的帧指针压栈这就形成了动态链。设置新帧指针把当前栈顶地址赋给帧指针。给局部变量和临时变量腾出空间栈指针向下移动一个固定大小。保存需要保留的寄存器值。过程结束时恢复栈指针和帧指针按动态链找到调用者。这里有一个非常关键的设计点局部变量通常不直接依赖栈顶而是依赖帧指针的固定偏移量。因为过程体执行过程中可能要调用其他过程栈顶会不断变化如果局部变量用栈指针加偏移来访问偏移量就一直在变而帧指针在过程执行期间保持不变用“帧指针 固定偏移”访问局部变量最稳定。调试器能看到调用栈靠的也是动态链。栈回溯stack unwinding会一层层沿着动态链往上走恢复每个过程的帧指针和代码位置最终打印出完整的调用路径。这也是为什么动态链即使不直接参与变量访问也仍然是运行时环境的重要部分。3. 静态链嵌套作用域访问外层变量的朴素做法现在进入本篇的核心嵌套过程和块结构中非局部变量是怎么被找到的。3.1 动态链和静态链千万别混淆先看一段类 Pascal 的代码program P; // 深度 1 var a: integer; procedure Q; // 深度 2 var b: integer; procedure R; // 深度 3 begin a : b 1; // 这里 a 和 b 都不是 R 的局部变量 end; begin R; end; begin Q; end.当 R 被调用时栈上的活动记录有两种关系。从动态链看R 是由 Q 调用的所以 R 的动态链指向 Q 的最新活动记录。从静态链看R 的源码文本嵌套在 Q 里面R 的静态链也应该指向 Q 的最新活动记录。在本例中R 的“调用者”和“词法外层”恰好都是 Q所以动态链和静态链指向同一个记录最容易混淆。再把程序改一下让 R 调用 Qprocedure R; // 深度 3 begin Q; // 调用词法上的外层过程 end;这次 Q 的活动记录是从 R 内部被调用的。Q 的动态链指向 R但 Q 的静态链指向 P因为 Q 的词法外层是 P。两条链彻底分开了。理解这一点就理解了静态链设计的百分之八十。3.2 调用时如何计算并保存静态链给被调用过程 Q 建立静态链本质上是回答一个问题Q 的词法外层过程的最新活动记录在当前调用环境中处于哪个位置我在手写编译器代码生成部分时采用过一个稳妥的规则假设当前代码所在过程的词法深度是caller_depth被调用过程的词法深度是callee_depth那么从调用者当前活动记录开始沿静态链往下走caller_depth - (callee_depth - 1)步得到的就是被调用过程静态链应该指向的活动记录。举几个例子验证一下Q 深度 2R 深度 3Q 调用 R。因为 R 直接嵌套在 Q 里R 的静态链应该指向 Q。按公式caller_depth2callee_depth3走的步数是2 - (3 - 1) 0也就是不沿链跳转直接把当前活动记录 R? 不对等等走 0 步意味着被调者的静态链就是当前调用者的活动记录。这里我重新表达一下更通用的说法是被调用过程的静态链应该指向调用者活动记录所在的访问环境中、与被调用过程词法父层对应的那一条记录。算法上从当前活动记录出发沿静态链前进对应步数。如果被调用过程直接嵌在调用者过程里那它的静态链就是调用者当前活动记录本身不需要沿链跳转。再比如当前在深度 3 的 R 里调用深度 2 的 QQ 的静态链应该指向深度 1 的 P。从 R 出发R 的静态链指向 Q深度 2Q 的静态链指向 P深度 1所以要走两步才能拿到 P 的活动记录。这正是公式算出来的结果。这个过程在代码生成阶段要翻译成具体的访存指令。编译器会为每次调用生成一小段“沿静态链寻找父活动记录”的代码。深度差是编译期常量所以循环次数可以静态展开不需要在运行时判断。3.3 非局部变量访问的偏移计算静态链建好了非局部变量访问就很简单。假设当前过程深度是current_depth变量声明所在过程深度是decl_depth那么需要沿静态链走current_depth - decl_depth步走到变量所在活动记录然后加上编译期算好的变量偏移。以最开始的代码为例R 深度 3 访问变量aa声明在深度 1 的 P 中差值是 2。运行时沿着 R 的静态链走一步到 Q 的活动记录再走一步到 P 的活动记录最终地址就是“P 活动记录基址 a的偏移”。从这个过程能看到访问一次非局部变量开销取决于嵌套深度差。深度差越大需要沿链跳转的次数越多。频繁访问深层非局部变量运行性能会明显下降。这就是为什么后面要引入 Display 表。4. Display 表用一张表把链式访问变成 O(1)静态链的办法简单直接但访问非局部变量要遍历链效率不高。Display 表的思路是空间换时间维护一个全局数组让编译器能在常数时间内找到任意词法深度对应的最新活动记录。4.1 Display 表的基本结构假设语言允许的最大词法嵌套深度是n那么就维护一个长度为n的数组D其中D[i]指向当前正在执行的、词法深度为i的过程的最新活动记录。还是用刚才 P/Q/R 的例子。当执行到 R 内部时运行时的 Display 表应该是D[1]指向 P 的活动记录。D[2]指向 Q 的活动记录。D[3]指向 R 的活动记录。这时要访问变量a编译器生成的代码很简单取D[1]再加上a的偏移。访问b取D[2]加上b的偏移。与静态链相比少了一连串的链跳转而且不管嵌套多深访问开销都是固定的。4.2 进入和退出过程时的表维护天下没有免费的午餐。Display 表带来的额外成本在过程调用和返回时需要维护这张表。当一个词法深度为j的过程被调用时要做两件事把旧的D[j]保存到新活动记录的一个专门字段中。把D[j]设置为新活动记录的基址。过程返回时把保存的旧D[j]恢复回去。这里有个细节容易让人困惑进入一个嵌套深度更浅的过程时D[j1]这些更深槽位要不要清空我在实际实现中验证过不需要清空。因为词法作用域规则保证了深度为j的过程内部无法访问深度大于j的非局部变量。更深槽位里残留的值虽然在物理上还存在但任何合法的访问都触不到它们。等之后某个更深层过程被调用时新的活动记录会直接覆盖这些槽位。所以 Display 表的过程进入/退出代价理论上可以是 O(1)只需要保存和恢复一个槽位。很多教材会在这一节讨论“进入块结构时显示表如何保存多层槽位”那是把“过程深度”和“块深度”同时建模导致的复杂情况如果编译器只按过程嵌套层级来建立 Display 表实现会清爽很多。4.3 静态链和 Display 表的取舍我在写 Toy Compiler 时两种方案都试过把它们放在一起对比如下对比项静态链Display 表非局部变量访问O(嵌套深度差)O(1)过程调用额外开销建链时可能需要沿链走几步保存/恢复一个槽位存储位置每个活动记录里放一个静态链指针全局数组各活动记录里放旧槽位调试友好度活动记录结构直观需要额外检查全局表典型使用场景经典 Pascal 编译器、GCC 嵌套函数老式 Pascal 编译器、部分函数式语言运行时实际工程里还有个折中做法把 Display 表的前几层放到寄存器里剩下的放到内存。因为大多数程序的词法嵌套深度不会超过三四层这样访问最常用的几个层级几乎零开销。代价是过程调用和返回时要多保存、恢复几个寄存器。如果程序词法深度固定且不深Display 表优势明显如果嵌套深度普遍很小静态链的跳转次数也几乎可以忽略这时静态链反而更简单活动记录的内存量也更小。选择哪一种本质是“访问频率”和“调用频率”的权衡。5. 块、闭包与逃逸环境访问环境的延伸战场教材讲到 Display 表通常就收尾了但真正做编译器或解释器时变量访问环境还要面对几个扩展场景这里一起说清楚。5.1 块结构的局部变量要不要单独建帧很多语言允许在过程内部再写复合语句块比如procedure Test; begin for i : 1 to 10 do begin var temp: Integer; ... end; end;temp的作用域只在 for 循环体内部。编译器通常不会为块单独建立一个活动记录而会在编译期把块内变量分配到当前过程的栈帧上。进入块时不需要做任何运行时操作退出块后这组变量的栈空间可以复用给其他变量。所以块结构改变的是编译期的符号表作用域而不是运行时的活动记录链。这一点我很早的时候理解反了写出来的代码生成器在每进入一个块时都调整栈指针结果多出一堆不必要的指令还掩盖了一个 bug某些块内变量的初始化时机不对。5.2 闭包当静态链指向的活动记录已经销毁怎么办静态链和 Display 表都建立在“外层活动记录比内层活得更久”的假设上。但函数式语言和现代脚本语言里经常出现“向上逃逸upward funarg”的情况function MakeCounter() { let n 0; return function () { n; return n; }; } let counter MakeCounter(); counter(); counter();返回的匿名函数捕获了外层变量n。按正常栈式分配MakeCounter 返回后它的活动记录应该释放n就没了。但闭包要求n继续存活。这时候编译器不能简单地把匿名函数的静态链指向一个已失效的栈帧。常见的做法是堆分配捕获变量把被捕获的变量放到堆上而不是栈上。闭包携带环境指针函数对象中保存一个指向堆上“环境对象”的指针而不是单纯指向栈帧。逃逸分析优化如果编译器能证明闭包不会逃逸出当前过程就仍然可以栈分配否则只能保守地堆分配。从这个角度看闭包本质上是“变量访问环境”从栈上搬到堆上的一种形态。它和静态链解决的问题一样但生命周期规则不同所以底层机制也变了。写解释器时很多新手动用一个字典保存所有运行时变量其实和这种闭包环境模型很接近但在编译型语言里必须显式设计环境对象的布局。5.3 寄存器分配和栈帧布局对访问环境的影响最后补一个工程里容易忽略的点变量访问环境不仅影响运行时数据结构还影响寄存器分配。编译器做寄存器分配时如果某个非局部变量访问太频繁可能干脆把它加载到寄存器里缓存一段时间而不是每次访问都沿链找。但这要求编译器能准确知道该变量在所有路径上的存活状态分析成本不低。寄存器机器上Display 表也可以部分放寄存器但线程切换、信号处理、异常处理都会打乱寄存器中的表内容。稳妥的实现是在每次过程调用和恢复现场时同步内存和寄存器的 Display 表否则很容易出现“寄存器里的表是旧的内存里的表是新的”这类诡异问题。我自己调试这类 bug 的经验是先在纸上画出三个东西——活动记录的内存布局、静态链/Display 表的指向关系、当前执行位置对应的词法深度。三个图对不上问题一定出在某个过程的入口或出口代码上。绝大多数链式访问错误都不是编译器的“访问代码”错了而是“建链代码”或“恢复代码”错了。编译原理学到运行时存储这里才算真正把静态程序和动态执行打通。变量访问环境并不是一个需要死记硬背的知识点它是一套让你能在头脑里完整模拟“代码如何被编译、函数如何被调用、变量如何被找到”的思维工具。后面再去看闭包、协程、垃圾回收这些东西都会轻松很多。