综合 / 继承属性 · 与引擎解耦

属性文法：把 fold 形式化

解析流水线一页说过，parser 只该产结构，「算出多少」交给一次 fold。前面各页的引擎各自把这件事做成了 ad-hoc 的形态：Pratt 的 build 回调、combinator 的 map、递归下降里散落的构造调用。属性文法把它形式化成独立的一层。

1 · 综合属性与继承属性

定义 1.1（综合属性与继承属性） 树上一个节点的综合属性（synthesized attribute）由其子节点的属性算出，信息自底向上流动。继承属性（inherited attribute）由其父节点与左兄弟的属性算出，信息自顶向下与自左向右流动。给每条产生式配一组这样的规则，即得一份属性文法。

算术求值只需综合属性： $E \to E + T$ 的规则是「本节点的值等于两个子节点值之和」。而「把变量环境从根往下传」需要继承属性：环境不由子树决定，由上下文决定。

图 1-1 · 同一棵树上挂三套语义规则。树由所选引擎的真实 parse 产出，求值由 @vega/parsing/attribute 的 evaluate 完成；节点角标即该节点算出的属性值。可切换产树的引擎，观察同一套规则给出同一结果。

2 · 与引擎解耦

求值器找规则的方式是按「左部符号加子节点符号序列」查表，不依赖树是谁产的。这带来一条实际性质：Earley、LR、left-corner 产出的树喂进同一套属性规则，得到同一个结果。图 1-1 的第二张表逐引擎验证了这一点。

解耦的价值在于两侧可以独立更换。文法调整时语义规则不动；换引擎（比如从 LALR(1) 换到 GLR 以支持某处歧义）时语义规则也不动。相比之下，写在 Pratt 的 build 回调里的语义与那台引擎的控制流长在一起，换引擎意味着重写。

注 · 解耦的前提是各引擎产出的树逐字段相同。这对同一份文法通常成立，但有两个例外：文法歧义时不同引擎可能以不同顺序枚举多棵树（棵数相同，顺序不保证）；CNF 转换之类的文法变换会改变树形，此时规则必须按变换后的文法重写。图 1-1 的读数条把「各引擎的树是否相同」单独列了出来。第二个例外在本仓库里是现成的：cyk 的 parse 返回的是 CNF 文法的树而未折回原文法，n+n 得到的根是 S0、内部带 E_bin 与 T_+ 这些转换期符号，而 Earley 给出 E(E(T(F(n))) + T(F(n)))。按原文法写的属性规则匹配不上前者的任何一条产生式，因此 cyk 不在「换引擎语义规则不动」的适用范围内（见 CYK 与 Unger 一页）。

3 · S-attributed 与 L-attributed

任意属性文法的求值可能需要多趟遍历，甚至可能因属性间的循环依赖而无解。实践中只用两个受限子类。

S-attributed：只有综合属性。求值是一趟后序遍历，天然可与自底向上解析同步进行：yacc 的 $$ = $1 + $3 就是这个子类，语义动作在归约时执行。

L-attributed：综合属性加受限的继承属性，限制是「第 $i$ 个子节点的继承属性只能依赖父节点的继承属性与前 $i-1$ 个兄弟的综合属性」。这个限制刚好让一趟「下传继承、上传综合」的深度优先遍历成立，于是可与自顶向下解析同步：递归下降里「把上下文当参数传下去、把结果当返回值传上来」的写法就是 L-attributed 的手写形态。

定理 3.1 每个 S-attributed 文法都是 L-attributed 的；L-attributed 文法的属性可在一趟深度优先遍历中求出。

前半句由定义直得（无继承属性即满足限制）。后半句的构造是：进入节点时按规则算好各子节点的继承属性、递归、返回时算本节点的综合属性，限制保证了每个属性在被使用前已经算出。

4 · 一棵树上的多次 fold

图 1-1 的三套规则演示了「fold 的目标可以任意」：求值折成数字、前缀表达式折成字符串、树高折成一个与语言语义完全无关的结构度量。三者共用同一棵树与同一套遍历，差别只在合成函数。

这解释了为什么值得把语义从 parser 里分出来。真实编译器在同一棵树上要跑的 fold 有很多：类型检查、常量折叠、作用域解析、代码生成、格式化、lint 规则。它们各自是一次遍历，而树只需产出一次。

5 · 边界与替代

属性文法的形式化在 1968 年由 Knuth 提出，1980 年代的编译器生成器（yacc 的语义动作、Eli、LIGA）大量采用。今天它在编译器实现里的直接身影不多，原因有两个。

一是表达力的上限。真实语言的语义分析常需要跨树的信息流（全局符号表、类型推断的合一、跨模块引用），这些不适合表达成父子之间的属性依赖。工程上的做法是让树的遍历只做局部的事，把全局信息放进一个显式的可变上下文，那已经不是纯属性文法了。

二是多趟的现实。现代前端普遍是多趟的：先建符号表，再类型检查，再降级到中间表示。属性文法追求「一趟算完」的优势由此价值有限，而「哪些属性依赖哪些属性」这类调度问题在多趟结构里由趟次顺序显式表达，更好读。

它留下的遗产仍在：visitor 模式与 fold/cata 这些形态，本质上都是 S-attributed 求值；yacc 一族的 $$ 记号至今仍是最常见的语义规则写法。而「树到值应当与产树解耦」这条设计判据，比属性文法本身活得更久。

6 · 参考文献

Knuth, D. E. (1968). Semantics of context-free languages. Mathematical Systems Theory, 2(2), 127–145.
Paakki, J. (1995). Attribute grammar paradigms—a high-level methodology in language implementation. ACM Computing Surveys, 27(2), 196–255.
Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley. 第 5 章。