表达式求值

面对一个如 1 * ( 2 + 6 ) 的简单的表达式，计算机会怎么处理呢？

表达式求值可以用很多方法实现，这里介绍一下递归表达式求值算法。（如果对递归不是十分了解，可以先回顾一下汉诺塔问题open in new window）。

# 表达式的组成

第一眼看到表达式，我们会去分析它是由什么组成的，计算机也是如此。很容易就想到 + - * / 等常用运算符以及整数、小数、括号等等。对于 NEMU 中的运算可能还需要考虑到寄存器访问和十六进制数，如下列表达式：

0x01001100+($eax+1)*2

当然也有可能是类似于 C 的指针解引用运算以及变量的运算：

*($ecx+1)*variable

还有可能是不小心多打了几个空格：

1    +      2   *3

# 词法分析

**词法分析open in new window**是个专业词汇，通俗地讲就是识别出表达式 expr 中的单元，我们把这些单元叫做 token。在 NEMU 中，token 的定义如下：

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

token 是 expr 中有意义的最短子串，比如上文出现的表达式 1 * ( 2 + 6 )，我们应该识别出1, *, (, 2, +, 6, )这些 token；另一条 0x01001100 + （ $eax + 1 ) * 2 则为0x01001100, +, (, $eax, +, 1, ), *, 2，所以分为许多类型。这部分类型通过枚举来匹配：

enum {
    TK_NOTYPE = 256,
    TK_EQ = ...
    /* TODO: Add more token types */
}

对于单个的字符识别起来比较简单，但是对于类似123, 0x00111100, $ebp之类的长串，它们都有各自的特点，仅由 0-9 的数字组成、以 $ 开头等等，我们需要写一些规则去描述这些长串以便计算机识别。所以你需要了解简单的正则表达式open in new window。

# 正则表达式

正则表达式是对字符串操作的一种逻辑表达式，由事先定义好的特殊字符组合形成规则字符串，表达对字符串的过滤逻辑。下面我们将简要介绍本课程中可能用到的部分正则表达式的形式，你可以使用带有正则表达式匹配功能的文本编辑器（如 Notepad++），使用其查找功能尝试一下。

# 基本语法

记住如下的若干条基本语法，你就能成为一个正则表达式大佬：

• 元字符 . 将匹配除换行符以外的任意字符；

• 转义字符 \ 将下一字符标记为特殊字符、原义字符等，如 \d 匹配一个数字，或把 \. 解释为小数点而不是匹配任意字符的元字符；
• 元字符 \w 将匹配一个字母或数字或下划线或汉字，如 \w 可以匹配 1，也可以匹配 a；
• 元字符 \s 将匹配一个空白字符，如 \s 可以匹配 <space>，也可以匹配 <tab>，甚至可以匹配换行符；
• 元字符 \d 将匹配一个数字，如 \d 可以匹配 1，也可以匹配 2；
• 元字符 ^ 和 $ 分别匹配字符串的开始和结束，如 ^ 匹配字符串 abc 的字符 a 之前的那个位置，$则匹配字符 c 之后的那个位置（不过本节似乎用不到这个匹配 :-）；
• 限定符 * 将匹配前子表达式 0-n 次，如 \d*abc 可以匹配 1234abc，亦可以匹配 abc；
• 限定符 + 将匹配前子表达式 1-n 次，如 \d+abc 可以匹配 1234abc，但不能匹配 abc；
• 限定符 {n} 将匹配前子表达式 n 次，其中 n 为非负整数，如 \d{5}abc 可以匹配 12345abc，但不能匹配 123abc；
• 限定符 {n,m} 匹配前子表达式 n-m 次，其中 n,m 为非负整数，n<=m，如 \d{1,3}abc 可以匹配 1abc，13abc，但不能匹配 abc，然而，可以匹配 1234abc 的 234abc 部分；
• 字符类的表达可以使用一对中括号 []，如 [a-c1-5] 可以匹配 a ,b, c, 1, 2, 3, 4, 5 之中的任意一个字符，如表达式 [a-c1-5]{3} 可以匹配 a1c, 23b 等等字符串；
• 分枝条件 abc|123 将匹配字符串 abc 或 123；

看了基本语法，可能有同学还是一头雾水，下面我们再用几个简单的例子来理解一下：

例1：表达式 '137\d{8}' 可以匹配所有以 '137' 开头的手机号码，如 '13712345678', '13762892353'.
例2：表达式 'str[a-z]+' 可以匹配所有以 'str' 开头的字符串，如 'strcpy', 'strlen'.

掌握以上正则表达式，你可以在非常多的场合下快速使用正则表达式匹配出你需要的字符串，非常便利。如果你还想了解更多关于正则表达式的学习资料，可以查看下面的链接：

http://www.runoob.com/regexp/regexp-syntax.htmlopen in new window

http://deerchao.net/tutorials/regex/regex.htm#missionopen in new window

# 编写规则

回到我们的项目中来，现在你需要编写相应正则表达式规则来匹配有可能出现的各种 token 形式：

rules[] = {
    /* TODO: Add more rules.
     * Pay attention to the precedencd level of different rules.
     */
    {" +", TK_NOTYPE}, //space
    {"\\+", '+'},      //plus
    {"==", TK_EQ},     //equal
    ...
}

一条规则是由正则表达式和 token 类型组成的二元组。框架代码中已经给出了加号 + 和空格串的规则, 其中空格串的 token 类型是 TK_NOTYPE , 因为空格串并不参加求值过程, 识别出来之后就可以将它们丢弃了；+ 的 token 类型是 '+' . 事实上 token 类型 只是一个整数, 只要保证不同的类型的 token 被编码成不同的整数就可以了。 框架代码中还有一条用于识别双等号的规则, 不过我们现在可以暂时忽略它. 这些规则会在 NEMU 初始化的时候被编译成一些用于进行 pattern 匹配的内部信息，这些内部信息是被库函数使用的，而且它们会被反复使用，但你不必关心它们如何组织。但如果正则表达式的编译不通过，NEMU 将会触发assertion fail，此时你需要检查编写的规则是否符合正则表达式的语法。

# make_token 函数

给出一个待求值表达式, 我们首先要识别出其中的 token, 进行这项工作的是 make_token() 函数。make_token() 函数的工作方式十分直接, 它用 position 变量来指示当前处理到的位置, 且按顺序尝试用不同的规则来匹配当前位置的字符串. 当一条规则匹配成功, 并且匹配出的子串正好是position所在位置的时候, 我们就成功地识别出一个 token, Log() 宏会输出识别成功的信息. 你需要做的是将识别出的 token 信息记录下来 (一个例外是空格串) .总结，make_token() 函数用于得到表达式中的token, position 是表达式中字符的位置，tokens 数组用于按顺序存放已经被识别出的 token 信息, nr_token 指示已经被识别出的token数目. 如果尝试了所有的规则 rule 都无法在当前位置识别出 token, 识别将会失败, 这通常是待求值表达式并不合法造成的, make_token() 函数将返回 false , 表示词法分析失败.

# 算术表达式递归求值

权衡各类表达式求值算法的利弊，我们决定选择递归求值. 把待求值表达式中的 token 都成功识别出来之后, 接下来我们就可以进行求值了.

算术表达式归纳定义

我们把表达式表示为 expr, 数字表示为 number, 采用经典的 BNF 巴科斯范式open in new window进行归纳定义如下

<expr> ::= <number>        #一个数也是一个表达式两者等价
   | "(" <expr> ")"        #表达式加括号也是表达式
   | <expr> "+" <expr>     #中间用加号连接也是表达式
   | <expr> "-" <expr>     #表达式相减也是表达式
   | <expr> "*" <expr>     #...
   | <expr> "/" <expr>

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

(NEMU) p (1+   2)  * (3+4 *(5 +6))

141

# 递归求值

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

"4 +3*(2- 1)"

的token表达式为

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

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

uint32_t eval(int p, int 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()

bool check_parentheses(your param){
    ...
    return true or false;
}

举一些例子关于括号匹配以及对应返回值的测试用例：

"(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

# 优先级处理

上面的 eval 框架已经考虑了BNF中算术表达式的开头两种定义, 接下来我们来考虑剩下的情况 ( 即上述伪代码中最后一个 else 中的内容 ) . 一个问题是, 给出一个最左边和最右边不同时是括号的长表达式, 我们要怎么正确地将它分裂成两个子表达式?

# dominant operator

我们定义 dominant operator 为表达式人工求值时最后一步进行运行的运算符, 它指示了表达式的类型 ( 例如当最后一步是减法运算时, 表达式本质上是一个减法表达式 ) . 要正确地对一个长表达式进行分裂, 就是要找到它的dominant operator.

比如说分解表达式 4 + 3 * ( 2 - 1 ) 我们可以有三种形式

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


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


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

我们很容易发现, 只有第一种分裂才是正确的. 这其实也符合我们人工求值的过程: 先算 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的函数.

# 递归求值

有了以上所有的铺垫，整体的递归求值思路就很清晰了：先对分裂出来的两个子表达式进行递归求值, 然后再根据dominant operator的类型对两个子表达式的值进行运算即可：

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 dominant operator 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);
        }
    }
}

"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语言中运算符的功能是一致的, 包括优先级和结合性, 如有疑问, 请查阅相关资料.

# 指针解引用

和符号 ' - ' 一样，在进行词法分析的时候我们无法区分 ' * ' 代表的是乘号还是指针解引用，所以在递归求值之前我们就需要加以区分. 我们只要看 ' * ' 前一个token的类型, 我们就可以决定这个 ' * ' 是乘法还是指针解引用了. 所以在expr()函数中调用eval()进行递归求值之前就进行对应的处理：

if (!make_token(e)) {
    *success = false;
    return 0;
}
/* TODO: Implement code to evaluate the expression. */
for (i = 0; i < nr_token; i ++) {
    if (tokens[i].type == '*' && (i == 0 || tokens[i - 1].type == certain type) ) {
        tokens[i].type = DEREF;
	}
}
return eval(?, ?);

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

# 注意事项

此外，要注意的地方是：

• 词法分析中编写规则的顺序, 不正确的顺序会导致一个运算符被识别成两部分, 例如 != 被识别成 ! 和 = .
• 关于变量的功能,它需要涉及符号表和字符串表的查找, 我们在PA中暂不实现.
• 上面的BNF并没有列出C语言中所有的运算符, 例如各种位运算, <= 等等. == , != 和逻辑运算符很可能在使用监视点的时候用到, 因此要求你实现它们. 如果你在将来的使用中发现由于缺少某一个运算符而感到使用不方便, 到时候你再考虑实现它.

# 从表达式中窥探编译器

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

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

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

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

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

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

以上是 PA1.2 的全部内容。