产生式的优先级

首先我们列出乘除法的文法：

1 2	term -> term '*' num \| term '/' num \| num num -> '0' \| '1' \| '2' \| '3' \| '4' \| '5' \| '6' \| '7' \| '8' \| '9'

这里的term是项的意思，是指在加减法里运算符左右的两个项，先不要纠结具体是什么意思，一会就会用到了。

我们以几个例子来人肉分析一下，这个文法和加减法的文法怎么结合，才能获得正确的优先级：

1
2
3

expr(1+2*3) = num(1) '+' term(2*3)
expr(1*2+3) = term(1*2) '+' num(3)
expr(1*2+3*4) = term(1*2) '+' term(3*4)

而在上面乘除法的文法里可以看到，实际上term是可以推导为num的，所以上述例子又可以变成：

1
2
3

expr(1+2*3) = term(1) '+' term(2*3)
expr(1*2+3) = term(1*2) '+' term(3)
expr(1*2+3*4) = term(1*2) '+' term(3*4)

是不是写到这里就豁然开朗了，如果乘除法的优先级更高，则让乘除法的解析先进行，乘除法的结果当做加减法的项就可以了。在文法里的表现就是，优先级越高的产生式会越靠后，结果是这样：

1
2
3

expr -> expr '+' term | expr '-' term | term
term -> term '*' num | term '/' num | num
num  -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

具体的验证大家自己试试就可以了，绝对可以按照正确的优先级进行解析。

前一章代码的隐患

文法已经准备好了，本来可以开始写递归逻辑了，但是我们得先解决前一章代码的隐患。先看看之前的代码：

int expr(const char *expStr)
{
    解析number，读取expStr下一个字符
    while(expStr是加减号) {
        解析加减号，读取expStr下一个字符
        解析number，读取expStr下一个字符
    }
}

看上去逻辑是没什么问题的，但是这是因为number肯定是单个字符的，如果按照之前的代码继续实现本章的文法，就会得到这样的难题：

int expr(const char *expStr)
{
    解析term，该读取expStr后的第几个字符？
    while(expStr是加减号) {
        解析加减号，读取expStr下一个字符
        解析term，该读取expStr后的第几个字符？
    }
}

所以将字符串指针后移的操作，应该交给解析了字符或者说消化掉字符的角色来做，那么我们要用指针的指针来先改进一下上一章的代码：

int number(const char **expStr)
{
    int result = **expStr - '0';
    (*expStr)++;
    return result;
}

int expr(const char **expStr)
{
    int result = number(expStr);
    while (**expStr == '+' || **expStr == '-') {
        char op = **expStr;
        (*expStr)++;
        if (op == '+') {
            result += number(expStr);
        } else {
            result -= number(expStr);
        }
    }
    return result;
}

实现乘除法和取余

大家有了文法，也掌握了消除左递归的方法，还知道怎么转换成递归代码，我感觉其实都不太需要把代码给大家贴出来了。😂

乘除法的实现思路和上一章加减法的思路完全一致，我们顺带把取余也加上就好了：

int term(const char **expStr)
{
    int result = number(expStr);
    while (**expStr == '*' || **expStr == '/' || **expStr == '%') {
        char op = **expStr;
        (*expStr)++;
        if (op == '*') {
            result *= number(expStr);
        } else if (op == '/') {
            result /= number(expStr);
        } else {
            result %= number(expStr);
        }
    }
    return result;
}

下一步就是把加减法里的number解析都换成term解析，换完之后的expr函数会长这样：

int expr(const char **expStr)
{
    int result = term(expStr);
    while (**expStr == '+' || **expStr == '-') {
        char op = **expStr;
        (*expStr)++;
        if (op == '+') {
            result += term(expStr);
        } else {
            result -= term(expStr);
        }
    }
    return result;
}

实验下，确认我们的表达式解析器可以按照正确的优先级计算加减乘除了。

加入括号的处理

括号的运算优先级是比乘除法还要高的，所以我们新增一个非终结符factor（因子），用来在文法中描述它：

expr -> expr '+' term | expr '-' term | term
term -> term '*' factor | term '/' factor | factor
factor -> number | '(' expr ')'
number -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

嘿嘿，这次就真的不给大家贴代码了，相信这次大家应该可以熟练的搞定代码，毕竟已经是个成熟的程序猿了。

完整的代码存放在SlimeExpressionC，需要的同学可以自取，今天的入门课就到这里。