Skip to content

词法分析与递归表达式求值

1. 词法分析基础

1.1 词法分析概念

  • 定义：识别表达式中的基本单元（token）
  • token：有独立含义的子串，如数字、运算符、括号等

1.2 复杂表达式示例

"0x80100000+   ($a0 +5)*4 - *(  $t1 + 8) + number"

包含：十六进制整数、小括号、寄存器访问、指针解引用、变量访问等

1.3 正则表达式应用

  • 利用正则表达式识别各类token
  • 规则：(正则表达式, token类型)组成的二元组
  • 常见token类型：
    • 十进制整数
    • 运算符：+, -, *, /
    • 括号：(, )
    • 空格串：一个或多个空格（类型为TK_NOTYPE，识别后丢弃）

1.4 Token结构体

typedef struct token {
  int type;  // token类型
  char str[32];  // token字符串表示
} Token;
  • 大部分token仅需记录类型（如运算符）
  • 对于数字等token，需记录其字符串表示用于后续求值
  • 注意str长度限制，防止缓冲区溢出

2. 递归求值机制

2.1 算术表达式BNF定义

<expr> ::= <number>     // 一个数是表达式
  | "(" <expr> ")"      // 在表达式两边加个括号也是表达式
  | <expr> "+" <expr>   // 两个表达式相加也是表达式
  | <expr> "-" <expr>   // 两个表达式相减也是表达式
  | <expr> "*" <expr>   // 两个表达式相乘也是表达式
  | <expr> "/" <expr>   // 两个表达式相除也是表达式

2.2 求值函数框架

eval(p, q) {  // p和q指示子表达式的开始和结束位置
  if (p > q) {
    /* 错误表达式 */
  }
  else if (p == q) {
    /* 单个token（数字），返回其值 */
  }
  else if (check_parentheses(p, q) == true) {
    /* 整个表达式被匹配的括号包围，移除括号 */
    return eval(p + 1, q - 1);
  }
  else {
    /* 处理复合表达式 */
    op = 找到主运算符位置;
    val1 = eval(p, op - 1);
    val2 = eval(op + 1, q);

    switch (op_type) {
      case '+': return val1 + val2;
      case '-': return val1 - val2;
      case '*': return val1 * val2;
      case '/': return val1 / val2;
      default: assert(0);
    }
  }
}

2.3 括号匹配检查

check_parentheses(p, q)函数用于：

  1. 判断表达式是否被一对匹配的括号包围
  2. 检查表达式的左右括号是否匹配

示例：

  • "(2 - 1)" - 返回true
  • "(4 + 3 * (2 - 1))" - 返回true
  • "4 + 3 * (2 - 1)" - 返回false（不被括号包围）
  • "(4 + 3)) * ((2 - 1)" - 返回false（括号不匹配）
  • "(4 + 3) * (2 - 1)" - 返回false（最左和最右括号不匹配）

2.4 主运算符识别

主运算符：表达式最后一步进行运算的运算符

主运算符识别规则：

  1. 非运算符token不是主运算符
  2. 出现在一对括号中的token不是主运算符
  3. 主运算符优先级在表达式中最低（最后计算）
  4. 当多个运算符优先级相同时，根据结合性，最后被结合的是主运算符

示例："4 + 3 * (2 - 1)"中的主运算符是+

2.5 错误处理

  • 在求值过程中检查表达式合法性
  • 对非法表达式返回错误标识或终止程序
  • 合法表达式的结果以uint32_t类型返回