11

也就是说,是否有一种工具可以自动显示给定语法的完整语言,包括突出显示歧义(如果有的话)?

4

2 回答 2

5

BNF 风格的语法可能有一些特殊性,但一般来说,确定给定的上下文无关语法(例如 BNF)是否模棱两可是不可能的。

简而言之,不存在工具,因为一般来说,该工具在数学上是不可能的。不过,可能有一些特殊情况可能对您有用。

于 2011-01-25T23:42:58.563 回答
2

一般来说,没有。

但作为一种实用的方法,你可以做的是,给定一个语法,为每个规则枚举有效终端/非终端的可能字符串,看看是否有任何规则有两个或多个等价推导(这将是一个歧义)。

我们的DMS Software Reengineering Toolkit是一个针对任意计算机语言的程序转换系统,由明确的语法描述驱动。DMS 使用解析器生成器来驱动其 GLR 解析引擎。

DMS 的解析器生成器将通过在所有语法规则上运行迭代深化搜索来选择性地进行歧义检查。这是实用的,因为它具有解析表来有效地指导选择的枚举。您可以告诉它将此检查运行到某个选定的深度。如果您选择任何有趣大小的深度可能会花费很长时间,但实际上 3 或 4 的深度足以找到在大型语法中引入的许多愚蠢的歧义。我们通常在我们最初的语法调试过程中这样做,并且在我们认为我们非常正确的时候。

于 2011-07-08T22:37:27.677 回答