PA 2-3 可选任务：完善调试器¶
在nemu/src/monitor/ui.c中，框架代码提供了一系列用于帮助调试NEMU的调试和执行命令。目前这些命令所提供的功能都比较初级。在这一个可选任务中，我们考虑进一步完善调试器的功能。具体而言，我们试图完成以下两个功能：
-
表达式求值；
-
添加变量和函数名支持。
通过第一项任务，我们得以一窥编译器的设计原理；而第二项任务涉及到符号表的解析，属于ELF文件解析的一部分。为配合平行试验，这一节的教程内容组织方式按照问题来组织。
§2-3.1 表达式求值¶
§2-3.1.1 预备知识和代码导读¶
给你一个表达式的字符串
"5 + 4 * 3 / 2 - 1"
你如何求出它的值? 表达式求值是一个很经典的问题, 以至于有很多方法来解决它. 我们在所需知识和难度两方面做了权衡, 在这里使用如下方法来解决表达式求值的问题:
-
首先识别出表达式中的单元
-
根据表达式的归纳定义进行递归求值
* 词法分析¶
"词法分析"这个词看上去很高端, 说白了就是做上面的第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, 进行这项工作的是位于nemu/src/monitor/expr.c中的make_token()函数. make_token()函数的工作方式十分直接, 它用position变量来指示当前处理到的位置, 并且按顺序尝试用不同的规则来匹配当前位置的字符串. 当一条规则匹配成功, 并且匹配出的子串正好是position所在位置的时候, 我们就成功地识别出一个token, Log()宏会输出识别成功的信息. 你需要做的是将识别出的token信息记录下来(一个例外是空格串), 我们使用定义在nemu/src/monitor/expr.c中的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, 识别将会失败, 这通常是待求值表达式并不合法造成的, make_token()函数将返回false, 表示词法分析失败.
作为表达式求值的第一步，你需要完成词法分析的功能，具体要求参见“实验要求”。
* 递归求值¶
把待求值表达式中的token都成功识别出来之后, 接下来我们就可以进行求值了. 需要注意的是, 我们现在是在对tokens数组进行处理, 为了方便叙述, 我们称它为"token表达式". 例如待求值表达式
"4 +3*(2- 1)"
的token表达式为
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| NUM | '+' | NUM | '*' | '(' | NUM | '-' | NUM | ')' |
| "4" | | "3" | | | "2" | | "1" | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
图2-9 tokens数组举例
根据表达式的归纳定义特性, 我们可以很方便地使用递归来进行求值. 首先我们给出算术表达式的归纳定义:
<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中的内容). 一个问题是, 给出一个最左边和最右边不同时是括号的长表达式, 我们要怎么正确地将它分裂成两个子表达式? 我们定义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 )"
图2-10 dominant operator举例
上面列出了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的类型对两个子表达式的值进行运算即可. 于是完整的求值函数如下:
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);
}
}
}
由于ICS不是算法课, 我们已经把递归求值的思路和框架都列出来了, 你需要做的是理解这一思路, 然后在框架中填充相应的内容. 实现表达式求值的功能之后, p命令也就不难实现了.
需要注意的是, 上述框架中并没有进行错误处理, 在求值过程中发现表达式不合法的时候, 应该给上层函数返回一个表示出错的标识, 告诉上层函数"求值的结果是无效的". 例如在check_parentheses()函数中, (4 + 3)) * ((2 - 1)和(4 + 3) * (2 - 1)这两个表达式虽然都返回false, 因为前一种情况是表达式不合法, 是没有办法成功进行求值的; 而后一种情况是一个合法的表达式, 是可以成功求值的, 只不过它的形式不属于BNF中的"(" <expr> ")", 需要使用dominant operator的方式进行处理, 因此你还需要想办法把它们区别开来.
当然, 你也可以在发现非法表达式的时候使用assert(0)终止程序, 不过这样的话, 你在使用表达式求值功能的时候就要十分谨慎了.
* 调试中的表达式求值¶
实现了算术表达式的求值之后, 你可以很容易把功能扩展到复杂的表达式. 我们用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()函数的框架:
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就由你自己来思考啦! 其实上述框架也可以处理负数问题, 如果你之前实现了负数, *的识别对你来说应该没什么困难了.
另外和GDB中的表达式相比, 我们做了简化, 简易调试器中的表达式没有类型之分, 因此我们需要额外说明两点:
-
为了方便统一, 我们认为所有结果都是
uint32_t类型. -
指针也没有类型, 进行指针解引用的时候, 我们总是从内存中取出一个
uint32_t类型的整数, 同时记得使用vaddr_read()来读取内存.
§2-3.1.2 实验要求¶
* 实现表达式的词法分析¶
你需要完成以下的内容:
-
为算术表达式中的各种
token类型添加规则, 你需要注意C语言字符串中转义字符的存在和正则表达式中元字符的功能. -
在成功识别出
token后, 将token的信息依次记录到tokens数组中.
* 实现表达式的递归求值¶
你需要实现上文BNF中列出的功能. 一个要注意的地方是词法分析中编写规则的顺序, 不正确的顺序会导致一个运算符被识别成两部分, 例如 != 被识别成 ! 和 =. 关于变量的功能, 它需要涉及符号表和字符串表的查找, 因此你会在下一阶段中实现它.
上面的BNF并没有列出C语言中所有的运算符, 例如各种位运算, <= 等等. == , != 和逻辑运算符很可能在使用监视点的时候用到, 因此要求你实现它们. 如果你在将来的使用中发现由于缺少某一个运算符而感到使用不方便, 到时候你再考虑实现它.
在完成上述两个任务的时候，你可以尝试分步走的办法：首先针对简单的算术表达式实现其词法和求值功能，再扩展到更为复杂的表达式。
§2-3.1.3 延伸话题：从表达式求值窥探编译器¶
你在程序设计课上已经知道, 编译是一个将高级语言转换成机器语言的过程. 但你是否曾经想过, 机器是怎么读懂你的代码的? 回想你实现表达式求值的过程, 你是否有什么新的体会?
事实上, 词法分析也是编译器编译源代码的第一个步骤, 编译器也需要从你的源代码中识别出token, 这个功能也可以通过正则表达式来完成, 只不过token的类型更多, 更复杂而已. 这也解释了你为什么可以在源代码中插入任意数量的空白字符(包括空格, tab, 换行), 而不会影响程序的语义; 你也可以将所有源代码写到一行里面, 编译仍然能够通过.
一个和词法分析相关的有趣的应用是语法高亮. 在程序设计课上, 你可能完全没有想过可以自己写一个语法高亮的程序, 事实是, 这些看似这么神奇的东西, 其实也没那么复杂, 你现在确实有能力来实现它: 把源代码看作一个字符串输入到语法高亮程序中, 在循环中识别出一个token之后, 根据token类型用不同的颜色将它的内容重新输出一遍就可以了. 如果你打算将高亮的代码输出到终端里, 你可以使用ANSI转义码的颜色功能.
在表达式求值的递归求值过程中, 逻辑上其实做了两件事情: 第一件事是根据token来分析表达式的结构(属于BNF中的哪一种情况), 第二件事才是求值. 它们在编译器中也有对应的过程: 语法分析就好比分析表达式的结构, 只不过编译器分析的是程序的结构, 例如哪些是函数, 哪些是语句等等. 当然程序的结构要比表达式的结构更复杂, 因此编译器一般会使用一种标准的框架来分析程序的结构, 理解这种框架需要更多的知识, 这里就不展开叙述了. 另外如果你有兴趣, 可以看看C语言语法的BNF.
和表达式最后的求值相对的, 在编译器中就是代码生成. ICS理论课会有专门的章节来讲解C代码和汇编指令的关系, 即使你不了解代码具体是怎么生成的, 你仍然可以理解它们之间的关系, 这是因为C代码天生就和汇编代码有密切的联系, 高水平C程序员的思维甚至可以在C代码和汇编代码之间相互转换. 如果要深究代码生成的过程, 你也不难猜到是用递归实现的: 例如要生成一个函数的代码, 就先生成其中每一条语句的代码, 然后通过某种方式将它们连接起来.
我们通过表达式求值的实现来窥探编译器的组成, 是为了落实一个道理: 学习汽车制造专业不仅仅是为了学习开汽车, 是要学习发动机怎么设计. 我们也强烈推荐你在将来修读"编译原理"课程, 深入学习"如何设计发动机".
§2-3.2 添加变量和函数名支持¶
§2-3.2.1 预备知识和代码导读¶
你已经在上一阶段中实现了简易调试器. 同时在这一阶段现在你已经将用户程序换成了C程序. 和之前的mov.S相比, C程序多了变量和函数的要素, 那么在表达式求值中如何支持变量的输出呢?
(nemu) p test_data
换句话说, 我们怎么从test_data这个字符串找到这个变量在运行时刻的信息? 下面我们就来讨论这个问题.
符号表(symbol table)是可执行文件的一个section, 它记录了程序编译时刻的一些信息, 其中就包括变量和函数的信息. 为了完善调试器的功能, 我们首先需要了解符号表中都记录了哪些信息.
以add这个用户程序为例, 使用readelf命令查看ELF可执行文件的信息:
readelf -a add
你会看到readelf命令输出了很多信息, 这些信息对了解ELF的结构有很好的帮助, 我们建议你在课后仔细琢磨. 目前我们只需要关心符号表的信息就可以了, 在输出中找到符号表的信息:
Symbol table '.symtab' contains 10 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 00000000 0 NOTYPE LOCAL DEFAULT UND
1: 00100000 0 SECTION LOCAL DEFAULT 1
2: 0010009c 0 SECTION LOCAL DEFAULT 2
3: 00100100 0 SECTION LOCAL DEFAULT 3
4: 00000000 0 SECTION LOCAL DEFAULT 4
5: 00000000 0 FILE LOCAL DEFAULT ABS add.c
6: 00100084 22 FUNC GLOBAL DEFAULT 1 add
7: 00100000 129 FUNC GLOBAL DEFAULT 1 main
8: 00100120 256 OBJECT GLOBAL DEFAULT 3 ans
9: 00100100 32 OBJECT GLOBAL DEFAULT 3 test_data
图2-11 符号表举例
其中每一行代表一个表项, 每一列列出了表项的一些属性, 现在我们只需要关心Type属性为OBJECT的表项就可以了. 仔细观察Name属性之后, 你会发现这些表项正好对应了testcase/src/add.c中定义的全局变量, 而相应的Value属性正好是它们的地址(你可以与testcase/bin/add的反汇编结果进行对比), 而找到地址之后就可以找到这个变量了.
太好了, 我们可以通过符号表建立变量名和其地址之间的映射关系! 别着急, readelf输出的信息是已经经过解析的, 实际上符号表中Name属性存放的是字符串在字符串表(string table)中的偏移量. 为了查看字符串表, 我们先查看readelf输出中Section Headers的信息:
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS 00100000 001000 00009a 00 AX 0 0 4
[ 2] .eh_frame PROGBITS 0010009c 00109c 000058 00 A 0 0 4
[ 3] .data PROGBITS 00100100 001100 000120 00 WA 0 0 32
[ 4] .comment PROGBITS 00000000 001220 00001c 01 MS 0 0 1
[ 5] .shstrtab STRTAB 00000000 00123c 00003a 00 0 0 1
[ 6] .symtab SYMTAB 00000000 0013b8 0000a0 10 7 6 4
[ 7] .strtab STRTAB 00000000 001458 00001e 00 0 0 1
图2-12 Section Headers举例
从Section Headers的信息可以看到, 字符串表在ELF文件偏移为0x1458的位置开始存放. 在shell中可以通过以下命令直接输出ELF文件的十六进制形式:
hd add
查看输出结果的最后几行, 我们可以看到, 字符串表只不过是把标识符的字符串拼接起来而已. 现在我们就可以厘清符号表和字符串表之间的关系了:
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 7] .strtab STRTAB 00000000 001458 00001e 00 0 0 1
|
+--------------+ +-----------------------+
V V |
00001450 20 00 00 00 11 00 03 00 00 61 64 64 2e 63 00 61 | ........add.c.a| |
00001460 64 64 00 6d 61 69 6e 00 61 6e 73 00 74 65 73 74 |dd.main.ans.test| |
00001470 5f 64 61 74 61 00 ^ ^ |_data.| |
| | |
| +-------------+ |
| | |
+---------------------+ | |
Symbol table '.symtab' contains 10 entries: | | |
Num: Value Size Type Bind Vis Ndx Name | | |
5: 00000000 0 FILE LOCAL DEFAULT ABS 1 | | |
6: 00100084 22 FUNC GLOBAL DEFAULT 1 7 ---+---+------------------+
7: 00100000 129 FUNC GLOBAL DEFAULT 1 11 | |
8: 00100120 256 OBJECT GLOBAL DEFAULT 3 16 ---+ |
9: 00100100 32 OBJECT GLOBAL DEFAULT 3 20 -------+
图2-13 利用字符串表解析符号表中各表项的Name域
一种解决方法已经呼之欲出了: 在表达式递归求值的过程中, 如果发现token的类型是一个标识符, 就通过这个标识符在符号表中找到一项符合要求的表项(表项的Type属性是OBJECT, 并且将Name属性的值作为字符串表中的偏移所找到的字符串和标识符的命名一致), 找到标识符的地址, 并将这个地址作为结果返回. 在上述add程序的例子中:
(nemu) p test_data 0x100100
需要注意的是, 如果标识符是一个基本类型变量, 简易调试器和GDB的处理会有所不同: 在GDB中会直接返回基本类型变量的值, 但我们在表达式求值中并没有实现类型系统, 因此我们无法区分一个标识符是否基本类型变量, 所以我们统一输出变量的地址. 如果对于一个整型变量 x , 我们可以通过以下方式输出它的值:
(nemu) p *x
而对于一个整型数组 A , 如果想输出 A[1] 的值, 可以通过以下方式:
(nemu) p *(A + 4)
§2-3.2.2 实验要求¶
* 为表达式求值添加变量的支持¶
根据上文提到的方法, 向表达式求值添加变量的支持, 为此, 你还需要在表达式求值的词法分析和递归求值中添加对变量的识别和处理. 框架代码提供的load_elf_tables()函数已经为你从可执行文件中抽取出符号表和字符串表了, 其中strtab是字符串表, symtab是符号表, nr_symtab_entry是符号表的表项数目, 更多的信息请阅读nemu/src/monitor/elf.c. ---感谢16级张航帆同学发现的教程笔误。
头文件<elf.h>已经为我们定义了与ELF可执行文件相关的数据结构, 为了使用符号表, 请查阅
man 5 elf
实现之后, 你就可以在表达式中使用变量了. 在NEMU中运行add程序, 并打印全局数组某些元素的值.
* 消失的符号？¶
在实验报告中，回答下面这个问题：
我们在testcase/src/add.c中定义了宏NR_DATA, 同时也在add()函数中定义了局部变量c和形参a , b, 但你会发现在符号表中找不到和它们对应的表项, 为什么会这样? 思考一下, 什么才算是一个符号(symbol)?