testing - 如何综合编译器测试数据？

Question

我正在编写一个简单的编译器作为学校作业。考虑到形式语法和其他规范，我正在寻找一种自动化方法来生成正面和负面测试数据来测试我的编译器。我正在处理的语言中等大小，有 38 个左右的非终端。为了便于说明，这里是语法的快照:

program: const_decl* declaration* ENDMARKER

# statement
stmt: flow_stmt | '{' stmt* '}' | NAME [stmt_trailer] ';' | ';'

stmt_trailer: arglist | ['[' expr ']'] '=' expr

flow_stmt: if_stmt | for_stmt | while_stmt | read_stmt ';' | write_stmt ';' | return_stmt ';'

return_stmt: 'return' ['(' expr ')']

if_stmt: 'if' '(' condition ')' stmt ['else' stmt]

condition: expr ('<'|'<='|'>'|'>='|'!='|'==') expr | expr

for_stmt: ('for' '(' NAME '=' expr ';' condition ';'
    NAME '=' NAME ('+'|'-') NUMBER ')' stmt)

是否有任何工具可以借助语法生成输入文件？手写测试太乏味或太弱，无法发现问题。这里有一个这种语言的例子:

void main() {
  int N;
  int temp;
  int i, j;
  int array_size;

  reset_heap;
  scanf(N);

  for (i = 0; i < N; i = i + 1) {
    scanf(array_size);
    if (array_size > max_heap_size) {
      printf("array_size exceeds max_heap_size");
    } else {
      for (j = 0; j < array_size; j = j + 1) {
        scanf(temp);
        heap[j] = temp;
      }
      heap_sort(array_size);
      print_heap(array_size);
    }
  }
}

自动生成可控的测试数据可以节省时间。鉴于语言的简单性，必须有一些方法可以有效地做到这一点。非常感谢任何指点和见解。

Answer 1

Any pointer and insight is greatly appreciated.

这应该有生成测试数据时如何避免组合爆炸的子主题。

虽然如果有工具可以执行此操作并具有为语法生成测试数据的相同需求，我不会感到惊讶，但我已经创建了一些一次性应用程序。

我找到的最好的系列文章之一是 Eric Lippert，Every Binary Tree There Is ，当你读树时，想想 BNF 转换为二元运算符然后转换为 AST。但是他使用Catalan (每个分支都有两片叶子)，当我编写我的应用程序时，我更喜欢 Motzikin (一个分支可以有一个或两个叶子)。

他还在 C# 中使用 LINQ 完成了他的工作我使用 DCG 在 Prolog 中完成了我的工作.

基于BNF或DCG生成数据并不难，真正的诀窍是限制扩展的区域和扩展的大小，并注入(inject)坏数据。

根据扩展区域，假设您想要测试三层深度的嵌套 if 语句，但必须具有可编译的有效代码。显然，您需要样板代码来使其编译，然后您开始通过添加或删除 else 子句来更改深度嵌套的 if 。因此，您需要加入约束，使样板代码保持不变，而测试部分是可变的。

根据扩展的大小，假设您要测试条件表达式。你可以很容易地计算出，如果你有很多运算符并且你想组合测试它们，你很快就会遇到组合爆炸。诀窍是确保您测试足够深入和足够广度，但不是每个组合。约束的司法使用再次有所帮助。

因此，所有这一切的重点是您从一个接受 BNF 并生成有效代码的工具开始。然后修改 BNF 以添加约束并修改生成器以了解生成代码示例的约束。

然后您针对无效数据修改 BNF，并同样修改生成器以理解这些规则。

在此之后，您就可以开始对自动化级别进行分层。

如果您确实走这条路并决定必须学习 Prolog，请查看 Mercury第一的。我没有用 Mercury 做过这个，但如果我再做一次，Mercury 在列表中名列前茅。

虽然我的实际代码没有公开，this和 this是最接近它的公共(public)的。

一路上我在 Code Golf 中玩得很开心.

在生成保留字或类型值等终端时，您可以使用包含有效数据和无效数据的预定义列表，例如对于 if 如果语言区分大小写，我会在列表中包含 if,If,IF,iF 等。对于无符号字节等值类型，我将包括 -1、0、255 和 256。

当我使用 +、-、* 和 ^ 测试基本的二进制数学表达式时，我生​​成了所有三个基本数字 -2、-1、0、1 和 2 的测试。我认为它没有用，因为我已经有数百个测试用例，但由于生成所有测试用例只花了几分钟，运行它只花了几个小时，令我惊讶的是它发现了一个我没有涵盖的模式。这里的要点是，与大多数人所说的必须进行许多测试用例相反，请记住，这只是通过更改一些约束在计算机上花费的时间，因此需要进行大量测试。