「palab02」表达式求值

本文最后更新于:2022年8月17日 上午

0 | vim操作学习

今天学习的操作包括

  1. text-object
  2. 各种跳转
  3. 基本命令全部过了一遍

表达式求值

1 | 词法分析

实现算术表达式的词法分析

你需要完成以下的内容:

  • 为算术表达式中的各种token类型添加规则, 你需要注意C语言字符串中转义字符的存在和正则表达式中元字符的功能.
  • 在成功识别出token后, 将token的信息依次记录到tokens数组中.

monitor/debug中存在这么个文件expr.c, 用于实现表达式求值

token类型共有:

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

1.1 | 识别tokens

那么我们要做的第一个工作就是: 识别tokens

根据分析, 程序中给出了部分tokens的示例, 这些tokens大概对应着一个二元组如doc中所说(正则表达式, TOKEN类型)

其中TOKEN类型需要自定义, 程序中给出了例子如下:

1
2
3
4
enum {
TK_NOTYPE = 256, TK_EQ,
/* TODO: Add more token types */
};

那么只需要仿照进行剩下的token类型定义就ok了 (事实上只需要定义数字类型就行了, 因为其他符号都是唯一确定的)

关于正则表达式的书写:

例子如下, 需要特别注意的点是c语言本身就有转义, 所以正则表达式比如\w规则在c++中需要写成\\w

1
2
3
4
5
6
7
8
9
10
11
12
static struct rule {
char *regex; // 正则表达式
int token_type;
} rules[] = {

/* TODO: Add more rules.
* Pay attention to the precedence level of different rules.
*/
{" +", TK_NOTYPE}, // spaces
{"\\+", '+'}, // plus
{"==", TK_EQ}, // equal
};

1.2 | 记录到tokens数组中

即补全make_token函数 (有点长这里不复制了)

token结构如下:

1
2
3
4
typedef struct token {
int type;
char str[32];
} Token;

其中type用于存+, -这一类确定的, 而str存的是十进制数

这里需要考虑的点(根据doc)

  1. 十进制整数溢出如何处理
  2. 词法分析失败如何处理 (框架貌似处理好了)

这里我搞完也不知道对不对, doc也没给出如何测试..

2 | 递归求值

doc中给出的求值递归框架:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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);
}
}
}

其中我们需要额外实现两个函数:

  1. check_parentheses(p, q), 功能为:
    • 判断表达式是否被括号包围
    • 判断表达式括号是否匹配
  2. find_major_op(p, q), 功能为:
    • 找到表达式的主运算符将表达式分为左右两部分

check_parenthese的实现就是一个括号匹配的任务, 因为只有一种类型的括号, 左右扫一遍就可以, 注意pq位置必须是对应的空格, 所以扫描检测括号匹配的区域为p + 1q - 1, 否则会死在(1 + 2) + (2 + 3)这个用例上(括号匹配了但是此表达式未被()包裹)

后期发现: 扫的时候注意情况的判断, 假设用cnt计数, 那么cnt永远不会是负数/正数(取决于如何计数)

find_major_op的规则(doc提供):

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

至于优先级的定义, 写死即可 (just like this)

1
2
3
4
5
6
7
8
9
10
int op_priority(int op) {
switch(op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
}

那么思路明确了: 从左到右遍历, 找到最后一个优先级最小的就是主操作符

后期发现: 遇到括号得直接跳过, 这里bug调了2小时我哭了

3 | debug

搞定后run一个

还行, 也就报了200万个错(

在经过3小时debug后终于成功运行了

我承认在加了一堆Log后调出正确结果是一件令人喜悦又悲伤的事情

但随之而来的溢出又是致命打击

现在是凌晨2:14, 再不睡我得狗带了, 明天再说了只能

错误用例p 1 + 2 + 5 - 1 * (3-1) +2 || p 1 + 2 + 5 - 10 * (3-1) +2 - 1

我刚又看了下, 确实有个会溢出, 但是神奇的事情是, 在出现溢出情况后, 本来不溢出的表达式计算后也溢出了, 难道是内存覆盖 or STH?


「palab02」表达式求值
https://blog.roccoshi.top/posts/20425/
作者
RoccoShi
发布于
2021年8月15日
许可协议