编译原理：词法分析

整理一下以前的笔记，说不定有人用得到呢。

文法

形式化定义

$G=(N,T,P,S)$，其中：$N$ 是非终结符集合，$T$ 是终结符集合，$P$ 是产生式集合，$S$ 是开始符号。

终结符：文法所定义的语言的基本符号，有时也叫 Token。例如，句子的基本符号是单词，那么这里单词就是句子文法中的终结符。
非终结符：表示语法成分的符号，有时也叫“语法变量”。由非终结符可以推导出句子的其他成分。例如，句子文法中的终结符就是名词、动词短语等。需要注意的是，$T \cap N=\varnothing$，$T \cup N=文法符号集$。
产生式：描述了将终结符和非终结符组合成串的方法。一般形式为：$\alpha \rightarrow \beta$，其中 $\alpha \in (T \cup N)^{+}$，且至少包含一个非终结符，称为产生式的头或左部；$\beta \in (T \cup N)^{*}$，称为产生式的体或右部。
开始符号：$S \in N$，这是一个特殊的非终结符，表示文法中最大的语法成分。

例如，一个包含了括号、加号和乘号的算术表达式文法可以定义为如下形式：

$$ \begin{align*} & G=(\{id,\ +,\ *,\ (,\ )\},\ \{E\},\ P,\ E)\\ & P=\{E \rightarrow E+E,\ E \rightarrow EE,\ E \rightarrow (E),\ E \rightarrow id\} \end{align*}$$

产生式的简写

对左部相同的一组 $\alpha$ 产生式w：

$$ \alpha \rightarrow \beta_{1},\ \alpha \rightarrow \beta_{2},\ …, \alpha \rightarrow \beta_{n} $$

可以简记为：

$$ \alpha \rightarrow \beta_{1}\ |\ \beta_{2}\ |\ …\ |\ \beta_{n} $$

其中，$\beta_{1},\ \beta_{2},\ …,\beta_{n}$ 称为 $\alpha$ 的候选式。

文法的分类

由 $k$ 型文法生成的语言就叫做 $k$ 型语言。同样地，由 X 文法生成的语言也可以叫做 X 语言（例如，正则文法生成的是正则语言）。

0~3 型文法是一个逐级包含的关系。也就是说，如果一个文法是 3 型文法，那么它也一定是 2 型、1 型和 0 型文法，反之则不成立。

0 型文法（无限制文法、短语结构文法）
$\forall \alpha \rightarrow \beta \in P$，$\alpha$ 中至少包含 1 个非终结符。
1 型文法（上下文有关文法，Context-Sensitive Grammar，CSG）
$\forall \alpha \rightarrow \beta \in P$，$\lvert \alpha \rvert \leq \lvert \beta \rvert$，即产生式左部的符号个数不能多于右部。产生式的一般形式为：$\alpha_{1} A \alpha_{2} \rightarrow \alpha_{1} \beta \alpha_{2} \ (\eta \neq \epsilon)$，即当非终结符 $A$ 的上文和下文分别是 $\alpha_{1}$ 和 $\alpha_{2}$ 时，才能将其替换为 $\beta$。需要注意的是，CSG 中不包含 $\epsilon$-产生式（空产生式）。
2 型文法（上下文无关文法，Context-Free Grammar，CFG）
$\forall \alpha \rightarrow \beta \in P,\ \alpha \in N$，即产生式的左部必须为非终结符。其一般形式为 $A \rightarrow \beta$，也就是说，将 $A$ 替换为 $\beta$ 不需要考虑上下文。例如，下面的文法就是一个 CFG：

$$ \begin{align*} & S \rightarrow L\ |\ LT \\ & T \rightarrow L\ |\ D\ |\ TL\ |\ TD \\ & L \rightarrow a\ |\ b\ |\ c\ |\ d\ |\ …\ |\ z \\ & D \rightarrow 0\ |\ 1\ |\ 2\ |\ 3\ |\ …\ |\ 9 \end{align*} $$

3 型文法（正则文法，Regular Grammar，RG）具体又分为以下两种（$w$ 表示终结符串）：
- 右线性文法：$A \rightarrow wB$ 或 $A \rightarrow w$。
- 左线性文法：$A \rightarrow Bw$ 或 $A \rightarrow w$。

$$ \begin{align*} & S \rightarrow a\ |\ b\ |\ c\ |\ d\ |\ …\ |\ z \\ & S \rightarrow aT\ |\ bT\ |\ cT\ |\ dT\ |\ …\ |\ zT \\ & T \rightarrow a\ |\ b\ |\ c\ |\ d\ |\ …\ |\ z\ |\ 0\ |\ 1\ |\ 2\ |\ …\ |\ 9 \\ & T \rightarrow aT\ |\ bT\ |\ cT\ |\ dT\ |\ …\ |\ zT\ |\ 0T\ |\ 1T\ |\ 2T\ |\ …\ |\ 9T \end{align*} $$

CFG

推导

对于下列文法：

$$ E \rightarrow E+E\ |\ E*E\ | \ -E\ |\ (E)\ |\ id $$

我们考虑其中的一个产生式 $E \rightarrow -E$，它表明，如果 $E$ 表示一个产生式，那么 $-E$ 也一定表示一个产生式。将一个 $E$ 替换为 $-E$ 的过程写作 $E \Rightarrow -E$，读作“$E$ 推导出 $-E$”。

推导的正式定义是：

对于文法符号序列 $\alpha A \beta$，$\alpha$ 和 $\beta$ 是任意的文法符号串，$A$ 是一个非终结符。给定产生式 $A \rightarrow \gamma$，将 $A$ 替换为 $\gamma$ 的过程写作 $A \Rightarrow \gamma$。这个过程叫做推导。符号 $\Rightarrow$ 表示“通过一步推导出”。
如果通过一个推导序列 $\alpha_{1} \Rightarrow \alpha_{2} \Rightarrow … \Rightarrow \alpha_{n}$ 将 $\alpha_{1}$ 替换为 $\alpha_{n}$，那么我们说 $\alpha_{1}$ 推导出 $\alpha_{1}$。
如果 $\alpha_{1}$“经过零步或多步推导出”$\alpha_{n}$，我们可以写作 $\alpha_{1} \stackrel{*}{\Rightarrow} \alpha_{n}$。对于任何串 $\alpha$，有 $\alpha \stackrel{}{\Rightarrow} \alpha$。若 $\alpha \stackrel{*}{\Rightarrow} \beta$ 且 $\beta \Rightarrow \gamma$，则有 $\alpha \stackrel{*}{\Rightarrow} \gamma$。
类似地，$\alpha_{1} \stackrel{+}{\Rightarrow} \alpha_{n}$ 表示 $\alpha_{1}$“经过一步或多步推导出”$\alpha_{n}$。

句型

若 $S \stackrel{*}{\Rightarrow} \alpha$，其中 $S$ 是文法 $G$ 的开始符号，则称 $\alpha$ 是文法 $G$ 的一个句型。句型可以包含终结符，也可以包含非终结符，还可以是空串。

句子

句子是不包含非终结符的句型。一个文法生成的语言就是其所有句子的集合。若两个文法能生成相同的句子，则它们等价。

分析树

对下列文法：

$$ \begin{align*} & G: \\ & ①\ E→E+E \\ & ②\ E-EE \\ & ③\ E→-E \\ & ④\ E→(E) \\ & ⑤\ E→id \\ \end{align*} $$

有一个如下的树形结构：

根节点为文法开始符号。
非根节点表示了对一个产生式 $A \rightarrow \beta$ 的应用。这个非根节点的标号是产生式的左部，子节点标号从左至右构成了产生式的右部。例如，上面的分析树中，根节点是对于产生式 ③ 的应用。
叶节点的内容既可以是非终结符，也可以是终结符。从左至右排列分析树得到的内容，叫做这棵分析树的产出（yield）或边缘（frontier）。
分析树是推导的图形化表示。给定一个推导 $S \Rightarrow \alpha_{1} \Rightarrow \alpha_{2} \Rightarrow … \Rightarrow \alpha_{n}$，对于推导过程中得到的每一个 $\alpha_{i}$，都可以构造出一棵以其为边缘的分析树。

短语

给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语。

仍旧以上面的分析树为例，其中的短语有：

$$ \begin{align*} & -(E+E) \\ & (E+E)\\ & E+E\\ \end{align*} $$
特别地，如果子树只有父子两代节点（高度为 2），那么这棵子树的边缘就称为该句型的一个直接短语。进而我们可以知道，直接短语一定是某个产生式的右部，但反之不一定成立。

在上面的例子中，直接短语只有 $E+E$。

句柄

直接短语中的最左直接短语称为该句型的句柄。

在上面的例子中，因为直接短语只有一个 $E+E$，因此它也就是该句型的句柄。

【例】

给定下列文法：

$$ \begin{align*} & G: \\ & ① \ S \rightarrow (L) \ | \ aS \ | \ a \\ & ② \ L \rightarrow L,S \ | \ S \end{align*} $$

证明 $(S,(a)) (S,(a))(S,(a))$ 是该文法的一个句型，并指出这个句型的短语、直接短语和句柄。

【解】

首先画出分析树：

（1）根据定义，逐层求解短语。

对于第 1 层的非终结符 $S$，可以求出一个短语 $(S,(a))$。

对于第 2 层的非终结符 $L$，可以求出一个短语 $S,(a)$。

对于第 3 层的非终结符 $L$，可以求出一个短语 $S$。

对于第 3 层的非终结符 $S$，可以求出一个短语 $(a)$。

对于第 4 层的非终结符 $L$，可以求出一个短语 $a$。

对于第 5 层的非终结符 $S$，可以求出一个短语 $a$。

综上，给定句型的短语有：

$$ \begin{align*} & (S,(a)) \\ & S,(a) \\ & S \\ & (a) \\ & a \end{align*} $$

（2）由定义可以知道，直接短语有：

$$ \begin{align*} & S \\ & a \end{align*}$$

（3）由定义可以知道，句柄为 $S$。

如果一个文法可以为某个句子生成多棵分析树，那么这个文法就是二义性文法。

例如下面条件语句的文法，其中前两个产生式表示条件语句，第三个产生式表示除了条件语句之外的其他语句。

$$ \begin{align*} S \rightarrow & \textbf{if}\ E\ \textbf{then}\ S \\ & |\ \textbf{if}\ E\ \textbf{then}\ S\ \textbf{else}\ S \\ & |\ other \end{align*} $$

给定句型 $\textbf{if}\ E_{1}\ \textbf{then}\ \textbf{if}\ E_{2}\ \textbf{then}\ S_{1}\ \textbf{else}\ S_{2}$，我们可以得到如下的两棵分析树：

这里产生歧义的原因是，句型中有两个 $\textbf{if}$，而只有一个 $\textbf{else}$。后者与前者的匹配就会出现歧义。因此我们需要进行消歧义。

大多数的程序设计语言规定，每个 else 和离它最近的尚未匹配的 if 相匹配。基于此，对于上面的文法，左侧的分析树是正确的。

对于任意一个 CFG，不存在能判断它是无二义性的算法。但是能给出一组充分条件，满足这组充分条件的文法是无二义性的。

从正则表达式到 CFG

考虑正则表达式 (a|b)*abb 和下列文法：

$$ \begin{align*} & A_{0} \rightarrow aA_{0}\ |\ bA_{0}\ |\ aA_{1} \\ & A_{1} \rightarrow bA_{2} \\ & A_{2} \rightarrow bA_{3} \\ & A_{3} \rightarrow \epsilon \end{align*} $$

它们描述了同一个语言：以 abb 结尾的、由 a 和 b 组成的所有串的集合。

将正则表达式转换为对应的 CFG，可以采用下述方法：

① 构造正则表达式的 NFA
② 对于 NFA 的每个状态 $i$，创建一个非终结符 $A_{i}$
③ 若状态 $i$ 有一个在输入 $a$ 上到达状态 $j$ 的转换，则加入产生式 $A_{i} \rightarrow aA_{j}$。如果这个输入是 $\epsilon$，则加入产生式 $A_{i} \rightarrow A_{j}$
④ 若 $i$ 是一个接收状态，则加入产生式 $A_{i} \rightarrow \epsilon$
⑤ 若 $i$ 是 NFA 的开始状态，则令 $A_{i}$ 为所得文法的开始符号

自顶向下分析概述

自顶向下的分析过程是从分析树的顶部（根节点）向底部（叶节点）方向构造分析树。也可以看成是从文法开始符号 $S$ 推导出词串 $w$ 的过程。

例如：

在每一步推导中，需要做出以下两个选择：

替换当前句型中的哪个非终结符
使用该终结符的哪个候选式进行替换

最左推导和最右推导

最左推导

在最左推导中，总是选择每个句型的最左非终结符进行替换。

如果 $S \stackrel{*}{\Rightarrow}_{lm} \alpha$，则称 $\alpha$ 是当前文法的最左句型。

最右推导

在最右推导中，总是选择每个句型的最右非终结符进行替换。

在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导。

唯一性

给定一棵分析树，其最左推导和最右推导都是唯一的，因为在推导过程中其最左终结符和最右终结符是唯一的。

自顶向下分析的通用形式：递归下降过程

由一组过程组成，每个过程对应一个非终结符
从文法开始符号 $S$ 对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果 $S$ 对应的过程体恰好扫描了整个输入串，则成功完成语法分析。

void A()
{
    // 选择一个 A 产生式，A -> X1 X2 ... Xk
    for (int i = 1; i <= k; i++)
    {
        if (X 是一个非终结符号)
            // 调用过程 X0
        else if (Xi 等于当前的输入符号 a)
            // 读入下一个输入符号
        else
            // 出错
    }
}

在递归下降的过程中，可能会因为出现回溯的情况，导致分析效率降低。例如，当遇到多个以 $A$ 开头的候选式时，分析器需要逐个尝试。如果当前候选式无法成功匹配，则会回溯，重新选择下一个候选式。

需要回溯的分析器叫做不确定分析器，能够预测而不需要回溯的分析器叫做预测分析器。

预测分析

预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常为 1）符号来选择正确的 $A$-产生式。它不需要回溯，是一种确定的分析方法。

可以对某些文法构造出向前看 $k$ 个输入符号的预测分析器，该类文法有时也称为 LL(k) 文法类。

左递归

含有 $A \rightarrow A \alpha$ 形式产生式的文法是直接左递归的。更一般的情况是，若文法中存在推导 $A \stackrel{+}{\Rightarrow} A \alpha$，则称该文法是左递归的。

消除直接左递归

对于产生式 $A \rightarrow A \alpha\ |\ \beta\ (\alpha \neq \epsilon 且 \beta 不以 A 开头)$，可以得出以下推导：

$$ \begin{align*} A & \Rightarrow A \alpha \\ & \Rightarrow A \alpha \alpha \\ & \Rightarrow A \alpha \alpha \alpha \\ & \Rightarrow \ … \\ & \Rightarrow A \alpha\ …\ \alpha \\ & \Rightarrow \beta \alpha\ …\ \alpha \end{align*} $$

它对应的正则表达式为 r=βα*。

因为 $A$ 经过推导最终得到的串是以 $\beta$ 开头，那么我们可以引入一个新的终结符 $A'$，然后将原有的产生式改写为：

$$ \begin{align*} & A \rightarrow \beta A' \\ & A' \rightarrow \alpha A'\ |\ \epsilon \end{align*} $$

上述两组产生式是等价的。

实际上，这里消除左递归，就是将其改写成了右递归。上述产生式可以当作直接左递归的“通式”记下来，利用这个“通式”，来看一个例子：

对于存在多个直接左递归的情况，我们可以将其扩展到一般形式：

$$ \begin{gather*} A \rightarrow A \alpha_{1}\ |\ A \alpha_{2}\ |\ … |\ A \alpha_{n}\ |\ \beta_{1}\ |\ \beta_{2}\ |\ …\ |\ \beta_{m} \ (\alpha_{i} \neq \epsilon且 \beta_{j} 不以 A 开头) \\ \Downarrow \\ \begin{aligned} & A \rightarrow \beta_{1}A'\ |\ \beta_{2}A'\ |\ …\ |\ \beta_{m}A' \\ & A' \rightarrow \alpha_{1}A'\ |\ \alpha_{2}A'\ |\ …\ |\ \alpha_{n}A'\ |\ \epsilon \end{aligned} \end{gather*} $$

毕竟鱼和熊掌不可兼得，消除左递归也会有代价，在这个过程中会引入新的非终结符和 $\epsilon$-产生式。

消除间接左递归

对于下列文法：

$$ \begin{align*} & S \rightarrow Aa\ |\ b \\ & A \rightarrow Ac\ |\ Sd\ |\ \epsilon \end{align*} $$

会产生推导 $S \Rightarrow Aa \Rightarrow Sda$，在第二步推导的结果中，出现了左递归。经过一步或多部推导出现的左递归，叫做间接左递归。那么该如何消除呢？

将 $S$ 的产生式带入到 $A$ 的产生式中，得到：

$$ A \rightarrow Ac\ |\ Aad\ |\ bd\ |\ \epsilon $$

这个产生式中就出现了直接左递归，利用之前提到的方法消除即可：

$$ \begin{align*} & A \rightarrow bdA'\ |\ A' \\ & A' \rightarrow cA'\ |\ adA'\ |\ \epsilon \end{align*} $$

上面的 $S$ 产生式和这时得到的 $A$ 和 $A'$ 产生式即是原始产生式消除间接左递归之后的结果。

提取左公因子

多个产生式中的公共前缀叫做左公因子。如果含有左公因子，需要将其提取出来。例如下面的文法 $G$：

$$ \begin{align*} & G: \\ & S \rightarrow aAd\ |\ aBe \\ & A \rightarrow c \\ & B \rightarrow b \end{align*} $$

在提取左公因子之后就得到了文法 $G'$：

$$ \begin{align*} & G: \\ & S \rightarrow aS' \\ & S' \rightarrow Ad\ |\ Be\\ & A \rightarrow c \\ & B \rightarrow b \end{align*} $$

在左公因子存在的情况下，分析器扫描到公共前缀时将无法做出下一步决策。提取左公因子就是通过改写产生式来推迟决定，等待读入了足够多的输入、获得足够多的信息之后再做出正确的选择。

LL(1) 文法

$S$-文法

预测分析法的工作过程

从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符 $A$ 和当前输入符号 $a$ ，选择正确的 $A$-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

$S$-文法的定义（简单的确定性文法）

满足以下条件的文法即为 $S$-文法：

每个产生式的右部都以终结符开始
同一非终结符的各个候选式的首终结符都不同

由上述定义可以看出，$S$-文法不含 $\epsilon$-产生式。如果包含空产生式，则可能产生问题。

例如对于下列文法：

$$\begin{align*} & S \rightarrow aBC \\ & B \rightarrow bC\\ & B \rightarrow dB \\ & B \rightarrow \epsilon \\ & C \rightarrow c \\ & C \rightarrow a \\ & D \rightarrow e \end{align*} $$

如果给定输入 $ada$，则有推导 $S \Rightarrow aBC \Rightarrow adBC \Rightarrow adC \Rightarrow ada$。

然而，对于给定输入 $ade$，当推导进行到 $S \Rightarrow aBC \Rightarrow adBC \Rightarrow adC$ 的时候，由于 $C$ 不存在能推导出 $e$ 的产生式，因此推导无法继续进行。这涉及到了何时能使用 $\epsilon$-产生式的问题。

如果当前某非终结符 $A$ 与当前输入符 $a$ 不匹配时，若存在 $A \rightarrow \epsilon$，可以通过检查 $a$ 是否可以出现在 $A$ 的后面，来决定是否使用产生式 $A \rightarrow \epsilon$。若文法中没有 $A \rightarrow \epsilon$，则应报错。

非终结符的后继符号集

基于上面的原因，我们引入非终结符的后继符号集这一概念。

可能在某个句型中紧跟在 $A$ 后的终结符 $a$ 的集合，记为 $FOLLOW(A)$。$FOLLOW(A) = \{a\ |\ S \stackrel{*}{\Rightarrow} \alpha Aa \beta,\ a \in T,\ \alpha,\beta \in (T \cup N)^{*}\}$。同时我们规定，如果 $A$ 是某个句型的最右符号，则将结束符 $\#$ 加入 $FOLLOW(A)$ 中。

例如上面的文法中，我们可以看出 $FOLLOW(B) = \{a,\ c\}$ 。

计算方法

不断应用下列规则，直到没有新的终结符可以被加入任何 $FOLLOW$ 集为止：

对于文法开始符号 $S$，将 $\#$ 加入 $FOLLOW(S)$
若存在产生式 $A \rightarrow \alpha B \beta$，则 $FIRST(\beta)$ 中除了 $\epsilon$ 之外的所有符号都在 $FOLLOW(B)$ 中
若存在产生式 $A \rightarrow \alpha B$，或存在产生式 $A \rightarrow \alpha B \beta$ 且 $\epsilon \in FIRST(\beta)$，则 $FOLLOW(A)$ 中的所有符号都在 $FOLLOW(B)$ 中

【例 1】

$$ \begin{align*}& ①\ E \rightarrow TE' && FIRST(E) = \{(,\ \text{id}\} && FOLLOW(E) = \{\#,\ ),\ \} \\& ②\ E' \rightarrow +TE'\ |\ \epsilon && FIRST(E') = \{+,\ \epsilon\} && FOLLOW(E') = \{\#,\ )\} \\& ③\ T \rightarrow FT' && FIRST(T) = \{(,\ \text{id}\} && FOLLOW(T) = \{+,\ \#,\ ) \} \\& ④\ T' \rightarrow *FT'\ |\ \epsilon && FIRST(T') = \{*,\ \epsilon\} && FOLLOW(T') = \{+,\ \#,\ ) \} \\& ⑤\ F \rightarrow (E)\ |\ \text{id} && FIRST(F) = \{(,\ \text{id}\} && FOLLOW(F) = \{*,\ +,\ \#,\ )\}\end{align*} $$
1. 文法的开始符号 $E$ 本身就是一个句型，它也是这个句型的最右符号，因此我们将 $\#$ 加入 $FOLLOW(E)$；
2. 由产生式 ① 可以看出，$FIRST(E')$ 中的所有终结符可以跟在 $T$ 之后，因此我们将前者中的所有终结符（即 $+$）加入 $FOLLOW(T)$。由于 $\epsilon \in FIRST(E')$，即存在推导 $E' \Rightarrow \epsilon$，因此当 $E'$ 被 $\epsilon$ 替换时，能跟在 $T$ 之后的终结符就能跟在 $E$ 之后，因此将目前 $FOLLOW(E)$ 中的所有元素（即 $\#$）加入 $FOLLOW(T)$；
3. 继续考虑产生式 ① 中的 $E'$，它是该产生式的右部的最右符号，因此能跟在 $E$ 之后的终结符也能跟在 $E'$ 之后，因此我们将目前 $FOLLOW(E)$ 中的所有符号（即 $\#$）加入 $FOLLOW(E')$；
4. 产生式 ② 中，$T$ 和 $E'$ 的位置与产生式 ① 中类似，因此结果与产生式 ① 相同，跳过；
5. 由产生式 ③ 可以看出，$FIRST(T')$ 中的所有非终结符（即 $*$）可以加入 $FOLLOW(F)$；
6. 同样，由于 $\epsilon \in FIRST(T)$，即存在推导 $T \Rightarrow \epsilon$，因此当 $T'$ 被 $\epsilon$ 替换时，能跟在 $T$ 之后的终结符就能跟在 $F$ 之后，因此将目前 $FOLLOW(T)$ 中的所有元素（即 $+$ 和 $\#$）加入 $FOLLOW(F)$；
7. 继续考虑产生式 ② 中的 $T'$，类似步骤 3 的方法，将 $FOLLOW(T)$ 中的所有元素加入 $FOLLOW(T')$；
8. 产生式 ④ 中，$F$ 和 $T'$ 所处位置类似产生式 ③，因此得到的结果也是一样的；
9. 产生式 ⑤ 中，$)$ 跟在 $E$ 之后，因此将 $)$ 加入 $FOLLOW(E)$；
10. 从前面的步骤中我们可以看出，$FOLLOW(E')$ 依赖于 $FOLLOW(E)$，$FOLLOW(T')$ 依赖于 $FOLLOW(T)$，因此需要进行相应的更新。因此我们需要重复上述过程以确保更新了所有的 $FOLLOW$ 集；
11. 由步骤 2，$FOLLOW(T)$ 依赖于 $FOLLOW(E)$，因此我们将后者中新的元素（即 $)$）加入 $FOLLOW(T)$；
12. 由步骤 3，$FOLLOW(E')$ 依赖于 $FOLLOW(E)$，因此我们将后者中新的元素（即 $)$）加入 $FOLLOW(E')$；
13. 由步骤 6，$FOLLOW(F)$ 依赖于 $FOLLOW(T)$，因此我们需要将后者中新的元素（即 $)$）加入 $FOLLOW(F)$；
14. 由步骤 7，$FOLLOW(T')$ 依赖于 $FOLLOW(T)$，因此我们需要将后者中新的元素（即 $)$）加入 $FOLLOW(F)$。

【例 2】

$$ \begin{align*}& ①\ S \rightarrow uBDz && FIRST(S) = \{u\} && FOLLOW(S) = \{\$\} \\& ②\ B \rightarrow Bv\ |\ w && FIRST(B) = \{w\} && FOLLOW(B) = \{x,\ y,\ z,\ v\} \\& ③\ D \rightarrow EF && FIRST(D) = \{x,y,\epsilon\} && FOLLOW(D) = \{z\} \\& ④\ E \rightarrow y\ |\ \epsilon && FIRST(E) = \{y,\epsilon\} && FOLLOW(E) = \{x,\ z\}\\& ⑤\ F \rightarrow x\ |\ \epsilon && FIRST(F) = \{x,\epsilon\} && FOLLOW(F) = \{z\}\end{align*} $$

非终结符的串首终结符集合

位于串首位置的终结符，称为串首终结符，简称首终结符。

给定文法符号串 $\alpha$。将可以从 $\alpha$ 推导出的所有串首终结符构成的集合定义为 $\alpha$ 的串首终结符集 $FIRST(\alpha)$。若 $\alpha \stackrel{*}{\Rightarrow} \epsilon$，那么 $\epsilon \in FIRST(\alpha)$。

计算方法

单个文法符号 $\alpha$ 的 $FIRST$ 集

不断应用下列规则，直到没有新的终结符或 $\epsilon$ 可以被加入到任何 $FIRST$ 集中为止：

若 $X$ 是一个非终结符，那么 $FIRST(X) = \{X\}$
若 $X$ 是一个非终结符，且 $X \rightarrow Y_{1}…Y_{k} \in P\ (k \ge 1)$，那么如果对于某个 $i$，$a \in FIRST(Y_{i})$ 且 $\epsilon$ 在所有的 $FIRST(Y_{1}),…,FIRST(Y_{i-1})$ 中（即 $Y_{1}…Y{i-1} \stackrel{*}{\Rightarrow} \epsilon$），则将 $a$ 加入 $FIRST(X)$。若对于所有的 $j = 1,2,…,k$，$\epsilon \in FIRST(Y_{j})$，则将 $\epsilon$ 加入 $FIRST(X)$
若 $X \rightarrow \epsilon \in P$，则将 $\epsilon$ 加入 $FIRST(x)$

【例 1】

$$ \begin{align*}& ①\ E \rightarrow TE' && FIRST(E) = \{(,\ \text{id}\} \\& ②\ E' \rightarrow +TE'\ |\ \epsilon && FIRST(E') = \{+,\ \epsilon\} \\& ③\ T \rightarrow FT' && FIRST(T) = \{(,\ \text{id}\} \\& ④\ T' \rightarrow *FT'\ |\ \epsilon && FIRST(T') = \{*,\ \epsilon\}\\& ⑤\ F \rightarrow (E)\ |\ \text{id} && FIRST(F) = \{(,\ \text{id}\}\end{align*} $$
1. 非终结符能推导出的首终结符，取决于其产生式的右部。若产生式右部以非终结符开始（②、④、⑤），那么该终结符就是产生式左部可以推导的串首终结符，因此我们将这些终结符加入到左部非终结符的 $FIRST$ 集中。在这里就是将 $+$ 加入 $FIRST(E')$，将 $*$ 加入 $FIRST(T')$，将 $($ 和 $\text{id}$ 加入 $FIRST(F)$；
2. 根据定义，若终结符能推导出 $\epsilon$，则它也在这个终结符的 $FIRST$ 集中。在这里涉及到产生式 ② 和 ④，因此我们将 $\epsilon$ 加入 $FIRST(E')$ 和 $FIRST(T')$；
3. 若产生式右部以非终结符开始，如产生式 ①，此时右部非终结符 $T$ 的 $FIRST$ 集中的所有终结符，都是左部非终结符 $E$ 可以推导出的首终结符，因此将 $FIRST(T)$ 中的所有终结符加入 $FIRST(E)$。由于此时 $FIRST(T)$ 为空，我们暂时先放在这里，稍后回来计算；
4. 根据第 3 步中的描述，我们将 $FIRST(F)$ 中的所有非终结符（也就是 $($ 和 $\text{id}$）加入 $FIRST(T)$。同时因为第 3 步中我们说 $FIRST(E)$ 依赖于 $FIRST(T)$，因此我们同样将 $($ 和 $\text{id}$）加入 $FIRST(E)$。至此该文法中的各个非终结符的 $FIRST$ 集计算完毕。

【例 2】

$$ \begin{align*}& ①\ S \rightarrow uBDz && FIRST(S) = \{u\} \\& ②\ B \rightarrow Bv\ |\ w && FIRST(B) = \{w\} \\& ③\ D \rightarrow EF && FIRST(D) = \{x,y,\epsilon\} \\& ④\ E \rightarrow y\ |\ \epsilon && FIRST(E) = \{y,\epsilon\} \\& ⑤\ F \rightarrow x\ |\ \epsilon && FIRST(F) = \{x,\epsilon\}\end{align*} $$
1. 产生式 ①、②、④ 和 ⑤ 很容易确定出 $S$、$E$ 和 $F$ 的 $FIRST$ 集。我们将 $u$ 加入 $FIRST(S)$，将 $w$ 加入 $FIRST(B)$，将 $y$ 和 $\epsilon$ 加入 $FIRST(E)$，将 $x$ 和 $\epsilon$ 加入 $FIRST(F)$
2. 对于产生式 ③，$FIRST(D)$ 和 $E$、$F$ 都有关。当 $E \Rightarrow y$ 时，我们将 $y$ 加入 $FIRST(E)$；当 $E \Rightarrow \epsilon$ 时，我们将 $FIRST(F)$ 中的所有终结符（也就是 $x$ 和 $\epsilon$）加入 $FIRST(F)$

串 $X_{1} X_{2} … X_{n}$ 的 $FIRST$ 集

向 $FIRST(X_{1} X_{2} … X_{n})$ 加入 $FIRST(X_{1})$ 中所有的非 $\epsilon$ 符号
若 $\epsilon \in FIRST(X_{i})$，再加入 $FIRST(X_{i + 1})$ 中的所有非 $\epsilon$ 符号。不断重复该过程直到无法继续

产生式的可选集

产生式 $A \rightarrow \beta$ 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为 $SELECT(A \rightarrow \beta)$。

$SELECT(A \rightarrow a\beta) = \{a\}$：对于一个产生式，如果其右部的第一个符号为终结符，则该产生式的可选集中只包含该终结符。即只有当遇到该终结符时，才能选用这个产生式。
$SELECT(A \rightarrow \epsilon) = FOLLOW(A)$：若产生式右部为空串，则只有当遇到 $FOLLOW(A)$ 中的元素时，才能选用该产生式。

基于串首终结符集合的概念，我们对产生式的可选集概念进行扩充：

若 $\epsilon \notin FIRST(\alpha)$，则 $SELECT(A \rightarrow \alpha) = FIRST(\alpha)$
若 $\epsilon \in FIRST(\alpha)$，则 $SELECT(A \rightarrow \alpha) = (FIRST(\alpha) - \{\epsilon\}) \cup FOLLOW(A)$

对于左部相同的产生式，若它们的可选集互不相交，则分析时可以做出确定的选择。

$q$-文法

每个产生式的右部要么为 $\epsilon$，要么以非终结符开始
具有相同左部的产生式有互不相交的可选集

也就是说，$q$-文法不含右部以终结符开始的产生式。

计算方法

给定下列文法：

$$\begin{align*}& ①\ E \rightarrow TE' && SELECT(①) = \{(,\ \text{id}\} \\& ②\ E' \rightarrow +TE' && SELECT(②) = \{+\} \\& ③\ E' \rightarrow \epsilon && SELECT(③) = \{\#, )\} \\& ④\ T \rightarrow FT' && SELECT(④) = \{(,\ \text{id}\} \\& ⑤\ T' \rightarrow *FT' && SELECT(⑤) = \{*\} \\& ⑥\ T' \rightarrow \epsilon && SELECT(⑥) = \{+,\ ), \#\} \\& ⑦\ F \rightarrow (E) && SELECT(⑦) = \{(\} \\& ⑧\ F \rightarrow \text{id} && SELECT(⑧) = \{\text{id}\}\end{align*}$$

这个文法也就是上面计算非终结符的后继符号集中例 1 的文法，我们已经求出了该文法中串首终结符集合以及非终结符的后继符号集，如下所示：

$$ \begin{align*}& FIRST(E) = \{(,\ \text{id}\} && FOLLOW(E) = \{\#,\ ),\ \} \\& FIRST(E') = \{+,\ \epsilon\} && FOLLOW(E') = \{\#,\ )\} \\& FIRST(T) = \{(,\ \text{id}\} && FOLLOW(T) = \{+,\ \#,\ ) \} \\& FIRST(T') = \{*,\ \epsilon\} && FOLLOW(T') = \{+,\ \#,\ ) \} \\& FIRST(F) = \{(,\ \text{id}\} && FOLLOW(F) = \{*,\ +,\ \#,\ )\}\end{align*} $$

因此我们可以求出各个产生式的可选集。步骤如下：

$SELECT(①)$ 是产生式右部第一个非终结符 $T$ 的 $FIRST$ 集中的终结符，即 $SELECT(①) = \{(,\ \text{id}\}$；
产生式 ② 右部以终结符 $+$ 开始，因此 $SELECT(②) = \{+\}$；
产生式 ③ 为 $\epsilon$-产生式，因此 $SELECT(③) = FOLLOW(E') = \{\#, )\}$；
$SELECT(④)$ 是产生式右部第一个非终结符 $F$ 的 $FIRST$ 集中的终结符，即 $SELECT(④) = \{(,\ \text{id}\}$；
产生式 ⑤ 右部以终结符 $*$ 开始，因此 $SELECT(⑤) = \{*\}$；
产生式 ⑥ 为 $\epsilon$-产生式，因此 $SELECT(⑥) = FOLLOW(T') = \{+,\ ), \#\}$；
产生式 ⑦ 右部以终结符 $($ 开始，因此 $SELECT(⑦) = \{(\}$；
产生式 ⑧ 右部只有终结符 $\text{id}$，因此 $SELECT(⑧) = \{\text{id}\}$。

可以看出，产生式 ② 和 ③ 具有相同的左部，它们的可选集互不相交；产生式 ⑤ 和 ⑥ 具有相同的左部，它们的可选集互不相交。因此这是一个 LL(1) 文法。进一步，我们可以为其构造预测分析表。

构造预测分析表

预测分析表的行对应非终结符，列对应输入符号。每一个单元格根据产生式的可选集填入对应的产生式。继续考虑上面的文法例子，其预测分析表构造如下：

	$\text{id}$	$+$	$*$	$($	$)$	$\#$
$E$	$E \rightarrow TE'$			$E \rightarrow TE'$
$E'$		$E' \rightarrow +TE'$			$E' \rightarrow \epsilon$	$E' \rightarrow \epsilon$
$T$	$T \rightarrow FT'$			$T \rightarrow FT'$
$T'$		$T' \rightarrow \epsilon$	$T' \rightarrow *FT'$		$T' \rightarrow \epsilon$	$T' \rightarrow \epsilon$
$F$	$F \rightarrow \text{id}$			$F \rightarrow (E)$

以产生式 ① 的 $E \rightarrow TE'$ 为例，$SELECT(①) = \{(,\ \text{id}\}$，表示当 $E$ 遇到输入 $($ 或 $\text{id}$ 时，可以选用该产生式。其他单元格以此类推。

LL(1) 文法的定义

当且仅当文法 $G$ 的任意两个具有相同左部的产生式 $A \rightarrow \alpha\ |\ \beta$ 满足下列条件时，我们说 $G$ 是 LL(1) 文法：

若 $\alpha$ 和 $\beta$ 均不能推导出 $\epsilon$，则 $FIRST(\alpha) \cap FIRST(\beta) = \varnothing$
$\alpha$ 和 $\beta$ 最多只有一个能推导出 $\epsilon$
如果都能推导出 $\epsilon$ 的话，则二者的可选集中都包含 $FOLLOW(A)$
若 $\beta \stackrel{}{\Rightarrow} \epsilon$，则 $FIRST(\alpha) \cap FOLLOW(A) = \varnothing$；若 $\alpha \stackrel{}{\Rightarrow} \epsilon$，则 $FIRST(\beta) \cap FOLLOW(A) = \varnothing$

上述三个条件保证了同一非终结符的各个产生式互不相交。基于此，我们可以为 LL(1) 文法构造预测分析器。

LL(1) 名称中，第一个 L 表示从左向右扫描输入，第二个 L 表示产生最左推导，1 表示每一步中只需要向前看 1 个输入符号来决定语法分析动作。

预测分析法

递归的预测分析法

递归的预测分析法是指：在递归下降分析中，编写每一个非终结符对应的过程时，根据预测分析表进行产生式的选择。

void A()
{
    // 选择一个 A 产生式，A -> X1 X2 ... Xk
    for (int i = 1; i <= k; i++)
    {
        if (X 是一个非终结符号)
            // 调用过程 X0
        else if (Xi 等于当前的输入符号 a)
            // 读入下一个输入符号
        else
            // 出错
    }
}

例如，对于文法：
$$ \begin{align*} & ①\ \langle \text{PROGRAM} \rangle \rightarrow \text{program}\ \langle \text{DECLIST} \rangle\ :\ \langle \text{TYPE} \rangle\ ;\ \langle \text{STLIST} \rangle\ \text{end} \\ & ②\ \langle \text{DECLIST} \rangle \rightarrow \text{id}\ \langle \text{DECLISTN} \rangle \\ & ③\ \langle \text{DECLISTN} \rangle \rightarrow ,\ \text{id}\ \langle \text{DECLISTN} \rangle \\ & ④\ \langle \text{DECLISTN} \rangle \rightarrow \epsilon \\ & ⑤\ \langle \text{STLIST} \rangle \rightarrow \text{s}\ \langle \text{STLISTN} \rangle \\ & ⑥\ \langle \text{STLISTN} \rangle \rightarrow ;\ s\ \langle \text{STLISTN} \rangle \\ & ⑦\ \langle \text{STLISTN} \rangle \rightarrow \epsilon \\ & ⑧\ \langle \text{TYPE} \rangle \rightarrow \text{real} \\ & ⑨\ \langle \text{TYPE} \rangle \rightarrow \text{int} \end{align*} $$

我们能求出 $SELECT(④) = \{:\}$ 和 $SELECT(⑦) = \{\text{end}\}$。

然后开始构造递归下降分析器的主程序。

program DESCENT;
    begin
        GETNEXT(TOKEN); // 获得下一个输入符号 TOKEN
        PROGRAM(TOKEN); // 传入 TOKEN，调用文法开始符号处理过程
        GETNEXT(TOKEN); // 继续获得下一个输入符号
        if TOKEN <> '#' then ERROR; // 不为结束符时报错
    end

$\langle PROGRAM \rangle$ 的处理过程如下，其处理过程依赖于产生式 ① 的右部：

procedure PROGRAM(TOKEN);
    begin
        if TOKEN <> 'program' then ERROR; // 右部第一个符号为终结符 program，已经由函数参数传入，直接检查 

        GETNEXT(TOKEN);
        DECLIST(TOKEN); // 右部的下一个符号为非终结符 <DECLIST>

        if TOKEN <> ':' then ERROR; // 判断终结符 :

        GETNEXT(TOKEN);
        TYPE(TOKEN); // 非终结符 <TYPE>

        GETNEXT(TOKEN);
        if TOKEN <> ';' then ERROR; // 终结符 ;

        GETNEXT(TOKEN);
        STLIST(TOKEN); // 非终结符 STLIST

        if TOKEN <> 'end' then ERROE; // 终结符 end
    end

$\langle DECLIST \rangle$ 的处理过程如下:

procedure DECLIST(TOKEN);
    begin
        if TOKEN <> 'id' then ERROR;

        GETNEXT(TOKEN);
        DECLISTN(TOKEN);
    end

$\langle DECLISTN \rangle$ 对应两个候选式，第一个候选式的可选集为 ${,}$，第二个产生式的可选集为 ${:}$。若当前的 TOKEN 为 , 则依据产生式 ③ 编写过程，为 : 则依据产生式 ④ 编写过程。伪代码如下：

procedure DECLISTN(TOKEN);
    begin
        if TOKEN <> ',' then
            begin
                GETNEXT(TOKEN);
                if TOKEN <> 'id' then ERROR;

                GETNEXT(TOKEN);
                DECLISTN(TOKEN);
            end
        else if TOKEN <> ':' then ERROR;
    end

$\langle STLIST \rangle$ 的处理过程如下：

procedure STLIST(TOKEN);
    begin
        if TOKEN <> 's' then ERROR;

        GETNEXT(TOKEN);
        STLISTN(TOKEN);
    end

$\langle STLISTN \rangle$ 的处理过程如下：

procedure STLISTN(TOKEN);
    begin
        if TOKEN = ';' then
            begin
                GETNEXT(TOKEN);
                if TOKEN <> 's' then ERROR;

                GETNEXT(TOKEN);
                STLISTN(TOKEN);
            end
        else if TOKEN <> 'end' then ERROR;
    end

$\langle TYPE \rangle$ 的处理过程如下：

procedure TYPE(TOKEN);
    begin
        if TOKEN <> 'real' or TOKEN <> 'int' then ERROR;
    end

非递归的预测分析法

非递归的预测分析不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析。

为这种目的构造的自动机叫做下推自动机（Push Down Automata, PDA）。相比于 FA，PDA 增加了一个叫做“下推存储器”的栈，起到了记忆的作用。例如，对于语言 $L={a^{n}b^{n}\ |\ n \ge 1}$，想要识别该语言的句子，就需要记录读入的 $a$ 和 $b$ 的个数，这对于 FA 是不可能的。因为 FA 需要利用不同的状态来表示不同个数的 $a$ 和 $b$，而识别该语言需要无限多种状态，与 FA 的状态有穷性矛盾。

而如果采用 PDA，每当遇到一个输入 $a$ 就将其压入栈中，每当遇到一个输入 $b$ 时则将一个 $a$ 出栈。如果输入读头到达串尾时恰好最后一个 $a$ 出栈（即 $a$ 和 $b$ 的个数相等），那么就成功接收该串。

下推自动机的工作流程（预测分析表的使用）

以之前“构造预测分析表”一节得到的预测分析表为例，给定输入为 $\text{id}+\text{id}*\text{id}$。

	$\text{id}$	$+$	$*$	$($	$)$	$\#$
$E$	$E \rightarrow TE'$			$E \rightarrow TE'$
$E'$		$E' \rightarrow +TE'$			$E' \rightarrow \epsilon$	$E' \rightarrow \epsilon$
$T$	$T \rightarrow FT'$			$T \rightarrow FT'$
$T'$		$T' \rightarrow \epsilon$	$T' \rightarrow *FT'$		$T' \rightarrow \epsilon$	$T' \rightarrow \epsilon$
$F$	$F \rightarrow \text{id}$			$F \rightarrow (E)$

分析流程如下：

栈内容（右侧为栈底）	剩余输入	输出	说明
$E\#$	$\text{id}+\text{id}*\text{id}\#$		初始状态，$\#$ 作为栈底
$TE'\#$	$\text{id}+\text{id}*\text{id}\#$	$E \rightarrow TE'$	栈顶 $E$ 遇到 $\text{id}$ 选择 $E \rightarrow TE'$ 此时左部出栈，右部进栈
$FT'E'\#$	$\text{id}+\text{id}*\text{id}\#$	$T \rightarrow FT'$	栈顶 $T$ 遇到 $\text{id}$ 选择 $T \rightarrow FT'$
$\text{id}T'E'\#$	$\text{id}+\text{id}*\text{id}\#$	$F \rightarrow \text{id}$	栈顶 $F$ 遇到 $\text{id}$ 选择 $F \rightarrow \text{id}$ 栈顶 $\text{id}$ 与输入匹配
$T'E'\#$	$+\text{id}*\text{id}\#$		$\text{id}$ 出栈，输入指向下一个符号
$E'\#$	$+\text{id}*\text{id}\#$	$T' \rightarrow \epsilon$	栈顶 $T'$ 遇到 $+$ 选择 $T' \rightarrow \epsilon$
$+TE'\#$	$+\text{id}*\text{id}\#$	$E' \rightarrow +TE'$	栈顶 $E'$ 遇到 $+$ 选择 $E' \rightarrow +TE'$ 栈顶 $+$ 与输入匹配
$TE'\#$	$\text{id}*\text{id}\#$		$+$ 出栈，输入指向下一个符号
$FT'E'\#$	$\text{id}*\text{id}\#$	$T \rightarrow FT'$	栈顶 $T$ 遇到 $\text{id}$ 选择 $T \rightarrow FT'$
$\text{id}T'E'\#$	$\text{id}*\text{id}\#$	$F \rightarrow \text{id}$	栈顶 $F$ 遇到 $\text{id}$ 选择 $F \rightarrow \text{id}$ 栈顶 $\text{id}$ 与输入匹配
$T'E'\#$	$*\text{id}\#$		$\text{id}$ 出栈，输入指向下一个符号
$*FT'E'\#$	$*\text{id}\#$	$T' \rightarrow *FT'$	栈顶 $T'$ 遇到 $$ 选择 $T' \rightarrow FT'$ 栈顶 $*$ 与输入匹配
$FT'E'\#$	$\text{id}\#$		$*$ 出栈，输入指向下一个符号
$\text{id}T'E'\#$	$\text{id}\#$	$F \rightarrow \text{id}$	栈顶 $F$ 遇到 $\text{id}$ 选择 $F \rightarrow \text{id}$ 栈顶 $\text{id}$ 与输入匹配
$T'E'\#$	$\#$		$\text{id}$ 出栈，输入指向下一个符号
$E'\#$	$\#$	$T' \rightarrow \epsilon$	栈顶 $T'$ 遇到 $\#$ 选择 $T' \rightarrow \epsilon$
$\#$	$\#$	$E' \rightarrow \epsilon$	栈顶 $E'$ 遇到 $\#$ 选择 $E' \rightarrow \epsilon$

当栈和输入都为空（即只剩下 $\#$）时，分析结束。输入产生式的序列对应一个最左推导。

递归和非递归的预测分析法的对比

	较易递归的预测分析法	非递归的预测分析法
程序规模	程序规模较大，不需要载入预测分析表	主控程序规模较小，需要载入预测分析表（但是表较小）
直观性	较好	较差
效率	较低	分析时间大约正比于分析程序的长较低度
自动生成的难易度	较难	较难

预测分析法的实现步骤

构造文法
改造文法：消除二义性、消除左递归、消除回溯。需要注意的是，求 $FIRST$ 和 $FOLLOW$ 集时，不必消除二义性和左递归
求每个变量的 $FIRST$ 和 $FOLLOW$ 集，从而求得每个候选式的 $SELECT$ 集
检查是不是 LL(1) 文法，若是，则继续构造预测分析表
对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法

自底向上的语法分析

从分析树的底部（叶节点）向顶部（根节点）方向构造分析树
可以看成是将输入串 $w$ 归约为文法开始符号 $S$ 的过程
自顶向下的语法分析采用最左推导方式；自底向上的语法分析采用最左归约方式（反向构造最右推导）

移入-归约分析

给定文法：

$$ \begin{align*} & ①\ E \rightarrow E + E \\ & ②\ E \rightarrow E * E \\ & ③\ E \rightarrow (E) \\ & ④\ E \rightarrow \text{id} \end{align*} $$

和输入 $\text{id}+(\text{id}+\text{id})$。那么移入-归约分析的流程如下（栈底在左，栈顶在右）：

栈	剩余输入	动作
$\#$	$\text{id}+(\text{id}+\text{id}) \#$
$\# \text{id}$	$+(\text{id}+\text{id}) \#$	移入将当前的输入符号 $\text{id}$ 移入到栈中此时栈顶的 $\text{id}$ 是产生式 ④ 的右部
$\# E$	$+(\text{id}+\text{id}) \#$	归约：$E \rightarrow \text{id}$
$\# E+$	$(\text{id}+\text{id}) \#$	移入
$\# E+($	$\text{id}+\text{id}) \#$	移入
$\# E+(\text{id}$	$+\text{id}) \#$	移入此时栈顶的 $\text{id}$ 是产生式 ④ 的右部
$\# E+(E$	$+\text{id}) \#$	归约：$E \rightarrow \text{id}$
$\# E+(E+$	$\text{id}) \#$	移入
$\# E+(E+\text{id}$	$) \#$	移入
$\# E+(E+E$	$) \#$	归约：$E \rightarrow \text{id}$
$\# E+(E$	$) \#$	归约：$E \rightarrow E+E$
$\# E+(E)$	$\#$	移入
$\# E+E$	$\#$	归约：$E \rightarrow (E)$
$\# E$	$\#$	归约：$E \rightarrow E+E$ 此时输入缓冲区已经为空，同时在栈中归约出了文法的开始符号 $E$

每次归约的符号串称为“句柄”。一旦句柄在栈顶形成则立即归约，因此保证了每一步都是最左归约。

在任意时刻，栈内符号串 + 剩余输入 = 规范句型。

关键问题

当栈中内容为 $\# \text{var}\ \langle IDS\rangle,\ \text{i}_{B}$ 时，同时满足了产生式 (2) 和 (3) 的右部。如果此时选择使用产生式 (2) 进行归约，就会造成如上图所述的无法继续进行分析的问题。

如果我们选择使用产生式 (3) 进行归约，那么分析过程就可以顺利进行。

造成上述错误的原因是错误地识别了句柄。在自底向上的分析过程中，每次归约的符号串应该是当前句型的一个直接短语（分析树中某个高度为 2 的子树的边缘，一定是某个产生式的右部）。在产生式 (2) 中，$\text{i}$ 虽然是该产生式的右部，但并不是某个高度为 2 的子树的边缘，也就不是当前句型的直接短语。当前句型的两个直接短语分别是 $\langle IDS \rangle,\ \text{i}_{B}$ 和 $\text{real}$，前者是最左直接短语（句柄），因此选择前者进行归约而不是后者。

LR 分析法

可以用 LR 分析法进行分析的文法称为 LR 文法。LR 文法是最大的、可以构造出相应移入-归约语法分析器的文法类。L 表示对输入进行从左到右的扫描，R 表示反向构造出一个最右推导序列。进一步地，为了准确识别句柄，LR(k) 分析需要向前查看 $k$ 个输入符号。当 $k = 0$ 和 $k = 1$ 时具有实践意义。省略 (k) 表示 $k = 1$。

基本原理

自底向上分析的关键时如何正确识别句柄。而句柄时逐步形成的，我们用“状态”表示句柄识别的进展程度。

例如，对于产生式 $S \rightarrow bBB$，可以有以下四种状态：
$$\begin{align*} & S \rightarrow \cdot bBB && 初始时期待终结符 b。b 出现之后可以将其移入分析栈，因此称该状态为移进状态\\ & S \rightarrow b\cdot BB && b 移入之后，期待归约出 B。\\ & S \rightarrow bB\cdot B && B 归约之后，期待再次归约出一个 B。该状态和上个状态被称为待约状态。\\ & S \rightarrow bBB\cdot && 两个 B 都归约出来之后，就可以将右部规约成文法开始符号 S。该状态称为归约状态。\\ \end{align*} $$

LR 分析器基于这些状态来构造自动机进行句柄的识别。

LR 自动机的总体结构如下：

LR 分析表的结构和使用

给定文法：

$$ \begin{align*} & ①\ S \rightarrow BB \\ & ②\ B \rightarrow aB \\ & ③\ B \rightarrow b \end{align*} $$

和分析表：

状态	ACTION			GOTO
状态	$a$	$b$	$\$$	$S$	$B$
0	s3	s4		1	2
1			acc
2	s3	s4			5
3	s3	s4			6
4	r3	r3	r3
5	r1	r1	r1
6	r2	r2	r2

其中每一行对应一个状态，0~6 共计 7 个状态。ACTION 表的每列对应文法中的一个终结符和结束符。ACTION 表的每项表示一个语法分析动作，$\text{s}n$ 表示移入动作，将当前输入符号入栈并进入状态 $n$，$\text{r}n$ 表示归约动作，用第 $n$ 个产生式进行归约（栈顶状态出栈，产生式左部入栈）。GOTO 表中的每列对应一个非终结符，每项表示在某个状态遇到某个非终结符时所要进入的后继状态。

给定输入 $bab$。

状态栈符号栈	剩余输入	说明
0 $\#$	$bab\#$	初始状态
0 4 $\# b$	$ab\#$	状态 0 遇到 $b$ 进行移入动作，转入状态 4
0 $\# B$	$ab\#$	状态 4 遇到 $a$ 使用产生式 ③ 进行归约动作此时状态栈顶为状态 0
0 2 $\# B$	$a b \#$	状态 0 遇到 $B$ 转入状态 2
0 2 3 $\# B a$	$b\#$	状态 2 遇到 $a$ 进行移入动作，转入状态 3
0 2 3 4 $\# B a b$	$\#$	状态 3 遇到 $b$ 进行移入动作，转入状态 4
0 2 3 $\# B a B$	$\#$	状态 4 遇到 $\#$ 使用产生式 ④ 进行归约
0 2 3 6 $\# B a B$	$\#$	状态 3 遇到 $B$ 转入状态 6
0 2 $\# B B$	$\#$	状态 6 遇到 $\#$ 使用产生式 ② 进行归约
0 2 5 $\# B B$	$\#$	状态 2 遇到 $B$ 转入状态 5
0 $\# S$	$\#$	状态 5 遇到 $\#$ 使用产生式 ① 进行归约
0 1 $\# S$	$\#$	状态 0 遇到 $\#$ 转入状态 1 状态 1 遇到 $\#$ 成功接受

LR(0) 分析法

将右部某位置存在圆点的产生式，称为相应文法的一个 LR(0) 项目（简称为项目），如 $A \rightarrow \alpha_{1} \cdot \alpha_{2}$。项目描述了句柄识别的状态。对于空产生式 $A \rightarrow \epsilon$，只产生一个项目 $A \rightarrow \cdot$。

设 $G$ 是一个以 $S$ 为开始符号的文法，则 $G$ 的增广文法 $G'$ 就是在 $G$ 中加上新的开始符号 $S'$ 和产生式 $S' \rightarrow S$ 而得到的文法。引入新的开始产生式的目的时使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态。

例如，下方左侧的是原有文法，右侧的是增广文法：

$$ \begin{align*} & ①\ E \rightarrow E + T && ⓪\ E' \rightarrow E \\ & ②\ E \rightarrow T && ①\ E\ \rightarrow E + T \\ & ③\ T \rightarrow T * F && ②\ E \rightarrow T\\ & ④\ T \rightarrow F && ③\ T \rightarrow T * F\\ & ⑤\ F \rightarrow (E) && ④\ T \rightarrow F\\ & ⑥\ F \rightarrow \text{id} && ⑤\ F \rightarrow (E)\\ &&& ⑥\ F \rightarrow \text{id}\end{align*} $$

文法中的项目

考虑如下文法和它每条产生式的项目：

$$ \begin{align*} & ①\ S' \rightarrow S && ②\ S \rightarrow \text{v}I:T && ③\ I \rightarrow I,\text{i} && ④\ I \rightarrow \text{i} && ⑤\ T \rightarrow \text{r} \\ \\ & && (2)\ S \rightarrow \cdot \text{v} I:T \\ & && (3)\ S \rightarrow \text{v} \cdot I:T && (7) I \rightarrow \cdot I,\text{i} \\ & && (4)\ S \rightarrow \text{v} I \cdot :T && (8) I \rightarrow I\cdot ,\text{i} \\ & (0)\ S' \rightarrow \cdot S && (5)\ S \rightarrow \text{v} I :\cdot T && (9)\ I \rightarrow I, \cdot \text{i} && (11)\ I \rightarrow \cdot \text{i} && (13)\ T \rightarrow \cdot \text{r} \\ & (1)\ S' \rightarrow S\cdot && (6)\ S \rightarrow \text{v} I:T\cdot && (10)\ I \rightarrow I,\text{i} \cdot && (12)\ I \rightarrow \text{i} \cdot && (14)\ T \rightarrow \text{r} \cdot\end{align*} $$

其中 $S'$ 对应的第一个项目（即项目 (0)）称为初始项目，对应的最后一个项目（即项目 (1)）称为接收项目。圆点位于产生式末尾的项目称为规约项目。

同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目。例如，$A \rightarrow \alpha \cdot X \beta$ 的后继项目是 $A \rightarrow \alpha X \cdot \beta$。

每一个项目对应句柄识别的一个状态，如果将全部状态用来构造自动机会过于庞大，因此我们希望寻找出等价项目。考虑初始项目 (0)，它表示正在等待文法开始符号 $S$，又由产生式 ② 可以看出，$S$ 由 $\text{v}$、$I$、$:$ 和 $T$ 构成，那么等待 $S$ 就是在等待 $S$ 右部的第一个符号 $\text{v}$，即项目 (2)。因此我们说，项目 (0) 和项目 (2) 等价。

项目 (3) 在等待 $I$，又由产生式 ④ 可以看出，$I$ 由 $I$、$,$ 和 $\text{i}$ 构成，那么等待 $I$ 就是在等待句柄 $I,\text{i}$ 的 $I$ 或者句柄 $\text{i}$ 的 $\text{i}$，即项目 (7) 和项目 (11)。因此我们说，项目 (3)、(7) 和 (11) 等价。

项目 (5) 在等待 $T$，又由产生式 ⑤ 可以看出，$T$ 由 $\text{r}$ 构成，那么等待 $T$ 就是在等待 $\text{r}$，即项目 (13)。因此我们说，项目 (5) 和项目 (13) 等价。

综上所述，当一个项目中的圆点后是一个非终结符时，它就存在等价项目。

可以把所有的等价项目组成一个项目集 $I$，称为项目集闭包。每个项目集闭包对应自动机的一个状态。

构造 LR(0) 自动机

给定文法和每条产生式对应的项目：

$$ \begin{align*} & ①\ S' \rightarrow S && ②\ S \rightarrow BB && ③\ B \rightarrow aB && ④\ B \rightarrow b \\ \\ & && (2)\ S \rightarrow \cdot BB && (5) B \rightarrow \cdot aB \\ & (0)\ S' \rightarrow \cdot S && (3)\ S \rightarrow B \cdot B && (6)\ B \rightarrow a \cdot B && (8)\ B \rightarrow \cdot b \\ & (1)\ S' \rightarrow S\cdot && (4)\ S \rightarrow BB \cdot && (7)\ B \rightarrow aB \cdot && (9)\ B \rightarrow b \cdot\end{align*} $$

易得：项目 (0)、(2)、(5) 和 (8) 等价；项目 (3)、(5)、(8) 等价；项目 (6)、(5)、(8) 等价。

首先构造其初始状态 $I_{0}$。先放入初始项目 (0)，然后将其等价项目 (2)、(5) 和 (8) 放入。

根据 $I_{0}$ 中的第一个项目（即项目 (0)）可以看出，当归约出文法开始符号 $S$ 后，识别的过程就可以向前进展一步，进入状态 $I_{1}$。其中包含了项目 (1)，即项目 (0) 的后继项目。此时圆点后不再有非终结符，那么这个项目独自形成一个项目集闭包。

根据 $I_{0}$ 中的第二个项目（即项目 (2)）可以看出，当归约出 $B$ 之后，识别的过程就可以向前进展一步，进入状态 $I_{2}$，自然将项目 (2) 的后继项目 (3) 先加入。又因为项目 (3) 的圆点后是非终结符 $B$，因此需要其等价项目 (5) 和 (8) 放入。

根据 $I_{0}$ 的第三个项目（即项目 (5)）可以看出，当识别出 $a$ 之后，识别的过程就可以向前进展一步，进入状态 $I_{3}$，自然将项目 (5) 的后继项目 (6) 先加入。又因为项目 (6) 的圆点后时非终结符 $B$，因此需要将其等价项目 (5) 和 (8) 放入。

根据 $I_{0}$ 的第四个项目（即项目 (8)）可以看出，当识别出 $b$ 之后，识别的过程就可以向前进展一步，进入状态 $I_{4}$，自然将项目 (8) 的后继项目 (9) 先加入。此时圆点后不再有非终结符，那么这个项目独自形成一个项目集闭包。

考虑 $I_{1}$，它处于归约状态，不再有后继状态。

考虑 $I_{2}$，由于圆点后还有符号，因此还存在后继状态。根据 $I_{2}$ 的第一个项目（即项目 (3)）可以看出，当识别出 $B$ 之后可以继续进行一步，进入 $I_{5}$，同时先将其后继状态 (4) 加入。此时圆点处于末尾，因此 $I_{5}$ 为归约状态，不再有等价项目。

根据 $I_{2}$ 的第二个项目（即项目 (5)）可以看出，当识别出 $a$ 之后可以继续进行一步，进入 $I_{3}$。

根据 $I_{2}$ 的第三个项目（即项目 (8)）可以看出，当识别出 $b$ 之后可以继续进行一步，进入 $I_{4}$。

考虑 $I_{3}$，由于圆点后还有符号，因此还存在后继状态。根据 $I_{3}$ 的第一个项目（即项目 (6)）可以看出，当识别出 $B$ 之后可以继续进行一步，进入 $I_{6}$，同时先将其后继状态 (7) 加入。此时圆点处于末尾，因此 $I_{6}$ 为归约状态，不再有等价项目。

根据 $I_{3}$ 的第二个项目（即项目 (5)）可以看出，当识别出 $a$ 之后可以继续进行一步，进入 $I_{3}$.

根据 $I_{3}$ 的第三个项目（即项目 (8)）可以看出，当识别出 $b$ 之后可以继续进行一步，进入 $I_{4}$。

考虑 $I_{5}$ 和 $I_{6}$，均为归约状态，因此都不存在后继状态。至此该文法的 LR(0) 自动机构造完毕，如下所示。

然后我们根据自动机构造分析表。

状态 0 遇到非终结符 $S$ 进入状态 1，遇到非终结符 $B$ 进入状态 2；遇到终结符 $b$ 时将 $b$ 移入然后进入状态 4，遇到终结符 $a$ 时将 $a$ 移入然后进入状态 3。

状态 1 为接受状态，因此只有当遇到结束符 $\#$ 时才成功接受。

状态 2 遇到非终结符 $B$ 进入状态 5；遇到终结符 $a$ 时将 $a$ 移入然后进入状态 3，遇到终结符 $b$ 时将 $b$ 移入然后进入状态 4。

状态 4 为归约状态，对应产生式 ③，因此无论遇到什么输入符号，均采取规约动作，即用产生式 ③ 进行归约。因此状态 4 的 ACTION 表中的每一项都是 $\text{r}3$。

状态 3 遇到终结符 $b$ 时将 $b$ 移入并进入状态 4，遇到终结符 $a$ 时将 $a$ 移入并进入状态 3；遇到非终结符 $B$ 进入状态 6。

状态 5 为归约状态，对应产生式 ①，因此无论遇到什么输入符号，均采取规约动作，即用产生式 ① 进行归约。因此状态 4 的 ACTION 表中的每一项都是 $\text{r}1$。

状态 6 为归约状态，对应产生式 ②，因此无论遇到什么输入符号，均采取规约动作，即用产生式 ② 进行归约。因此状态 4 的 ACTION 表中的每一项都是 $\text{r}2$。

至此 LR(0) 分析表构造完成，如下所示。

状态	ACTION			GOTO
状态	$a$	$b$	$\$$	$S$	$B$
0	s3	s4		1	2
1			acc
2	s3	s4			5
3	s3	s4			6
4	r3	r3	r3
5	r1	r1	r1
6	r2	r2	r2

从上述过程可以看出，要实现 LR(0) 自动机，需要计算两个函数 $CLOSURE()$ 和 $GOTO()$。

$CLOSURE(I)$ 就是计算给定项目集 $I$ 的闭包，数学定义为 $CLOSURE(I) = I \cup \{B \rightarrow \cdot \gamma\ |\ A \rightarrow \alpha \cdot B\beta \in CLOSURE(I),B \rightarrow \gamma \in P\}$。计算过程用伪代码表示如下。

SetOfItems CLOSURE(I) {
    J = I; // 初始时令 J 等于输入的项目集 I
    repeat
        for (J 中的每个项 A -> α·Bβ)
            for (G 的每个产生式 B -> γ)
                if (项 B -> ·γ 不在 J 中)
                    将 B -> ·γ 加入 J;
    until 某一轮中没有新的项被加入 J 中;
    return J;
}

$GOTO(I,X)$ 返回项目集 $I$ 对应于文法符号 $X$ 的后继项目集闭包，数学定义为 $GOTO(I,X) = CLOSURE(\{A \rightarrow \alpha X \cdot \beta\ |\ A \rightarrow \alpha \cdot X \beta \in I\})$。计算过程用伪代码表示如下。

SetOfItems GOTO(I, X) {
    将 J 初始化为空集;
    for (I 中的每个项 A -> α·Xβ)
        将项 A -> α·Xβ 加入集合 J 中;
    return CLOSURE(J);
}

构造 LR(0) 自动机的状态集

定义规范 LR(0) 项集族 $C = \{I_{0}\} \cup \{I\ |\ \exists J \in C,X \in N \cup T,I = GOTO(J,X)\}$。

void items(G') {
    C = {CLOSURE({[S' -> ·S]})}; // 初始状态，C 中只有初始项目的项目集闭包
    repeat
        for (C 中的每个项集 I)
            for (每个文法符号 X)
                if (GOTO(I,X) 非空且不在 C 中)
                    将 GOTO(I,X) 加入 C;
    until 在某一轮中没有新的项集加入 C;
}

构造 $G'$ 的规范 LR(0) 项集族 $C = \{I_{0}, I_{1}, …, I_{n}\}$
令 $I_{i}$ 对应状态 $i$。状态 $i$ 的语法分析动作按照下面的方法决定
- $\text{if}\ A \rightarrow \alpha \cdot \text{a} \beta \in I_{i}\ \text{and}\ GOTO(I_{i},\text{a}) = I_{j}\ \text{then}\ ACTION[i,\text{a}] = \text{s}j$
- $\text{if}\ A \rightarrow \alpha \cdot B \beta \in I_{i}\ \text{and}\ GOTO(I_{i},B) = I_{j}\ \text{then}\ GOTO[i,B] = j$
- $\text{if}\ A \rightarrow \alpha \in I_{i} \ \text{and}\ A \neq S'\ \text{then}\ \text{for}\ \forall \text{a} \in T \cup {\#}\ \text{do}\ ACTION[i,\text{a}] = \text{r}j$（$j$ 十产生式 $A \rightarrow \alpha$ 的编号）
- $\text{if}\ S' \rightarrow S \cdot \in I_{i}\ \text{then}\ ACTION[i,\#] = \text{acc}$
没有定义的所有条目都设置为 error

LR(0) 自动机的形式化定义

文法

$$ G = (N,T,P,S) $$

LR(0) 自动机

$$ \begin{align*} & M = (C,N \cup T, GOTO, I_{0}, F) \\ 其中，& C = \{I_{0}\} \cup \{I\ |\ \exists J \in C,X \in N \cup T,I = GOTO(J,X)\} \\ & I_{0} = CLOSURE(\{S' \rightarrow \cdot S\}) \\ & F = \{CLOSURE(\{S' \rightarrow S \cdot\})\}\end{align*} $$

LR(0) 分析过程中的冲突

对于状态 $I_{2}$ 和 $I_{9}$，第一个动作是归约动作，第二个动作是移入动作，在分析过程中就会产生冲突，即“移入/归约冲突”。这一点从分析表中也能看出。

状态	ACTION						GOTO
状态	$\text{id}$	$+$	$*$	$($	$)$	$\$$	$E$	$T$	$F$
0	s5			s4			1	2	3
1		s6				acc
2	r2	r2	r2/s7	r2	r2	r2
3	r4	r4	r4	r4	r4	r4
4	s5			s4			8	2	3
5	r6	r6	r6	r6	r6	r6
6	s5			s4				9	3
7	s5			s4					10
8		s6			s11
9	r1	r1	r1/s7	r1	r1	r1
10	r3	r3	r3	r3	r3	r3
11	r5	r5	r5	r5	r5	r5

类似地，还存在“归约/归约冲突”。例如下面的文法：

$$ \begin{align*} & (0)\ S' \rightarrow T \\ & (1)\ T \rightarrow aBd \\ & (2)\ T \rightarrow \epsilon \\ & (3)\ B \rightarrow Tb \\ & (4)\ B \rightarrow \epsilon\end{align*} $$

和对应的 LR(0) 状态机：

在状态 $I_{2}$ 中，$B \rightarrow \cdot$ 和 $T \rightarrow \cdot$ 分别表示将栈顶的空串归约为 $B$ 和 $T$。

如果 LR(0) 分析表中不存在语法分析动作冲突，那么给定的文法就称为 LR(0) 文法。不是所有的 CFG 都能用 LR(0) 分析法进行分析，即，CFG 并不总是 LR(0) 文法。

SLR 分析法

上面提到了构造 LR(0) 分析表时可能会遇到移入/归约冲突。归根结底，依旧是如何识别句柄的问题。如果栈顶符号 $T$ 是一个句柄，则应采取归约动作。由于 LR(0) 向前查看了 0 个符号，无法提供更多信息来帮助决定。

$X$	$FOLLOW(X)$
$E$	$), +, \$$
$T$	$), +, \$, *$
$F$	$), +, \$, *$

事实上，对于 $I_{2}$，当下一个输入符号为 $*$ 时，若将栈顶的 $T$ 归约为 $E$，由 $FOLLOW(E)$ 可知，$* \notin FOLLOW(E)$，即使归约出 $E$，其后也不可能跟着 $*$。因此这里不应进行归约动作，$T$ 不是一个句柄。

SLR 分析法的基本思想

已知项目集 $I$ 中有 $m$ 个移进项目 $A_{1} \rightarrow \alpha_{1} \cdot \text{a}{1} \beta{1},\ A_{2} \rightarrow \alpha_{2} \cdot \text{a}{2} \beta{2},\ …,\ A_{m} \rightarrow \alpha_{m} \cdot \text{a}{m} \beta{m}$ 和 $n$ 个归约项目 $B_{1} \rightarrow \gamma_{1} \cdot,\ B_{2} \rightarrow \gamma_{2} \cdot,\ …,\ B_{n} \rightarrow \gamma_{n} \cdot$，若集合 $\{\text{a}{1},\ \text{a}{2},\ …,\ \text{a}{m}\}$ 和 $\{FOLLOW(B{1}),\ FOLLOW(B_{2}),\ …,\ FOLLOW(B_{n})\}$ 两两不相交，则项目集 $I$ 中的冲突可以按照以下原则解决：

设 $\text{a}$ 是下一个输入符号，

若 $\text{a} \in \{\text{a}{1},\ \text{a}{2},\ …,\ \text{a}_{m}\}$，则移进 $\text{a}$
若 $\text{a}{1} \in FOLLOW(B{i})$，则用产生式 $B_{i} \rightarrow \gamma_{i}$ 归约
其他情况报错

基于此，得到上述文法的 SLR 分析表：

状态	ACTION						GOTO
状态	$\text{id}$	$+$	$*$	$($	$)$	$\$$	$E$	$T$	$F$
0	s5			s4			1	2	3
1		s6				acc
2		r2	s7		r2	r2
3		r4	r4		r4	r4
4	s5			s4			8	2	3
5		r6	r6		r6	r6
6	s5			s4				9	3
7	s5			s4					10
8		s6			s11
9		r1	s7		r1	r1
10		r3	r3		r3	r3
11		r5	r5		r5	r5

再例如下面的存在归约/归约冲突的文法。$FOLLOW(B)$ 中只有 $d$，因此当 $I_{2}$ 遇到 $d$ 时采用产生式 (4) 进行归约。而 $FOLLOW(T)$ 中存在 $\#$ 和 $b$ 两个符号，因此当 $I_{2}$ 遇到 $\#$ 和 $b$ 时采用产生式 (2) 进行归约。

SLR 分析表的构造算法

构造 $G'$ 的规范 LR(0) 项集族 $C = {I_{0}, I_{1}, …, I_{n}}$
令 $I_{i}$ 对应状态 $i$。状态 $i$ 的语法分析动作按照下面的方法决定
- $\text{if}\ A \rightarrow \alpha \cdot \text{a} \beta \in I_{i}\ \text{and}\ GOTO(I_{i},\text{a}) = I_{j}\ \text{then}\ ACTION[i,\text{a}] = \text{s}j$
- $\text{if}\ A \rightarrow \alpha \cdot B \beta \in I_{i}\ \text{and}\ GOTO(I_{i},B) = I_{j}\ \text{then}\ GOTO[i,B] = j$
- $\text{if}\ A \rightarrow \alpha \in I_{i} \ \text{and}\ A \neq S'\ \text{then}\ \text{for}\ \forall \text{a} \in FOLLOW(A) \ \text{do}\ ACTION[i,\text{a}] = \text{r}j$（$j$ 十产生式 $A \rightarrow \alpha$ 的编号）
- $\text{if}\ S' \rightarrow S \cdot \in I_{i}\ \text{then}\ ACTION[i,\#] = \text{acc}$
没有定义的所有条目都设置为 error

文法

形式化定义

产生式的简写

文法的分类

CFG

推导

句型

句子

分析树

短语

句柄

从正则表达式到 CFG

自顶向下分析概述

最左推导和最右推导

最左推导

最右推导

唯一性

自顶向下分析的通用形式：递归下降过程

预测分析

左递归

消除直接左递归

消除间接左递归

提取左公因子

LL(1) 文法

$S$-文法

预测分析法的工作过程

$S$-文法的定义（简单的确定性文法）

非终结符的后继符号集

计算方法

非终结符的串首终结符集合

计算方法

单个文法符号 $\alpha$ 的 $FIRST$ 集

串 $X_{1} X_{2} … X_{n}$ 的 $FIRST$ 集

产生式的可选集

$q$-文法

计算方法

构造预测分析表

LL(1) 文法的定义

预测分析法

递归的预测分析法

非递归的预测分析法

下推自动机的工作流程（预测分析表的使用）

递归和非递归的预测分析法的对比

预测分析法的实现步骤

自底向上的语法分析

移入-归约分析

关键问题

LR 分析法

基本原理

LR 分析表的结构和使用

LR(0) 分析法

文法中的项目

构造 LR(0) 自动机

构造 LR(0) 自动机的状态集

LR(0) 自动机的形式化定义

LR(0) 分析过程中的冲突

SLR 分析法

SLR 分析法的基本思想

SLR 分析表的构造算法

发送评论 编辑评论

发送评论编辑评论