判断 BNF 语法是否有歧义的最简单方法是什么？
也就是说，是否有一种工具可以自动显示给定语法的完整语言，包括突出显示歧义（如果有）？
Namely, is there a tool out there that will automatically show the full language for a given grammar, including highlighting ambiguities (if any)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
BNF 样式语法可能有一些特殊性，但一般来说，确定给定的上下文无关语法（例如 BNF）是否有歧义是不可能的。
简而言之，不存在一种工具，因为一般来说，该工具在数学上是不可能的。不过，可能有一些特殊情况适合您。
There might be some peculiarity about BNF-style grammars, but in general, deciding whether a given context-free grammar (such as BNF) is ambiguous is not possible.
In short, there does not exist a tool because in general, that tool is mathematically impossible. There might be some special cases that could work for you, though.
一般来说，没有。
但作为一种实用的方法，你可以做的是，给定一个语法，对于每个规则，枚举有效终结符/非终结符的可能字符串，以查看任何规则是否具有两个或多个等效推导（这将是一个歧义）。
我们的 DMS 软件重组工具包是一个用于任意计算机语言的程序转换系统，由明确的语法描述。 DMS 使用解析器生成器来驱动其 GLR 解析引擎。
DMS 的解析器生成器将选择性地通过对所有语法规则运行迭代加深搜索来进行上面概述的歧义性检查。这是实用的，因为它具有解析表来有效地指导选择的枚举。您可以告诉它运行此检查到某个选定的深度。如果您选择任何有趣大小的深度，则可能需要很长时间，但实际上 3 或 4 的深度足以找到大型语法中引入的许多愚蠢的歧义。我们通常在最初的语法调试期间以及我们认为我们已经非常正确的时候这样做。
In general, no.
But as a practical approach, what you can do, is given a grammar, is for each rule, to enumerate possible strings of valid terminals/nonterminals, to see if any rule has two or more equivalent derivations (which would be an ambiguity).
Our DMS Software Reengineering Toolkit is a program transformation system for arbitrary computer langauges, driven by explicit grammar descriptions. DMS uses a parser generator to drive its GLR parsing engine.
DMS's parser generator will optionally the ambiguity check sketched above, by running an iterative deepening search across all grammar rules. This is practical because it has the parse tables to efficiently guide the enumeration of choices. You can tell it to run this check up to some chosen depth. It can take a long time if you choose a depth of any interesting size, but in fact a depth of 3 or 4 is sufficient to find many stupid ambiguities introduced in a large grammar. We generally do this during our initial grammar debugging, and at the point where we think we have it pretty much right.