编译原理(三):语法分析之自底向上分析算法

本文最后更新于:5 个月前

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

编译原理(三):语法分析之自底向上分析算法

自底向上分析算法

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

LR 算法

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

  1. 移进:不规约,继续展开右边的式子
  2. 规约:把推导式右边的部分,归成左边的非终结符

LR(0) 算法

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

算法 3.0

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

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

1
2
3
4
5
0: 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
3
0: S' -> S$
1: S -> xxT
2: T -> y

分析输入串 xxy$

这个文法的语法要求其实非常简单,就是 xxy。那么第 0 条规则的作用是什么呢?

  1. 保证即起始的非终结符符号,不出现在任何推导的右部。当然,起始符号是有可能出现在推导的右部的,在加上 S' 之后就可以避免这种情况。
  2. $ 是输入的结束标记符,放在输入的最后。各位可以类比于 C 语言字符串的 EOF。当然每个语法分析器可以自己来规定结束符号,这边先利用 $ 统一表示一下。

接下来类比词法分析的状态转移图,我们也可以画出文法的状态转移图:

有以下几点需要解释一下:

  1. 在节点 1 中,S' -> •S$ 表示接下来碰到的输入,要可以匹配 • 右边的 S。
  2. 既然接下来期待匹配的是 S,那么匹配 S 其实就是匹配 xxT,所以 S' -> •S$S -> •xxT 就合并到了一起。对于节点 3 同理。
  3. 那么方向上的字符表示什么意思呢?比如 1->2 的 x,就是碰到 x 后,状态怎么转移。所以非常直观,碰到一个 x 之后 • 自然就往后挪动了一位,就是节点 2 了。其他的也是同理的。
  4. 那么还有 2 条特殊的边,1->6、3->5。注意,上面那一条中,我用的是“…碰到 x…”,这里用 “碰到” 而不是 “读入”,含义就是这个图表示的整个转移过程,不仅有移进,还会有规约,如果这里没法理解也没事,下面会有例子来直观地表示什么叫 “碰到”;以 3->5 为例,在碰到 T 之后,就转移到了节点 5;1->6 同理,并且 6 号节点还比较特殊,其实是即将终结的状态,如果继续读入读到一个结束符,那么就分析成功了。
  5. 识别出了某一个推导式完整的右部,就要开始规约;否则继续移进;输入消耗完毕之后,在终结状态上,那么就接受,反正拒绝。

依旧有些抽象吧?来看个具体的例子,那我们就假设输入是 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
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

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,查表为空,即拒绝

我们结合上面的过程,在仔细观察表中的状态 3,其实可以这么理解:当栈顶是状态 3 的时候,不管输入的符号是什么,都要开始规约,所以状态 3 的那一行,有 3 个 r2。状态 5 也同理。而我们观察文法可以发现,S 后面只能跟 $,那么在状态 4 的时候,输入必须只剩 $,否则就不能被接受,继续倒退一步,如果我们在状态 3 上即将开始规约的时候(即已经得到了 stack = [1, x, 2, y, 3] 后),发现剩下的输入不是 $,其实就可以报错了,否则继续规约,最后也得报错,早报错当然比晚报错好。状态 5 也同理。反映在分析表上,就是状态 3、5 遇到 x、y 的时候,直接报错而不是规约:

动作(ACTION) 转移(GOTO)
状态\符号 x y $ S
1 s2 s3 g4
2 s2 s3 g5
3 r2
4 accept
5 r1

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

LR(0) 的冲突

接下来看这个文法:

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

1
2
3
4
5
6
S' -> 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
24
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)

举几个例子,还是来看这个文法:

1
2
3
4
5
6
S' -> S$
S -> L=R
S -> R
L -> *R
L -> id
R -> L

转移图如下:

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

1
2
3
4
5
6
7
8
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 来说可以用类。

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

总结

至此,语法分析相关的知识都讲完了。

相关算法稍多,来总结一下吧:

语法分析器的实现方法:

  1. 手工方式
    • 递归下降分析器
  2. 使用语法分析器的自动生成器
    • LL(1)
    • LR(1)

两种方式在实际的编译器中都有广泛的应用,自动的方式更适合快速对系统进行原型。


这个系列别的不说
画图表都画的累死了...
好在编译原理系列马上结束了!