在今天的PA中, 我为我的简易调试器添加了表达式求值命令p. 而这也是我第一次切实感受到PA与其他oj实验的重要区别: PA中并没有提供测试数据, 因此需要我们自行设计单元测试并确保测试的完备性. 本文将简单介绍表达式求值命令的运行方式, 以及分享一些单元测试的经验教训.
表达式求值
表达式求值的命令格式为:
p <EXPR>
其中<EXPR>可以是任一表达式. 大概是为了实现的简洁起见, PA中目前只要求实现十进制数的简单无符号运算, 并未涉及变量或其他进制数的运算, 但是在搭建整体架构后, 添加更复杂的功能的难度并不高, 因此我还是以介绍表达式求值的整体原理为主.
相信大部分非cs专业的同学很少有与命令行打交道的机会, 因此在这里我想先介绍一下命令行(CLI)的大致原理. 大家要是在自己电脑上打开powershell(Windows)或终端(MacOS), 就会看到一个在黑客电影中经常出现的黑框框, 这就是命令行. 在命令行中, 我们可以通过输入指令来运行程序或执行操作. 命令行中的命令通常格式如下:
<CMD> [-f <value>] <ARGS> ...其中
<CMD>是我们要执行的程序或操作的名称;[-f <value>]标志了一些命令的选项, 其中<value>是可能需要的参数; 而<ARGS>则是程序执行所需的一些参数.当我们输入一条指令
<CMD>时, 我们的命令行会在环境中寻找这条指令. 环境指一系列路径, 其中很重要的一部分是$PATH环境变量中的路径, 用户自行下载的软件通常都要加入$PATH中才能够正常执行. 命令行程序能遍历环境中的所有路径, 并在其中寻找<CMD>对应的可执行程序.这也解释了在Day01中我将
$PATH弄没了会有什么后果在找到对应的程序后, 命令行会运行该程序, 并将我们所提供的命令选项和参数传入该程序, 从而正确执行我们想要的功能.
在简易调试器中, 指令的执行实际上原理也十分类似, 只不过简易调试器只需要在代码中所定义的命令集合(对应$PATH)中寻找与用户提供的命令(对应<CMD>)对应的命令, 并且将用户提供的参数(以字符串的形式)传入该命令对应的函数(对应可执行程序).
以上是对命令行和简易调试器运行原理的大致介绍, 了解了在简易调试器中调用指令的原理之后, 我们才能更直观地体会到完成p命令的两大难点: 语法分析和求值.
语法分析
在简易调试器中, 我们传入函数的参数是以字符串形式存储的, 这也就意味着对于
p 1 + 1
命令, 传入函数cmd_p的参数是字符串”1 + 1”. 而为了能够对这个式子进行运算, 我们必须设法从”1 + 1”中想办法提取出”1”, “+”和”1”. 实现这种语法分析有很多方式, 其中最简单的是使用正则表达式.
正则表达式(Regular Expression, 简称正则)是一种强大的工具, 用于匹配, 查找, 提取和操作文本数据. 它是一种基于特定规则的字符串模式, 通过定义规则, 能够对文本数据进行精确的匹配和处理.
我们可以通过为不同符号定义不同的规则, 并在所传入的参数字符串中对齐一一进行匹配, 从而解析出一系列可以参与运算的符号.
求值
很容易便能发现, 对于一个合法的表达式expr而言(然而这个项目最麻烦的其实是判断不合法的表达式QAQ), 以下规则成立:
- 一个数字是一个合法的表达式, 而且其值就是自身, 即不需要进行运算.
expr + expr是一个合法的表达式.expr * expr是一个合法的表达式.expr - expr是一个合法的表达式.expr / expr是一个合法的表达式.(expr)是一个合法的表达式, 其值是expr的值, 括号可以直接拆掉.
因此, 为了写一个进行求值的函数eval(expr), 我们只需要能够将表达式识别为以上六种情况的其中一种, 即可对其求值(数字)或将其分解为subexpr [+-*/] subexpr, 而我们只需要想办法求出subexpr的值, 我们就能对任意一个expr求值了.
那怎么求subexpr的值呢? 要是我们有一个能对表达式求值的函数就好了……哦! 我们有一个对表达式求值的函数eval呀! 太棒了, 那subexpr的值不就是eval(subexpr)吗?
这种思想被称为递归, 是我个人认为十分优美的一种算法设计思想. 我希望不熟悉递归的同学们可以仔细考虑一下以上思路, 看看能不能想明白:)
单元测试
为了确保我在以上两个部分中实现的准确性(实际上可以说是三个部分, 其中一个部分我为了思路的美观性并没有介绍), 我在编写的过程中对这两个功能都单独设计的单元测试, 即单独查看函数的功能是否正确.
单元测试在编写这样一个大型项目中是十分关键的. 在大型项目中, 一些看似简单的功能都需要多个模块配合实现, 而要是基础模块的正确性不能保障, 那么功能出现问题时是很难确定问题发生的具体位置的.
在我们发现bug并解决之后, 一定也要对相关的模块进行单元测试, 我就大致花了一个小时去寻找一个因我修改bug而引发的新bug.
单元测试是保证代码基本准确性的前提, 未经多轮测试过的代码几乎一定是有问题的. 在这种情况下, 人工涉及测试数据是很耗时耗力的, 因此可以使用代码随机生成大量测试数据进行测试.
And this concludes PA 1.2.