如何判断文法是否二义性？S -> () | (S) | SS文法分析及Parse tree绘制疑问

1. 如何判断一个文法是否具有二义性？ #

首先得明确核心定义：一个文法是二义性的，当且仅当存在至少一个句子，它能生成两种或两种以上完全不同的语法分析树（Parse Tree），或者存在两种不同的最左推导/最右推导。

判断的核心思路就是找「反例」——只要能找到这样一个句子，就能直接证明文法是二义的。不过要注意：目前没有通用算法能自动判定任意文法是否二义（这是个不可判定问题），所以咱们只能靠人工找反例的方式验证。

具体可以按这个步骤来：

• 先挑选文法能生成的、带有重复嵌套/并列结构的句子（这类句子更容易出现多推导路径）
• 尝试用不同的产生式替换顺序（比如优先替换左边的非终结符，或优先替换右边的）生成同一个句子
• 如果能得到结构完全不同的语法分析树，那这个文法就是二义性的

2. 给定文法 S -> () | (S) | SS 是否为二义性文法？ #

答案是：是的，这个文法是二义性的。

咱们用具体句子()()()来验证——它可以通过两种不同的推导路径生成，对应两种不同的语法分析树：

第一种最左推导路径： #

1. S → SS（选择第三个产生式）
2. SS → ()S（第一个S选择第一个产生式）
3. ()S → ()SS（第二个S选择第三个产生式）
4. ()SS → ()()S（第一个S选择第一个产生式）
5. ()()S → ()()()（最后一个S选择第一个产生式）

对应的树结构：根节点S下分两个子S，第一个子S直接展开为()，第二个子S再分两个子S，各自展开为()和()。

第二种最左推导路径： #

1. S → SS（选择第三个产生式）
2. SS → SS()（第二个S选择第一个产生式）
3. SS() → ()S()（第一个S选择第一个产生式）
4. ()S() → ()()()（中间的S选择第一个产生式）

对应的树结构：根节点S下分两个子S，第二个子S直接展开为()，第一个子S再分两个子S，各自展开为()和()。

这两棵树的结构完全不同，却生成了同一个句子，所以这个文法是二义性的。

如何绘制Parse Tree（语法分析树）？ #

绘制的核心逻辑是从开始符号出发，跟着推导步骤逐步展开非终结符，直到所有叶子节点都是终结符，每一次产生式的替换对应树的分支生成。还是以()()()为例，给你拆解步骤：

1. 先画根节点：写开始符号S。
2. 如果第一步用了S -> SS，就在根节点S下方画两个并列的子节点，都标记为S。
3. 选其中一个子S，用S -> ()替换：给这个S画两个子节点，分别是(和)。
4. 对另一个子S，如果用S -> SS替换，就再画两个并列的子S，然后分别把这两个S替换成(和)。
5. 等所有叶子节点都是(或)，一棵完整的分析树就完成了。

换一种推导顺序的话，只是调整替换非终结符的先后顺序，最终会得到结构不同但叶子节点序列相同的树——这就是判断二义性的关键依据。

内容的提问来源于stack exchange，提问作者황인서