编译原理 3：自底向上的语法分析

我们在之前提到了自顶向下的语法分析，它之所以「自顶向下」，是因为它的分析过程是从文法出发去「套」句子（输入的符号串）。这一节我们的分析是「自底向上」的，即从句子出发去「套」文法。具体来说，对于句子 $w$，我们从左到右扫描它，寻找它的一个最左归约。

在分析的过程中，如果当前句型的一个最左子串与某一产生式的右部匹配，我们就用这个产生式的左部代替那个子串。如果每一步都能合理地选择子串，最终只剩下一个文法开始符号，那么整个句子就是符合文法的。每次归约的子串称为相应句型的「句柄」，顾名思义就是这个句子「生长」的依附点。「找句柄」，就是分析过程的学问所在。

自底向上分析的移进-规约法 #

自底向上的分析主要使用一种叫做「移进-规约」法的分析方法，本小节会说明它的思路和过程。

移进-规约分析 #

与预测分析法的带栈自动机类似，移进-规约法也是一个带栈的自动机，它同样在一张分析表的指导下动作。

启动时，栈底元素为 $#$。机器自左向右地扫描输入串 $w$，不停地将扫描到的符号压栈。与此同时，检查栈顶是否出现句柄 $\alpha$ 即某个产生式 $A\to\alpha$ 的右部，若出现则将句柄用 $A$ 进行替换。以下面的文法为例：

对句子 $\mathbf{id}+\mathbf{id}*\mathbf{id}$ 的移进-规约的过程如下：

当然，我们在上节已经提到这个文法是有二义性的，因此还存在一种与上述过程不同的「移进-规约」过程。

在整个移进-规约的过程中，一个关键问题是「如何判定栈顶出现了句柄」，或者说「如何确定句柄的起始位置和结束位置」。对这个问题的不同解决办法造就了不同的移进-规约分析法。

文法符号的优先级 #

正如表达式需要先计算乘除法后计算加减法一样，文法符号之间可能有优先关系，使得句柄内的各符号具有同样的优先级，但总是高于句柄外符号的优先级。用 $\equiv$ 表示优先级相同，用 $\nless$ 和 $\ngtr$ 表示优先级的大小关系，设现在有句型 $X_1X_2\cdots X_n$，若有

此时 $X_iX_{i+1}\cdots X_j$ 就是句柄，句柄中的符号同时归约。如果某个文法各个符号之间的优先关系不冲突（确定），则利用这套优先关系可以识别任意句型的句柄，这样的文法称为「简单优先文法」，这种分析方法称为「简单优先分析法」。

再观察上面算术表达式的文法，发现其有一个特征：不存在哪个产生式的右部有两个相邻的语法变元。有这样的特征的文法称为「算符文法」。如果各终结符之间的优先关系不冲突，则称「算符优先文法」。

后文会深入介绍这些文法的细节。

算符优先分析法 #

所谓的「算符优先分析法」，是将句型中的终结符作为「算符」，然后定义算符之间的优先关系，利用这种关系寻找句柄来归约。在某个句型中相邻（允许中间有一个语法变元）的任意两个终结符 $a$ 和 $b$ 之间可能存在 $a\nless b$、$a\ngtr b$ 和 $a\equiv b$ 三种关系，在这样的关系之上，我们建立一套文法体系——「算符优先文法」。

考虑算术表达式文法 $G$：

其所有产生式的右部都没有两个语法变元直接相邻，因此它不会产生 $\cdots E_1E_2\cdots$ 这样的句型。这种文法我们称为算符文法。

另一方面，我们定义算符文法中的终结符归约顺序。假设 $G$ 不含 $\varepsilon$-产生式，$A$、$B$ 和 $C$ 都是 $G$ 的语法变元，$G$ 的任何一对终结符 $a$ 和 $b$ 的关系定义为：

• $a\equiv b$，当且仅当 $G$ 中有 $A\to\cdots ab\cdots$ 或 $A\to\cdots aBb\cdots$ 这样的产生式。
• $a\nless b$，当且仅当 $G$ 中有 $A\to\cdots aB\cdots$ 的产生式，且要么 $B\xRightarrow{+}b\cdots$ 要么 $B\xRightarrow{+}Cb\cdots$。
• $a\ngtr b$，当且仅当 $G$ 中有 $A\to\cdots Bb\cdots$ 的产生式，且要么 $B\xRightarrow{+}\cdots a$ 要么 $B\xRightarrow{+}\cdots aC$。
• $a$ 与 $b$ 无关，当且仅当 $a$ 和 $b$ 在 $G$ 的任何句型中都不相邻。

如果算符文法 $G$ 的任何一对终结符都满足且仅满足上述关系之一，称 $G$ 为算符优先文法。上面的算术表达式文法不是算符优先文法，因为其 $+$ 和 $*$ 的优先关系不能确定。

算符优先矩阵 #

算符优先矩阵是用来描述任意两个终结符之间优先级关系的矩阵，或者说，「表」。从上面的 $a$ 和 $b$ 关系可以知道，对于 $\nless$ 关系，我们需要找到 $A\to\cdots aB\cdots$ 中 $B$ 能推出的所有最左终结符。同理，对于 $\ngtr$ 关系，我们需要找到 $A\to\cdots Bb\cdots$ 中 $B$ 能推出的所有最右终结符。定义下面的两个集。

此时很容易求出所有的优先关系。假设某产生式右部形如 $\cdots aB\cdots$，则 $\forall b\in\mathrm{FIRSTOP}(B)$ 有 $a\nless b$。如果某产生式右部形如 $\cdots Bb\cdots$，则 $\forall c\in\mathrm{LASTOP}(B)$ 有 $\textcolor{red}{c\ngtr b}$。注意 $a\nless b$ 不代表 $b \ngtr a$。考虑完善后的算术表达式文法 $G_e$：

写出 $E$、$T$ 和 $F$ 的 $\mathrm{FIRSTOP}$ 和 $\mathrm{LASTOP}$ 集：

其算符优先矩阵为：

算符优先分析算法 #

借助前文的算符优先矩阵，我们可以判定栈顶符号和下一个输入符号之间的优先关系，进而判断栈顶符号是否是句柄的尾。如果是句柄尾（栈顶 $\ngtr$ 输入），就从栈顶开始向下找句柄头（下一个符号 $\nless$ 句柄头），在 $\nless$ 和 $\ngtr$ 之间的就是句柄，将句柄弹栈规约即可。

以上节使用的「完善」算术表达式为例，分析 $\mathbf{id}+\mathbf{id}$，它的分析过程如下表所示。

​

尽管能正确地分析句子，这种算法有着一些问题，如有时未规约真正的句柄，且并不能产生真正的最左规约。不过，它依然是一种有效的分析文法。

LR 分析法 #

所谓 LR(k) 分析法是指：从左向右扫描输入字符串，构造最右推导的逆过程，每次向前扫描 $k$ 个字符。对应地，LR 分析器就是用来执行 LR 分析的程序。典型的 LR 分析器有四种：

• LR(0)：分析能力最弱，是其他分析器的基础。
• SLR(1)：分析能力稍强于 LR(0)，弱于 LR(1)。
• LR(1)：分析能力最强，代价最高。
• LALR(1)：能力和代价适中，可以应用于多数语言并有高效实现。

LR 分析算法的过程 #

LR 分析法是一种基于状态的分析文法，它将句柄的识别过程划分为若干个「状态」，分析器根据当前的状态确定是否找到了句柄。栈顶符号和输入符号是状态转移的条件，状态是句柄识别「程度」的描述。自然地，一个长为 $n$ 的句柄识别需要 $(n+1)$ 个状态。在每个状态，识别到的句柄的那一部分就是当前句型的一个前缀，称为规范句型的「活前缀」。一个文法的规范句型的所有活前缀构成一个正则语言。LR 分析器原理上就是一个识别这种语言的 DFA。

具体来说，这个 DFA 由动作（action）表和转移（goto）表控制，二者合称 LR 分析表。该表给出每个状态下需要采取的动作（移进、规约、接受、报错）以及要转移的下一个状态。上面不同的 LR 分析器的差别，就是分析表的构造文法不同。

• 动作表表项 $\mathrm{action}[S_m, a_i]$ 指明，当栈顶状态为 $S_m$，输入符号为 $a_i$ 时，分析器应当执行的动作，即移进、规约、接受和报错四者之一。
• 转移表表项 $\mathrm{goto}[S_m, A]$ 指明，当栈顶状态为 $S_m$，且分析器刚刚规约出语法变元 $A$ 时，要转向的下一个状态。

与之前的自动机不同，除了分析栈外，还需要一个额外的「状态栈」来保存状态。LR 分析器的工作过程如下：

• 启动时，状态栈为 $S_0$ 即初始状态，分析栈为 $#$ 即栈底。输入缓冲区为 $a_1a_2\cdots a_n#$。

• 设某个时刻，状态栈为 $S_0S_1\cdots S_m$，分析栈为 $#X_1X_2\cdots X_m$，缓冲区为 $a_ja_{j+1}\cdots a_n#$，用当前输入符号 $a_j$ 查动作表，有：

  • 如果 $\mathrm{action}[S_m, a_j]=S_i$ 即移进，将 $a_j$ 和 $S_i$ 入栈。
  • 如果 $\mathrm{action}[S_m, a_j]=r_k$ 即规约，按第 $k$ 个产生式 $A\to X_{m-(l-1)}X_{m-(l-2)}\cdots X_m$ 规约。规约完成后，状态栈被削至 $S_0S_1\cdots S_{m-l}$，分析栈被削至 $#X_1X_2\cdots X_{m-l}A$。这时，我们查转移表 $\mathrm{goto}[S_{m-l}, A]=S_j$，然后将 $S_j$ 压入状态栈。
  • 如果 $\mathrm{action}[S_m, a_j]=\mathrm{acc}$ 即接受，分析成功，停机。
  • 如果 $\mathrm{action}[S_m, a_j]=\mathrm{error}$ 即出错，则转错误处理。

前文已经说过，不同 LR 分析法的区别是那两张表不同。下面详细说明。

LR(0) 分析法 #

考虑如下文法 $G$

它的 LR(0) 分析表如下所示。空白表示出错。

​

上表的一个特点是：执行规约动作（即表项为 $r_x$）时，与输入符号无关。这就是 LR(0) 中「0」的含义。它的能力非常弱，只能分析一些非常简单的文法。上面的 LR(0) 分析表分析串 $bab$ 的过程如下：

​

我们观察分析栈和输入缓冲区。显然，在任何一个时刻，它们都共同构成了一个完整的规范句型。而栈中的那部分，则是这个规范句型的一个前缀。这个前缀没有句柄右边的任何符号，称为「活前缀」。

对于一个产生式 $A\to\beta$，设它对应即将被规约的句柄，它与活前缀的关系有：

• 活前缀有句柄的所有符号，立即可以归约，记作 $A\to\beta.$。
• 活前缀完全没有句柄的符号，句柄还完全没有移进来，记作 $A\to.\beta$。
• 句柄的一部分在活前缀中，记作 $A\to\beta_1.\beta_2$。

称右部有圆点的产生式为「LR(0) 项目」。LR(0) 项目描述了活前缀的不同识别状态，即句柄的分析状态。利用所有的 LR(0) 项目，就能构造出识别规范句型前缀的 DFA。为了让分析器最终能收敛到一个确定的状态，增加产生式 $S’\to S$ 得到 $G$ 的增广文法 $G’$，它的全部 LR(0) 项目有 10 个，容易写出。

设 $A\to\alpha X\beta$ 是文法 $G=(V, T, P, S)$ 的一个产生式：

• $A\to\alpha X\beta.$ 称为「归约项目」，因为它相当于整个句柄已经移入，可以立即归约。
• $A\to\alpha.X\beta$ 如果 $X\in T$，称为「移进项目」；如果 $X\in V$，称为「待约项目」。

而在 $G$ 的增广文法中，$S’\to S.$ 用于最后一次规约，称为「接受项目」。

用 LR(0) 项目可以构造一个识别规范句型活前缀的 DFA。考虑 DFA 的初始状态 $I_0$，$S’\to.S$ 应当在 $I_0$ 中。而 $S\to.BB$ 实际上和 $S’\to.S$ 在同一个状态——在 $S’\to.S$ 时，不用识别任何符号，也是在 $S\to.BB$。称 $S\to.BB$ 是从 $S’\to.S$ 出发 $\varepsilon$-可达的。

同样，$B\to.aB$ 和 $B\to.b$ 是从 $S\to.BB$ 出发 $\varepsilon$-可达的。显然 $\varepsilon$-可达是有传递性的。将 $S’\to.S$ 的 $\varepsilon$-闭包中的所有项目加入状态 $I_0$。得到

$\varepsilon$-闭包的定义是：

记 $I_0$ 为状态 0 即启动状态，在这个状态成功归约或者读入出不同的符号，将决定下一个状态向何处转移。具体地：

• 如果规约出 $S$，进入 $I_1=\mathrm{CLOSURE}(S’\to S.)$。这就是最终我们要进入的状态。
• 如果规约出 $B$，进入 $I_2=\mathrm{CLOSURE}(S\to B.B)$。
• 如果读入 $a$，进入 $I_3=\mathrm{CLOSURE}(B\to a.B)$。
• 如果读入 $b$，进入 $I_4=\mathrm{CLOSURE}(B\to b.)$。

算出 $I_i$ 并画出这些状态之间的关系：

​

称 $A\to\alpha X.\beta$ 是 $A\to\alpha.X\beta$ 的「后继项目」，定义「后继项目集」$\mathrm{GO}(I, X)=\mathrm{CLOSURE}({A\to\alpha X.\beta|\forall A\to\alpha.X\beta\in I})$。$\mathrm{GO}$ 为项目集的「转移函数」。上面的 $I_1$—$I_6$ 就是后继项目集。记 $C={I_0, I_1, \cdots, I_6}$ 为文法 $G$ 的 LR(0) 项目集规范族。

现在，我们已经构造出一台识别文法所有活前缀的 DFA。然而，我们的目标是构造 LR(0) 状态表，识别句型的 DFA 肯定要比这台识别前缀的 DFA 复杂，但它们的状态数是相同的。事实上，我们用下面的算法构造识别增广文法 $G’$ 的 $\mathrm{action}$ 表和 $\mathrm{goto}$ 表。

1. 令 $I_0=\mathrm{CLOSURE}({S’\to.S})$，构造 $G’$ 的 LR(0) 项目集规范族 $C={I_0, I_1,\cdots, I_n}$。

2. 令 $I_i$ 对应状态 $i$。状态 0 为初始状态。

3. $\forall k\in[0, n]$：

   1. 若 $A\to\alpha.a\beta\in I_k$ 且 $a\in T$ 且 $\mathrm{GO}(I_k, a)=I_j$，则 $\mathrm{action}[k, a]=S_j$。
   2. 若 $A\to\alpha.B\beta\in I_k$ 且 $B\in V$ 且 $\mathrm{GO}(I_k, B)=I_j$，则 $\mathrm{goto}[k, B]=S_j$。
   3. 若 $A\to\alpha.\in I_k$ 且 $A\to\alpha$ 为 $G$ 的第 $j$ 个产生式，则对 $\forall a\in T\cup{#}$ 有 $\mathrm{action}[k, a]=r_j$。
   4. 若 $S’\to S.\in I_k$，则 $\mathrm{action}[k, #]=\mathrm{acc}$。

4. 其他未填充的表项为 $\mathrm{error}$。

如果 $G$ 是 LR(0) 文法，那么上面构造的转移表是唯一的，反之会产生「移进-规约冲突」或「归约-归约冲突」。只有很少一部分文法是 LR(0) 文法。因此，有必要设计新的句型识别方式。

SLR(1) 分析法 #

利用曾经提到过的 $\mathrm{FOLLOW}$ 集

将上面 LR(0) 算法的第 3 条改成：

若 $A\to \alpha.\in I_k$ 且 $A\to \alpha$ 为 $G$ 的第 $j$ 个产生式，则对 $\forall a\in\mathrm{FOLLOW}(A)$ 有 $\mathrm{action}[k, a]=r_j$。

这样得到的分析表称为 SLR(1) 分析表。能用这样的文法分析的文法叫做 SLR(1) 文法。大多数程序设计语言的语法成分都可以用 SLR(1) 文法来描述。

下面举一个例子。考虑下面的简单算术表达式文法 $G$（怎么又是你）：

首先得到增广文法 $G’$：

列出初始状态 $I_0$ 的 LR(0) 产生式：

• $I_0={E’\to.E, E\to.E+T, E\to.T, T\to.T*F, T\to.F, F\to.(E), F\to.\mathbf{id}}$

然后列出转移后的各个状态：

• $I_0\xrightarrow{E}I_1={E’\to E., E\to E.+T}$
• $I_0\xrightarrow{T}I_2={E\to T., T\to T.*F}$
• $I_0\xrightarrow{F}I_3={T\to F.}$
• $I_0\xrightarrow{(}I_4={F\to(.E), E\to.E+T, E\to.T, T\to.T*F, T\to.F, F\to.(E), F\to.\mathbf{id}}$
• $I_0\xrightarrow{\mathbf{id}}I_5={F\to\mathbf{id}.}$

再列出各个子状态转移之后的状态：

• $I_2\xrightarrow{}I_6={T\to T.F, F\to.(E), F\to.\mathbf{id}}$
• $I_1\xrightarrow{+}I_7={E\to E+.T, T\to.T*F, T\to.F, F\to.(E), F\to.\mathbf{id}}$
• $I_6\xrightarrow{F}I_8={T\to T*F.}$
• $I_7\xrightarrow{T}I_9={E\to E+T., T\to T.*F}$
• $I_4\xrightarrow{E}I_{10}={F\to(E.), E\to E.+T}$
• $I_{10}\xrightarrow{)}I_{11}={F\to(E).}$

再完善各个状态之间的转换，画出 DFA 状态图：

​

求出非终结符的 $\mathrm{FIRST}$ 集和 $\mathrm{FOLLOW}$ 集：

运行 SLR(1) 分析表的构造算法，可以得到下面的分析表。

​

LR(1) 文法 #

假设文法 $G$ 是上下文无关的，如果存在规范推导 $S\xRightarrow{*}\delta Aw\Rightarrow \delta\alpha\beta w$，记 $a$ 是 $w$ 的首字母，则称 $[A\to\alpha.\beta, a]$ 对前缀 $\delta\alpha$ 是有效的。如果 $w=\varepsilon$，则 $a=#$，$[A\to\alpha.\beta, a]$ 称为 $G$ 的 LR(1) 项目，$a$ 称为「搜索符」或「展望符」。

与 LR(0) 分析法类似，我们构造 DFA 来识别文法全部的活前缀，DFA 的每个状态也用 LR(1) 项目集表示。如果 $[A\to\alpha.B\beta, a]$ 对活前缀 $\delta\alpha$ 是有效的，即存在规范推导 $S\xRightarrow{}\delta Aax\Rightarrow\delta\alpha B\beta ax$，假定 $\beta ax\xRightarrow{}by$，则对任意 $B\to\eta$ 的产生式有 $S\xRightarrow{*}\delta\alpha Bby\Rightarrow\delta\alpha\eta by$，于是 $[B\to.\eta, b]$ 对 $\delta\alpha$ 有效，$b$ 是 $\beta ax$ 的首符号。此时，$[A\to\alpha.B\beta, a]$ 和 $[B\to.\eta, b]$ 表示相同的句柄识别进度，即属于同一个项目集。

定义 LR(1) 闭包：

定义转移函数：

用下面的算法构造 LR(1) 分析表：

1. 令 $I_0=\mathrm{CLOSURE}({[S’\to.S, #]})$，构造 $G’$ 的 LR(1) 项目集规范族 $C={I_0, I_1, \cdots, I_n}$。

2. 令 $I_i$ 对应状态 $i$，状态 0 为初始状态。

3. $\forall k\in[0, n]$

   1. 若 $[A\to\alpha.a\beta, b]\in I_k$ 且 $a\in T$ 且 $\mathrm{GO}(I_k, a)=I_j$，则 $\mathrm{action}[k, a]=S_j$。
   2. 若 $\mathrm{GO}(I_k, B)=I_j$，且 $B\in V$，则 $\mathrm{goto}[K, B]=j$。
   3. 若 $[A\to\alpha., a]\in I_k$，且 $A\to\alpha$ 是 $G’$ 的第 $j$ 个产生式，则 $\mathrm{action}[k, a]=r_j$。
   4. 若 $[S’\to S., #]\in I_k$，则 $\mathrm{action}[k, #]=\mathrm{acc}$。

4. 其他未填充的表项为 $\mathrm{error}$。

LR 分析的基本步骤 #

1. 编写增广文法，求 $\mathrm{FOLLOW}$ 集。
2. 求识别所有活前缀的 DFA。
3. 构造 LR 分析表。

小结 #

• 自底向上的语法分析，即从给定的符号串 $w$ 出发，自底向上地为其建立一棵语法分析树——即从输入符号串出发寻找一个 $w$ 的最左规约。
• 移进-规约分析是最基本的一种分析方式。利用句型中文法符号的「优先级」来判定被规约对象是否形成，这种方法叫「优先法」。利用分析进展的状态来判定，则称为「状态法」。
• 算符优先分析法是一种优先法，通过定义算符之间的优先关系来确定移进和规约，需要维护一张算符优先关系表。
• LR 分析法则利用识别活前缀的 DFA 来设计分析过程中的状态，是一种状态法。取决于分析过程中的读入信息量，分为 LR(0)，SLR(1)，LR(1) 几种方法。

本节笔记到此结束。