告訴BNF文法是否含糊不清的最簡單方法是什麼？

也就是說，有沒有一種工具可以自動顯示給定語法的完整語言，包括突出顯示歧義（如果有的話）？告訴BNF文法是否含糊不清的最簡單方法是什麼？

2011-01-24 user456584

也許這是相關的：http://cstheory.stackexchange.com/questions/4352/how-is-proving-a-context-free-language-to-be-ambiguous-undecidable – 2011-01-25 03:23:32

BNF風格的語法可能有一些特殊性，但總的來說，決定給定的上下文無關文法（如BNF）是否不明確是不可能的。

總之，不存在一個工具，因爲一般來說，該工具在數學上是不可能的。不過，可能有些特殊情況可能適用於您。

來源

2011-01-25 23:42:58

更具體地說，你可以檢查不管語法是否模棱兩可，但是你不能證明它不是。 – OrangeDog 2011-01-26 00:22:50

@OrangeDog：那麼，一般來說你不能證明它，但是對於某些語法來說是可能的（下面是一個你可以很容易地證明它的小語法：「goal = a;」）。 – 2012-04-16 23:30:04

一般來說，沒有。

但是作爲一種實用的方法，你可以做什麼，給定一個語法，是爲每個規則，列舉可能的有效終端/非終結符串，看看是否有任何規則有兩個或更多等價的派生（這將是含糊不清）。

我們的DMS Software Reengineering Toolkit是任意計算機語言的程序轉換系統，由明確的語法描述驅動。 DMS使用解析器生成器來驅動其GLR解析引擎。

DMS的解析器生成器可選地通過在所有語法規則上運行迭代加深搜索，在上面勾畫出模糊性檢查。這很實用，因爲它具有分析表來有效地指導選項的枚舉。您可以告訴它將此檢查運行到某個選定的深度。如果您選擇任意有趣尺寸的深度，可能需要很長時間，但實際上，3或4的深度足以發現大語法中引入的許多愚蠢歧義。在我們最初的語法調試過程中，我們通常會這樣做，並且在我們認爲我們已經非常正確的時候。

來源

2011-07-08 22:37:27

告訴BNF文法是否含糊不清的最簡單方法是什麼？

回答

相關問題