⋖ ≐ ⋗ · 句柄 · 只识别

算符优先分析：优先级作为关系矩阵

把优先级做成数据的想法比 Pratt 早十年。Robert Floyd 在 1963 年提出的算符优先分析（operator-precedence parsing）同样绕开了分层非终结符，但它选了另一种表示：不给每个运算符一个数，给的是每对终结符一个关系。

这条路线在 1970 年代是编译器前端的主流之一，Fortran 与早期 Pascal 编译器都用过。它今天的价值主要是作为对照：把同一个问题的两种编码方式并置，能看清哪些性质来自「优先级」这个概念本身，哪些只是某种编码的副产物。

1 · 优先关系

设 $a$ 与 $b$ 是两个终结符，关系有三种： $a \lessdot b$ 表示 $a$ 让位于 $b$ （ $b$ 所在的句柄先归约）， $a \doteq b$ 表示两者同属一个句柄， $a \gtrdot b$ 表示 $a$ 先归约。

关系由文法机械算出，依据是两个辅助集合。 $\text{LEADING}(A)$ 收的不止是 $A$ 能推出的串的首终结符，还包括紧跟在首个非终结符之后的那个终结符： $A \Rightarrow^+ a\alpha$ 与 $A \Rightarrow^+ B\,a\,\alpha$ 两种情形的 $a$ 都算。 $\text{TRAILING}(A)$ 从右端对称定义。多收的这一项容易漏掉：对 $A \to B\,x$ 、 $B \to b$ 实测，buildTable 给出 $\text{LEADING}(A) = \{x, b\}$ ，而按「可能的第一个终结符」只会得到 $\{b\}$ 。少了 $x$ 就算不出 $x$ 与外层终结符的 $\gtrdot$ 关系，含此形态的文法会被误判为不可用。规则如下：

产生式右部里相邻的两个终结符 $a\,b$ 给出 $a \doteq b$ ；
形如 $a\,B$ 的相邻处，对每个 $b \in \text{LEADING}(B)$ 给出 $a \lessdot b$ ；
形如 $B\,b$ 的相邻处，对每个 $a \in \text{TRAILING}(B)$ 给出 $a \gtrdot b$ 。

图 1-1 · 从文法到关系矩阵到归约窗口。关系表与识别结果均由 @vega/parsing/op-precedence 的 buildTable / recognize 给出。文法可编辑；末行把关系插进输入串，⋖ 开一个句柄、⋗ 处发生归约。切到歧义文法或含相邻非终结符的文法，可见该方法拒绝的两类形态。

2 · 关系串与归约次序

矩阵的用法有一个极简的图示：把输入串的终结符逐个排开，在每对相邻终结符之间填上它们的关系。

$ ⋖ n ⋗ + ⋖ n ⋗ * ⋖ n ⋗ $

读法是：每段 $\lessdot \dots \gtrdot$ 之间的内容构成一个句柄，归约就发生在 $\gtrdot$ 处。栈驱动的算法照此运行：比较栈顶终结符与当前输入终结符， $\lessdot$ 或 $\doteq$ 则移进， $\gtrdot$ 则归约，直到栈上只剩起始符号。

n+n*n 的关系里 $+ \lessdot *$ 而 $* \gtrdot +$ ，n*n 先归约，得到与优先级一致的结果。这两个关系是从文法的分层结构（ $T \to T * F$ 嵌在 $E \to E + T$ 之内）自动算出的，不是人工指定的。文法里已经写着优先级，算法只是把它提取成了矩阵。

3 · 对文法形态的要求

算符优先分析对文法的要求比 LR 一族更严：

定义 3.1（算符文法） 一个文法是算符文法，若它的任何产生式右部都不含相邻的两个非终结符，且没有 ε 产生式。

相邻非终结符是致命的，因为算法的每步决策只看「栈顶终结符」与「当前输入终结符」，两个非终结符挨在一起时它们之间没有终结符可作依据。图 1-1 里那个 $S \to L = R$ 的文法之所以被拒，起因是 $L \to *\,R$ 里的 * R 之后 $R \to L$ 又可推出以非终结符起头的形态。

第二处限制是关系必须唯一：同一对 $(a, b)$ 被上述规则推出多种关系即为冲突，文法不可用。歧义文法必然在此触雷， $E \to E + E \mid n$ 实测报出的冲突对就是 $(+, +)$ 。

这两处限制在引擎里是两个独立的判据，读表时容易混。isOperatorPrecedence 要求既是算符文法、又无关系冲突，因此冲突列表为空不等于文法可用： $S \to A\,B$ 实测的 conflicts 长度为 0，而 isOperatorPrecedence 是 false，它栽在形态而非冲突上。

4 · 只识别的局限

一个更根本的局限：归约时算法知道「栈上某一段是一个句柄」，但不知道这个句柄对应哪条产生式，矩阵里没有这个信息。本模块因此只提供 recognize，返回接受或拒绝，没有 parse。

这不是实现偷懒，而是方法本身的性质，而且后果比「不建树」更重：不查产生式意味着它接受的串比文法生成的语言更多。拿 $E \to E + T \mid T$ 那份标准算术文法实测，把 recognize 与 Earley 的 recognize 逐项对照（两者吃同一个 grammar 对象），下列输入算符优先全部接受，而 Earley 全部拒绝：

输入	算符优先	Earley
`n+` `+n`	接受	拒绝
`n++n` `n*n` `n+n`	接受	拒绝
`(n` `n)` `n+n)`	拒绝	拒绝

规律是运算符缺操作数、运算符连排一概放行，而括号失配能被拦住。原因在于括号的两侧由 $\doteq$ 关系配对约束，运算符的元数则无人过问： $n\,{+}\,{+}\,n$ 的关系串处处合法，只是归约时凑不出一条真产生式，而算法从不检查这一步。工业实现的补救是在归约时按句柄的符号串去查一张产生式索引，但那已经是往 LR 的方向走了：LR 的项集自动机记住了「当前可能在哪条产生式的什么位置」，所以它归约时知道用哪条规则，也能建树（见 LR 一页）。

5 · 与 Pratt 的对照

两种方法编码的是同一件事，差别在三处：

	算符优先	Pratt
优先级的编码	终结符两两之间的关系， $O(n^2)$ 个格子	每个运算符一个标量， $O(n)$ 个数字
驱动方式	自底向上，显式栈，移进与归约	自顶向下，递归，带门槛的循环
产物	接受或拒绝	语法树

标量表示为什么够用？因为一维的大小关系已经能表达「谁先结合」这个偏序，成对关系带来的额外自由度（例如让 $a \lessdot b$ 同时 $b \lessdot a$ ）在合理的优先级体系里本就不该出现。矩阵的多余自由度正是冲突的来源。

注 · 结合性在两种表示里的落点不同。Pratt 用 rbp 的 $\pm 1$ 表达；算符优先则靠同级运算符之间的关系方向， $+ \gtrdot +$ 即左结合， $+ \lessdot +$ 即右结合。两者都是「同级时谁让位」的一次二选一，只是一个写成算术、一个写成矩阵格子。

6 · 参考文献

Floyd, R. W. (1963). Syntactic analysis and operator precedence. Journal of the ACM, 10(3), 316–333.
Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley. §4.6（算符优先分析）。