文法歧义 | Codeboy's Blog

形式陈述

定义关注语法树，而非任意推导顺序

上下文无关文法 $G$ 称为歧义的，当且仅当存在某个 $w\in L(G)$ ，它有两棵不同的语法树。等价地，它有两个不同的最左推导，也等价于有两个不同的最右推导。

限定“最左”或“最右”很重要。考虑

S\to AB,\qquad A\to a,\qquad B\to b.

既可以 $S\Rightarrow AB\Rightarrow aB\Rightarrow ab$ ，也可以 $S\Rightarrow AB\Rightarrow Ab\Rightarrow ab$ 。它们只是先展开左子树还是右子树不同，最终树完全相同。这不是歧义。最左推导固定每次展开最左边的非终结符，消除了这种无关的调度差异。

歧义也不要求两棵树一定算出不同数值。某些语义可能碰巧把它们解释成相同结果，甚至根本没有附加语义；只要解析树不同，文法性质就已经成立。

直觉

同一串字符，可以长出两棵树

字符串 id+id*id 只规定三个操作数和两个运算符的先后次序，没有自行说明先做加法还是乘法。上下文无关文法若同时允许下面两种结构，就产生了歧义：

text

加法作为根：id + (id * id)
乘法作为根：(id + id) * id

这里的括号用来展示结构，不是往待解析字符串里增添字符。两棵树的叶子从左到右都是同一个 id+id*id；不同的是哪个运算包含哪个运算。如果把三个 id 分别解释成 $2,3,4$ ，两种结构还会给出 $14$ 与 $20$ 两个结果。[1]

例子与边界

从歧义文法到保持语言的改写

考虑含加法、乘法及显式括号的文法

E\to E+E\mid E*E\mid(E)\mid\mathrm{id}.

对没有显式括号的字 id+id*id，两条不同的最左推导是

\begin{aligned} E&\Rightarrow E+E\Rightarrow\mathrm{id}+E \Rightarrow\mathrm{id}+E*E \Rightarrow\mathrm{id}+\mathrm{id}*E \Rightarrow\mathrm{id}+\mathrm{id}*\mathrm{id},\\ E&\Rightarrow E*E\Rightarrow E+E*E \Rightarrow\mathrm{id}+E*E \Rightarrow\mathrm{id}+\mathrm{id}*E \Rightarrow\mathrm{id}+\mathrm{id}*\mathrm{id}. \end{aligned}

第一条的根是加法，第二条的根是乘法。两条推导中途到达了相同的句型，并不会使它们此前生成的树结构变成同一棵树。

要规定乘法优先于加法、同级运算左结合，可以改为

\begin{aligned} E&\to E+T\mid T,\\ T&\to T*F\mid F,\\ F&\to\mathrm{id}\mid(E). \end{aligned}

$F$ 只允许一个操作数或一段显式括号表达式； $T$ 由这些因子相乘； $E$ 再把乘积相加。因而 id+id*id 只能把右侧乘法作为一个完整的 $T$ ，根部选择加法。左递归又使 id+id+id 的根对应最后一个顶层加号，形成 $(\mathrm{id}+\mathrm{id})+\mathrm{id}$ 。[1]

两套文法生成的是同一种合法表达式字符串，变化的是每个字符串允许的结构数。这里两套文法都含括号产生式；若只在改写后加入括号，就会扩大语言，不能再声称只是消除了原文法歧义。

唯一性的核心是顶层切分：若有括号外的加号，最右一个确定根部的 $E+T$ 切分；没有这样的加号时进入 $T$ ，由最右一个括号外乘号确定乘法切分；两者都没有时，只剩单个 id 或唯一配对的最外层括号。递归应用同一规则，就得到唯一语法树。

文法歧义与语言固有歧义

一个语言可能有歧义文法，也有无歧义文法，上面的表达式语言就是例子。语言 $L$ 称为固有歧义，则要求每一个生成 $L$ 的上下文无关文法都歧义。此时问题不是当前规则写得不好，而是无法在 CFG 范围内换一套规则彻底解决。

经典例子是

\{a^ib^jc^k:i,j,k\ge1,\ i=j\text{ 或 }j=k\}.

分别描述两个分支的自然文法会在 $a^nb^nc^n$ 上重叠；这个语言确实固有歧义，但仅观察两个分支重叠还不是证明。固有歧义要排除所有可能的等价 CFG，而不是只指出一套并集文法有两种推导。[2]

这一区分也适用于解析器报错。某个解析算法出现 shift/reduce 或 reduce/reduce 冲突，可能与文法歧义有关，也可能是该算法的前瞻或状态合并能力不足；不能据此直接判定语言固有歧义。反过来，解析器用优先级声明强制选择一棵树，是增加了一套选择政策，也不等于原 CFG 自动变成无歧义。[1]

推论与应用

为什么有例子可查，却没有通用判定器

若一个 CFG 有歧义，有限的两棵不同语法树及其共同的终端产出就是证据。可以按树的大小公平枚举所有有限推导树，逐一比较相同终端产出的树；一旦找到一对，就确认歧义。因此歧义 CFG 的集合是可识别的。

若一个文法没有歧义，这种枚举可能永远找不到证据。一般 CFG 的歧义性不可判定，所以不存在对每个输入文法都停机、并正确回答有无歧义的算法。结合余可识别语言的定义，无歧义 CFG 的集合是余可识别的，却不能再拥有一个一般的可识别过程，否则两边交错运行就会得到被排除的判定器。[2]

这不妨碍对具体文法做严格分析。分层表达式文法可以通过结构归纳证明唯一性；LL(1)和LR(1)可用有限分析表的无冲突条件确认确定可解析性。反方向却不能只看冲突：LALR的四词反例有无歧义的规范LR(1)表，合并状态后仍会发生归约冲突。不可判定性限制的是覆盖所有CFG的统一算法，不是每个具体文法的可分析性。

参考资料

[1] Cornell CS 4120，Grammars，语法树、歧义、表达式优先级与文法设计。

[2] John E. Hopcroft、Rajeev Motwani、Jeffrey D. Ullman，Introduction to Automata Theory, Languages, and Computation，第 3 版，2006，第 5 章的 CFG 歧义与第 9 章的不可判定性。

形式陈述 ​

定义关注语法树，而非任意推导顺序 ​

同一串字符，可以长出两棵树 ​

从歧义文法到保持语言的改写 ​

文法歧义与语言固有歧义 ​