1、我們能不能說不符合LR(1)的文法等價(jià)于二義文法？

2、在DBv1中文版P151第10行，說“應(yīng)該指出，存在一些非二義文法，每種LR語法分析構(gòu)造方法都會為其產(chǎn)生包含沖突分析動作的語法分析動作表。”既然二義文法是不可判定的，為什么書上面就能信誓旦旦地說存在不符合所有LR語法分析的文法仍然是非二義的呢？

1、顯然不能。如果等價(jià)，那么就可以找到一個判定文法是否二義的方法了。

2、所有LR文法都是無二義的。如果一種文法可以通過LR語法分析構(gòu)造方法構(gòu)造無沖突語法分析表，就可以證明該文法是無二義的。但是如果文法不能通過LR語法分析構(gòu)造方法構(gòu)造出無沖突語法分析表，也不能證明它是二義的，即它有可能是二義的，也可能是無二義的。文法二義性是不可判定的，我的理解是：對任意一種文法，不存在一種確定的算法判斷其是否二義的。但是有些文法還是可以判定的，例如LR文法；如果能找出文法中一個有不同語法樹的句子，也可以判定該文法是二義的。雖然二義文法是不可判定的，但是“不符合所有LR語法分析的非二義文法”的存在性還是可以判定的吧。

“但是有些文法還是可以判定的，例如LR文法；如果能找出文法中一個有不同語法樹的句子，也可以判定該文法是二義的。雖然二義文法是不可判定的，但是“不符合所有LR語法分析的非二義文法”的存在性還是可以判定的吧。”

如果我們學(xué)的東西都是對的話，根據(jù)推理，當(dāng)然這有可能是對的。但問題這只是你的猜測而已。

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

我們在設(shè)計(jì)一個編譯程序時(shí)，應(yīng)事先設(shè)法弄清所處理的語言是否由二義性文法定義的。但遺憾的是，并不存在這樣的一個算法，它能判斷任一上下文無關(guān)文法G是否為二義性文法，即上下文無關(guān)文法是否具有二義性是不可判定的。這是早在1962年至1963年就為Floyd, Contor和Chomsky等人證明了的事實(shí)。

雖然如此，我們卻不必為此感到擔(dān)心，因?yàn)檫@僅僅是前后文無關(guān)文法類中的一個最一般性的結(jié)論，對于某些具體的文法而言，我們?nèi)钥膳袛嗨鼈兊亩x性或無二義性.比如我們已經(jīng)學(xué)過的LR文法.

而且,我們可以在學(xué)習(xí)的過程中發(fā)現(xiàn)檢查文法二義性的充分條件.比如說,若一個文法既含有左遞歸,又含有右遞歸,則可以判定這個文法是二義的.舉個例子:

A -> Aa | bA | a

則存在兩個不同的規(guī)范推導(dǎo)都可以推導(dǎo)出同一個句子bbaa:

(1) A -> bA -> bbA -> bbAa -> bbaa (規(guī)范推導(dǎo))

(2) A -> bA -> bAa -> bbAa -> bbaa (規(guī)范推導(dǎo))

當(dāng)然,這只是其中一個簡單的例子,嚴(yán)謹(jǐn)?shù)淖C明我不會- -!!! 不過我上網(wǎng)查證了這個結(jié)論的正確性.所以以后遇到這種類型的文法是可以直接斷言其二義性的.

個人感覺,這種充分條件應(yīng)該還是蠻多的.如果大家有新的發(fā)現(xiàn)的話,麻煩不吝賜教.

不符合LR(1)的文法與二義文法顯然不等價(jià)。二義性文法絕不是LR文法，當(dāng)然，也不是OPP文法或LL(k)文法。但正如DBv1中提到，存在非二義文法，每種LR語法分析構(gòu)造方法都會為其產(chǎn)生包含沖突分析動作的語法分析動作表。所以不符合LR(1)的文法是二義文法的超集。

下面舉出一個既不是二義文法，又不是LR(1)文法的例子。

S -> A S b | a

A -> ε

這個文法顯然不是二義文法（我是沒看出二義性，請大家看看）。下面給出DFA圖中的狀態(tài)I0

S’-> ? S, $

S -> ? A S b, $

S -> ? a, $

A -> ? , a

顯然I0對于輸入a存在shift/reduce沖突。因此這個文法也不是LR(1)文法。

其實(shí)
"A不可判斷"
在某些時(shí)候說的是任何A不可判斷
在某些時(shí)候說的是存在A不可判斷
在某些時(shí)候說的是不存在判斷A的普適算法

我覺得本次討論來自于這種自然語言中的二義性。

至于LR(1)和二義性文法之間的關(guān)系之類，似乎大家早已爛熟，不至于討論至此吧...>_<

在這個問題上，我們有時(shí)可以判斷或證明某一個文法有二義性或無二義性，但我們沒有一個普適的算法可以判斷任何文法有無二義性。應(yīng)該是上面的第三種理解。

hovey問“怎樣判斷或怎樣證明"。或許這個問題更多的是對人來說的。如同辦案。我們有很多種辦法去尋找證據(jù)(如當(dāng)我們發(fā)現(xiàn)一個文法是LR(1)文法時(shí)，我們就知道它一定是好人)，但我們沒有制造證據(jù)的工廠。