表达式求值

在TRM中, 寄存器(包括PC)和内存中的值唯一地确定了计算机的一个状态. 因此从道理上来讲, 打印寄存器和扫描内存这两个功能一定可以帮助我们调试出所有的问题. 但为了方便使用, 我们还希望简易调试器能帮我们计算一些带有寄存器和内存的表达式. 所以你需要在简易调试器中添加表达式求值的功能. 为了简单起见, 我们先来考虑数学表达式的求值实现.

数学表达式求值

给你一个表达式的字符串

"5 + 4 * 3 / 2 - 1"

你如何求出它的值? 表达式求值是一个很经典的问题, 以至于有很多方法来解决它. 我们在所需知识和难度两方面做了权衡, 在这里使用如下方法来解决表达式求值的问题:

首先识别出表达式中的单元
根据表达式的归纳定义进行递归求值

词法分析

"词法分析"这个词看上去很高端, 说白了就是做上面的第1件事情, "识别出表达式中的单元". 这里的"单元"是指有独立含义的子串, 它们正式的称呼叫token. 具体地说, 我们需要在上述表达式中识别出5, +, 4, *, 3, /, 2, -, 1这些token. 你可能会觉得这是一件很简单的事情, 但考虑以下的表达式:

"0x80100000+   ($a0 +5)*4 - *(  $t1 + 8) + number"

它包含更多的功能, 例如十六进制整数(0x80100000), 小括号, 访问寄存器($a0), 指针解引用(第二个*), 访问变量(number). 事实上, 这种复杂的表达式在调试过程中经常用到, 而且你需要在空格数目不固定(0个或多个)的情况下仍然能正确识别出其中的token. 当然你仍然可以手动进行处理(如果你喜欢挑战性的工作的话), 一种更方便快捷的做法是使用正则表达式. 正则表达式可以很方便地匹配出一些复杂的pattern, 是程序员必须掌握的内容. 如果你从来没有接触过正则表达式, 请查阅相关资料. 在实验中, 你只需要了解正则表达式的一些基本知识就可以了(例如元字符).

学会使用简单的正则表达式之后, 你就可以开始考虑如何利用正则表达式来识别出token了. 我们先来处理一种简单的情况 -- 算术表达式, 即待求值表达式中只允许出现以下的token类型:

十进制整数
+, -, *, /
(, )
空格串(一个或多个空格)

首先我们需要使用正则表达式分别编写用于识别这些token类型的规则. 在框架代码中, 一条规则是由正则表达式和token类型组成的二元组. 框架代码中已经给出了+和空格串的规则, 其中空格串的token类型是TK_NOTYPE, 因为空格串并不参加求值过程, 识别出来之后就可以将它们丢弃了; +的token类型是'+'. 事实上token类型只是一个整数, 只要保证不同的类型的token被编码成不同的整数就可以了. 框架代码中还有一条用于识别双等号的规则, 不过我们现在可以暂时忽略它.

这些规则会在简易调试器初始化的时候通过init_regex()被编译成一些用于进行pattern匹配的内部信息, 这些内部信息是被库函数使用的, 而且它们会被反复使用, 但你不必关心它们如何组织. 但如果正则表达式的编译不通过, NEMU将会触发assertion fail, 此时你需要检查编写的规则是否符合正则表达式的语法.

给出一个待求值表达式, 我们首先要识别出其中的token, 进行这项工作的是make_token()函数. make_token()函数的工作方式十分直接, 它用position变量来指示当前处理到的位置, 并且按顺序尝试用不同的规则来匹配当前位置的字符串. 当一条规则匹配成功, 并且匹配出的子串正好是position所在位置的时候, 我们就成功地识别出一个token, Log()宏会输出识别成功的信息. 你需要做的是将识别出的token信息记录下来(一个例外是空格串), 我们使用Token结构体来记录token的信息:

typedef struct token {
  int type;
  char str[32];
} Token;

其中type成员用于记录token的类型. 大部分token只要记录类型就可以了, 例如+, -, *, /, 但这对于有些token类型是不够的: 如果我们只记录了一个十进制整数token的类型, 在进行求值的时候我们还是不知道这个十进制整数是多少. 这时我们应该将token相应的子串也记录下来, str成员就是用来做这件事情的. 需要注意的是, str成员的长度是有限的, 当你发现缓冲区将要溢出的时候, 要进行相应的处理(思考一下, 你会如何进行处理?), 否则将会造成难以理解的bug. tokens数组用于按顺序存放已经被识别出的token信息, nr_token指示已经被识别出的token数目.

如果尝试了所有的规则都无法在当前位置识别出token, 识别将会失败, 框架代码会输出当前token的位置(当表达式过长导致在终端里输出需要换行时, ^可能无法指示正确的位置, 此时建议通过输出的position值来定位token的位置). 这通常是待求值表达式并不合法造成的, make_token()函数将返回false, 表示词法分析失败.

实现算术表达式的词法分析

你需要完成以下的内容:

为算术表达式中的各种token类型添加规则, 你需要注意C语言字符串中转义字符的存在和正则表达式中元字符的功能.
在成功识别出token后, 将token的信息依次记录到tokens数组中.

调试公理

The machine is always right. (机器永远是对的)
- Corollary: If the program does not produce the desired output, it is the programmer's fault.
Every line of untested code is always wrong. (未测试代码永远是错的)
- Corollary: Mistakes are likely to appear in the "must-be-correct" code.

这两条公理的意思是: 抱怨是没有用的, 接受代码有bug的现实, 耐心调试.

jyy曾经将它们作为fact提出. 事实上无数程序员(包括你的学长学姐)在实践当中一次又一次验证了它们的正确性, 因此它们在这里作为公理出现.

如何调试

不要使用"目光调试法", 要思考如何用正确的工具和方法帮助调试
- 程序设计课上盯着几十行的程序, 你或许还能在大脑中像NEMU那样模拟程序的执行过程; 但程序规模大了之后, 很快你就会放弃的: 你的大脑不可能模拟得了一个巨大的状态机
- 我们学习计算机是为了学习计算机的工作原理, 而不是学习如何像计算机那样机械地工作
使用assert()设置检查点, 拦截非预期情况
- 例如assert(p != NULL)就可以拦截由空指针解引用引起的段错误
结合对程序执行行为的理解, 使用printf()查看程序执行的情况(注意字符串要换行)
- printf()输出任意信息可以检查代码可达性: 输出了相应信息, 当且仅当相应的代码块被执行
- printf()输出变量的值, 可以检查其变化过程与原因
使用GDB观察程序的任意状态和行为
- 打印变量, 断点, 监视点, 函数调用栈...

如果你突然觉得上述方法很有道理, 说明你在程序设计课上没有受到该有的训练.

为什么printf()的输出要换行?

如果不换行, 可能会发生什么? 你可以在代码中尝试一下, 并思考原因, 然后STFW对比你的想法.

系统设计的黄金法则 -- KISS法则

这里的KISS是Keep It Simple, Stupid的缩写, 它的中文翻译是: 不要在一开始追求绝对的完美.

你已经学习过程序设计基础, 这意味着你已经学会写程序了, 但这并不意味着你可以顺利地完成PA, 因为在现实世界中, 我们需要的是可以运行的system, 而不是求阶乘的小程序. NEMU作为一个麻雀虽小, 五脏俱全的小型系统, 其代码量达到3000多行(不包括空行). 随着PA的进行, 代码量会越来越多, 各个模块之间的交互也越来越复杂, 工程的维护变得越来越困难, 一个很弱智的bug可能需要调好几天. 在这种情况下, 系统能跑起来才是王道, 跑不起来什么都是浮云, 追求面面俱到只会增加代码维护的难度.

唯一可以把你从bug的混沌中拯救出来的就是KISS法则, 它的宗旨是从易到难, 逐步推进, 一次只做一件事, 少做无关的事. 如果你不知道这是什么意思, 我们以上文提到的str成员缓冲区溢出问题来作为例子. KISS法则告诉你, 你应该使用assert(0), 就算不"得体"地处理上述问题, 仍然不会影响表达式求值的核心功能的正确性. 如果你还记得调试公理, 你会发现两者之间是有联系的: 调试公理第二点告诉你, 未测试代码永远是错的. 与其一下子写那么多"错误"的代码, 倒不如使用assert(0)来有效帮助你减少这些"错误".

如果把KISS法则放在软件工程领域来解释, 它强调的就是多做单元测试在新窗口中打开: 写一个函数, 对它进行测试, 正确之后再写下一个函数, 再对它进行测试... 一种好的测试方式是使用assertion进行验证, reg_test()就是这样的例子. 学会使用assertion, 对程序的测试和调试都百利而无一害.

KISS法则不但广泛用在计算机领域, 就连其它很多领域也视其为黄金法则, 这里在新窗口中打开有一篇文章举出了很多的例子, 我们强烈建议你阅读它, 体会KISS法则的重要性.

递归求值

把待求值表达式中的token都成功识别出来之后, 接下来我们就可以进行求值了. 需要注意的是, 我们现在是在对tokens数组进行处理, 为了方便叙述, 我们称它为"token表达式". 例如待求值表达式

"4 +3*(2- 1)"

的token表达式为

+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| NUM | '+' | NUM | '*' | '(' | NUM | '-' | NUM | ')' |
| "4" |     | "3" |     |     | "2" |     | "1" |     |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+

根据表达式的归纳定义特性, 我们可以很方便地使用递归来进行求值. 首先我们给出算术表达式的归纳定义:

<expr> ::= <number>    # 一个数是表达式
  | "(" <expr> ")"     # 在表达式两边加个括号也是表达式
  | <expr> "+" <expr>  # 两个表达式相加也是表达式
  | <expr> "-" <expr>  # 接下来你全懂了
  | <expr> "*" <expr>
  | <expr> "/" <expr>

上面这种表示方法就是大名鼎鼎的BNF在新窗口中打开, 任何一本正规的程序设计语言教程都会使用BNF来给出这种程序设计语言的语法.

根据上述BNF定义, 一种解决方案已经逐渐成型了: 既然长表达式是由短表达式构成的, 我们就先对短表达式求值, 然后再对长表达式求值. 这种十分自然的解决方案就是分治法在新窗口中打开的应用, 就算你没听过这个高大上的名词, 也不难理解这种思路. 而要实现这种解决方案, 递归是你的不二选择.

为了在token表达式中指示一个子表达式, 我们可以使用两个整数p和q来指示这个子表达式的开始位置和结束位置. 这样我们就可以很容易把求值函数的框架写出来了:

eval(p, q) {
  if (p > q) {
    /* Bad expression */
  }
  else if (p == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
  }
  else if (check_parentheses(p, q) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    return eval(p + 1, q - 1);
  }
  else {
    /* We should do more things here. */
  }
}

其中check_parentheses()函数用于判断表达式是否被一对匹配的括号包围着, 同时检查表达式的左右括号是否匹配, 如果不匹配, 这个表达式肯定是不符合语法的, 也就不需要继续进行求值了. 我们举一些例子来说明check_parentheses()函数的功能:

"(2 - 1)"             // true
"(4 + 3 * (2 - 1))"   // true
"4 + 3 * (2 - 1)"     // false, the whole expression is not surrounded by a matched
                      // pair of parentheses
"(4 + 3)) * ((2 - 1)" // false, bad expression
"(4 + 3) * (2 - 1)"   // false, the leftmost '(' and the rightmost ')' are not matched

至于怎么检查左右括号是否匹配, 就当作一个程序设计作业, 留给聪明的你来思考吧!

上面的框架已经考虑了BNF中算术表达式的开头两种定义, 接下来我们来考虑剩下的情况(即上述伪代码中最后一个else中的内容). 一个问题是, 给出一个最左边和最右边不同时是括号的长表达式, 我们要怎么正确地将它分裂成两个子表达式? 我们定义"主运算符"为表达式人工求值时, 最后一步进行运行的运算符, 它指示了表达式的类型(例如当一个表达式的最后一步是减法运算时, 它本质上是一个减法表达式). 要正确地对一个长表达式进行分裂, 就是要找到它的主运算符. 我们继续使用上面的例子来探讨这个问题:

"4 + 3 * ( 2 - 1 )"
/*********************/
case 1:
    "+"
   /   \
"4"     "3 * ( 2 - 1 )"


case 2:
        "*"
       /   \
"4 + 3"     "( 2 - 1 )"


case 3:
              "-"
             /   \
"4 + 3 * ( 2"     "1 )"

上面列出了3种可能的分裂, 注意到我们不可能在非运算符的token处进行分裂, 否则分裂得到的结果均不是合法的表达式. 根据主运算符的定义, 我们很容易发现, 只有第一种分裂才是正确的. 这其实也符合我们人工求值的过程: 先算4和3 * ( 2 - 1 ), 最后把它们的结果相加. 第二种分裂违反了算术运算的优先级, 它会导致加法比乘法更早进行. 第三种分裂破坏了括号的平衡, 分裂得到的结果均不是合法的表达式.

通过上面这个简单的例子, 我们就可以总结出如何在一个token表达式中寻找主运算符了:

非运算符的token不是主运算符.
出现在一对括号中的token不是主运算符. 注意到这里不会出现有括号包围整个表达式的情况, 因为这种情况已经在check_parentheses()相应的if块中被处理了.
主运算符的优先级在表达式中是最低的. 这是因为主运算符是最后一步才进行的运算符.
当有多个运算符的优先级都是最低时, 根据结合性, 最后被结合的运算符才是主运算符. 一个例子是1 + 2 + 3, 它的主运算符应该是右边的+.

要找出主运算符, 只需要将token表达式全部扫描一遍, 就可以按照上述方法唯一确定主运算符.

找到了正确的主运算符之后, 事情就变得很简单了: 先对分裂出来的两个子表达式进行递归求值, 然后再根据主运算符的类型对两个子表达式的值进行运算即可. 于是完整的求值函数如下:

eval(p, q) {
  if (p > q) {
    /* Bad expression */
  }
  else if (p == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
  }
  else if (check_parentheses(p, q) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    return eval(p + 1, q - 1);
  }
  else {
    op = the position of 主运算符 in the token expression;
    val1 = eval(p, op - 1);
    val2 = eval(op + 1, q);

    switch (op_type) {
      case '+': return val1 + val2;
      case '-': /* ... */
      case '*': /* ... */
      case '/': /* ... */
      default: assert(0);
    }
  }
}

需要注意的是, 上述框架中并没有进行错误处理, 在求值过程中发现表达式不合法的时候, 应该给上层函数返回一个表示出错的标识, 告诉上层函数"求值的结果是无效的". 例如在check_parentheses()函数中, (4 + 3)) * ((2 - 1)和(4 + 3) * (2 - 1)这两个表达式虽然都返回false, 因为前一种情况是表达式不合法, 是没有办法成功进行求值的; 而后一种情况是一个合法的表达式, 是可以成功求值的, 只不过它的形式不属于BNF中的"(" <expr> ")", 需要使用主运算符的方式进行处理, 因此你还需要想办法把它们区别开来. 当然, 你也可以在发现非法表达式的时候使用assert(0)终止程序. 不过这样的话, 你在使用表达式求值功能的时候就要十分谨慎了.

最后, 为了方便统一, 我们认为所有结果都是uint32_t类型.

实现算术表达式的递归求值

由于ICS不是算法课, 我们已经把递归求值的思路和框架都列出来了. 你需要做的是理解这一思路, 然后在框架中填充相应的内容. 实现表达式求值的功能之后, p命令也就不难实现了.

实现带有负数的算术表达式的求值 (选做)

在上述实现中, 我们并没有考虑负数的问题, 例如

"1 + -1"
"--1"    /* 我们不实现自减运算, 这里应该解释成 -(-1) = 1 */

它们会被判定为不合法的表达式. 为了实现负数的功能, 你需要考虑两个问题:

负号和减号都是-, 如何区分它们?
负号是个单目运算符, 分裂的时候需要注意什么?

你可以选择不实现负数的功能, 但你很快就要面临类似的问题了.

从表达式求值窥探编译器

你在程序设计课上已经知道, 编译是一个将高级语言转换成机器语言的过程. 但你是否曾经想过, 机器是怎么读懂你的代码的? 回想你实现表达式求值的过程, 你是否有什么新的体会?

事实上, 词法分析也是编译器编译源代码的第一个步骤, 编译器也需要从你的源代码中识别出token, 这个功能也可以通过正则表达式来完成, 只不过token的类型更多, 更复杂而已. 这也解释了你为什么可以在源代码中插入任意数量的空白字符(包括空格, tab, 换行), 而不会影响程序的语义; 你也可以将所有源代码写到一行里面, 编译仍然能够通过.

一个和词法分析相关的有趣的应用是语法高亮. 在程序设计课上, 你可能完全没有想过可以自己写一个语法高亮的程序. 事实是, 这些看似这么神奇的东西, 其实也没那么复杂, 你现在确实有能力来实现它: 把源代码看作一个字符串输入到语法高亮程序中, 在循环中识别出一个token之后, 根据token类型用不同的颜色将它的内容重新输出一遍就可以了. 如果你打算将高亮的代码输出到终端里, 你可以使用ANSI转义码的颜色功能在新窗口中打开.

在表达式求值的递归求值过程中, 逻辑上其实做了两件事情: 第一件事是根据token来分析表达式的结构(属于BNF中的哪一种情况), 第二件事才是求值. 它们在编译器中也有对应的过程: 语法分析就好比分析表达式的结构, 只不过编译器分析的是程序的结构, 例如哪些是函数, 哪些是语句等等. 当然程序的结构要比表达式的结构更复杂, 因此编译器一般会使用一种标准的框架来分析程序的结构, 理解这种框架需要更多的知识, 这里就不展开叙述了. 另外如果你有兴趣, 可以看看C语言语法的BNF.

和表达式最后的求值相对的, 在编译器中就是代码生成. ICS理论课会有专门的章节来讲解C代码和汇编指令的关系, 即使你不了解代码具体是怎么生成的, 你仍然可以理解它们之间的关系. 这是因为C代码天生就和汇编代码有密切的联系, 高水平C程序员的思维甚至可以在C代码和汇编代码之间相互转换. 如果要深究代码生成的过程, 你也不难猜到是用递归实现的: 例如要生成一个函数的代码, 就先生成其中每一条语句的代码, 然后通过某种方式将它们连接起来.

我们通过表达式求值的实现来窥探编译器的组成, 是为了落实一个道理: 学习汽车制造专业不仅仅是为了学习开汽车, 是要学习发动机怎么设计. 我们也强烈推荐你在将来修读"编译原理"课程, 深入学习"如何设计发动机".

如何测试你的代码

你将来是要使用你自己实现的表达式求值功能来帮助你来进行后续的调试的, 这意味着程序设计课上那种"代码随便测试一下就交上去然后就可以撒手不管"的日子已经一去不复返了. 测试需要测试用例, 通过越多测试, 你就会对代码越有信心. 但如果让你来设计测试用例, 设计十几个你就会觉得没意思了, 有没有一种方法来自动产生测试用例呢?

一种常用的方法是随机测试在新窗口中打开. 首先我们需要来思考如何随机生成一个合法的表达式. 事实上, 表达式生成比表达式求值要容易得多. 同样是上面的BNF, 我们可以很容易写出生成表达式的框架:

void gen_rand_expr() {
  switch (choose(3)) {
    case 0: gen_num(); break;
    case 1: gen('('); gen_rand_expr(); gen(')'); break;
    default: gen_rand_expr(); gen_rand_op(); gen_rand_expr(); break;
  }
}

你应该一眼就能明白上述代码是如何工作的: 其中uint32_t choose(uint32_t n)是一个很简单又很重要的函数, 它的作用是生成一个小于n的随机数, 所有随机生成的内容几乎都是通过它来选择的.

有了这些随机表达式作为测试输入, 我们怎么知道输出对不对呢? 如果要我们把这些表达式手动算一遍, 那就太麻烦了. 如果可以在生成这些表达式的同时, 也能生成它们的结果, 这样我们就能得到类似OJ的测试用例啦! 但我们在NEMU中实现的表达式求值是经过了一些简化的, 所以我们需要一种满足以下条件的"计算器":

进行的都是无符号运算
数据宽度都是32bit
溢出后不处理

嘿! 如果我们把这些表达式塞到如下C程序的源文件里面:

#include <stdio.h>
int main() {
  unsigned result = ???; // 把???替换成表达式
  printf("%u", result);
  return 0;
}

然后用gcc编译它并执行, 让它输出表达式的结果, 这不就是我们想要的"计算器"吗?

还真能这样做! 我们已经准备好这个表达式生成器的框架代码了(在nemu/tools/gen-expr/gen-expr.c中). 你需要实现其中的void gen_rand_expr()函数, 将随机生成的表达式输出到缓冲区buf中. main函数中的代码会调用你实现的gen_rand_expr(), 然后把buf中的随机表达式放入上述C程序的代码中. 剩下的事情就是编译运行这个C程序了, 代码中使用了system()和popen()等库函数来实现这一功能. 最后, 框架代码将这个C程序的打印结果和之前随机生成的表达式一同输出, 这样就生成了一组测试用例.

表达式生成器如何获得C程序的打印结果?

代码中这部分的内容没有任何注释, 聪明的你也许马上就反应过来: 竟然是个RTFM的圈套! 阅读手册了解API的具体行为可是程序员的基本功. 如果觉得去年一整年的程序员都白当了, 就从现在开始好好锻炼吧.

不过实现的时候, 你很快就会发现需要面对一些细节的问题:

如何保证表达式进行无符号运算?
如何随机插入空格?
如何生成长表达式, 同时不会使buf溢出?
如何过滤求值过程中有除0行为的表达式?

这些问题大多都和C语言相关, 就当作是C语言的又一个编程练习吧.

为什么要使用无符号类型? (建议二周目思考)

我们在表达式求值中约定, 所有运算都是无符号运算. 你知道为什么要这样约定吗? 如果进行有符号运算, 有可能会发生什么问题?

除0的确切行为

如果生成的表达式有除0行为, 你编写的表达式生成器的行为又会怎么样呢?

过滤除0行为的表达式

乍看之下这个问题不好解决, 因为框架代码只负责生成表达式, 而检测除0行为至少要对表达式进行求值. 结合前两个蓝框题的回答(前提是你对它们的理解都足够深入了), 你就会找到解决方案了, 而且解决方案不唯一喔!

实现表达式生成器

根据上文内容, 实现表达式生成器. 实现后, 就可以用来生成表达式求值的测试用例了.

./gen-expr 10000 > input

将会生成10000个测试用例到input文件中, 其中每行为一个测试用例, 其格式为

结果 表达式

再稍微改造一下NEMU的main()函数, 让其读入input文件中的测试表达式后, 直接调用expr(), 并与结果进行比较. 为了容纳长表达式的求值, 你还需要对tokens数组的大小进行修改.

随着你的程序通过越来越多的测试, 你会对你的代码越来越有信心.

温馨提示

PA1阶段2到此结束.

# 表达式求值

# 数学表达式求值

# 词法分析