表达式求值

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

数学表达式求值

给你一个表达式的字符串

"5 + 4 * 3 / 2 - 1"

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

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

词法分析

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

"0xc0100000+   ($eax +5)*4 - *(  $ebp + 8) + number"

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

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

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

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

这些规则会在NEMU初始化的时候被编译成一些用于进行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都成功识别出来之后, 接下来我们就可以进行求值了. 需要注意的是, 我们现在是在对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类型.

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

如何测试你的代码

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

一种常用的方法是随机测试. 首先我们需要来思考如何随机生成一个合法的表达式. 事实上, 表达式生成比表达式求值要容易得多. 同样是上面的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程序的打印结果和之前随机生成的表达式一同输出, 这样就生成了一组测试用例.

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

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

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

./gen-expr 100 > input

结果 表达式