今天就要开始正式写表达式解析器了，第一章的核心代码一共二十行都不到，包简单包学会，但是里面涉及的原理知识可能要花点时间讲一讲。

首先为了能快速简单的开始写我们的解析器，先要对表达式的规则做一定简化：

暂时只考虑最简单的同优先级的运算，也就是加减法
每个字符代表一个元素，也就是暂时只支持个位数的运算（当然计算结果可以超出个位数）

然后我们会采用递归加循环的方式来解析表达式，还玩不转递归的同学必须要先过递归这道坎。

上下文无关文法

我们学习语法分析先得从文法入手，文法是解析表达式的关键，一个优秀的文法可以指导我们轻松的写出解析表达式的递归逻辑。这里的文法一般说的是上下文无关文法，后面就简称文法了。文法具体是什么，翻开书本或者打开wiki，看了半天定义可能还是一头雾水。我们来举个例子说明：

1 2	sum -> num '+' num num -> '0' \| '1' \| '2' \| '3' \| '4' \| '5' \| '6' \| '7' \| '8' \| '9'

这是一个解析两数和的文法。文法包含4个元素：

终结符号：就是例子里的'+'、'0'、'1'…'9'，他们都是确定的字符。

一段可解析的表达式，最终总归能分解成这些终结符号且只能包含这些终结符号。什么意思呢？比如说1+2在这个例子的文法里就是可解析的，+1+仅包含终结符所以可能是可解析的，但是a+1或者1?2这种包含了别的符号所以肯定是不可解析的。
非终结符号：就是例子里的'sum'和'num'，他们都是由终结符或者非终结符组成的组合。

说起来他们就是描述文法时用的中间变量，最后在递归逻辑中的表现可能就是对应到一个递归函数上，要尽量使他们可复用。
产生式：例子的两行，每行就是一个产生式，他表达了一个非终结符是由什么组合成的，也就是说是用来描述符号之间关系的。
开始符号：文法需要指定一个非终结符号为开始符号，这个例子里面就是'sum'。

开始符号的意义就是明确一下你最后要解析出来的是个什么。在这个例子里，最终想要解析出来的是一个求两数和的表达式，而不是一个数字。

好了，接着用这个例子演示下怎么用文法来进行推导，人肉推导一下1+2：

过程：
因为 '1' = num，且 '2' = num
所以 '1+2' = num '+' num
因为 num '+' num = sum
所以 '1+2' = sum
结论：
sum(1+2) = num(1) '+' num(2) = '1+2'

人脑推导这种简单的文法还是很简单的，但是电脑可做不到。为了让电脑可以按照文法解析表达式，我们要用到递归的办法，示例的伪代码如下：

int num(表达式) {
    解析 '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
}
int sum(表达式) {
    num(表达式);
    解析 '+'
    num(表达式);
}

这样调用sum('1+2')就可以正常的依次解析'1'、'+'、'2'了，是不是很直观？用文法配合递归的方法，就可以很轻松的解析表达式。当然伪代码里还省略了很多细节，后面我们再补充。

加减法表达式的文法

首先列出来加减法表达式的文法：

① 正确示范
expr -> expr '+' num | expr '-' num | num
num  -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

② 错误示范
expr -> num '+' expr | num '-' expr | num
num  -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

这里把正确示范和错误示范都列出来了，虽然两者都可以解析加减法表达式，但是②里的优先级是有问题的。具体是什么问题，我们用3-2+1为例子分析一下：

① 正确优先级
推导过程：
因为 expr = expr '+' num | expr '-' num | num，且 num 是只能包含数字的，只有 expr 可以继续展开
所以 expr(3-2+1) = expr(3-2) '+' num(1)
继续推导得 expr(3-2) = expr(3) '-' num(2)
继续推导得 expr(3) = num(3)
递归求解：
expr(3) = num(3) = 3
expr(3-2) = expr(3) '-' num(2) = 3 - 2 = 1
expr(3-2+1) = expr(3-2) '+' num(1) = 1 + 1 = 2

② 错误优先级
推导过程：
expr(3-2+1) = num(3) '-' expr(2+1)
expr(2+1) = num(2) '+' expr(1)
expr(1) = num(1)
递归求解：
expr(1) = num(1) = 1
expr(2+1) = num(2) '+' expr(1) = 2 + 1 = 3
expr(3-2+1) = num(3) '-' expr(2+1) = 3 - 3 = 0

虽然乍看两个文法都可以解析加减法表达式，但是仔细推导后就会发现只有文法①是正确的。

消除左递归

接下来就要试一试用递归来实现这个文法了，但是刚开始写就会发现悲催了：

int expr(表达式) {
    expr(表达式);
    ...
}

这不就是一个死循环式的无限递归么！？

02-A

这里就要引入一个消除左递归的概念。

我们现在遇到的情况是一种直接左递归，也就是类似A->Aα这种文法，这里用大写英文字母表示非终结符，小写希腊字母表示终结符，在一个产生式里的第一个元素就是产生式左侧的非终结符自身，这就叫做直接左递归。A->Aα只是举个例子哈，但是它其实是个非法的文法，因为永远包含非终结符，所以永远停不下来😂。

最简单且合法的直接左递归文法应该是A->Aα|β，我们人肉分析一下它的“特色”可以得出：A可以匹配的表达式一定是一个β后面跟着0到无限个α。所以说起来这个文法可以转换成：

1	A -> β {α} // {} 表示内部元素可以出现 0 - N 次

这样的话就可以用递归配合循环来写解析逻辑了，后面我们实际上就会用这种方式来写解析逻辑。

但是这种文法看起来不是很直观，括号嵌套多了看着眼花，所以我们还要讨论另一种变换形式的文法：

1 2	A -> β B B -> α B \| null // null 是什么意思就不用解释了吧？……

大家自己思考一下，应该就能发现这个文法和A->Aα|β其实是一模一样的。拿一个βαα解析下作个实验：

1	A(βαα) = β B(αα) = β α B(α) = β α α B(null) = β α α

实现加减法！

把加减法表达式的文法消除左递归，得到：

1
2
3

expr  -> num expr1
expr1 -> '+' num expr1 | '-' num expr1 | null
num   -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

然后我们就可以去写对应的逻辑代码了，前面也说过了实际写的时候我们会把expr函数写成递归配合循环式的，也就是类似这样：

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

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