woaidongmao

1、我们能不能说不符合LR(1)的文法等价于二义文法？

2、在DBv1中文版P151第10行，说“应该指出，存在一些非二义文法，每种LR语法分析构造方法都会为其产生包含冲突分析动作的语法分析动作表。”既然二义文法是不可判定的，为什么书上面就能信誓旦旦地说存在不符合所有LR语法分析的文法仍然是非二义的呢？

1、显然不能。如果等价，那么就可以找到一个判定文法是否二义的方法了。

2、所有LR文法都是无二义的。如果一种文法可以通过LR语法分析构造方法构造无冲突语法分析表，就可以证明该文法是无二义的。但是如果文法不能通过LR语法分析构造方法构造出无冲突语法分析表，也不能证明它是二义的，即它有可能是二义的，也可能是无二义的。文法二义性是不可判定的，我的理解是：对任意一种文法，不存在一种确定的算法判断其是否二义的。但是有些文法还是可以判定的，例如LR文法；如果能找出文法中一个有不同语法树的句子，也可以判定该文法是二义的。虽然二义文法是不可判定的，但是“不符合所有LR语法分析的非二义文法”的存在性还是可以判定的吧。

“但是有些文法还是可以判定的，例如LR文法；如果能找出文法中一个有不同语法树的句子，也可以判定该文法是二义的。虽然二义文法是不可判定的，但是“不符合所有LR语法分析的非二义文法”的存在性还是可以判定的吧。”

如果我们学的东西都是对的话，根据推理，当然这有可能是对的。但问题这只是你的猜测而已。

到底是怎么判定，或者怎么证明，有人能解答不？

我们在设计一个编译程序时，应事先设法弄清所处理的语言是否由二义性文法定义的。但遗憾的是，并不存在这样的一个算法，它能判断任一上下文无关文法G是否为二义性文法，即上下文无关文法是否具有二义性是不可判定的。这是早在1962年至1963年就为Floyd, Contor和Chomsky等人证明了的事实。

虽然如此，我们却不必为此感到担心，因为这仅仅是前后文无关文法类中的一个最一般性的结论，对于某些具体的文法而言，我们仍可判断它们的二义性或无二义性.比如我们已经学过的LR文法.

而且,我们可以在学习的过程中发现检查文法二义性的充分条件.比如说,若一个文法既含有左递归,又含有右递归,则可以判定这个文法是二义的.举个例子:

A -> Aa | bA | a

则存在两个不同的规范推导都可以推导出同一个句子bbaa:

(1) A -> bA -> bbA -> bbAa -> bbaa (规范推导)

(2) A -> bA -> bAa -> bbAa -> bbaa (规范推导)

当然,这只是其中一个简单的例子,严谨的证明我不会- -!!! 不过我上网查证了这个结论的正确性.所以以后遇到这种类型的文法是可以直接断言其二义性的.

个人感觉,这种充分条件应该还是蛮多的.如果大家有新的发现的话,麻烦不吝赐教.

不符合LR(1)的文法与二义文法显然不等价。二义性文法绝不是LR文法，当然，也不是OPP文法或LL(k)文法。但正如DBv1中提到，存在非二义文法，每种LR语法分析构造方法都会为其产生包含冲突分析动作的语法分析动作表。所以不符合LR(1)的文法是二义文法的超集。

下面举出一个既不是二义文法，又不是LR(1)文法的例子。

S -> A S b | a

A -> ε

这个文法显然不是二义文法（我是没看出二义性，请大家看看）。下面给出DFA图中的状态I0

S’-> ? S, $

S -> ? A S b, $

S -> ? a, $

A -> ? , a

显然I0对于输入a存在shift/reduce冲突。因此这个文法也不是LR(1)文法。

其实
"A不可判断"
在某些时候说的是任何A不可判断
在某些时候说的是存在A不可判断
在某些时候说的是不存在判断A的普适算法

我觉得本次讨论来自于这种自然语言中的二义性。

至于LR(1)和二义性文法之间的关系之类，似乎大家早已烂熟，不至于讨论至此吧...>_<

在这个问题上，我们有时可以判断或证明某一个文法有二义性或无二义性，但我们没有一个普适的算法可以判断任何文法有无二义性。应该是上面的第三种理解。

hovey问“怎样判断或怎样证明"。或许这个问题更多的是对人来说的。如同办案。我们有很多种办法去寻找证据(如当我们发现一个文法是LR(1)文法时，我们就知道它一定是好人)，但我们没有制造证据的工厂。