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

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.

这应该有 How to avoid combinatorial explosion when generating test data 的子主题。

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

我发现的最好的系列文章之一是埃里克·利珀特 (Eric Lippert)，Every Binary Tree There Is, think BNF converted to binary operators then converted to AST when you read tree. However he uses Catalan (every branch has two leaves) and when I wrote my app I preferred Motzikin（一个树枝可以有一个或两个叶子）。

他还用 LINQ and I did mine in Prolog using DCG 在 C# 中完成了他的工作。

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

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

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

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

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

在此之后，您可以开始在自动化级别上分层。

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

虽然我的实际代码不是 public，但 and 最接近它，即 public。

一路上我在 Code Golf.

玩得很开心

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

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

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

How to synthesise compiler testing data?

compiler-construction

testing