数学表达式求值

给你一个表达式的字符串

"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类型是 NOTYPE , 因为空格串并不参加求值过程, 识别出来之后就可以将它们丢弃了; + 的token类型是 '+' , 事实上token类型只是一个整数, 只要保证不同的类型的token被编码成不同的整数就可以了; 框架代码中还有一条用于识别双等号的规则, 不过我们现在可以暂时忽略它.

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

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

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

如果尝试了所有的规则都无法在当前位置识别出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 来指示这个子表达式的开始位置和结束位置. 这样我们就可以很容易把求值函数的框架写出来了:

其中 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 中的内容). 一个问题是, 给出一个最左边和最右边不同时是括号的长表达式, 我们要怎么正确地将它分裂成两个子表达式? 我们定义 dominant operator 为表达式人工求值时, 最后一步进行运行的运算符, 它指示了表达式的类型(例如当最后一步是减法运算时, 表达式本质上是一个减法表达式). 要正确地对一个长表达式进行分裂, 就是要找到它的dominant operator. 我们继续使用上面的例子来探讨这个问题:

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


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


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

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

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

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

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

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

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

调试中的表达式求值

实现了算术表达式的求值之后, 你可以很容易把功能扩展到复杂的表达式. 我们用BNF来说明需要扩展哪些功能:

<expr> ::= <decimal-number>
    | <hexadecimal-number>    # 以"0x"开头
    | <reg_name>            # 以"$"开头
    | "(" <expr> ")"
    | <expr> "+" <expr>
    | <expr> "-" <expr>
    | <expr> "*" <expr>
    | <expr> "/" <expr>
    | <expr> "==" <expr>
    | <expr> "!=" <expr>
    | <expr> "&&" <expr>
    | <expr> "||" <expr>
    | "!" <expr>
    | "*" <expr>            # 指针解引用

它们的功能和C语言中运算符的功能是一致的, 包括优先级和结合性, 如有疑问, 请查阅相关资料. 需要注意的是指针解引用(dereference)的识别, 在进行词法分析的时候, 我们其实没有办法把乘法和指针解引用区别开来, 因为它们都是 * . 在进行递归求值之前, 我们需要将它们区别开来, 否则如果将指针解引用当成乘法来处理的话, 求值过程将会认为表达式不合法. 其实要区别它们也不难, 给你一个表达式, 你也能将它们区别开来, 实际上, 我们只要看 * 前一个token的类型, 我们就可以决定这个 * 是乘法还是指针解引用了, 不信你试试? 我们在这里给出 expr() 函数的框架:

其中的 certain type 就由你自己来思考啦! 其实上述框架也可以处理负数问题, 如果你之前实现了负数, * 的识别对你来说应该没什么困难了.

另外和GDB中的表达式相比, 我们做了简化, 简易调试器中的表达式没有类型之分, 因此我们需要额外说明两点:

• 为了方便统一, 我们认为所有结果都是 uint32_t 类型.
• 指针也没有类型, 进行指针解引用的时候, 我们总是从内存中取出一个 uint32_t 类型的整数, 同时记得使用 swaddr_read() 来读取内存.