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)文法時，我們就知道它一定是好人)，但我們沒有制造證據的工廠。