形式陈述

若某 CFG 存在一个词具有两棵不同解析树，等价地具有两个不同最左推导，则该文法有歧义。若一个上下文无关语言的每个生成文法都有歧义，则称其固有歧义。歧义是文法属性，不是单纯的语言成员资格属性；判定任意 CFG 是否有歧义是不可判定问题。

直觉

有歧义意味着同一个符号串拥有两种结构解释。词本身没有告诉解析器应选哪棵树，因此后续求值、类型或翻译可能产生不同结果。

例子与边界

文法 $E\to E+E\mid E*E\mid a$$E\to E+E\mid E\ast E\mid a$ 对 a+a*a 有两种树。通过分层非终结符 $E\to E+T\mid T$$E\to E+T\mid T$、$T\to T*F\mid F$$T\to T\ast F\mid F$、$F\to a$$F\to a$ 可编码乘法优先级并消除这一例的歧义。但一个文法有歧义不代表其语言固有歧义；可能存在另一无歧义文法。反之，解析器用优先级冲突规则选定一棵树，只是额外规定语义，并没有证明原 CFG 无歧义。

推论与应用

识别和控制歧义是编程语言语法、自然语言处理与协议格式设计的核心工作；LL/LR 文法类通过更强的确定性条件换取可预测解析。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 1–9。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。