编译原理入门课：（一）用最简单的语法分析器解析加减法

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

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

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

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

上下文无关文法

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

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

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

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

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

2. 非终结符号：就是例子里的 'sum' 和 'num' ，他们都是由终结符或者非终结符组成的组合。

   说起来他们就是描述文法时用的中间变量，最后在递归逻辑中的表现可能就是对应到一个递归函数上，要尽量使他们可复用。

3. 产生式：例子的两行，每行就是一个产生式，他表达了一个非终结符是由什么组合成的，也就是说是用来描述符号之间关系的。

4. 开始符号：文法需要指定一个非终结符号为开始符号，这个例子里面就是 '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(表达式);
    ...
}

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

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

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

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

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

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

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

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

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

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

实现加减法！

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

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

真的没有骗你们，核心代码一共就这么点。因为我们限定了表达式的规则，所以每一个字符都是一个元素，每识别一个元素后对字符串指针做自增操作就可以移动到下一个元素继续进行分析，逻辑可以写得十分的简单。因为我们也不用纠结运算符优先级，所以每识别一个运算符，就可以直接进行计算得到进一步的结果。

这么短的代码应该难不倒各位吧？在理解了文法的原理后，就可以理解这短短十几行代码里的奥秘。完整的代码放在 SlimeExpressionC ，需要的同学可以自取，今天的入门课就到这里啦。

其它章节

（前言）实现一个表达式解析计算器

（一）用最简单的语法分析器解析加减法

（二）递归解析中怎么处理运算符优先级

（三）简单错误处理逻辑以及负数的解析

（四）用词法解析处理多位数字和空白符

（五）解析ID型词法和函数调用语法

（六）用函数表来优化函数解析的逻辑