告诉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文法是否含糊不清的最简单方法是什么？

回答

相关问题