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

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

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

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

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

移进-规约分析

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

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

\[\begin{aligned} E&\to E+E \\ E&\to E*E \\ E&\to (E) \\ E&\to\mathbf{id} \end{aligned}\]

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

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

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

文法符号的优先级

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

\[X_1X_2\cdots X_{i-1}\nless X_i\equiv X_{i+1}\equiv\cdots\equiv X_{j-1}\equiv X_j\ngtr X_{j+1}X_{j+2}\cdots X_n\]

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

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

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

算符优先分析法

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

考虑算术表达式文法 \(G\)：

\[\begin{aligned} E&\to E+E \\ E&\to E-E \\ E&\to E*E \\ E&\to E/E \\ E&\to (E) \\ E&\to\mathbf{id} \end{aligned}\]

其所有产生式的右部都没有两个语法变元直接相邻，因此它不会产生 \(\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\) 能推出的所有最右终结符。定义下面的两个集。

\[\begin{aligned} & \mathrm{FIRSTOP}(B)=\{b|B\xRightarrow{+}b\cdots\,\text{或}\,B\xRightarrow{+}Cb\cdots ,b\in T, C\in V\} \\ & \mathrm{LASTOP}(B)=\{a|B\xRightarrow{+}\cdots a\,\text{或}\,B\xRightarrow{+}\cdots aC, a\in T, C\in V\} \end{aligned}\]

此时很容易求出所有的优先关系。假设某产生式右部形如 \(\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\)：

\[\begin{aligned} E &\to T \\ E &\to E + T\\ E &\to E-T \\ T&\to F \\ T &\to T*F \\ T &\to T/F \\ F&\to (E) \\ F&\to \mathbf{id} \end{aligned}\]

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

\[\begin{aligned} & \mathrm{FIRSTOP}(E)=\{\mathbf{id}, (, *, /, +, -\} \\ & \mathrm{FIRSTOP}(T)=\{\mathbf{id}, (, *, /\} \\ & \mathrm{FIRSTOP}(F)=\{\mathbf{id}, (\} \\ & \mathrm{LASTOP}(E)=\{\mathbf{id}, ), *, /, +, -\} \\ & \mathrm{LASTOP}(T)=\{\mathbf{id}, ), *, /\} \\ & \mathrm{LASTOP}(F)=\{\mathbf{id}, )\} \end{aligned}\]

其算符优先矩阵为：

算符优先分析算法

借助前文的算符优先矩阵，我们可以判定栈顶符号和下一个输入符号之间的优先关系，进而判断栈顶符号是否是句柄的尾。如果是句柄尾（栈顶 \(\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\)

\[\begin{aligned} S&\to BB \\ B&\to aB \\ B&\to b \end{aligned}\]

它的 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\)。得到

\[I_0=\mathrm{CLOSURE}(\{S'\to.S\})=\{S'\to.S, S\to.BB, B\to.aB, B\to.b\}\]

\(\varepsilon\)-闭包的定义是：

\[\mathrm{CLOSURE}(I)=I\cup\{B\to.\gamma|A\to\alpha.B\beta\in I, B\to\gamma\in P\}\]

记 \(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}\) 集

\[\mathrm{FOLLOW}(A)=\{a|S\xRightarrow{+}\cdots Aa\cdots, a\in\{\#\}\cup T\}\]

将上面 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\)（怎么又是你）：

\[\begin{aligned} E&\to E+T \\ E&\to T \\ T&\to T*F \\ T&\to F\\ F&\to (E) \\ F&\to \mathbf{id} \end{aligned}\]

首先得到增广文法 \(G'\)：

\[\begin{aligned} E'&\to E \\ E&\to E+T \\ E&\to T \\ T&\to T*F\\ T&\to F \\ F&\to (E) \\ F&\to \mathbf{id} \end{aligned}\]

列出初始状态 \(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}\) 集：

\[\begin{aligned} &\mathrm{FIRST}(F)=\{\mathbf{id}, (\} \\ &\mathrm{FIRST}(T)=\{\mathbf{id}, (\} \\ &\mathrm{FIRST}(E)=\{\mathbf{id}, (\} \\ &\mathrm{FOLLOW}(E)=\{), +, \#\} \\ &\mathrm{FOLLOW}(T)=\{), +, \#, *\} \\ &\mathrm{FOLLOW}(F)=\{), +, \#, *\} \end{aligned}\]

运行 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) 闭包：

\[\mathrm{CLOSURE}(I)=\{[B\to.\eta, b]|\exist[A\to\alpha.B\beta, a]\in\mathrm{CLOSURE}(I), B\to\eta\in P, b\in\mathrm{FIRST}(\beta a)\}\]

定义转移函数：

\[\mathrm{GO}(I, X)=\mathrm{CLOSURE}(\{[A\to\alpha X.\beta, a]|\forall[A\to\alpha.X\beta, a]\in I\})\]

用下面的算法构造 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) 几种方法。

本节笔记到此结束。