Lab1: Test Driver for PA1 (PA1+测试优化实验)

小实验 (Labs) 是 ICS 这门课程里的一些小练习题，旨在结合课堂知识解决一些实际PA中的问题。PA本身以外的实验也依旧存在很多值得研究并付出努力的地方。这些练习也能够有效帮助大家在完成PA过程中写出更优的实现。

Deadline: 2025年10月26日23:59:59

1 背景

在 PA1 的表达式求值部分，你已经实现了一个支持四则运算、优先级和括号的表达式求值器。然而，手动构造测试用例不仅繁琐，而且很难覆盖各种边界情况，通过肉眼比对来验证结果也十分低效。为了全面、高效地检验你的求值器是否正确与鲁棒，我们需要借助程序来自动生成大量且多样的测试用例。

在本实验中，你的任务是实现一个测试用例生成器 gen-expr。这个生成器需要能够产出符合特定条件的合法与非法表达式，并能自行计算出合法表达式的期望结果，从而实现测试的自动化。

2 实验要求

2.1 代码获取

git clone https://git.nju.edu.cn/icspa/lab1.git

你也可以从NEMU 的 gen-expr.c找到最初的样子，但为了提交方便，请使用上述项目框架。你需要完成lab1/src/expr.c使其能够随机生成表达式字符串并计算其正确结果。

在测试阶段，我们make，然后调用你产生的可执行程序 gen-expr 生成 1000 个表达式。生成的表达式需满足以下多样性要求，以确保测试的广度与深度。

至少包含一个同时使用 +, -, *, / 及 () 的复杂表达式
表达式的字符串长度应覆盖以下区间： 1~10、10~100、100~1000、1000~10000
参与运算的数值应覆盖以下区间： 0~10、10~100、……、100000000~1000000000
至少 10% 的表达式需包含除法运算，且除数不能为零
至少 10% 的表达式在计算其中间步骤时会触发无符号整数的上溢和下溢
至少 10% 的表达式出现寄存器访问和指针解引用
……

正如在酒吧里点炒饭的笑话一样，你不能总是期望用户的输入是合法的。为验证求值器的鲁棒性（在遇到不合法输入时不会崩溃），生成器还必须产出一定数量的非法表达式。对于这些非法表达式，你的求值结果应该为 invalid。

非法表达式的例子包括但不限于：

括号不匹配，如 (1+2 或 1+2)
操作数缺失，如 1+。
0 作为除数，如 1/0。
非法字符，如 1+a。

2.2 提交与查询

请保证文件目录不动，并支持make一键编译，并生成名为‘gen-expr’的可执行文件。

你可以直接在lab1目录下，make submit即可提交，无需管理分支。但需要保证你的token已正确存储到环境变量中。

在相应的oj页面查看 Online Judge 的返回结果，页面地址为：http://why.ink:8080/oj/ICS2025/Lab1/拼接实验项目与邮件给每人自己发的TOKEN。例如：TOKEN为AABB的同学可于http://why.ink:8080/oj/ICS2025/Lab1/AABB页面查看该实验的实时提交OJ结果（注意大小写）。

2.3 评分与正确性标准

测试用例分为 Easy 和 Hard。

对于 Easy 测试用例，我们会调用 ./gen-expr 生成 1000 个表达式，在确认你生成的表达式合法且结果正确后，我们会按照之前提到的标准验证你生成的的表达式是否满足最基础的多样性。

对于 Hard 测试用例，我们会将 ./gen-expr 生成的表达式输入到我们准备的存在错误的表达式求值器中。这个错误可能很隐蔽，但是只要你生成的表达式中有一条能够触发这些错误就算通过。

2.4 输入输出约定

在测试时，我们会单独编译并执行 ./gen-expr 1000 来生成 1000 个测试用例。你需要确保你的程序能正确处理命令行参数，并在标准输出上打印出指定数量的测试用例。每个测试用例占一行，格式为 <期望结果> <表达式字符串>。其中期望结果为 unsigned int 范围内的十进制整数，这一行除此之外的所有内容都会被当成表达式字符串。表达式字符串的长度不应超过 65536 个字符。例如：

$ cd lab1
$ make
$ ./gen-expr 3
9 (1+2)*3
invalid *0
0 0   + 1   -  (3   -  2)

框架已经帮你完成了绝大部分输入输出代码，你可以正常调用 gcc、python 等命令行工具来辅助生成表达式和计算结果，但除此之外的工具我们不做任何保证。此外，OJ 只实现了 PA1 监视点一节中定义的“扩展表达式求值”语法，请确保你生成的表达式不包含任何未说明的语法。

3 实验指南

除了实验要求中提到的方面，一个鲁棒的表达式求值器还需要考虑更多边界情况。你可以回顾自己在 PA1 中的实现，思考每个模块（如词法分析、主运算符分析、求值）可能存在的漏洞，并尝试在生成器中有针对性地构造相应的测试用例。

本次实验的核心目标是引导你思考如何设计一套完备的软件测试方案。在现实世界中，单一、固定的生成规则往往难以发现程序中所有潜在的 Bug。而完全随机生成的字符串触发 bug 的概率又会很低。因此，为了覆盖更多边界情况，你的表达式生成器可能需要一些“策略性”的硬编码。例如：

每 100 个表达式中强制生成一个包含除以零的表达式。
每 100 个表达式中强制生成一个包含深度嵌套括号的表达式。
每 100 个表达式中强制生成一个包含极大值的表达式。

虽然编写测试用例生成器比手动设计单个样例的工作量更大，单个样例的覆盖率也可能不及手动编写的测试用例，但它的优势是显而易见的。在大型项目中，许多 Bug 源于不经意的笔误或错误的 copy-paste，这些 bug 的位置往往是随机且难以预料的。专门为代码里已知难点设计的测试用例反而可能忽略这些“平凡”的错误。相比之下，随机生成的测试用例能够覆盖更广泛的程序执行路径，并且每次运行时都能产生全新的组合。这种“用海量随机用例探索程序行为”的策略，在软件测试领域还有一个更常见的变种叫模糊测试（Fuzzing）。相比于 Random Testing，Fuzzing 会更智能地生成大量的测试用例。这些用例大部分是随机的，但会概率性地故意在边界情况进行探索。在本次实验中，你实现的正是一个简单版本的 Fuzzing。除了上面这些技巧，Fuzzing 还会利用代码覆盖率工具来指导测试用例的生成，确保新生成的用例能够覆盖到更多未被执行过的代码路径。此次实验只是引起大家对这方面的兴趣和重视，就不要求过多了。

在 PA1 的实验指南中，我们已经提到了一些基础的实现思路。为了生成更多样性的测试用例，你可以为你的“生成函数”增加一系列参数来控制生成的表达式的复杂度、数值范围、是否包含特定运算符等。例如：

最小递归深度: 若当前递归深度未达到一个预设的阈值，则强制进入递归分支，生成更复杂的子表达式。
最大递归深度: 若当前递归深度达到一个预设的阈值，则强制生成一个数字，避免生成深度过深的表达式。
控制数值分布: rand() 函数正常是一个 0 到 RAND_MAX 的均匀分布。你可以在 rand() 前后增加一些逻辑来控制生成的数字变成指数分布（即生成 [0, 10) 和 [10000000, 100000000) 范围内数字的概率相等），避免绝大部分数字都是 9 位数的情况。
控制目标结果：若需要生成一个除以 0 的表达式，你可以在生成除法表达式时，强制右侧操作数的求值结果为 0。具体而言，在生成求值结果为 0 的表达式时，你可以先正常随机一个左操作数和运算符，然后根据运算符生成一个合适的右操作数使结果为 0。

然后在主函数中，根据规则或随机数来决定调用哪个“生成函数”以及传入哪些参数，从而生成多样化的表达式。

需要生成非法的表达式时，直接随机生成一个字符串当然没有问题，但它恰好构成一个有意义的非法表达式（如括号不匹配）的概率极低。更高效的方法是“先生成，再破坏”。在需要生成时非法表达式时，先按照上述方法生成一个合法的表达式，然后对这个合法的字符串进行随机的、有针对性的修改，来将其变为非法表达式。例如：

随机删除一个左括号或右括号。
在表达式开头、中间或末尾添加一个多余的运算符，如 (1+2)*3+。
将表达式中的某个数字替换为非法字符，如 1a+2。

在引入寄存器和指针解引用后，gcc 不再能够直接对原始的表达式求值，表达式的求值结果也开始因为寄存器和内存的值而变得不确定。在这个实验中，你可以假定所有寄存器的值均为 0，所有合法内存地址的值均为 0。合法内存地址定义为 0x80000000 到 0x87ffffff 之间的地址。至于如何求得含有寄存器和指针解引用的表达式的标准结果，你可以考虑在生成时输出两个表达式字符串，分别代表用于测试 NEMU 的表达式字符串和用于 gcc 求值的表达式字符串。并在用于 gcc 求值的字符串中将寄存器和指针解引用进行替换，然后再进行求值。例如你生成的表达式为 *($eax + 1) + 2，那么用于 gcc 求值的表达式字符串可能为 vaddr_read(0 + 1) + 2，其中 vaddr_read 会在内存地址越界时输出 invalid 并直接结束程序。这种技巧也被称为 Mock，能够有效地隔离被测代码与外部环境的依赖，从而简化测试的编写。

此外，一个 C 语言程序在运行时出现除以 0 的异常时，程序会被操作系统终止并输出 Floating point exception (core dumped)。这个 core dump 过程非常耗时，会极大地拖慢测试速度甚至导致 OJ 测试超时。避免这个问题的方法有很多种，这就作为一个额外的挑战留给你来解决。