测试语法的歧义

Question

我正在为正式语言编写语法。理想情况下，我希望该语法是明确的，但这可能是不可能的。无论哪种情况，我都想在开发语法时了解所有可能的歧义。我怎样才能做到这一点？

到目前为止，当我开发一门语言时，大部分时间我都会求助于 Bison，为它编写一个 LR(1) 语法，以详细模式运行 Bison 并查看所有的 shift-reduce 和 reduce-reduce 冲突它告诉我。确保我在每种情况下都同意它的选择。

但是现在我在一个项目中，Bison 没有用于所需目标语言之一的代码生成器，并且已经使用了 ANTLR。此外，该语言不是 LR(1)，将其重写为 LR(1) 将需要在解析器完成后进行额外的语法检查，从而降低语法作为描述语言的工具的表现力。

所以我现在正在与 ANTLR 一起工作，给它我的语法，而且一切似乎都运行良好。但是 ANTLR 似乎不会在编译时检查歧义。例如，以下语法有歧义：

grammar test;
lst: '(' ')'      {System.out.println("a");}
   | '(' elts ')' {System.out.println("b");} ;
elts: elt (',' elt)* ;
elt: 'x' | /* empty */ ;

输入()可以解释为空列表，也可以解释为由单个空元素组成的列表。生成的解析器选择前一种解释，但我希望能够手动验证该选择。

• 是否有命令行开关可以用来让 ANTLR 告诉我关于歧义的信息？
• 或者我可以在语法文件中设置一个选项？
• 或者我应该使用其他工具来检查语法是否有歧义？
• 如果是这样，是否有一个已经可以读取 ANTLR 语法的方法，或者我是否必须删除所有操作并将其归结为 BNF？

该ANTLRErrorListener.reportAmbiguity方法表明 ANTLR可能能够在运行时执行一些歧义测试。但我想这只会告诉您对给定输入的解析是否有歧义。有什么策略可以利用它来检测所有的歧义，使用一组精心挑选的输入吗？

Answer 1

好吧，据我所知，ANTLR 没有真正的选项来检查歧义，除了如果您编写歧义语法并提供触发歧义的输入时它产生的错误。但是我知道一些可以检查歧义的工具。它们都有不同的语法，我不知道任何使用 ANTLR 语法的工具。

1. 一个名为AtoCC的软件有一个名为KfG的工具，可以检查歧义。
2. ACLA（使用语言近似的歧义检查）。
3. 上下文无关语法工具。

就我个人而言，我发现工具 3 最容易使用，但也是最有限的。但重要的是要注意，没有任何工具可以 100% 确定。如果工具说你的语法是模棱两可的，那它就是模棱两可的书面。

希望这可以帮助。