11.2 构造 LR(0) 分析器

LR(0) 分析法是一种最基本的 LR 分析法，其构造过程中的核心是 状态 和 形态 ，以下给出相关术语的正式定义，并介绍如何构造 LR(0) 分析器。

形态（configuration） ： 一个产生式的解析程度，用一个产生式加一个位置黑点来表示，例如，产生式 A -> XYZ 有 4 中可能的解析程度：

A –> •XYZ

A –> X•YZ

A –> XY•Z

A –> XYZ•

位置黑点表示本产生式解析过程中前进到的位置，比如一个产生式: S -> abc ，则它最开始的形态为 S -> •abc ，读入一个 a 后其形态变为 S -> a•bc ，再读入一个 b 后变为 S -> ab•c 。

形态一般用大写字母 C 表示。

需要注意的是，如果一个产生式的右边是空串，如 A -> ε ，那么形态 A -> •ε 和 A -> ε• 是同样的形态，一般都只采用后一种表示方式。

产生式的起始形态（start configuration of a production） ： 位置黑点位于该产生式右边的第一个符号的前面的形态，如： A –> •XYZ 。

产生式的已完成形态（complete configuration of a production） ： 位置黑点位于该产生式右边的最后一个符号的后面的形态，如： A –> XYZ• 。也称为 可折叠形态（reduceable configuration）。

形态的转移 ： 当一个形态 A –> X•YZ 遇到一个符号 Y 时，它就转移到下个形态： A –> XY•Z ，见下图：图11.1 形态转移示意图

若记 C = [A -> X•YZ] ， C’ = [A –> XY•Z] ，称形态 C’ 为形态 C 遇到符号 Y 时的 后继形态（successor configuration） ，可写为 NEXT(C, Y) 。若形态 C 遇到的符号 X 不等于其位置黑点后面的符号时，称 NEXT(C, X) 不存在。

延伸形态（extended configuration） ：对于形态 A –> v•Yw ，若 Y 为非终结符，且 Y -> u ，则形态 Y -> •u 是形态 A –> v•Yw 的延伸形态，进一步的，若 u 的第一个符号为非终结符 Z ，且 Z -> u1 ，则形态 Z -> •u1 既是 Y -> •u 的延伸形态，也是 A –> v•Yw 的延伸形态。

例如，语法：

S -> Ab
A -> Bc
B -> d

A -> •Bc 和 B -> •d 都是 S -> •AB 的延伸形态。

这里要注意的是： 延伸的方向是单向的 ，上面这个语法中，A -> •Bc 是 S -> •AB 的延伸形态，但 S -> •AB 不是 A -> •Bc 的延伸形态，只有 B -> •d 才是 A -> •Bc 的延伸形态。

形态集合（configurating set） ： 一个由有限个形态组成的集合。

形态集合的闭合（closure of a configurating set） ： 形态集合的闭合就是把这个集合里所有形态的所有延伸形态全部添加进这个集合。按以下步骤进行（设该集合名为 I ）：

（1） 遍历 I ，对 I 中的每一条形态 A -> u • v ，若 v 的第一个符号为非终结符 B ，则将其所有的产生式的起始形态添加进 S ，即若 B -> u1 | u2 | … | un ，则将 B -> • u1, B -> • u2, …, B -> • un 添加进 I 。

（2） 重复（1），直到不再出现新的形态。

闭合操作的得到的新集合 I’ 称为原集合 I 的 闭包集合 ，记为 CLOSURE(I) 。

状态（state） ： 进行过闭合操作的形态集合，一般用大写字母 I 表示，也就是说，若形态 C 属于 状态 I ，则 C 的延伸形态也属于 I 。

上下文无关语法的起始状态（start state of a CFG） ： 若一个 CFG 的起始符号 S 的所有产生式为 S -> u1 | u2 | … | un ，且 S 不位于任何产生式的右边，则其起始状态（记为 I0 ）是这些产生式的起始形态的集合的闭包集合，即：

I0 = CLOSURE( { [S-> • u1], [S-> • u2], … [S-> • un] } )

例如，语法：

S -> A
A -> aBd
B -> bc

的起始状态 I0 = { [S-> • A], [A-> • aBd] } 。

起始状态可以认为是语法解析的初始状态，此时尚未读入任何符号，因此起始符号的所有产生式都处在其初始形态。

上面提到了，要求 S 不位于任何产生式的右边。如果 S 位于某条产生式的右边，则这个状态可能不能代表语法解析的初始状态。例如，对于语法： S -> a | aS 。当解析句子 aaa 的时候，状态{ [S-> • a], [S-> • aS] }，可能代表 ” • aaa” 的状态，也可能代表 “a • aa” 的状态 （这里的 ” • ” 表示已读入符号和未读入符号的分割位置）。

为了保证起始符号不位于任何产生式的右边，一般在语法中增加一个非终结符 S’ 和一条产生式 S’ -> S ，而用这个 S’ 作为起始符号。如前面这个语法 S -> a | aS 可以改为：

S' -> S
S  -> a
S  -> aS

此时的状态 { [S’-> • S], [S-> • a], [S-> • aS] } 就只能代表 ” • aaa” 的状态了。

后继状态（succesor state） ： 当状态 I 遇到符号 X 时，可能转移到另一个状态，称此状态为状态 I 遇到符号 X 的后继状态，记为 NEXT(I, X) ，按下式计算：

NEXT(I, X) = CLOSURE( { NEXT(C, X) | C ∈ I } )

NEXT(I, X) 的计算步骤为：

（1） 置 I’ 为空集。

（2） 遍历 I ，对 I 中每一条形态 C ，若 NEXT(C, X) 存在，则将 NEXT(C, X) 加入 I’ 。

（3） 对 I’ 进行闭合操作。

注意，NEXT(I, X) 可能为空集。

下面用一个非常简单的例子来介绍如何使用形态和状态来构造 LR(0) 分析。语法为：

S -> A
A -> aBd
B -> bc

首先，求出该语法的起始状态 I0 ：

I0:
    S -> .A
    A -> .aBd

对语法中的所有符号 X （S, A, B, a, b, c, d） ，求出 I0 遇到 X 的后继状态 NEXT(I0, X) ，若 NEXT(I0, X) 不是空集，则将其添加到状态转移图中，如下：图11.2 状态转移图1

按以上方法，不断的生成新的状态，直到不再出现新的状态，最终如下：图11.3 状态转移图2

显然，解析的最开始的时候，没有读入任何符号，此时的状态为 I0 ，每读入一个符号，则转移到另一个状态。

这个状态转移图似乎和有限状态自动机的运行图很相似，那么，解析的过程是不是就是用有限状态自动机来依照上面那个图来运行一遍？答案是不行的。上一章已经说过了，有限状态自动机只能解析正则语言，无法解析复杂的上下文无关语言。为了解析上下文无关语法，我们需要一种更强大的自动机，这种自动机不仅仅需要记住它当前的状态，还需要记住它的历史路径，记住它是如何到达当前状态的。

简单来说，这种自动机含有一个栈，它的大致的运行机制为：在读入符号之前，将初始状态 I0 压入栈顶，之后，每读入一个符号，它就转移到下一个状态（将下一个状态压入栈顶），当它转移到一个可折叠状态时，它执行一个折叠动作（将前面的一些状态出栈、再压入下一个状态），一直到它折叠得到的非终结符是起始符号，且下一个符号是 $ 时，它才终止运行。

上面这段描述只是一个大致的运行流程，里面有两个重要的问题没讲清楚，一个是 转移 和 折叠 动作的具体操作步骤，另一个什么是 可折叠状态 。

我们先把后一个问题讲清楚：

可折叠状态（reduceable state） ： 只含有一个形态的状态，且此形态为可折叠形态，如图11.3中的 I1 、 I5 和 I6 。

自动机的具体操作流程为：

（1） 将初始状态 I0 压入栈顶；

（2） 读入下一个符号 x ，相当于调用一次 x = yylex() ，有两种情况：

（2.1） x 不是终结符：输入不合语法，执行 deny 操作，终止解析；

（2.2） x 是终结符：转到（3）；

（3） 置 X = x ；

（4） 设栈顶状态为 I ，有以下两种情况：

（4.1） I 不是可折叠状态，有以下三种情况：

（4.1.1） NEXT(I, X) 存在（设为 I’）、 X 为终结符：执行 shift I’ 操作，将 I’ 压入栈顶，转到（2）；

（4.1.2） NEXT(I, X) 存在（设为 I’）、 X 为非终结符：执行 goto I’ 操作，将 I’ 压入栈顶，转到（3）；

（4.1.3） NEXT(I, X) 不存在：输入不合语法，执行 deny 操作，终止解析；

（4.2） I 是可折叠状态，设 I 里面的形态对应的产生式为 A -> X1 X2 … Xn ，有以下三种情况：

（4.2.1） A != S ：执行 reduce (A, n) 操作，将栈顶及以下 n 个状态出栈，置 X = A ，转到（4）；

（4.2.2） A == S 、 X != $ ：输入不合语法，执行 deny 操作，终止解析；

（4.2.3） A == S 、 X == $ ：输入合法，执行 accept 操作，终止解析。

注意，以上流程只适用于起始符号 S 不在任何产生式的右边的语法。例如，如果有 A -> Sa 这样的产生式时，那么即使折叠得到了 S ，也不代表原句子已经全部折叠完了。

根据以上流程，按状态转移图构造出动作表 M ， M 中的 M[I, X] 表示栈顶状态为 I ，下一个符号为 X 时所应采取的动作，按以下情况确定：

（1） I 不是可折叠状态：

（1.1） NEXT(I, X) 存在（设为 I’）、 X 为终结符： M[I, X] = shift I’ ；

（1.2） NEXT(I, X) 存在（设为 I’）、 X 为非终结符： M[I, X] = goto I’ ；

（1.3） NEXT(I, X) 不存在： M[I, X] = deny ；

（2） I 是可折叠状态、其中的形态对应的产生式为 A -> X1 X2 … Xn ：

（2.1） A != S： M[I, X] = reduce A -> X1 X2 … Xn ；

（2.3） A == S、 X != $ ： M[I, X] = deny ；

（2.2） A == S、 X == $ ： M[I, X] = accept 。

按以上步骤以及图11.3，构造出的动作表 M 如下，其中 M[I, X] 为空白的表示 deny 动作：

构造出动作表后，LR(0) 的具体操作流程为：

（1） 将初始状态 I0 压入栈顶；

（2） 读入一个符号 x ，相当于调用一次 x = yylex() ，有两种情况：

（2.1） x 不是终结符：输入不合语法，执行 deny 操作，终止解析；

（2.2） x 是终结符：转到（3）；

（3） 置 X = x；

（4） 设栈顶状态为 I ，有以下五种情况：

（4.1） M[I, X] 为 shift I’ 动作：执行 shift I’ 操作，将 I’ 压入栈顶，转到（2）；

（4.2） M[I, X] 为 goto I’ 动作：执行 goto I’ 操作，将 I’ 压入栈顶，转到（3）；

（4.3） M[I, X] 为 reduce A-> X1 X2 … Xn ：执行 reduce(A, n) 操作，将栈顶及以下 n 个状态出栈，置 X = A ，转到（4）；

（4.4） M[I, X] 为 ACCEPT ：输入合法，执行 accept 操作，终止解析；

（4.5） M[I, X] 为空白：输入不合语法，执行 deny 操作，终止解析。

按以上步骤，对句子 “abcd” 进行解析，全过程如下：