表达式求值

你应在本节中完成以下任务

  1. 在 GDB 中尝试使用表达式求值功能;
  2. 阅读项目中和本节相关的源代码;
  3. 实现表达式求值相关功能;
  4. 回答讲义中的所有思考题。

面对一个如 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;

tokenexpr有意义的最短子串,比如上文出现的表达式 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 可以匹配 1abc13abc,但不能匹配 abc,然而,可以匹配 1234abc234abc 部分;
  • 字符类的表达可以使用一对中括号 [],如 [a-c1-5] 可以匹配 a ,b, c, 1, 2, 3, 4, 5 之中的任意一个字符,如表达式 [a-c1-5]{3} 可以匹配 a1c, 23b 等等字符串;
  • 分枝条件 abc|123 将匹配字符串 abc123

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

例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

一些简单的正则表达式

下面是一些帮助你学习正则表达式的简单题目,请聪明的你回答到报告中。

  • 0x 开头的 32 位十六进制整数;
  • 英文字母和数字组成的字符串;
  • C 语言中的变量名或函数名。

下面这个对于你可能有些难度,但是也应该难不到你吧!(提示: [\u4e00-\u9fa5] 将匹配一个汉字)

  • 学号 - 姓名 - PA1.1.pdf,如 161722222 - 张三 - PA1.1.pdf

如果你从某处看到了最后这个题目的答案也没有关系,你可以说说答案是如何匹配到这个字符串的。

编写规则

回到我们的项目中来,现在你需要编写相应正则表达式规则来匹配有可能出现的各种 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此时你需要检查编写的规则是否符合正则表达式的语法

系统设计的黄金法则

这里的 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 法则不但广泛用在计算机领域, 就连其它很多领域也视其为黄金法则, 这里open in new window有一篇文章举出了很多的例子, 我们强烈建议你阅读它, 体会 KISS 法则的重要性.

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的应用, 就算你没听过这个高大上的名词, 也不难理解这种思路. 而要实现这种解决方案, 递归是你的不二选择.

任务1:编写匹配规则(1)

你需要编写上面的定义中所涉及的最简单的规则,即:

  • 十进制数字、十六进制数字,如 0x1234567
  • 现阶段所定义的 9 个寄存器,如 $eax, $ebx
  • 左括号、右括号;
  • 加号、减号、乘号、除号;
  • 空格串(一个或多个空格)。

你应该把这些规则添加到规则数组中。

这是为什么?

请注意,如果你需要使用正则表达式中的转义字符 \,你应该在定义规则的字符串中输入两个 \ 才能代表一个 \,想一想,这是为什么?

任务2:为

不要忘记在 PA1.1 中你添加过了许多命令,这里规定求解表达式的命令为 p,请自行到对应的文件中添加. 使用 p 命令的方法约定如下:

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

上述命令应得到的结果是:

141

任务3:存储匹配到的

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

如何处理以上的问题?

如题。

递归求值

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

"4 +3*(2- 1)"

的token表达式为

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

递归求值的过程?

你可以自学一下算术表达式的 BNF 的表达,画一个简单的图示说明你对递归求值过程的理解。

为了在 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. */
    }
}

递归求值的起点

你可以直接在 expr() 函数中使用语句 return eval() 来调用 eval() 函数并返回计算结果。

括号匹配

其中 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

任务4:实现括号匹配

你需要按照上面的讲义实现 check_parentheses() 函数(框架没有给出,你需要在 expr.c 中自己定义),你可以直接使用上面的测试用例进行测试。

优先级处理

上面的 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的函数.

任务5:寻找当前子表达式的中心操作符

你需要按照上面的思路,在 expr.c 中自己编写函数 find_dominated_op(int p, int q),其中 pq 意义和 eval() 中的相同,success 用于返回函数执行是否成功,该函数返回一个整数,意义为所寻找到的中心操作符的坐标。

递归求值

有了以上所有的铺垫,整体的递归求值思路就很清晰了:先对分裂出来的两个子表达式进行递归求值, 然后再根据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);
        }
    }
}

错误处理

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

选做任务:带有负数的表达式求值

在上述的实验中我们并没有考虑到负数的问题,根据 KISS 法则,如果之前的问题你都完美地解决了,可以挑战一下附属的处理,比如

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

任务6:编写匹配规则(2)

你需要编写上面所涉及的各种类型的操作符、操作数、寄存器和括号。

指针解引用

和符号 ' - ' 一样,在进行词法分析的时候我们无法区分 ' * ' 代表的是乘号还是指针解引用,所以在递归求值之前我们就需要加以区分. 我们只要看 ' * ' 前一个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 就由你自己来思考啦! 其实上述框架也可以处理负数问题, 如果你之前实现了负数, ' * ' 的识别对你来说应该没什么困难了.

任务7:实现指针解引用

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

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

注意事项

此外,要注意的地方是:

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

从表达式中窥探编译器

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

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

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

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

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

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


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

Last Updated 2023-04-02 14:55:00