binding power · nud / led · 一个循环

Pratt parsing：优先级作为数据

表达式是解析里最不服管的部分。语句的结构由关键字领起，看一个 token 就知道走哪条产生式；而 1 + 2 * 3 里的 2 被 + 与 * 同时争夺，谁赢取决于优先级，1 - 2 - 3 里两个同级运算符的次序又取决于结合性。

递归下降的经典应对是把优先级编码进文法的层数：

expr   := term ( ('+' | '-') term )*
term   := factor ( ('*' | '/') factor )*
factor := NUMBER | '(' expr ')'

每一档优先级对应一个非终结符、一个函数、一层调用。代价是每加一个优先级档次就要改文法与代码结构。而真实语言有十几档，C 有十五档，最内层的数字字面量要穿过十五层函数调用才能抵达。

1 · 一张表取代一叠非终结符

Vaughan Pratt 在 1973 年第一届 POPL 上提出的做法把这件事反过来：优先级不再是结构，而是数据。每个运算符带一个数字，一个统一的循环按这些数字决定结合次序。

图 1-1 · Pratt 驱动循环的单步轨迹。左侧是 minBp 栈（栈顶即当前层的门槛，栈深即递归层数），右侧是本层已建成的 left 子树，下方是 binding power 表。轨迹在文法回调侧记账，执行的是 @vega/parsing/pratt 的真实驱动循环。切换示例可对照左结合、右结合、前缀与后缀四种情形下同一个循环的不同走法。

引擎的全部控制流就是图 1-1 代码面板里那十一行，与实现逐行对应。它对文法一无所知：文法由调用方以两组回调给出，prefix 说明某个 token 出现在「左边还没有操作数」的位置时怎么解析，infix 说明它出现在「左边已有一个操作数」时怎么解析。Pratt 原文分别称之为 nud（null denotation）与 led（left denotation）。

2 · 抓取门槛

驱动循环的核心是一个参数 minBp，即本层的抓取门槛。

定义 2.1（binding power） 每个中缀运算符配一个数 lbp（left binding power），表示它向左抓取操作数的力度。函数 parse(minBp) 的契约是：解析出一个子表达式，且只吸收 lbp 严格大于 minBp 的运算符；遇到不大于门槛的运算符即停止并返回，把它留给外层处理。

1 + 2 * 3 的走法：顶层以 parse(0) 启动，取到 1，看见 +（lbp 20 > 0）便吸收，递归解析右操作数时门槛升到 21；子层取到 2，看见 *（lbp 30 > 21）也吸收，得到 2 * 3；返回后顶层合成 1 + (2 * 3)。反过来 1 * 2 + 3 的子层看见 +（20 不大于 31）就停手，把 + 归还给顶层，先成的是 1 * 2。

表里的绝对数值无意义，只有相邻档次的相对大小有意义。

循环还有第二个出口，与门槛无关：infix 表里查不到当前 token 的规则时同样跳出。@vega/parsing 的实现让这两个出口共用一条 break（engines/pratt/pratt.ts 的 !rule || rule.lbp <= minBp），代价是「输入正常结束」与「表达式后面跟了垃圾」在循环内不可区分：末尾哨兵 (end) 没有 infix 规则，走的是同一条路。区分只能在顶层补做：parse() 在驱动返回后额外检查一次剩余 token 是否为哨兵，不是则报「表达式之后出现多余内容」。

3 · 结合性与右侧门槛

递归右操作数时传入的门槛记作 rbp，完全由 lbp 与结合性决定：

结合性	`rbp`	效果
左结合	`bp + 1`	同级运算符抓不动，归还外层，先成左边
右结合	`bp - 1`	同级运算符抓得动，被右侧吸收，先成右边

例 3.1 1 - 2 - 3 中，顶层吸收首个 - 后以门槛 21 解析右侧；子层取到 2，看见第二个 -（lbp 20 不大于 21）即停手，右操作数只是 2，结果为 (1 - 2) - 3。而 2 ^ 3 ^ 2 中 ^ 的 rbp 是 49，子层看见第二个 ^（50 大于 49）便吸收，结果为 2 ^ (3 ^ 2) = 512。

这个 $\pm 1$ 并不发生在引擎里。InfixRule 只有 lbp 与 build 两个成员，rbp 不在接口上；加减发生在文法侧的 build 回调内，即 engines/pratt/builders.ts 中 binaryLeft 写 p.parse(bp + 1)、binaryRight 写 p.parse(bp - 1)。引擎不只是对文法一无所知，它连「结合性」这个概念都没有：它看到的仅是回调递归时传下来的一个数。

4 · 特殊形态的统一处理

这几类形态无须任何新机制：

前缀运算符是 prefix 规则，它以自身的 bp 为门槛递归一次。取负的 bp 若低于 ^，则 -2 ^ 2 归约为 $-(2^2)$ ，与 C、Python、JavaScript 一致；若高于 ^，就会得到 $(-2)^2$ 。同一份代码，改一个数字即换语义。
后缀运算符是不递归的 infix 规则：消费左操作数后直接返回，不向右取任何东西。
左括号是 prefix 规则，规则体内以门槛 0 递归一次再要求闭合括号。门槛归零对应的即「括号内是一个独立的表达式」。

同一套机制还能覆盖三元运算符、函数调用的 (、下标的 [，它们都是「左边已有操作数」时的 led 规则，只是规则体内多做几步。Pratt 的分发依据是每个 token 在表达式里扮演的角色，优先级只是这套分发的一个参数。

5 · 与算符优先分析的分工

把优先级做成数据的想法比 Pratt 更早：Robert Floyd 在 1963 年的算符优先分析用一张终结符之间的关系矩阵（ $\lessdot$ 、 $\doteq$ 、 $\gtrdot$ ）驱动一个栈，同样避开了分层非终结符。两者的差别在于表的形状与驱动方式：矩阵是 $O(n^2)$ 的成对关系加自底向上的栈驱动，binding power 是 $O(n)$ 的一维标量加自顶向下的递归。算符优先分析一页把两者摆在同一份文法上对照。

注 · Pratt 的论文在当年是一篇对形式文法的公开反叛，标题即「Top Down Operator Precedence」，主张手写与可扩展性优于文法的形式化。这个立场使它长期被编译原理教材忽略，直到二十一世纪初被工业界实现重新发掘。今天的取舍是分工：语句层的结构适合用文法描述，表达式层的优先级适合用表描述。

6 · 手写的代价

TypeScript、rustc、Clang、Go 的 gc 都在表达式层采用这一族做法。直接收益是新增运算符只改表不动控制流，而分层文法要动结构；clang 那种需要在解析中途做上下文判断的场合也更容易插手，因为控制流始终在手里。

代价与所有手写方法相同：文法不再是显式的数据，没有工具能替作者检查它是否有歧义、某个运算符组合是否不可达。LR 一页的表驱动方法会在构表阶段就报出冲突。

这一节原先写的是「表里两个运算符的 bp 相等时会发生什么，只能靠测试发现」。实测下来这句不对，改的是正文而不是引擎：同 bp 的行为由 rule.lbp <= minBp 里的 <= 唯一确定，同级一律停手归还外层，等价于左结合，没有不确定性。真正无人警告的是在同一档 bp 上混用结合性。

警示 · 把 + 声明为 binaryLeft(20)、= 声明为 binaryRight(20)，两者相对的结合方向就取决于谁先出现：a + b = c 解析为 (a + b) = c，而 a = b + c 解析为 a = (b + c)。两次解析都不报错，也没有任何构表阶段能提示这处不对称，因为根本没有构表阶段。同一门语言写成产生式 E → E '+' E | E '=' E | id 则是歧义文法，LR 构表时会报移进-归约冲突。

7 · 参考文献

Pratt, V. R. (1973). Top down operator precedence. In Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (pp. 41–51).
Floyd, R. W. (1963). Syntactic analysis and operator precedence. Journal of the ACM, 10(3), 316–333.
Crockford, D. (2007). Top Down Operator Precedence. In A. Oram & G. Wilson (Eds.), Beautiful Code. O'Reilly.