6

纯粹作为自学练习，我正在尝试使用该Parse::RecDescent模块在 Perl 中编写 Java 解析器。稍后我可能会使用其他其他工具（如Antlr、bison等）重新实现解析器。

但是，根据 Java 语言规范，我如何确保我的解析器确实生成了正确的解析？意思是，它对悬空else、运算符关联性和-precedence 等的正确处理。

一种方法是将我的解析器与已知的、无错误的解析器进行比较，方法是让两个解析器为大量测试 Java 程序生成 AST，然后比较两组 AST。

如果这确实是唯一的方法，我在哪里可以找到一套全面覆盖整个 Java 语言规范的大型测试 Java 程序？

我看过JavaParser，但它似乎没有详尽的测试数据集。

当然，另一种方法是亲自编写数以万计的测试 Java 程序，这对我来说是非常不切实际的，不仅在时间方面而且在确保其详尽无遗方面！

4

2 回答 2

6

要确定您是否有正确的答案，理想情况下您必须与某种标准进行比较。这对于计算机语言来说很难。

比较 AST 会很困难，因为没有这样的标准。每个构建 AST 的解析器都会构建一个 AST，其结构是由编写解析器的人设计的。

这意味着如果你构建了一个生成 AST 的解析器，并且你得到了其他人的生成 AST 的解析器，你会发现你选择的 AST 节点与另一个 AST 不匹配。现在你必须建立一个从你的 AST 到另一个的映射（你怎么知道这个映射是有效的？）。您可以尝试让您的解析器从另一个解析器生成 AST，但您会发现您生成的 AST 受您使用的解析技术的影响。

我公司生产的 Java 前端也有类似的问题（如果您想了解更多信息，请参阅 bio）。我们满足于测试答案是自洽的，然后我们对大段代码进行大量长期的体验测试。

我们的解决方案是：

  • （构建一个解析器，使用我们可以获得的最强解析技术（GLR）。这意味着我们可以识别某些其他解析技术（LL、LR、...）不容易识别的结构，从而生成其他解析器可以使用的 AST 节点很难生成。请参阅下面的评论以获取这很重要的示例。即便如此，我们生成 AST 节点的方式完全避免了我们必须按照大多数其他解析技术的要求手动编码 AST 节点构造；这往往会产生一些与手工编码的 AST 不同）。
  • 解析大量 Java 代码（生成 AST）以确保我们没有解析错误。[JDK 是一个很好的大小示例，很容易获得]
  • 我们的工具可以采用 AST 并重新生成（漂亮打印）源代码，并带有注释，但布局可能有所不同。我们验证已解析然后漂亮打印的代码也可以解析。我们重新 prettyprint 解析的漂亮打印版本；这应该与漂亮打印的版本相同，因为我们总是产生相同的布局。这个测试很好地表明我们的 AST 设计和实现不会丢失任何源代码
  • 构建符号表，解析名称的含义，并根据我们的前端验证合法的 Java 程序类型检查。这并没有告诉你任何关于 AST 本质的信息，只是它足够好（实际上，它已经足够好了！）因为类型检查任务非常复杂（去检查你当地的 Java 标准），它也很漂亮脆弱的。如果你没有把所有的东西都做好，当应用于大量代码时，类型检查很可能会失败。同样，JDK 对此进行了很好的测试。注意：没有名称和类型解析的 Java 解析器在实践中不是很有用
  • 根据上述结果生成包含超链接源代码的 JavaDoc 之类的交叉引用。这意味着很容易手动检查位代码以查看名称解析（因此是 AST 构造）是否正常。
  • 接受结果，将前端​​应用于各种程序分析和代码转换。我们发现偶尔出现的问题并修复它。

很难做到这一点。你必须接近并持续保持测试压力，特别是因为 Java 语言不断发展。（我们在 Java 8，而 Java 9 正受到威胁）。底线：构建这样的解析器并检查其健全性需要大量工作。

我们希望有一套独立的测试，但我们还没有在野外看到过。如果存在这些测试（我假设 Oracle 和 IBM 拥有它们），我希望它们真的不会直接测试解析和名称解析，而是测试一些代码编译和运行是否产生已知结果。由于我们没有构建编译器，因此如果我们拥有它们，我们将无法运行此类测试。我们将能够进行名称解析和类型一致性检查，这将很有帮助。

[我们实际上为许多语言前端这样做。你认为 Java 很难，用 C++ 试试这个]

于 2016-09-25T16:36:31.180 回答
1

我同意@ira-baxter 所写的。

简而言之，很容易验证您的解析器是否可以解析所有有效的源代码（只需向其抛出大量代码：我们这样做是为了测试 JavaParser，我们只是没有在存储库中放入数百兆字节的源代码） .

很难验证您生成的 AST 是否具有正确的形状，因为您可以有许多不同的方法来解析相同的代码并构建不同但同样有效的 AST。有些形状会更容易与其他形状一起使用，但没有“真理”可以坚持。

如果您的工具生成的 AST 与另一个解析器生成的 AST 不同，这并不一定意味着这两个解析器中的任何一个都是错误的，它可能只是一种设计选择。

于 2016-10-28T16:54:45.403 回答