「palab02」表达式求值

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类型需要自定义, 程序中给出了例子如下:

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

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

关于正则表达式的书写:

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

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结构如下:

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

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

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

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

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

2 | 递归求值

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

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

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

find_major_op的规则(doc提供):

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

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

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?