编译原理系列第三篇，更加实用的语法分析算法~

编译原理（三）：语法分析之自底向上分析算法

自底向上分析算法

自顶向下的算法貌似到头了，是时候寻找新的算法了！

LR 算法

LR 分析算法也被叫做移进-规约算法，是语法分析器的自动生成器中广泛采用的算法，例如：YACC 等。相比于 LL(1)，它的分析同样高效，并且不需要对文法进行特殊处理。LR 算法之所以被称为是 移进-规约算法，是因为算法中两个核心操作是：移进（shift）和规约（reduce）。

移进：不规约，继续展开右边的式子
规约：把推导式右边的部分，归成左边的非终结符

LR(0) 算法

先来介绍 LR 中最简单的 LR(0)：从左（L）向右读入程序，最右（L）推导（严格来说是最右推导的逆过程），不用前看符号来决定产生式的选择（0 个前看符号，这里的 0 有点特殊，后面会提到）。它容易实现，但是有一些缺点，比如导致错误发现延后、会出现冲突（后面会看到）。

算法 3.0

为了方便标记语法分析器已经读入了多少输入，先引入一个点记号：•，• 左边表示已经读入的输入，• 右边表示剩余的输入。

接下来以这个文法为例子：

0: E -> E + T
1:    | T
2: T -> T * F
3:    | F
4: F -> num

先看看 LR(0) 算法处理 3 + 4 * 5 的过程：

• 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
3

0: 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$ 好了：

•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 是遇到一个非终结符。有了这个表之后呢，就很容易指导语法分析的过程了，用一个栈实现，非常直观：

输入: 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
3

0: 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：

输入: 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，查表为空，即拒绝

我们结合上面的过程，在仔细观察表中的状态 3，其实可以这么理解：当栈顶是状态 3 的时候，不管输入的符号是什么，都要开始规约，所以状态 3 的那一行，有 3 个 r2。状态 5 也同理。而我们观察文法可以发现，S 后面只能跟 $，那么在状态 4 的时候，输入必须只剩 $，否则就不能被接受，继续倒退一步，如果我们在状态 3 上即将开始规约的时候（即已经得到了 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>

1 s2 s3 g4 2 s2 s3 g5 3 r2 4 accept 5 r1

这么做的话，就可以将报错的时机提前。并且分析表的规模也会减小，对于一个比较大的语言来说，分析表可能会很大，能够节省肯定是件好事。

LR(0) 的冲突

接下来看这个文法：

0: 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 也仅仅是解决了部分冲突。来看这个文法：

S' -> S$
S  -> L=R
S  -> R
L  -> *R
L  -> id
R  -> L

它的转移图如下：

可以看到，节点 2，出现了移进-规约冲突。我们可以按照 SLR 算法来试试，首先计算 FOLLOW(R)，如果你已经忘记怎么计算了，可以去第二篇里回顾一下 FOLLOW 集的计算方式：

FOLLOW 集计算过程如下：
# 对于规则 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)。

举几个例子，还是来看这个文法：

S' -> S$
S  -> L=R
S  -> R
L  -> *R
L  -> id
R  -> L

转移图如下：

计算节点 1 中的项的前看符号：

1. 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
3

E -> 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 来说可以用类。

最后有个需要注意的地方，源程序一旦被转换成抽象语法树，那么源代码就都被丢弃了，后续的阶段只处理抽象语法树。所以抽象语法树必须保留足够的源代码信息，例如每个语法结构在源代码中的位置（文件、行号、列号等），这样后续的检查阶段才能精确的报错，所以抽象语法树必须仔细地设计。