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

Question

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

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

• 序列化文本和预期输出(如空格)之间存在微不足道的无意义差异.例如,之间没有区别:

  (attribute (symbol str) (symbol length))
  

  (已序列化)和:

  (attribute (symbol str)
             (symbol length))
  

  (这是我手写的)在他们的意思,但字符串比较当然区分他们.好的,我可以通过规范化来解决它.

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

我尝试的第二个是编写S表达式解析器并比较AST,解析器(待测试)生成AST,S表达式解析器(我刚刚实现)从手写的预期输出生成.但是我意识到S-expression也必须进行测试,这可能真的是无稽之谈.

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

PS.我正在使用Java,并且不希望任何依赖于第三方库.

Answer 1

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

输入不正确

创建一组错误输入的样本.然后为每个解析器提供解析,确保解析器拒绝它们.我最好为每个定义预期输出的测试用例提供元数据 - 解析器应该生成的特定错误代码/消息.

正确输入

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

为了解决这个问题,我将执行以下操作:以可以安全地解析的一些众所周知的格式描述每个测试用例的预期AST - 反序列化为实际的内存中AST结构 - 由第三方解析器认为是无错误的(适用于您的情况).自然的选择是XML,因为大多数语言/编程框架都涵盖XML支持并提供相应的(de)序列化工具.最好的解决方案是将反序列化直接转换为AST节点类型.由于存在方便的XML可视化编辑工具,因此构建大型测试用例是可行的.

然后我使用访问者模式构建一个AST比较器,它将两个AST配对并比较每对中的两个节点是否相等.但是,相等是每个AST节点类型的特定操作.

笔记:

• 这种方法适用于大多数单元测试框架,如JUnit.
• AST到XML序列化是一个用于调试编译器的受欢迎的工具.
• 访问者模式实现可以轻松地充当编译器内多个处理阶段的主干.
• 有免费提供的编译器测试套件可以为您的项目提供一些灵感 - 例如,参见Ada编程语言的Ada Conformity评估测试套件,尽管此测试套件处理更高级别的测试,而不仅仅是解析器测试.