2

我正在为一种小型查询语言构建一个 ANTLR 解析器。查询语言根据定义是模棱两可的，我们需要所有可能的解释 (AST) 来处理查询。

Example:

    query   : CLASSIFIED_TOKEN UNCLASSIFIED_TOKEN 
            | ANY_TOKEN UNCLASSIFIED_TOKEN 
            ;

在这种情况下，如果输入与两个规则都匹配，我需要获得 2 个具有两种解释的 AST。ANTLR 将返回第一个匹配的 AST。

你知道一种简单的方法来获得相同语法的所有可能的 AST 吗？我正在考虑多次运行解析器，在迭代之间“关闭”已经匹配的规则；这似乎很脏。有更好的主意吗？也许其他具有 java 支持的 lex/parser 工具可以做到这一点？

谢谢

4

2 回答 2

2

如果我是你，我会消除歧义。您通常可以通过使用上下文信息来确定实际触发的语法规则来做到这一点。例如，在

C* X;

在 C 中（不是您的语言，但这只是为了说明一点），您无法判断这是否只是无意义的乘法（用 C 编写是合法的），还是声明类型为“指向 C 的指针”的变量 X ”。因此，有两个有效（模棱两可）的解析。但是，如果您知道 C 是一种类型声明（从某些上下文，可能是更早的代码声明），您可以破解解析器以消除不适当的选择，并最终得到一个“正确”的解析，没有歧义。

如果您真的没有上下文，那么您可能需要一个 GLR 解析器，它会在您的最终树中愉快地生成两个解析。我不知道有任何可用于 Java 的。

我们的DMS Software Reengineering Toolkit [不是基于 Java 的产品] 具有 GLR 解析支持，我们一直使用它来解析具有歧义的困难语言。我们处理上面的 C 示例的方式是生成两个解析，因为 GLR 解析器很乐意这样做，然后如果我们有其他信息（例如符号表），则对树进行后处理以删除不适当的解析。

DMS 旨在支持任意语言的自定义分析和转换，例如您的查询语言，并且可以轻松定义语法。一旦你有了上下文无关的语法（是否有歧义），DMS 就可以解析代码，你可以决定以后做什么。

于 2012-07-26T20:23:07.520 回答
1

我怀疑您是否会让 ANTLR 返回多个解析树，而无需大规模重写代码。

我相信您将不得不将歧义划分为自己的明确语法并多次运行解析。如果歧义产生式的总数很大，您可能会拥有一组难以管理的不同语法。例如，对于三个二元歧义（两个选择），您最终会得到 8 个不同的语法，但如果一个歧义分支消除了一个或多个其他歧义，则可能会稍微少一些。

祝你好运

于 2012-07-26T19:16:43.217 回答