词法名字解析与声明身份

源码中的 x 是可重复使用的标签，声明 ID 则是这一次声明的身份。解析以后，编译器可以把 x#1 放进闭包环境，把 x#9 放在当前局部槽，而不再担心文本相同造成混淆。ID 没有携带数值，也不是堆地址。

字典里按名字叠起的栈，把“从里向外找最近声明”提前组织好。进入同名内层作用域只是压入一个新 ID，离开就弹回旧 ID。resolved AST 保存的是选中的 ID，不保存后来还会变化的字典查询，以免闭包转换时重新按调用点名字解释自由变量。

遮蔽、右侧和闭包体分别看谁 ​

let x = 4 in
let f = fun y -> x + y in
let x = x + 1 in
f(x)

按声明先序编号为 x#1、f#2、y#3、x#4。解析外层右侧常量 4 时 D 为空；解析 f 的函数体时 D[x]=[1]、D[y]=[3]，所以加法为 Add(Var(1),Var(3))。处理第二个 x 的右侧时还没有压入 4，因此它是 Add(Var(1),1)，不是读取尚未初始化的 x#4。

压入第二个 x 后，调用节点为 Call(Var(2),Var(4))。resolved AST 可以完整写成：

Let(1, 4,
  Let(2, Fun(3, Add(Var(1), Var(3))),
    Let(4, Add(Var(1), 1),
      Call(Var(2), Var(4)))))

运行时 x#4 得到 5，f 的代码仍读 x#1=4，所以结果为 9。如果把 f 中的 x 留成“运行时去当前名字表查询”，就会读到 5，得到 10。静态解析只决定 f 使用哪个声明；函数返回之后如何保留那个声明的值，由闭包转换理路闭包转换Closure conversion · 闭包变换把词法捕获改写为显式环境参数，同时保留遮蔽、求值顺序与共享可变单元。承担。

另看 (let x=1 in x, x)。解析第一分量后必须恢复外层字典；若初始环境没有 x，第二分量的 x 应报未绑定。忘记弹栈会错误接受该程序。let x=x in x 在空环境下也必须报错，因为非递归右侧的 x 没有声明；不能以目标语言碰巧把未初始化槽清零为语义。

从身份算捕获集合 ​

对上例函数体取旧绑定页的自由变量规则，得到 {1}，不是无区分的文本集合 {x}。形参 3 被移除，调用点新增的 4 从未进入该函数的捕获集合。若函数体另含 let x=8 in x+y，其中新的 x 身份只在内层有效，不能误把它加到外部捕获字段。

对一份成功解析的闭程序，所有使用 ID 都应存在于声明表，而且其声明在该使用的词法祖先作用域中。单独检查“ID 存在”仍不够：把使用错误改到同文件另一个作用域的声明，存在性会通过，作用域不变量却失败。

本算法使用字典理路字典、映射与集合 ADTDictionary ADT · Map ADT · Set ADT以有限偏函数统一刻画按键查询、更新和删除的字典、映射与集合接口。和每名字栈。假定标识符已驻留、哈希查找期望常数，n 个 AST 节点的工作期望为 $O(n)$，名字栈空间为当前活动声明数；递归遍历还需 $O(h)$ 调用栈，h 为 AST 高度，深层不含绑定的表达式也会增加 h；另有输出树 $O(n)$。每个名字字符串首次读取、驻留和哈希需按字符总数另计，不能因它最终变为一个整数 ID 就免费。改用平衡树，查找和更新为 $O(\log b)$，b 为活动不同名字数；按作用域组织“哈希表的栈”则一次查找可能经过深度 d 个表。

为诊断保存每次完整 D 的快照不是算法所需；若这样做，嵌套 n 层时记录总量可能为 $\mathrm{\Theta }(n^2)$。终点 checker 只记录绑定决策与事件序列，若开启完整 AST/状态打印，会单列序列化输出大小。

迁移任务：把第二个 x 改名 z，同时只把其绑定的最后调用实参改成 z。答案仍是 9，resolved AST 除诊断标签外完全相同。若把 f 函数体里的 x 也改成 z，它在定义点未绑定，必须失败。再把 let 改成受限 let rec f=fun y->...：应在解析函数右侧前先压入 f，但还需限定递归初始化；这不是把本页所有 let 一律提前压栈的理由。

名称解析的符号表与链接器符号表理路对象符号解析与重定位Symbol resolution and relocation · Static linking · 链接与重定位为两份对象文件布置节地址、解析局部和全局符号、原子计算带宽度的重定位，并区分静态链接与装载时绑定。处在不同层。前者连接语法出现与声明身份，后者连接不同对象文件的导出定义并计算地址。一个局部绑定不必成为导出的链接符号，同一个源程序也可能经消除优化而不再保留对应机器槽。