写完语法分析器那天我以为最难啃的骨头已经过去了。结果拿一段十几行的测试代码跑解析树漂亮得很语义检查一开报出七个错全是文法层面完全合法、只有在知道这个名字指的是哪个声明这个类型能不能赋给那个类型之后才能判定的东西。语义分析里的上下文相关处理本质上就是给上下文无关文法补上它天生表达不了的那一半信息——谁在哪、谁能看见谁、什么类型能流到哪去。这篇就聊聊这一层到底怎么做符号表怎么设计才不至于后面全推倒重来类型检查的遍历骨架长什么样重载和推断这些非要看上下文的活儿怎么落地以及报错信息为什么经常让人觉得编译器在骂人。如果你正在手写一个解释器或编译器或者要给已有的分析器加类型检查、加作用域、加泛型这篇里的取舍和坑应该能直接抄。哪怕你不写编译器只是想搞清楚为什么这段代码明明语法没错却编译不过看完也能明白那层检查是在干什么。1. 文法说合法语义说不行上下文相关到底藏在哪1.1 三个只有越过语法树才能回答的问题先看一段谁都写过的代码int f(int a, int b) { return a b; } void main() { f(1); }从文法角度f(1)是一个再标准不过的调用表达式标识符后面跟一对括号括号里是实参列表。任何上下文无关文法都会痛快地接受它。但编译器一检查就炸了——参数个数不对。这个不对的判定依据完全不在句法结构里它要求你去查f的声明长什么样而f的声明可能在这个文件的几百行之外也可能在另一个文件里。再看x 1;。文法同样无话可说。但语义层要回答三件事x声明过吗如果声明过它是变量还是常量它的类型能不能接受一个整型字面量这三个问题没有一个是看这行代码本身能答出来的。还有一类更容易被忽略的break;单独出现文法上是合法的跳转语句语义上却必须确认它被包在循环或者多分支结构里。这个约束的实现方式通常是在遍历时往上下文里带一个当前是否在可跳出结构内的标志而不是去符号表里查。类似地continue、return、yield都是这个套路。我习惯把这些约束分成三类来设计名字约束这个标识符指向哪个声明、类型约束这个值能不能流到这里、结构约束这个语句出现在什么位置才合法。三类约束的实现机制完全不同混在一起写代码很快就会变成一团。有意思的是边界并不总是这么清楚。有一类写法会让上下文相关的信息倒灌进语法分析阶段最典型的就是类型名和变量名共用同一套标识符语法的语言(a) * b;这一行如果a是个类型名它是一条把b声明为指针的声明语句如果a是个变量名它是一个乘法表达式。语法分析器在读到这一行的时候必须知道a属于哪一种否则连解析树都建不出来。这就是所谓的词法分析器与语法分析器需要通信实现上一般是在词法分析器里挂一个符号表的只读视图遇到标识符时顺手查一下它是不是类型名然后给出不同的 token 类型。这也是为什么这类语言的前置声明如此重要——你没声明过词法层就没法给你正确的 token。1.2 上下文相关信息的三种承载方式搞清楚了要补什么接下来是往哪儿放。我的经验是分成三层各管各的别互相串。第一层是符号表负责名字到声明的映射。它是有状态的、随时间变化的进入一个块可见的名字多了一批离开这个块这批名字就失效了。符号表最忌讳的设计是一次性建完再查因为作用域是有生命周期的遮蔽关系是动态的。第二层是类型环境负责表达式到类型的映射。严格说类型环境可以看成符号表的一部分每个符号条目里挂一个类型字段但逻辑上要分开想符号表回答这个x是谁类型环境回答这个x是什么类型。当符号解析失败时类型环境的查询应该返回一个特殊的未知类型而不是抛异常中断整个分析。第三层是AST 标注。语义分析的产出不应该只是一堆报错它必须把结论写回语法树上。每个标识符节点上挂一个符号 ID每个表达式节点上挂一个结果类型每个声明节点上挂一个分配好的存储位置或者偏移量。后面代码生成阶段就靠这些标注干活不用再回头查表。还有一个隐藏的第四层错误状态。这不是信息而是信息的缺失标记。当你解析不出一个名字或者算不出一个类型时要有一个明确的占位符往下传让上层知道这里已经出过错别再报了。这一层设计得好不好直接决定了用户看到的是一个错误还是一屏错误。2. 符号表不是一张哈希表是一条随时间变化的作用域时间线2.1 栈式、链式与扁平化三种实现各自的代价最直觉的实现是栈式符号表一个列表每个元素是一个字典代表一层作用域。class ScopeStack: def __init__(self): self.scopes [{}] def enter(self): self.scopes.append({}) def leave(self): return self.scopes.pop() def declare(self, name, sym): cur self.scopes[-1] if name in cur: raise SemanticError(f重复声明: {name}) cur[name] sym return sym def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] return None这套代码二十行就能写完能跑大部分教学项目用它就够了。代价是lookup是 O(作用域深度) 的。深度一般不会超过十层实际测下来几乎没有性能问题绝大多数场景下不必优化。链式实现本质一样只是把列表换成了父指针每层作用域持有一个指向外层的引用查找时沿着链往上爬。好处是作用域可以独立存在不必依附于一个全局栈坏处是要自己管理生命周期容易漏掉leave。真正值得说的是扁平化加唯一 ID方案。思路是符号表只在分析阶段存在但每个声明在建立时就分配一个全局唯一的整数 ID然后把 ID 写到 AST 的引用节点上。分析结束后符号表可以整个扔掉后续阶段全靠 ID 做 O(1) 的数组索引。class ResolvedName: def __init__(self, sym_id, name, decl_node, type): self.sym_id sym_id self.name name self.decl_node decl_node self.type type这个设计的好处远不止性能。重名不是问题——内层x和外层x是两个不同的 ID永远不会搞混。调试信息生成也方便直接按 ID 索引。最关键的是支持增量分析改了某个函数体只需要重跑这个作用域内的解析其他部分的符号 ID 不受影响。做语言服务器的同学应该深有体会没有唯一 ID 这套机制增量分析几乎无从下手。我的建议是教学项目用栈式顺手真要做产品一开始就上唯一 ID后面省事。改造成本远比你想象的大。2.2 声明点与可见性int x x;这类写法为什么容易做错这一节是符号表实现里最容易翻车的地方没有之一。看这段int x 1; { print(x); int x 2; print(x); }第一次print(x)打印的是外层那个x值为 1第二次打印的是内层那个值为 2。这个结果要求符号表在遍历到第一个print(x)时内层的x还没有进入作用域。也就是说局部变量的作用域从它的声明语句结束后才开始。直觉的实现是先遍历整个块把所有声明收集起来放进符号表然后再遍历一遍做检查。这么写第一个print(x)就会错误地绑定到内层x上输出 2而且编译器不报错——这种 bug 极难发现因为它看起来完全合理。正确做法是边遍历边声明走到int x 2;这条语句先解析初始化表达式此时内层x还不存在x x的右边会绑定到外层再把x放进当前作用域。int x 1; { int x x 1; // 右边那个 x 绑定外层值是 2 // 左边这个 x 从现在起才遮蔽外层 }不同类别的声明可见性起点是不一样的。这张表我建议直接贴在注释里声明类别可见性起点实现要点局部变量声明语句结束后初始化表达式里看到的是外层函数参数函数体开始参数之间是否互相可见取决于语言设计成员字段整个类型体内必须两遍收集字段之间可以互相引用顶层函数整个文件或整个模块需要先收集再解析类型名声明点之后与类型名/变量名歧义直接相关常量声明点之后与局部变量相同别搞特殊注意最后两行的区别。字段为什么可以两遍收集因为字段之间不存在遮蔽问题同一个类型里的字段名本来就应该是唯一的全收集起来再查反而更简单。函数为什么不支持声明点之后因为调用点可能在定义之前如果按顺序只能看到前面定义的函数那互相递归就没法写了。所以函数必须先收集全再解析体。这两条规则方向相反如果统一处理一定会错一个。2.3 分析结束后别把符号表扔掉很多人写语义分析符号表用完就释放了觉得反正后面代码生成也不需要名字了。这个想法在简单场景下能跑一旦要加调试信息、要加反射、要做错误消息的二次定位就立刻还债。最低限度每个符号条目要存这些东西名字的原始拼写不是 ID、声明位置文件、行、列、长度、类型、存储类别局部、参数、全局、字段、是否常量、所属作用域 ID。缺一个后面某个功能就做不了。比如未使用的变量警告这个功能需要遍历符号表看每个声明有没有被引用过。这就要求符号条目上有一个引用计数字段在解析标识符时自增。如果你在分析结束后把表扔了这个警告永远做不出来。再比如重命名重构把某个变量改名并更新所有引用需要知道每个引用指向哪个声明这又回到唯一 ID 的必要性上。只按名字文本匹配去改遇到同名遮蔽就全乱套了。3. 类型检查器的正确骨架合成属性向上继承属性向下3.1 用期望类型驱动遍历check 与 infer 两个入口教科书讲属性文法会说合成属性从子节点流到父节点继承属性从父节点流到子节点。翻译成代码就是两个函数def infer(node): # 不接受外部约束向上返回这个节点自己的类型 ... def check(node, expected): # 在期望是 expected这个约束下检查节点 actual infer(node) if not assignable(actual, expected): report(node.span, f类型不匹配期望 {expected}实际 {actual})只写infer是不够的。有些表达式在没有外部信息时根本推不出类型最典型的是空集合字面量、空引用、匿名函数。var x [];在很多强类型语言里是直接报错的因为空列表的元素类型未知而Listint x [];完全没问题因为期望类型从左边流下来了。这就是上下文相关最直观的一个体现同一个表达式在不同的上下文里会得到不同的类型。想支持这种写法check入口就必须存在不能只有infer。实际遍历的时候大部分语句节点的处理逻辑是先算期望再往下 checkdef check_assignment(node): lhs_type infer(node.target) # 赋值目标的类型 check(node.value, lhs_type) # 用目标类型约束右边 if not is_lvalue(node.target): report(node.target.span, 赋值左侧不是可取值的表达式)注意is_lvalue这个检查——赋值号左边必须是可被写入的位置不能是个字面量或者临时值。1 x文法上完全合法两边都是表达式语义上必须拒掉。这类结构性约束在类型检查器里到处都是取地址的操作数、的操作数、函数调用目标是否为可调用对象都是同一个套路。双向检查还有一个实际好处错误消息更精确。如果只有infer你在赋值语句里发现类型不对只能说这里类型不匹配有了check你能说清楚期望String实际int问题出在右边这个表达式上。用户看到的消息质量差了整整一个档次。3.2 类型相等、兼容与隐式转换的判定顺序类型检查器里最常写错的函数是assignable。很多人一上来就写if a b然后发现有一堆该过的地方过不去。正确的判定是有顺序的我一般这么排判定场景判定内容是否允许隐式转换赋值右边能否赋给左边允许加宽不允许窄化实参传递实参能否赋给形参同上返回值返回值能否赋给声明类型同上条件判断是否布尔类型多数语言不允许隐式相等比较两侧是否可比较有限通常要求同族下标访问是否整型允许整数提升加宽转换widening这条链要背清楚byte → short → int → long → float → double。这里有个反直觉的点——long到float会被算作加宽因为float的表示范围更大尽管它只有 24 位有效数字精度反而下降了。很多语言的规范明确这么规定实现时别自作聪明去拦它不然会跟其他编译器行为不一致。窄化narrowing就完全相反double → int必须显式转换因为会丢小数部分。判定assignable(src, dst)的逻辑是def assignable(src, dst): if src is ERROR_TYPE or dst is ERROR_TYPE: return True # 已经出过错不再报告 if src dst: return True if is_widening_path(src, dst): return True if is_subtype(src, dst): return True # 名义类型的继承关系 return False第二行那个ERROR_TYPE短路判断极其重要后面第 5 章会展开讲。还有一个坑类型相等判定要看语言用的是名义类型还是结构类型。名义类型下两个名字不同但结构完全一样的类型是不相等的结构类型下则相等。这个选择一旦定了就改不动会渗透到类型系统的每个角落包括泛型、子类型、序列化。做设计决策的时候想清楚别写到一半再改。3.3 常量表达式一个被低估的上下文相关约束case标签、数组长度、位域宽度、枚举初值、注解参数这些位置都要求一个编译期常量表达式。文法上它们就是普通的表达式语义上却必须能在编译期算出值。这个约束的实现依赖符号表条目的两个额外字段is_const和const_value。检查表达式时顺便做常量折叠遇到字面量直接给值遇到引用就查符号条目遇到运算就递归折叠子节点。def const_eval(node): if isinstance(node, IntLit): return node.value if isinstance(node, ResolvedName): if not node.is_const: report(node.span, f{node.name} 不是编译期常量) return None return node.const_value if isinstance(node, BinOp): left const_eval(node.left) right const_eval(node.right) if left is None or right is None: return None return apply_op(node.op, left, right) report(node.span, 这里需要一个常量表达式) return None这段代码有个细节值得说is_const和const_value是两回事。有些声明是只读但不是编译期常量——比如用函数返回值初始化的只读变量它是只读的没错但值要到运行时才知道。区分这两个概念否则case SOME_READONLY_VAR:会被错误地放行等到运行时才发现值不确定。另一个高频困惑为什么final int N someFunction();后面把它当数组长度会报错因为someFunction()不是常量表达式N 只能算只读变量不能算常量。这个区分在规范里写得很清楚但用户经常不理解报错信息里要把为什么不算常量讲明白比如直接指出初始化表达式不是编译期可求值的。4. 非看上下文不可的三件事重载、推断、泛型实例化4.1 重载解析先筛候选再算代价别边找边试同名函数有多个版本调用时该选哪个这是纯粹的上下文相关决策——单看f(1)这行你永远不知道选哪个必须把所有的f都找齐了再跟实参比对。正确流程是两阶段第一阶段筛出可行候选参数个数要匹配考虑默认参数和可变参数每个实参都要能转换成对应的形参类型泛型方法还要能完成类型推断。任何一个条件不满足从候选集里剔掉。如果剔完是空的报没有匹配的重载同时给出最接近的那个候选差在哪。第二阶段在可行候选里算转换代价取代价最小的。代价函数大致这么定转换类型代价例子精确匹配0int→int加宽转换1int→long装箱/拆箱2int→ 包装类型子类到父类2派生类 → 基类可变参数展开3三个int→int...def resolve_overload(candidates, args): viable [] for cand in candidates: if not arity_ok(cand, len(args)): continue total 0 ok True for arg, param in zip(args, cand.params): cost conversion_cost(arg.type, param.type) if cost is None: ok False break total cost if ok: viable.append((total, cand)) if not viable: report_best_near_miss(candidates, args) return ERROR_TYPE viable.sort(keylambda x: x[0]) if len(viable) 1 and viable[0][0] viable[1][0]: report_ambiguous(viable[0][1], viable[1][1], args) return ERROR_TYPE return viable[0][1]这里最容易被忽略的是歧义判定。两个候选代价相同编译器不能随便挑一个必须报歧义。否则同一份代码在不同编译器上会调用到不同函数这是灾难。实现上最大的坑是别边找边试。有些人图省事遍历候选列表遇到第一个能通过的就用。结果是有时候选中的不是最优匹配错误信息也一塌糊涂——因为你在还没看完全部候选的时候就下了结论。哪怕候选只有两三个也要老老实实先收齐、再打分。还有一个坑报没有匹配的重载的时候别把整张候选表都打印出来。用户看到十个签名会更懵。我的做法是找最接近的那一个——把每个候选的失败原因记下来第几个参数不匹配、为什么不能转换挑失败得最晚的那个不匹配的参数位置最靠后只报它。4.2 局部类型推断与合一算法的分工类型推断分两个层次不要混为一谈。第一个层次是局部推断只看初始化表达式把它的类型直接赋给变量。var x 42;推出x是整型。这种推断不需要任何全局信息也不需要解方程实现上就是先算右边再把类型抄给左边。绝大多数支持var的语言做的都是这个。第二个层次是全局推断函数不写返回类型靠函数体里的表达式反推。这就需要收集约束、解方程。经典算法是 Hindley-Milner核心是合一unification。def unify(t1, t2, subst): t1 prune(t1, subst) t2 prune(t2, subst) if t1 is t2: return if isinstance(t1, TypeVar): if occurs(t1, t2): raise TypeError(无限类型) subst[t1] t2 return if type(t1) is not type(t2): raise TypeError(f无法统一 {t1} 与 {t2}) if isinstance(t1, TypeCon) and t1.name t2.name: for a, b in zip(t1.args, t2.args): unify(a, b, subst) return raise TypeError(f无法统一 {t1} 与 {t2})occurs检查是必须的不是可选的优化。考虑λx. x x——把x用在自己身上会产生约束a a → b代进去就是无限展开的类型。没有occurs检查合一算法会直接死循环或者栈溢出。实操建议绝大多数工程场景下别做全局推断。原因很实在——错误信息会变得极其难懂。一个变量类型出错报错位置可能在完全不相干的地方因为约束是全局传导的。让用户写返回类型检查器就只需要做局部推理错误定位精确用户也不会困惑。全局推断适合学术场景和小型脚本语言产品级语言的取舍通常很保守。4.3 泛型实例化时机单态化、擦除与缓存键泛型怎么实现直接决定了上下文相关处理要在什么阶段完成。策略检查时机运行期形态主要代价单态化每个类型实参组合各自检查一遍每个组合一份独立代码代码体积膨胀编译变慢类型擦除只检查一次按约束检查统一为顶层类型运行时拿不到类型参数具体化检查一次保留元数据携带类型实参信息运行时元数据开销单态化最直接Listint和ListString是两个完全不同的类型各自生成代码。好处是运行时零开销坏处是代码膨胀——嵌套泛型能膨胀得非常夸张。类型擦除最省事但用户会遇到运行时拿不到类型参数的限制比如不能靠类型参数做分支判断也不能直接创建类型参数的实例。不管选哪种实例化缓存都是必需品。缓存键是(泛型符号ID, 实参类型ID 元组)值是这个实例化后的类型对象。def instantiate(generic_sym, type_args): key (generic_sym.sym_id, tuple(t.type_id for t in type_args)) if key in INSTANTIATION_CACHE: return INSTANTIATION_CACHE[key] if len(type_args) ! len(generic_sym.type_params): report(generic_sym.span, 类型实参个数不匹配) return ERROR_TYPE # 检查每个实参是否满足约束 for arg, constraint in zip(type_args, generic_sym.type_params): if constraint and not satisfies(arg, constraint): report(span_of(arg), f{arg} 不满足约束 {constraint}) inst build_instance(generic_sym, type_args) INSTANTIATION_CACHE[key] inst return inst这个缓存不只是为了性能更是为了类型身份。同一个泛型实例化两次必须返回同一个类型对象否则Listint会变成两个不同的类型赋值判定和相等判定全乱套。把INSTANTIATION_CACHE放在分析阶段的最外层别放在递归函数里当局部变量这个坑我踩过一次找了两天才定位到。5. 报错质量决定工具接受度语义错误的定位、抑制与级联5.1 用错误类型吸收级联而不是见错就停语义分析必须在出错之后还能继续跑。一发现错就抛异常中断用户改完这个再跑一次又冒出下一个来回十次才把错误清干净这体验非常糟糕。最有效的机制是引入一个错误类型有的叫未知类型、有的叫待定类型class ErrorType(Type): def __init__(self): super().__init__(?) def __eq__(self, other): return isinstance(other, ErrorType)这个类型参与任何运算的结果都是它自己能与任何类型互相转换。也就是说ERROR_TYPE int得到ERROR_TYPEERROR_TYPE赋给int也不报错。这样做的效果是一个表达式出错后错误状态顺着表达式树往上冒但不会在每个层级都重新报一遍。用户只看到根源那一条错误。def infer(node): ... if lhs is ERROR_TYPE or rhs is ERROR_TYPE: return ERROR_TYPE ...这套机制有个副作用要注意过度抑制会让用户改一处冒十处。我遇到过的情况是一个公共函数返回类型写错几百个调用点全部静默通过等修好那一个之后几百个错误一次性涌出来。所以抑制的范围要限制在同一条语句内跨语句不要抑制得太狠。更精细的做法是分级抑制规则同一个声明体内只报第一个类型错误表达式内部错误向上传播时不再报已经报过错的符号后续所有引用都不再报。这几条规则叠加起来一次编译能给出的有效错误数量就稳定了。5.2 把错误指向最小可疑区间每个 AST 节点都要记录源码区间起始位置加长度。这不是可选功能是基本功。报错的时候指向哪个节点是有讲究的。看这个例子int x hello 1;类型不匹配发生在运算上。如果你把错误指向整个赋值语句用户得自己在这一行里找问题指向整个hello 1也不太够指向最小的出错位置也就是hello这个操作数用户一眼就知道问题在哪。规则我总结成两条涉及两个操作数的不匹配指向那个不符预期的操作数涉及运算符本身的比如运算符不支持这个操作数类型指向运算符。还有个小技巧错误消息里把类型用用户的写法渲染出来而不是内部表示。内部可能是TypeRef(37, [TypeArg(2)])这种东西用户看到会直接崩溃。写一个to_string函数输出ListString成本很低收益很高。6. 一遍还是多遍语义分析流水线的切分策略6.1 resolve 与 check 分开的真实收益早期编译器喜欢把符号表建立、类型检查、代码生成全揉在语法分析的动作里一遍扫完就出结果。速度快内存省但代价是错误处理极难做漂亮前向引用基本没法支持。我的做法是至少切成两遍resolve解析名字、建符号表、绑定标识符和check类型检查。第一遍只干一件事给每个标识符找到它对应的声明把NameNode替换成ResolvedName。这一遍不检查类型遇到未定义的名字就报错并塞一个占位符号。第二遍拿着完整的符号信息做类型检查。因为此时所有名字都已经绑定好了第二遍完全不需要再管作用域的事逻辑干净得多。这么切的好处很实在错误分类清晰未定义归第一遍类型不匹配归第二遍可以单独给第一遍写单元测试可以在第一遍失败时降级处理让第二遍跳过相关节点继续跑最关键的是泛型、递归类型这些需要先看全部再判断的特性只有分成两遍才做得干净。代价是要遍历两次 AST多存一份绑定信息。这点开销相对编译时间来说可以忽略不计。6.2 为不完整代码留一条降级通路如果你做的是编辑器插件或者语言服务器代码永远是正在输入中的状态。这时候语义分析不能假设代码是完整的必须能在缺胳膊少腿的情况下给出部分结果。具体做法resolve 阶段遇到找不到的符号别中断创建一个占位符号类型标记为未知继续往下走check 阶段对占位符号一律返回ERROR_TYPE不报错最后把这一轮分析标记为不完整但依然把已经算出来的类型信息返回给编辑器做补全和悬停提示。这套降级机制和 5.1 的错误类型是同一套基础设施。设计的时候一起想别等到做编辑器适配了才发现要重构。还有一个绕不开的问题缓存失效。增量分析要知道改了哪一段、影响了哪些作用域。这个依赖前面说的唯一符号 ID 方案——改了函数 A 的函数体只需要重跑 A 的作用域其他符号 ID 不变。如果当初选了按名字查找的方案这里就得推倒重来。我个人的体会是语义分析这一层的复杂度不在算法而在规则的边界情况。作用域什么时候开始、改写什么时候生效、重载什么时候算歧义、常量什么时候不算常量——每一条规则单独看都简单凑在一起就是一堆互相牵扯的特例。写的时候把规则列成表贴出来比在脑子里记要靠谱得多。另外报错信息值得多花时间打磨用户对这个工具的容忍度很大程度上取决于它出错时说话好不好听。
