86:NJU_PA_STUDY(3)

我们先前反复提到了一个式子EXPR，它代表着表达式含义，常见的表达式是通过操作符连接的。这里我们需要为我们的框架实现一个表达式求值的功能。我们要解决的问题是求值一个字符串表示的表达式。

PA1 表达式求值

为了简单起见，我们先从数学表达式求值实现开始。

数学表达式求值

如下的一个表达式的字符串：

"5 + 4 * 3 / 2 - 1"

我们应该怎么求出它的值？我们可以分成两个简单的步骤：

• 首先识别出表达式中的单元
• 根据表达式的归纳定义进行递归求值

词法分析

词法分析要做的事情就是识别出表达式中的单元，这里的单元指的就是有着独立含义的子串，我们称之为token。具体而言我们需要将表达式中所有的单元都赋予一个标签，方便之后根据标签来对表达式进行处理。这里我们使用正则表达式来对token进行处理。

出于简单起见，这里我们暂时只对以下的token类型进行处理：

• 十进制整数
• +，-，*，/
• (，)
• 空格串（一个或者多个空格）

首先我们需要使用正则表达式来编写用于识别这些token类型的规则，框架中演示了怎么对其进行匹配。

static struct rule {
  const 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
};

这些规则，在init_sdb()时调用了init_regex()来将其编译成正则结构体并存储在re中：

void init_regex() {
  int i;
  char error_msg[128];
  int ret;
  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

如果编译不通过，可能是你编写的token匹配的规则不符合正则表达式的语法。现在，我们可以给出一个待匹配的表达式，我们利用make_token()来识别出其中的token。用position变量指示当前待匹配的位置，然后按顺序对当前位置的字符串进行匹配。当一个规则匹配成功，并且匹配出的字串属于position指出的位置时，我们就成功的识别出了一个token。我们则使用Token结构体来将它的内容记录下来。

typedef struct token {
  int type;
  char str[32];
} Token;
static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

其中type成员用于记录token的类型，然后str用来保存token相应的字串。tokens数组用来保存识别出的token信息，而nr_token则用来指示被识别出的token数目。

现在我们需要向算数表达式中的各种tokens类型添加规则，在成功识别出tokenhi后，将token的信息一次记录到tokens数组之中。

rules[] = {
  // 这里需要注意对这些内容的匹配是有优先顺序的，从上到下
  {" +", TK_NOTYPE},    // spaces
  {"==", TK_EQ},        // equal
  {"\\+", '+'},         // plus
  {"-", '-'},           // minus
  {"\\*", '*'},         // multi
  {"/", '/'},       	// div
  {"\\(", '('},         // left brace
  {"\\)", ')'},         // right brace
  {"[0-9]+", TK_NUM},   // number
};

然后我们就需要将匹配到的token放入tokens中，并对它的各个字段进行赋值。对于大多数类型，我们只需要简单的保存它的类型就行了，但是对于有数据内容的token，我们需要保存它的data，在这里既是保存它的子串内容信息，方便我们进行进一步的计算。

static bool make_token(char *e) {
  int position = 0;
  int i;
  int index=0;
  regmatch_t pmatch;
  nr_token = 0;
  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;
        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);
        position += substr_len;
        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */
        switch (rules[i].token_type) {
          case TK_NUM:  
            tokens[index].type = rules[i].token_type;
            for(int j=0;j<substr_len;j++)
              tokens[index].str[j] = substr_start[j];
            // printf("The num is %s\n",tokens[index].str);
            break;
          default:
            tokens[index].type = rules[i].token_type;
        }
        index++;
        break;
      }
    }
    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }
  return true;
}

我们可以看到整个识别token的过程，每当我们获取一个token时，我们都会使用Log()将它的匹配规则，子串下标，子串长度，和对应的子串信息打印出来。便于我们观察标识符匹配的中间过程。对于未匹配到的类型，我们也会将其内容进行返回。

中间部分则是我们对token信息的存储过程，目前我们只对十进制整数的内容进行了保存，对于其他的标识符号，则是简单的保存类型。现在我们可以进一步的进行表达式求值了。

递归求值

我们现在将求值表达式的token识别出来之后就可以进行求值了。我们现在是对token数组进行处理，方便起见，我们称其为token表达式。（将空格忽略）

接下来，根据表达式的归纳定义特性，我们可以使用递归来进行求值：

<expr> ::= <number>    # 一个数是表达式
  | "(" <expr> ")"     # 在表达式两边加个括号也是表达式
  | <expr> "+" <expr>  # 两个表达式相加也是表达式
  | <expr> "-" <expr>  # 接下来你全懂了
  | <expr> "*" <expr>
  | <expr> "/" <expr>

这种表示方法就是我们常说的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()用于判断表达式是否被一堆匹配的括号所包围，同时检查表达式左右的括号是否匹配，如果不匹配，那么这个表达式就是非法的。我们以此来尝试实现：

static int check_parentheses(int start, int end){
  int cond=0;
  if(tokens[start].type!='('||tokens[end].type!=')') return 0;
  for(int i=start;i<=end;i++){
    if(tokens[i].type=='(') cond++;
    if(tokens[i].type==')'){
      cond--;
      if(cond<0) return -1;
    }
    if(cond==0) return (i == end) ? 1 : 0;
  }
  return (cond==0)?1:-1;
}

现在我们的框架代码，已经可以处理BNF的开始两种情况啦。像现在我们需要进一步的考虑剩下的情况，即四则运算的处理。但是问题在于，我们怎么对一个长表达式处理，将其分解为各个小的短表达式，并保证语法的正确呢？

我们以下为例：

"4 + 3 * ( 2 - 1 )"
/*********************/
case 1:
    "+"
   /   \
"4"     "3 * ( 2 - 1 )"
case 2:
        "*"
       /   \
"4 + 3"     "( 2 - 1 )"
case 3:
              "-"
             /   \
"4 + 3 * ( 2"     "1 )"

我们可以看到只有第一种情况是正确的，第二种情况违背了算术符号的优先级，而第三种情况则使得表达式的括号不再匹配。通过以上的例子，我们就可以总结出寻找主运算符（可以将一个长表达式分解成两个短表达式的运算符号）的逻辑了：

• 非运算符的token不是主运算符
• 出现在一对括号中的token不是主运算符号
• 主运算符的优先级在表达式中应该是最低的
• 有多个运算符的优先级最低时，根据结合性，最后被结合的运算符为主运算符号

现在我们根据以上规则来扫描出每个表达式中的主运算符号：

static int get_token(int start, int end){
  int token = -1;
  int par = 0;
  int min_priority = -1;
  for(int i=start;i<=end;i++){
    int tmp=tokens[i].type;
    if(tmp==TK_NUM) continue;
    if(tmp=='(') par++;
    else if(tmp==')'){
      par--;
      if(par<0) return -1;
    }
    if(par!=0) continue;
    switch (tmp){
    case '*': case '/':
      if(min_priority<=1){
        min_priority=1;
        token=i;
      } 
      break;
    case '+': case '-':
      if(min_priority<=2){
        min_priority=2;
        token=i;
      } 
      break;
    default:
      continue;
    }
  }
  if(token != -1){
    // Log("Main operator: %c at position %d\n", tokens[token].type, token);
  } else {
    printf("No operator found in range [%d, %d]\n", start, end);
  }
  return token;
}

找到表达式的主运算符之后，事情就变得简单了，我们先对两个分裂出来的子表达式进行递归求值，然后根据主运算符号的两个子表达式进行计算即可，现在我们的框架代码更新如下：

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);
    }
  }
}

现在，我们需要利用现有的规则和函数来填补实现我们的求值函数eval():

static int eval(int start, int end){
  if(start>end){
    printf("Unknown expression.\n");
    return -1;
  }else if(start==end){
    return atoi(tokens[start].str);
  }else if(check_parentheses(start,end)==1){
    return eval(start+1,end-1);
  }else if(check_parentheses(start,end)==-1){
    printf("parenthese mismatch error\n");
    return -1;
  }else{
    int op = get_token(start,end);
    if(op==-1){
      printf("Error: No valid operator found in expression\n");
      return -1;
    }
    word_t val1 = eval(start,op-1);
    word_t val2 = eval(op+1,end);
    switch(tokens[op].type){
      case '+': return val1+val2;
      case '-': return val1-val2;
      case '*': return val1*val2;
      case '/': 
        if(val2==0){
          printf("Error: Division by 0\n");
          return -1;
        }
        return val1/val2;
      default: assert(0);
    }
  }
}

经过测试，基本可以处理大多数情况了。我们现在可以将其封装在expr()中，然后实现p方法：

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
  word_t val = eval(0,nr_token-1);
  *success = (val!=-1);
  return val;
}

static int cmd_p(char* args){
  bool success;
  word_t val=expr(args,&success);
  if(success==true)
    printf("%d\n",val);
  return 0;
}

出于限制，我们只使用uint32_t作为我们的返回类型。

测试代码

按照PA的要求，我们现在应该测试一下我们这个函数，但是我就跳过这一部分了，因为赶时间。