派生树 · 卡塔兰数 · 不可判定

歧义：一个串几棵树

前面各页的确定性方法都会在某些文法上报冲突。冲突有两类成因，LR 一页已经点出：一类可以通过提高 lookahead 精度或改写文法消除，另一类不能。后者就是歧义。

这一页把歧义单独讲清楚，因为它决定了接下来几页的通用引擎为什么必要：它们要处理的就是确定性方法原理上处理不了的那部分。

1 · 定义与最短的例子

定义 1.1（歧义） 一份文法是歧义的，若存在某个串具有两棵以上不同的派生树。注意判据是树而非推导过程：同一棵树可以由不同顺序的推导步骤得到，那不算歧义。

最短的例子是 $E \to E + E \mid n$ 。串 n+n+n 有两棵树，分别对应 $(n+n)+n$ 与 $n+(n+n)$ 。文法没有说明该取哪一种，因为它对 + 的结合性一字未提。

图 1-1 · 同一个串的多棵派生树。棵数来自各引擎的真实 parse，末表逐项与卡塔兰数核对。可拖动滑块逐棵查看树形，或切到分层写法与悬垂 else 两个对照。

2 · 棵数是卡塔兰数

$E \to E + E$ 在 $n$ 个操作数上的树棵数恰好是卡塔兰数 $C_{n-1}$ ：

C_m = \frac{1}{m+1}\binom{2m}{m}, \qquad C_0, C_1, \dots = 1, 1, 2, 5, 14, 42, 132, \dots

定理 2.1 文法 $E \to E + E \mid n$ 在含 $n$ 个操作数的串上有 $C_{n-1}$ 棵派生树。

证明树的根把串分成左右两段，左段含 $i$ 个操作数、右段含 $n-i$ 个，$1 \le i \le n-1 $。左右子树互相独立，故棵数 $T_n$ 满足 $T_n = \sum_{i=1}^{n-1} T_i\,T_{n-i}$ ，且 $T_1 = 1$ 。这正是卡塔兰数的递推，故 $T_n = C_{n-1}$ 。∎

图 1-1 末表把这个断言逐项验证到 $n = 7$ （42 与 132）。数量级是指数的： $C_m \sim 4^m / (m^{3/2}\sqrt{\pi})$ 。这个增长率解释了为什么通用引擎必须提供「最多产出几棵树」的上限：把全部树物化出来在稍长的输入上就不可行，实用做法是产出一个共享的紧凑表示（SPPF，见 GLR 与 GLL 一页）而非枚举。

3 · 跨引擎交叉验证

歧义是文法的性质，与用什么方法解析无关。这构成一条极好的交叉验证：Earley、CYK、GLR、GLL、Unger、left-corner 的原理各不相同（chart、DP 三角表、多栈分叉、切分枚举），但它们在同一份文法与同一个串上必须报出同一个棵数。

图 1-1 的表格实测与此吻合：n+n+n 一律 2 棵，n+n+n+n 一律 5 棵，直到 42。这类跨实现的一致性比逐例对照期望值更能守住正确性，因为它不需要人工写出期望树。

42 这一档是终点而非任选的示例。表格统一给六台引擎传 maxTrees = 200，在这个上限下逐档实测：3 至 6 个操作数六台全部吻合卡塔兰数；到 7 个操作数（真值 132）时五台报 132，而 Unger 报 90 并置 stats.truncated，它先撞上的是三十万步的步数兜底而非树数上限；8 个操作数时 Unger 直接拒绝。所以「棵数一致」这条交叉验证只在各引擎都没触顶的档位内有效，而各引擎触顶的原因还不一样。

读这张表还要先看截断标记，而标记本身并不齐备。CYK 的 stats 只有 steps / cells / cnfRules 三项，没有 truncated：8 个操作数时它与 Earley 一样报 200，但 Earley 的 200 带截断标记、CYK 的 200 不带，单看棵数无从区分「恰好 200 棵」与「被截到 200」。跨实现对照的前提是各实现对「我没算完」有统一的自报方式，这一点在这套引擎里尚未对齐。

4 · 悬垂 else：真实语言里的歧义

歧义并非人造病例。经典的悬垂 else 出现在几乎所有 C 系语言的文法里，写成最小形态（ $i$ 代表 if 的头部， $e$ 代表 else， $x$ 代表一条语句）：

S -> i S | i S e S | x

串 iixex 有两棵树： $e$ 可以属于内层的 $i$ ，也可以属于外层。多数语言规定「就近匹配」，即属于内层，但这条规定写在语言规范的散文里，而不在文法里。

工程上的处理有三种。一是改文法，引入「已匹配语句」与「未匹配语句」两个非终结符，把就近匹配编码进结构；二是保留歧义文法，用生成器的显式优先级声明裁决（bison 的 %prec）；三是让 parser 报冲突并默认偏向移进，yacc 的默认行为刚好给出就近匹配的语义，这也是它被沿用几十年的原因之一。

5 · 不可判定性

一个自然的问题：能不能写个程序，输入一份文法、输出它是否歧义？

定理 5.1 上下文无关文法的歧义性判定问题是不可判定的。

这一结论由 Cantor、Floyd 与 Chomsky-Schützenberger 在 1961 至 1963 年间独立得到，证明路线是把后期对应问题（Post correspondence problem）归约到它。同族的不可判定问题还包括「两份文法是否等价」与「某文法的语言是否为全集」。

警示 · 不可判定意味着不存在通用判定程序，不意味着无法在实践中检测。工具的做法是保守近似。LR 构表报出的冲突是一个充分不必要的信号：有冲突未必歧义（可能只是 lookahead 不够），无冲突则必定无歧义（因为存在确定性解析器）。反向的启发式检测器（如 ambiguity checker 一族工具）会在有限深度内搜索歧义串，找到即确认歧义，找不到则不给结论。

6 · 参考文献

Cantor, D. C. (1962). On the ambiguity problem of Backus systems. Journal of the ACM, 9(4), 477–479.
Floyd, R. W. (1962). On ambiguity in phrase structure languages. Communications of the ACM, 5(10), 526.
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley. §7.3、§9.5。
Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press.