如何判断给定的上下文无关文法G是否具有二义性？

一、文法二义性的通用检验方法 #

文法二义性的定义是：若文法中存在至少一个句子，对应两棵不同的语法分析树（或两种不同的最左/最右推导），则该文法为二义文法。目前不存在能判定任意上下文无关文法是否二义的通用算法（该问题属于不可判定问题），常用的检验思路如下：

• 找反例验证：只要能找到任意一个存在两种不同合法推导的句子，就可以直接判定文法有二义性，这是证明文法二义性最直接的方法
• 文法子类判定：如果可以证明待检验文法属于某类天然无二义的文法子类（如LL(1)文法、LR(1)文法），则可以直接判定该文法无二义
• 消歧规则验证：如果需要对文法做优先级、结合性等消歧规则约束才能让所有句子有唯一推导，说明原文法存在二义性

二、给定文法的二义性判定 #

你给出的文法形式如下：

G = (V, T, P, S)
非终结符集合V = {S, A, B}
终结符集合T = {0, 1}
产生式集合P：
S → 0B | 1A
A → 0 | 0S | 1AA
B → 1 | 1S | 0BB

该文法的生成规律可通过归纳法证明：

• 非终结符S生成所有0、1数量相等的01串
• 非终结符A生成所有0的数量比1多1的01串
• 非终结符B生成所有1的数量比0多1的01串

目前没有在该文法中找到存在两种不同推导的句子，且通过构造LR(1)分析表可验证该文法不存在移进-归约冲突或归约-归约冲突，因此该文法属于无二义文法。

内容的提问来源于stack exchange，提问作者Suri