编译原理（三）：语法分析之自底向上分析算法
编译原理系列第三篇，更加实用的语法分析算法~
编译原理（三）：语法分析之自底向上分析算法
自底向上分析算法
自顶向下的算法貌似到头了，是时候寻找新的算法了！
LR 算法
LR 分析算法也被叫做移进-规约 算法，是语法分析器的自动生成器中广泛采用的算法，例如：YACC 等。相比于 LL(1)，它的分析同样高效，并且不需要对文法进行特殊处理。LR 算法之所以被称为是 移进-规约算法，是因为算法中两个核心操作是：移进（shift）和规约（reduce）。
- 移进：不规约，继续展开右边的式子
- 规约：把推导式右边的部分，归成左边的非终结符
LR(0) 算法
先来介绍 LR 中最简单的 LR(0)：从左（L）向右读入程序，最右（L）推导（严格来说是最右推导的逆过程），不用前看符号来决定产生式的选择（0 个前看符号，这里的 0 有点特殊，后面会提到）。它容易实现，但是有一些缺点，比如导致错误发现延后、会出现冲突（后面会看到）。
算法 3.0
为了方便标记语法分析器已经读入了多少输入，先引入一个点记号：•，• 左边表示已经读入的输入，• 右边表示剩余的输入。
接下来以这个文法为例子：
1
2
3
4
50: E -> E + T
1: | T
2: T -> T * F
3: | F
4: F -> num
先看看 LR(0) 算法处理 3 + 4 * 5 的过程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15• 2 + 3 * 4 # 开始
2 • + 3 * 4 # 首先读入 2，移进
F • + 3 * 4 # 根据语法规则 4 进行规约，得到
T • + 3 * 4 # 根据语法规则 3 进行规约，得到
E • + 3 * 4 # 根据语法规则 1 进行规约，得到
E + • 3 * 4 # 继续读入 +，移进
E + 3 • * 4 # 继续读入 3，移进
E + F • * 4 # 根据语法规则 4 进行规约，得到
E + T • * 4 # 根据语法规则 3 进行规约，得到
E + T * • 4 # 继续读入 *，移进
E + T * 4 • # 继续读入 4，移进
E + T * F • # 根据语法规则 4 进行规约，得到
E + T • # 根据语法规则 2 进行规约，得到
E • # 根据语法规则 0 进行规约，得到
S • # 回到初始符
如果从下往上看整个过程，其实就是文法的最右推导，那么自然，LR(0) 算法就是文法最右推导的逆过程。
接下来，最重要的问题是，怎么确定某一步是要移进还是要规约呢？例如当我们得到了 E • + 3 * 4 之后，为什么不把 E 规约成 S 呢？
要回答这个问题，我们再看一个更加简单的例子：
1
2
30: S' -> S$
1: S -> xxT
2: T -> y
分析输入串 xxy$。
这个文法的语法要求其实非常简单，就是 xxy。那么第 0 条规则的作用是什么呢？
- 保证即起始的非终结符符号，不出现在任何推导的右部。当然，起始符号是有可能出现在推导的右部的，在加上
S'之后就可以避免这种情况。 - $ 是输入的结束标记符，放在输入的最后。各位可以类比于 C 语言字符串的
EOF。当然每个语法分析器可以自己来规定结束符号，这边先利用$统一表示一下。
接下来类比词法分析的状态转移图，我们也可以画出文法的状态转移图：
有以下几点需要解释一下：
- 在节点 1 中，
S' -> •S$表示接下来碰到的输入，要可以匹配 • 右边的 S。 - 既然接下来期待匹配的是 S，那么匹配 S 其实就是匹配 xxT，所以
S' -> •S$和S -> •xxT就合并到了一起。对于节点 3 同理。 - 那么方向上的字符表示什么意思呢？比如 1->2 的 x，就是碰到 x 后，状态怎么转移。所以非常直观，碰到一个 x 之后 • 自然就往后挪动了一位，就是节点 2 了。其他的也是同理的。
- 那么还有 2 条特殊的边，1->6、3->5。注意，上面那一条中，我用的是“...碰到 x...”，这里用 “碰到” 而不是 “读入”，含义就是这个图表示的整个转移过程，不仅有移进，还会有规约，如果这里没法理解也没事，下面会有例子来直观地表示什么叫 “碰到”；以 3->5 为例，在碰到 T 之后，就转移到了节点 5；1->6 同理，并且 6 号节点还比较特殊，其实是即将终结的状态，如果继续读入读到一个结束符，那么就分析成功了。
- 识别出了某一个推导式完整的右部，就要开始规约；否则继续移进；输入消耗完毕之后，在终结状态上，那么就接受，反正拒绝。
依旧有些抽象吧？来看个具体的例子，那我们就假设输入是 S = xxy$ 好了：
1
2
3
4
5
6
7
8
9•xxy$ # 开始；在节点 1
x•xy$ # 读入 x；节点 1 在碰到 x 之后，走向节点 2
xx•y$ # 读入 x；节点 2 在碰到 x 之后，走向节点 3
xxy•$ # 读入 y；节点 3 在碰到 y 之后，走向 4
xx•T$ # 到节点 4 后，即 T-> y•，由于此时 • 已经在最后了，这个时候说明已经识别出了某一个推导式完整的右部，就要开始规约：移除规则 2 的右部，压入规则 2 的左部，返回节点 3
xxT•$ # 走到节点 3 后，• 前面是非终结符 T，节点 3 在碰到 T 之后，走到节点 5
•S$ # 到节点 5 后，同理，开始规约，移除规则 1 的右部，压入规则 1 的左部，返回节点 1
S•$ # 走到节点 1 后，• 前面是非终结符 S，节点 1 在碰到 S 之后，走到节点 6
S$• # 读入 $；节点 6 就是期待一个结束符 $，那么就接受了。
（再放一次这个图，方便对照）
如果我们把图中的方框，变成圆圈的话，就非常类似词法分析里的 DFA 了。整个过程是先走出去，再走回来，最后要走到终结状态。
那么有了这有一个DFA 之后，同样类比词法分析里的转移表，我们也可以构造出语法分析的分析表：
| 动作（ACTION） | 转移（GOTO） | ||||
|---|---|---|---|---|---|
| 状态 | x | y | $ | S | T |
| 1 | s2 | g6 | |||
| 2 | s3 | ||||
| 3 | s4 | g5 | |||
| 4 | r2 | r2 | r2 | ||
| 5 | r1 | r1 | r1 | ||
| 6 | accept | ||||
其中，s 是 shift，后面跟着的数字代表转移图里的状态；r 就 reduce，后面跟着的数字代表规则的编号；g 与 s 类似，区别在于 s 是遇到一个终结符，而 g 是遇到一个非终结符。有了这个表之后呢，就很容易指导语法分析的过程了，用一个栈实现，非常直观：
1
2
3
4
5
6
7
8
9输入: S = xxy$
stack = [1] # 栈里面存储的是状态与符号。那么初始状态自然只有一个节点 1 在栈里面
stack = [1, x, 2] # 栈顶是 1，查表可得 s2，需要读一个输入 x，然后压入 x、2
stack = [1, x, 2, x, 3] # 栈顶是 2，查表可得 s3，需要读一个输入 x，然后压入 x、3
stack = [1, x, 2, x, 3, y, 4] # 栈顶是 3，查表可得 s4，需要读一个输入 y，然后压入 y、4
stack = [1, x, 2, x, 3, T, 5] # 栈顶是 4，查表得 r2，需要按照规则 2 进行规约，弹出规则 2 的右部与栈中的状态：4、y，压入规则 2 的左部 T，然后查表可得 g5，还需要压入 5
stack = [1, S, 6] # 栈顶是 5，查表可得 r1，需要按照规则 1 进行规约，弹出规则 1 的右部与栈中的状态：5、T、3、x、2、x，压入规则 1 的左部 S，然后查表可得 g6，还需要压入 6
accept = True # 栈顶是 6，读入一个字符 $，查表可得 accept，即接受
大家可以尝试用代码实现一下 LR(0) 分析表的构造，以及在有了分析表之后，通过分析表实现语法分析，我这里为了避免篇幅过长，就省略了。
前面提到，LR(0) 有 2 个缺陷，一个是错误发现的时机延迟；一个是会出现冲突。
LR(0) 的错误时机延后问题
先来看错误发现的时机延迟：
1
2
30: S' -> S$
1: S -> xS
2 S -> y
对于这么一个文法来说，它的转移图为：
| 动作（ACTION） | 转移（GOTO） | |||
|---|---|---|---|---|
| 状态 | x | y | $ | S |
| 1 | s2 | s3 | g4 | |
| 2 | s2 | s3 | g5 | |
| 3 | r2 | r2 | r2 | |
| 4 | accept | |||
| 5 | r1 | r1 | r1 | |
假设输入 S = xyx：
1
2
3
4
5
6
7
8输入: S = xyx$
stack = [1] # 栈里面存储的是状态与符号。那么初始状态自然只有一个节点 1 在栈里面
stack = [1, x, 2] # 栈顶是 1，查表可得 s2，需要读一个输入 x，然后压入 x、2
stack = [1, x, 2, y, 3] # 栈顶是 2，查表可得 s3，需要读一个输入 x，然后压入 x、3
stack = [1, x, 2, S, 5] # 栈顶是 3，查表得 r2，需要按照规则 2 进行规约，弹出规则 2 的右部与栈中的状态：3、y，压入规则 2 的左部 S，然后查表可得 g5，还需要压入 5
stack = [1, S, 4] # 栈顶是 5，查表可得 r1，需要按照规则 1 进行规约，弹出规则 1 的右部与栈中的状态：5、S、2、x，压入规则 1 的左部 S，然后查表可得 g4，还需要压入 4
accept = False # 栈顶是 4，读入一个字符 x，查表为空，即拒绝
stack = [1, x, 2, y, 3] 后），发现剩下的输入不是 \(，其实就可以报错了，否则继续规约，最后也得报错，早报错当然比晚报错好。状态 5 也同理。反映在分析表上，就是状态 3、5 遇到 x、y 的时候，直接报错而不是规约： <table class="tg"> <thead> <tr> <th class="tg-nrix"></th> <th class="tg-nrix" colspan="3">动作（ACTION）</th> <th class="tg-nrix" colspan="1">转移（GOTO）</th> </tr> </thead> <tbody> <tr> <td class="tg-nrix">状态\符号</td> <td class="tg-nrix">x</td> <td class="tg-nrix">y</td> <td class="tg-nrix">\)
<td class="tg-nrix">S</td>这么做的话，就可以将报错的时机提前。并且分析表的规模也会减小，对于一个比较大的语言来说，分析表可能会很大，能够节省肯定是件好事。
LR(0) 的冲突
接下来看这个文法：
1
2
3
40: S -> E$
1: E -> T+E
2: E -> T
3: T -> n
转移图如下：
可以看到，对于状态 3 来说，既可以规约，也可以移进，这就出现了 移进-规约冲突。如果我们按照解决错误发现时机延迟的方式来看的话，在这里，3号状态应该只在遇到 $ 的时候做规约，其他情况做移进，如果所有情况都做规约的话，4、6 节点就不可能到达了。
SLR 算法
算法 3.1
那么可以总结出来，LR(0) 算法的两个缺陷，解决方式为：只对在 FOLLOW 集的非终结符进行规约。这个算法就是 SLR 算法。SLR 算法和 LR(0) 分析算法基本步骤相同，仅区别于对归约的处理：对于状态 i 上的项目 X -> α •，仅对 y ∈ FOLLOW(X) 添加 ACTION[i, y]。
但是，SLR 也仅仅是解决了部分冲突。来看这个文法：
1
2
3
4
5
6S' -> S$
S -> L=R
S -> R
L -> *R
L -> id
R -> L
它的转移图如下：
可以看到，节点 2，出现了移进-规约冲突。我们可以按照 SLR 算法来试试， 首先计算 FOLLOW(R)，如果你已经忘记怎么计算了，可以去第二篇里回顾一下 FOLLOW 集的计算方式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24FOLLOW 集计算过程如下：
# 对于规则 0，开始计算
temp = FOLLOW(S') # temp = {}
temp = {$}
FOLLOW(S) |= temp # FOLLOW(S) = {$}
temp = FIRST(S)
# 对于规则 1，开始计算
temp = FOLLOW(S) # temp = {$}
FOLLOW(R) |= temp # FOLLOW(R) = {$}
temp = FIRST(R) # temp = {*, id}
temp = {=}
FOLLOW(L) |= temp # FOLLOW(L) = {=}
temp = FIRST(L)
# 对于规则 2，开始计算
temp = FOLLOW(S) # temp = {$}
FOLLOW(R) |= temp # FOLLOW(R) = {$}
# 对于规则 3，开始计算
temp = FOLLOW(L) # temp = {=}
FOLLOW(R) |= temp # FOLLOW(R) = {$, =}
... # 避免篇幅过长，省略
可以看到 FOLLOW(R) 中包含了 =，所以按照 SLR 算法，这里是可以规约的。所以，利用 FOLLOW 集试图来消除移进-规约冲突是不够完善的。
LR(1) 算法
算法 3.2
首先，将为 [A -> α•β, a] 的项称为 LR(1) 项，其中 A-> α•β 是一个产生式，a 是一个终结符（$ 也视为一个终结符），它表示在当前状态下，A 后面必须紧跟的终结符，即该项的前看符号。
可以看到，LR(1) 的项（即转移图中一个状态中的一行），对比 LR(0) 的项就是多了一个元素；而对比 SLR 与 LR(1)，区别就是 SLR 的前看符号是 FOLLOW(A)，而 LR(1) 的前看符号则需要求 FIRST_S 集。
那么 LR(1) 的前看符号具体是怎么计算的呢？对项目 [X -> α•Yβ, a]，添加 [Y -> •Y, b]到项目集，其中 b ∈ FIRST_S(βa)。
举几个例子，还是来看这个文法：
1
2
3
4
5
6S' -> S$
S -> L=R
S -> R
L -> *R
L -> id
R -> L
转移图如下：
计算节点 1 中的项的前看符号：
1
2
3
4
5
6
7
81. S' -> •S$: [S' -> •S$ , $] # 第一条的前看符号肯定是 $；β 为空，a 为 $
2. S -> •L=R: [S -> •L=R , $] # 看 1，计算 FIRST_S($)，就是 $；β 为 =R，a 为 $
3. S -> •R: [S -> •R , $] # 看 1，计算 FIRST_S($)，就是 $；β 为空，a 为 $
4. L -> •*R: [L -> •id , $] # 看 2，计算 FIRST_S(=R$)，就是 =
5. L -> •id: [L -> •id , $] # 看 2，计算 FIRST_S(=R$)，就是 =
6. R -> •L: [R -> •L , $] # 看 3，计算 FIRST_S($)，就是 $；β 为空，a 为 $
7. L -> •*R: [R -> •L , $] # 看 6，计算 FIRST_S($)，就是 $
8. L -> •id: [L -> •id , $] # 看 6，计算 FIRST_S($)，就是 $
其他节点的计算方式与上面这个一致，为了避免篇幅过长就不写过程了。
这样，前看符号就更加精确了，避免了错误发现延后，以及冲突的出现。
那么 LR(1) 有没有缺点呢？当然有，就是二义性文法。实际上目前也没有什么算法可以处理所有的二义性文法。不过，有几类二义性文法是很容易理解的，因此，在 LR 分析器的生成工具中，可以对它们特殊处理，比如：优先级（* 比 + 高）、结合性（算数符左结合或者右结合）、悬空 else（多个 if-esle 块，if 应该与哪个 else 配对），这几种二义性文法都非常常见。
例如：
1
2
3E -> E + E •
E -> E • + E
E -> E • * E
按照第一条我们应该规约，按照后面两条应该移进。但如果我们告诉语法分析器，加法是左结合的，并且乘法比加法优先级高，那么分析器只需要看一下后面是加号还是乘号，如果后面是加号那么就规约，因为加号是左结合的，遇到完整的 E+E 就可以先做计算了；如果后面是乘号就移进，因为乘号优先高，移进来保证乘法先做计算。
所以理论上 LR(1) 是不能分析二义性文法的，但是我们可以通过提示语法分析器来解决二义性的问题。
抽象语法树（AST）
这是一个简单编译器的阶段划分：
可以看到，语法分析器的输入的记号流，输出是抽象语法树。但目前，我们仅仅能对一个输入 S 回答是否符合语法，然后回答 Yes 或者 No，所以我们还需生成抽象语法树，然后传给语义分析器做处理。
在讲抽象语法树之前，先来回顾一下分析树，其实它也可以叫“具体分析树”（CST），我们在系列第二篇讲 CFG 的推导的时候，提到了它。
来看这么一个分析树：
我们知道，分析树很具体地表明对句子推导的过程，也就是其中包含了语法，但是同时也包含了不必要的信息，而这些信息在实现的过程中，也是要占用内存的（编译器要可以编译上万行的代码）。那么问题来了，什么是“不必要的信息”呢？对于这个例子来说，编译只需要知道运算符和运算数，至于优先级、结合性等已经在语法分析部分处理掉了。
因此，这个分析树就可以“抽象”为这样一个抽象语法树：
抽象语法树（abstract syntax code，AST）是源代码的抽象语法结构的树状表示，树上的每个节点都表示源代码中的一种结构，这所以说是抽象的，是因为抽象语法树并不会表示出真实语法出现的每一个细节，比如说，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现。抽象语法树并不依赖于源语言的语法，也就是说语法分析阶段所采用的上下文无文文法，因为在写文法时，经常会对文法进行等价的转换（消除左递归，回溯，二义性等），这样会给文法分析引入一些多余的成分，对后续阶段造成不利影响，甚至会使各个阶段变得混乱。因此，很多编译器经常要独立地构造语法分析树，建立一个清晰的接口。
具体实现起来，AST 就是一组预定义的数据结构，抽象地描述了语法规则，对于 C 语言来说，可以用结构体；对于 Python 来说可以用类。
最后有个需要注意的地方，源程序一旦被转换成抽象语法树，那么源代码就都被丢弃了，后续的阶段只处理抽象语法树。所以抽象语法树必须保留足够的源代码信息，例如每个语法结构在源代码中的位置（文件、行号、列号等），这样后续的检查阶段才能精确的报错，所以抽象语法树必须仔细地设计。
总结
至此，语法分析相关的知识都讲完了。
相关算法稍多，来总结一下吧：
语法分析器的实现方法：
- 手工方式
- 递归下降分析器
- 使用语法分析器的自动生成器
- LL(1)
- LR(1)
两种方式在实际的编译器中都有广泛的应用，自动的方式更适合快速对系统进行原型。
这个系列别的不说
画图表都画的累死了...
好在编译原理系列马上结束了！
