例 9 证明下面的文法是二义的：

S→ｉ S ｅ S｜ｉ S｜ｉ

【解】解题思路：

根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该

句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对

程序语言的了解，不难发现，这个文法应该是用来表示 if….else….结构的（用“i”代表“if”

或语句集，“e”代表“else”）。因此我们就要到 if….else…结构中去找二义性。我们知道，

程序语言一般都规定 else 部分是和它前面离它最近的没有被匹配的的 if 语句进行匹配。而

上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在 else 前面有两个

if（如句子 iiiei）， else 和不同的 if 进行匹配时就会产生不同的语义。

解答：

考虑句子 iiiei，存在如下两个最右推导：

S => iSeS => iSei => iiSei => iiiei

S => iS => iiSeS => iiSei => iiiei

编义技术（文法的二义性）