parsing - 测试(自动)解析器的更好方法？

我最近正在编写一种小型编程语言，并且已经完成了其解析器的编写。我想为解析器编写一个自动化测试(其结果是抽象语法树)，但是我不确定哪种方法更好。

首先，我尝试的只是将AST序列化为S表达式文本，并将其与我手工编写的预期输出文本进行比较，但是它存在一些问题:

序列化的文本和预期的输出(如空格)之间有微不足道的毫无意义的差异。例如，两者之间没有区别:

(attribute (symbol str) (symbol length))

(已序列化)和:

(attribute (symbol str)
           (symbol length))

(由我手写)的含义，但字符串比较当然可以区分它们。好的，我可以通过规范化解决它。

测试失败时，它不会简明显示实际树和预期树之间的差异。我只想显示一个差异节点，而不是整个树。

其次，我尝试编写S表达式解析器，并将解析器(待测试)生成的AST与S表达式解析器(我刚刚实现)从手写的预期输出生成的AST进行比较。但是我意识到，S表达式也必须进行测试，这确实是胡说八道。

我想知道测试解析器的典型且简单的方法是什么。

PS。我正在使用Java，并且不希望对第三方库有任何依赖关系。

最佳答案

为您寻找解析器的完全自动化和可扩展的单元测试框架，我建议采用以下方法:

输入错误

创建一组不正确的输入样本。然后向解析器提供每个解析器，以确保解析器拒绝它们。我想为定义预期输出的每个测试用例提供元数据，即解析器应该产生的特定错误代码/消息。

正确输入

与前面的情况一样，创建一组代表各种正确输入的样本。除了解析器接受所有输入的简单验证之外，仍然存在验证实际抽象语法树是否有意义的问题。

为了解决这个问题，我将执行以下操作:以一种众所周知的格式描述每个测试用例的预期AST，可以将其安全地解析(反序列化为实际的内存中AST结构)，并由认为没有错误的第3方解析器解析。 (针对您的情况)。自然的选择是XML，因为大多数语言/编程框架都涵盖了XML支持并提供了各自的(反序列化)功能。最好的解决方案是直接反序列化AST节点类型。由于存在方便的XML可视化编辑工具，因此构造大型测试用例也是可行的。

然后，我将使用visitor pattern构造一个AST比较器，将两个AST配对，并比较每对中的两个节点是否相等。但是，相等性是每个AST节点类型的特定操作。

笔记:

这种方法适用于大多数单元测试框架，例如JUnit。

AST到XML序列化是用于调试编译器的受欢迎的工具。

访客模式实现可以轻松地充当编译器内多个处理阶段的 Backbone 。

有一些可免费使用的编译器测试套件，这些套件可以为您的项目提供一些启发-例如，参见Ada编程语言的Ada Conformity Assesment Test Suite，尽管该测试套件处理的是更高级别的测试，而不仅仅是解析器测试。

关于parsing - 测试(自动)解析器的更好方法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4768927/