🍊 编译原理（二）：语法分析之自顶向下分析算法

这是橘子杀手的第 28 篇文章
题图摄于：北京 · 北海公园

☁️ 语法分析器

这是一个简单编译器的阶段划分：

上一篇提到过，词法分析器接受字符流，产出记号流。这一篇我们来看语法分析器。词法分析器产出的记号流就是语法分析器的输入，然后语法分析器会判断输入的记号流是否合法，即是否符合语法规则，然后产出抽象语法树。接下来会逐步介绍这些步骤具体是如何实现的  

🌧 上下文无关文法（CFG）

既然语法分析器要判断记号流是否符合特定的语法规则，那么首先我们就需要形式化地来描述语言的语法规则。这就是 CFG 的作用：一个用来描述语言语法规则的数学工具。

❄️ 背景：乔姆斯基文法体系

很久以前，一位叫乔姆斯基的教授打算利用数学来研究人类自然语言的结构和规律。研究期间他发明了很多数学工具和方法，被后人称为乔姆斯基文法体系，其中一个就是 CFG。从我们后人的角度来看，一开始他本打算用这些数据工具来研究自然语言，却无意中用在了计算机领域，正是无心插柳柳成荫  

乔姆斯基文法体系给出了 4 类文法：

1. 0 型文法：任意文法，在程序设计语言当中不常用
2. 1 型文法：上下文有关文法，在程序设计语言当中也不常用
3. 2 型文法：即 CFG，这种文法可以用来描述语言的语法结构。
4. 3 型文法：又叫做正则文法，其实词法分析篇已经讨论过了，即正则表达式，这种文法可以用来描述语言的词法结构。

在这些文法中，0 型文法的表达能力最强，3 型文法最弱，画出来就是这样：

❄️ CFG 的数学定义

接下来给出 CFG 的数学定义。

上下文无关文法 G 是一个四元组：G = (T, N, P, S)

其中:

1. T: 终结符集合，终结符一般用小写
2. N: 非终结符集合，非终结符一般用大写
3. P: 一组产生式规则
• 规则的形式：X -> β1 β2 β3 ... βn
• X∈N, βi∈(T∪N)，即产生式的左边只能是非终结符，右边可以是非终结符或者终结符
4. S: 唯一的开始符号
• S∈N，即只能是非终结符

举个例子，G = (T, N, P, S) 中对应的各个值是：

1. T = {num, id, +, *}
2. N = {E}
3. S = {E}
4. P = {E -> num, E -> id, E -> E+E, E -> E*E}

那么对于这样一个文法，我们就可以这样来表示这个 CFG：

E -> num
E -> id
E -> E + E
E -> E * E

为了简化写法，避免重复写 E ->，可以这样来表示：

E -> num
   | id
   | E + E
   | E * E

❄️ CFG 的推导

推导的定义：给定文法 G，从 G 的开始符号 S 开始，用产生式的右部替换左侧的非终结符，不断重复，直到不出现非终结符为止。最后的得到的结果，我们把它称为 句子。

推导的方式，根据替换的顺序，分为 2 种：

1. 最左推导: 每次总是选择最左侧的符号进行替换
2. 最右推导: 每次总是选择最右侧的符号进行替换

举个例子，假如有以下文法：

S -> N V N
N -> s
   | t
   | g
   | w
V -> e
   | d

最左推导的示例（当然，这只是其中一种写法）：

S -> N V N
S -> s V N  # 任选一个终结符，比如 s
S -> s e N  # 任选一个终结符，比如 e
S -> s e s  <- 这个就是 “句子”

最右推导的示例（这也只是其中一种写法）：

S -> N V N
S -> N V s  # 任选一个终结符，比如 s
S -> N e s  # 任选一个终结符，比如 e
S -> s e s  <- 这个就是 “句子”

由此我们可以得出语法分分析的具体含义：给定文法 G 和句子 s，回答是否存在对句子 s 的推导？还是以上面那个文法为例，假如给定 s = ses，应该回答 yes；给定 s = sss 应该回答 no。

回到一开始提到的，语法分析器的输入是记号流，其实就是句子 s；而判断句子是否符合语法规则，就可以利用文法 G 来做判断。

❄️ 分析树与二义性

仔细观察上面的推导过程，实际上可以使用 树 来表示。每个内部节点代表的是非终结符；叶子节点代表终结符；每一步推导代表如何从双亲节点生成它的直接孩子节点。

例如文法：

E -> num
   | id
   | E + E
   | E * E

假设我们要推导这个句子：3 + 4 * 5，那么最左推导，实际上会有 2 种：

第一种，先选择 E + E：

E -> E + E
E -> 3 + E
E -> 3 + E * E
E -> 3 + 4 * E
E -> 3 + 4 * 5

对应的分析树：

第二种

E -> E * E
E -> E + E * E
E -> 3 + E * E
E -> 3 + 4 * E
E -> 3 + 4 * 5

通过对比可以看出，分析树的含义取决于对树进行后序遍历的结果。后续遍历即：左子树 -> 右子树 -> 根结点。所以对于第一种方式来说，应该是 3 + (4 * 5) = 23；对于第二种方式来说，是 (3 + 4) * 5 = 35。按照我们的常识来说，肯定是第一种才是我们想要的结果。

所以这个文法就是 二义性文法：给定文法 G，如果存在句子 s，它有两棵不同的分析树，那么称 G 是二义性文法。

从编译器角度来看，出现二义性文法，那么同一个程序会有不同的含义，即程序运行的结果不是唯一的，却都是“合理”的。这肯定是不行的，好在重写文法就可以解决二义性  

重写文法需要根据原文法来确定应该如何重写，所以需要具体例子具体分析。对于上面这个例子来说，我们想要先计算 *，则可以将推导过程分解为先计算 T = F * F，然后在计算 E = T + T。

E -> T + T
T -> F * F
F -> num
   | id

但是这样的话，+ 和 * 都只能出现一次，所以我们还可以再改写成递归的结构：

E -> E + T
   | T
T -> T * F
   | F
F -> num
   | id

推导句子 3 + 4 * 5 的分析树如下：

这个分析树的后续遍历就是正确的算术优先级的顺序。同时大家仔细观察也会发现，这个改写后的文法是满足算术运算符的左结合性的。

❄️ 自顶向下分析算法

上面说的分析方式，都是从开始符号出发推出句子，因此称为自顶向下分析，对应于分析树就是自顶向下的构造顺序。

自顶向下分析算法的定义：

• 目标：给定文法 G 和句子 s，回答 s 是否能够从 G 推导出来?
• 基本算法思想：从 G 的开始符号出发，随意推导出某个句子 t，比较 t 和 s
• 若 t == s，则回答 “是”
• 若 t != s，则...

需要注意的是，如果 t != s，我们是不能直接回答 “否” 的，因为 t 有很多种可能性，所以只有当 G 可以推导出的所有句子 t 都不等于 s 的时候，我们才能回答 “否”   

举个例子，假如有以下文法：

S -> N V N
N -> s
   | t
   | g
   | w
V -> e
   | d

我们需要判断它能否推出句子 s = gdw。

算法 1.0

直接遍历所有的可能性，寻找是否有产生与 s 相同句子。

过程如下：

S -> N V N
S -> s V N
S -> s e N
S -> s e s

可以看到，得到的 ses != gdw，所以我们只能回溯：

S -> N V N
S -> ...
S -> s e s <- 回溯
S -> s e N 
S -> s e t

一直重复这个过程，直到推出 gdw，发现与 s 相等，于是回答 “是”。

那么很明显，无脑遍历是没必要的，这样会浪费大量的时间去做回溯  

算法 1.1

在 1.0 的这一步 | s V N 中，我们没有必要继续往下把 V 替换了，因为此时 s != g，所以不管后面怎么遍历，都不可能相等，所有直接回溯 N 即可：

S -> N V N
S -> s V N <- 回溯
S -> t V N <- 回溯
S -> g V N
S -> g e N <- 回溯
S -> g d N
S -> ...

这个优化是非常明显，本来最多需要尝试 4 * 2 * 4 = 32 次，现在只需要 4 + 2 + 4 = 10 次。

大家仔细想想其实就会发现一个问题，这种优化可以如果出现终结符较多的情况，优化效果就会大打折扣，甚至与 1.0 相比差不了多少，比如：

E -> E + T
   | T
T -> T * F
   | F
F -> num
   | id

这样的话，我们只有在替换 F 的时候起到了优化的作用，如果 F 无法匹配，依旧需要对 T、E 做回溯，例如推导 1 + 1 * 1：

E -> E + T
E -> T + T
E -> T * F + T
E -> F * F + T
E -> 1 * F + T
E -> 1 * 1 + T <- 回溯
E -> 1 * F + T <- 回溯
E -> F * F + T <- 回溯
E -> T * F + T
E -> T * F * F + T
E -> F * F * F + T
E -> 1 * F * F + T
E -> 1 * 1 * F + T <- 回溯
E -> F * F * F + T <- 回溯
E -> T * F * F + T <- 回溯
E -> T * F + T <- 回溯
E -> T + T
E -> F + T
E -> 1 + T
E -> 1 + T * F
E -> 1 + T * F * F
...各种回溯
E -> 1 + T * F
E -> 1 + F * F
E -> 1 + 1 * F
E -> 1 + 1 * 1

可以看到，虽然 1.1 比 1.0 好了不少，但是有时候还是会进行大量的回溯   

递归下降分析算法

递归下降分析算法 也称为预测分析。它分析高效（线性时间），容易实现（方便手工编码），错误定位和诊断信息准确，被很多开源和商业的编译器所采用，比如 GCC4.0, LLVM, ...。

算法基本思想是，每个非终结符构造一个分析函数，用前看符号指导产生式规则的选择，避免回溯。

算法 2.0

还是这个例子：

S -> N V N
N -> s
   | t
   | g
   | w
V -> e
   | d

判断它能否推出句子 s = gdw。

S -> N V N
# 发现句子的第一个字符是 g
S -> s V N
# 发现句子的第二个字符是 d
S -> s d N
# 发现句子的第三个字符是 w
S -> s d w

“分而治之”的思想，这样就比算法 1.1 还要高效。

但是它与 1.1 有同样的问题，出现终结符较多的情况，优化效果也会大打折扣。所以，递归下降算法还需要继续优化  

LL(1) 分析算法

橘友们坐稳了，这一部分开始，稍微有些难度  

LL(1) 分析算法的原理

算法 2.1

LL(1) 分析算法的定义：从左（L）向右读入程序，最左（L）推导，采用一个（1）前看符号。

LL(1) 分析算法的特点：

• 分析高效(线性时间)
• 错误定位和诊断信息准确
• 有很多开源或商业的生成工具（ANTLR）

算法的基本思想：表驱动的分析算法。表驱动中的 “表”，就是分析表，用于指导语法分析器进行分析。

在介绍 LL(1) 之前，首先来看几个概念：

FIRST 集

FIRST 集就是从非终结符 N 开始推导，得出的句子开头的所有可能终结符的集合。注意：有些地方说 FIRST 集中可以存在 ε，有些地方有说不可以，我偷点懒，就认为 FIRST 集中不存在 ε。

还是这个例子：

S -> N V N
N -> s
   | t
   | g
   | w
V -> e
   | d

S 的 FIRST 集就是 N 的 FIRST 集；N 的 FIRST 集就是 {s, t, g, w}，V 的 FIRST 集就是 {e, d}。

注意，如果 S 自己也可以推出非终结符，例如：

S -> N V N
   | a
...

则 S 的 FIRST 集就是 N 的 FIRST 集并上 {a}，即 FIRST(S) = FIRST(N) ∪ {a}。

那么，FIRST 集到底有什么作用呢？或者我们怎么直观地去理解它？

例如，给定输入 S = sdw，我们推导的第一步是 S -> N V N，那么 FIRST 集就可以直接告诉我们，S 是否可以满足文法的要求，判断的方式就是输入的字符是否在 FIRST 集中。而 S 的第一个字符 s 在 S 的 FIRST 集中，s in {s, t, g, w}，所以第一步可以接受，推导就变成了 S -> s V N；同理，S 的第二个字符，d 也在 V 的 FIRST 集里，所以推导就变成了 S -> s d N，最后 w 也在 N 的 FIRST 集里，所以最终推导出 S -> s d w，那么结果就是接受此句子。

FIRST_S 集

首先给文法加个序号：

0: S -> N V N
1: N -> s
2:    | t
3:    | g
4:    | w
5: V -> e
6:    | d

简单来说，FIRST 集计算 S 的所有可能出现的第一个字符；FIRST_S 集 则是计算每一条产生式，可能出现的第一个字符：

分析表

有了 FIRST_S 集之后，就可以构造 LL(1) 分析表了。

然后画出一个表格，所有的非终结符（为列），再画出所有的终结符（为行），接下来开始填表。例如 N，遍历一遍它的 FIRST 集，比如 s，它遇到 s 的时候，查看 FIRST_S 集，应该是走推导式 1，所以就在 s 那一列，N 那一行对应填上 1。同理，就可以完成这个表格：

所以，分析表可以指导推导的过程，例如，在推导式 N，如果遇到了 t，应该走到哪一条推导式，对应这里就是第 2 条推导式。

NULLABLE 集合

需要注意的是，上面计算 FIRST 集的算法，其实是比较简陋的算法。为什么呢？例如有以下文法：

0: Z -> d
1:    | X Y Z
2: Y -> c
3:    | ε
4: X -> Y
5:    | a

可以看到，Y 可以直接推导出空串（ε），而 X 可以推导出 Y，所以其实 X 也有可能推导出空串。那么 FIRST(Z) 的计算会出现问题：如果 X、Y 都可以推出空串，那么计算 FIRST(Z) 的时候，就会有 Z -> W（X、Y 可以省略，因为可以不消耗输入字符）的规则，所以 FIRST(Z) 应该包含 FIRST(X)、FIRST(Y)、FIRST(W)。因此，若要考虑的周全一些，那么还需要计算哪些非终结符是可能推出空串。

当非终结符 X 满足以下条件的其中一点：

1. X -> ε，即 X 可以直接推出空串
2. X -> Y1 Y2 ... Yn，Y1 Y2 ... Yn 均为非终结符，且都属于 NULLABLE 集合

则 X 属于 NULLABLE 集合。那么对于产生式 M -> XY，有 FIRST(M) = FIRST(X) ∪ FIRST(Y)。

所以经过计算，我们可以得出 FIRST(Z) = {a, c, d}。

可以看到，在产生式右部的第一位开始，出现 NULLABLE 集的的时候，这样求解 FIRST 集更加完善。于是我们可以得出此表：

FOLLOW 集

按照上面的说法，只要得出 FIRST 集，那么我们就可以得出 FIRST_S，进而构造 LL(1) 分析表了。但是问题又来了，还是这个文法：

0: Z -> d
1:    | X Y Z
2: Y -> c
3:    | ε
4: X -> Y
5:    | a

计算 FIRST_S 集如下：

出现 ε 该如何计算呢？我们知道，此时不管输入什么，都应该跳过。举个例子，假如输入是 S = a a d，那么过程如下：

消耗 a，剩余 ad
Z
Z -> X Y Z # 根据 FIRST_S 集可得
Z -> a Y Z # 直接采用推导式 5

消耗 a，剩余 d
Z -> a Y Z # 暂停

我们看到，当输入是 a 的时候，由于 Y 右部没有直接推导得出的 a，所以按理应该回答 no 了。但是我们仔细观察，由于 Y 此时可以选择 ε，不消耗输入 a，那么就变成了：

消耗 a，剩余 d
Z -> a Y Z # 继续
回滚 a，剩余 ad
Z -> a ε Z

消耗 a，剩余 d
Z -> a ε X Y Z # 根据 FIRST_S 集可得
Z -> a ε a Y Z # 直接采用推导式 5

消耗 d，无剩余
Z -> a ε a ε Z # 与上面类似，不要着急回答 no
回滚 d，剩余 d

# 消耗 d，无剩余
Z -> a ε a ε d # 根据 FIRST_S 集可得

最后得到的 a ε a ε d 其实就是输入的 S，所以我们应该回答 yes。

回顾上面的过程，非常明显的一点是，如果 Y 可以不接受字符，即是 NULLABLE 集，那么应该继续考虑谁可以跟在 Y 后面，这里就是 Z。由于存在这么一个推导式 1，它的右部，Z 是跟在 Y 后面的，那么潜在的意思就是，如果 Y 无法接受输入，那么可以不消耗，让 Y 后面的那个终结符去试试。所以，FIRST_S(Y) 计算起来，是需要考虑到推导式 1 的。

可以跟在 N 后面的所有终结的符集合，这就是 FOLLOW 集的概念。注意：FOLLOW 集有些地方把它叫做 “...所有非终结符的集合...”，其实本质上是一样的，都是为了完善 FIRST_S 的求解  

举例，还是这个文法：

0: Z -> d
1:    | X Y Z
2: Y -> c
3:    | ε
4: X -> Y
5:    | a

FOLLOW 集计算过程如下：

FOLLOW(Z) = FOLLOW(Y) = FOLLOW(X) = {}

# 对于规则 0，开始计算
temp = FOLLOW(Z)  # 规则右部是 Z，这个时候 temp 其实就是 {}
temp = {d}  # d 是非终结符，直接加进来
# 规则 0 右边已经没有其他字符了，结束

# 对于规则 1，开始计算
temp = FOLLOW(Z)  # 规则右部是 Z，这个时候 temp 其实就是 {}
FOLLOW(Z) |= temp  # FOLLOW(Z) 其实还是 {}
temp = FIRST(Z)  # Z 不属于 NULLABLE 集，temp 现在是 {a, c, d}
FOLLOW(Y) |= temp  # FOLLOW(Y) 就是 {a, c, d}
temp |= FIRST(Y)  # temp 还是 {a, c, d}
FOLLOW(X) |= temp  # FOLLOW(X) 就是 {a, c, d}
temp |= FIRST(X)  # temp 还是 {a, c, d}
# 规则 1 右边已经没有其他字符了，结束

# 对于规则 2，开始计算
...  # 篇幅过长，省略

以上过程需要得是，看到这一步 FOLLOW(X) = FIRST(Y) ∪ FOLLOW(Y)，求解过程是通过产生式 Z -> X Y Z 的右部，来求 X 的 FOLLOW 集，那么显然从后往前求解比较合理。因为比如我们如果先求 FOLLOW(X)，那么其实是需要再计算 FOLLOW(Y) 的，所以还不如从后往前求解，先求 FOLLOW(Y)，再求 FOLLOW(X)。

那么接下来，我们就可以计算比较完善的 FIRST_S 集了。

文法：

0: Z -> d
1:    | X Y Z
2: Y -> c
3:    | ε
4: X -> Y
5:    | a

NULLABLE 集：{X, Y}

计算可得 FIRST_S 集：

最后，得出 LL(1) 分析表：

至此，之前提到的这个文法：

E -> E + T
   | T
T -> T * F
   | F
F -> num
   | id

那么显然，使用 LL(1) 分析算法，已经不会造成大量的回溯了。等等，不会造成 “大量” 的回溯？难道还会有回溯的情况吗？

是的，LL(1) 分析算法，还是无法完全避免回溯的问题  

上面那个分析表中，(Z, d) 项有 2 条路 0、1 可以走，即算法在遇到输入 d 之后，可以选择走 Z -> X Y Z，也可以选择走 Z -> d，那么这就会造成回溯。这样的话我们是没法使用 LL(1) 算法的，因为每个文法回溯的情况都不一样，LL(1) 算法设计的初衷就是通用算法。那如果对于存在回溯的文法，我们非要用 LL(1) 分析可以吗？其实也是有办法的。

LL(1) 分析算法的冲突

来看一个例子：

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

NULLABLE 集：{}

计算可得 FIRST_S 集：

最后，得出 LL(1) 分析表：

消除左递归

我们仔细观察，就会发现这个文法是有左递归的：产生式的右部最左符号是产生式头。很明显，E -> E + T 就是左递归的；又因为推导一定要停止，所以左递归往往会伴随一个“停止”状态，例如上面的 E -> T。那么和容易看出，具有左递归的文法，如果使用 LL(1) 分析算法来处理，那么肯定会有回溯，因为 E -> E + T 的 FIRST_S 集肯定包含 E -> T 的 FIRST_S 集。

那么怎么消除左递归呢？

0: E -> E + T
1:    | T

观察这个文法的前两个规则我们可以发现，0、1 在做的实际上就是这样

# 为了区分顺序，T 后加了数字
+ T0  # 选择第 0 条规则，不断递归
+ T1 + T0
+ T2 + T1 + T0
...
T + Tn + ... + T1 + T0  # 最后选择第 1 条规则，停止

那么实际上可以写成这样的形式：

0: E  -> T E'
1: E' -> + T E'
2:     | ε

怎么得出来的呢？首先上面文法的第 0 条规则，实际上对应的是原文法中最后选择第 1 条规则的操作；然后自然 E' 就是模拟原文法中不断 + 的操作，不但要可以递归下去（这里是右递归），还可以推出 ε 来结束递归。

提取左公因子

那么没有左递归的文法，一定可以用 LL(1) 算法吗？其实也不一定。来看一个例子：

0: X -> a Y
1:    | a Z 
2: Y -> b
3: Z -> c

很明显是存在冲突的，0 号规则在遇到 a 的时候，可以走 0 或者 1。

对于这种情况，我们也可以改写一下文法，类比与代数里的提取公因子，我们可以得到：

0: X  -> a X'
1: X' -> Y
2: X' -> Z
3: Y  -> b
4: Z  -> c

LL(1) 小结

这里稍微总结一下，可以使用 LL(1) 分析算法的文法，是 LL(1) 文法。通过上面改写文法的两种办法，我们可以总结出：

一个文法 G 是 LL(1) 的，当且仅当 G 的任意两个不同的产生式：

A -> α 
   | β

必须满足下面的 3 个条件：

1. FIRST(α) 和 FIRST(β) 是不相交的集合。
2. α 和 β 中最多只有一个可以推导出空串。
3. 如果 β 可以推出 ε，那么 FIRST(α) 和 FOLLOW(A) 是不相交的集合；α 同理。

通过上面改写文法的两种办法，我们可以把大多数的文法转为 LL(1) 文法，强行使用 LL(1) 来进行分析。

虽然 LL(1) 运行高效，但是它可以分析的文法还是比较有限的，并且在那些可以用 LL(1) 分析的文法中，很多文法是需要手动改写一下的，这个改写往往会破坏文法的可读性（例如消除左递归前这个文法的可读性非常好，消除左递归之后，可读性就大大降低了） 

☁️ 总结

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

本来打算把下一篇与这一篇合并的，但是行文至此字数已经超过 6k 了，太长看起来比较累，不如放到下一篇，方便阅读；在博客里我会进行合并，方便搜索。

还是有点烧脑的吧？
所以我拖更是情有可原的