浅谈编译原理——语法分析篇

1. 语法分析简介#

语法分析程序的地位：

词法分析程序接受字符流（即源程序），输出记号流，作为语法分析程序的输入（按照自左向右的顺序扫描输入的记号序列），语法分析程序会根据语法规则，判断输入的记号流是否合法，并输出分析树。

分析方法包括：自顶向下分析和自底向上分析。

2. 自顶向下分析方法#

2.1 递归下降分析#

核心思想是：

对每一个非终结符构造一个分析函数
用前看符号指导产生式规则的选择

由于上下文无关文法（CFG）中所有的产生式左边只有一个非终结符，所以我们在调用产生式规则的函数后，就分为两种情况：

遇到终结符，则直接把这个终结符和句子中对应位置的 token 进行比较，判断是否符合即可；符合就继续，不符合就返回（回溯）；
遇到非终结符，则调用这个非终结符对应的函数（可能会递归的调用，所以叫递归下降文法）；

以一个简单的文法为例，分析 aab 是否为该文法的句子：

1
S –> AB
2
A –> aA | ε
3
B –> b | bB

从起始状态 $S$ 开始，调用 $S$ 的函数，得到非终结符 $A,B$ ；
调用 $A$ 的函数，得到 $a,A$ ，由于 $a$ 为终结符，则取句子中的 token $a$ 进行比较，符合，继续；
继续递归调用 $A$ 的函数，得到 $a,A$ ，取句子中的 token $b$ 进行比较，不符合，回溯；
调用 $A$ 的另一个函数，得到 $\varepsilon$ ，符合，继续；
调用 $B$ 的函数，由于前面都是终结符 $b$ ，但产生式 1 已经到达结尾，所以选择第二个产生式并调用，得到 $b,B$ ，继续递归调用 $B$ 的函数，后略；

显然，这种方法不好：

如果语法存在左递归（形如 $A\Rightarrow^+ A\beta,A\in N$ 的推导），则会导致递归调用无限进行下去，使得分析过程陷入死循环；
通过回溯不断试探，效率低；

2.2 递归调用预测分析#

从递归下降分析方法的问题来看，优化的点就在于解决回溯，实现一种确定的、不带回溯的方法 —— 递归调用预测分析。

如何克服回溯？能够根据所面临的输入符号准确地指派一个候选式去执行任务。因此通常需要对文法进行改造，以满足自顶向下的分析方法的要求，具体包括：

消除文法的二义性
消除左递归
提取左公共因子
非终结符号 $A$ $A$ 的所有候选式的开头终结符号集两两互不相交；
- 即 $FIRST(\alpha_i)\cup FIRST(\alpha_j)=\emptyset (i\ne j)$

注：一般情况下，消除左递归和提取左公共因子后的文法无二义性。

Note

$FIRST(\alpha_i)$ : 由 $\alpha_i$ 开始推导，可以推导出的所有开头终结符号的集合（得出的句子开头的所有可能终结符的集合）。

求解 First 集合的方法：对于产生式 $A\rightarrow \beta_1\beta_2\cdots\beta_n$ ，根据开头的 $\beta_1$ 分情况讨论：

$\beta_1$ 是终结符，则 $\beta_1\in FIRST(A)$ ；
$\beta_1$ 是非终结符，则 $FIRST(\beta_1)\subseteq FIRST(A)$

注：针对考虑 $\varepsilon$ 产生式的 FIRST 集合，还需要处理：

如果 $A\rightarrow\varepsilon$ 也是产生式，则 $\varepsilon\in FIRST(A)$ ；
如果 $A\rightarrow\beta_1\cdots\beta_{i-1}\beta_i\cdots\beta_n$ ，其中 $FIRST(\beta_1)- FIRST(\beta_{i-1})$ 均含有 $\varepsilon$ ，则将 $FIRST(\beta_i)\subseteq FIRST(A)$ ；
同理如果 $FIRST(\beta_1)-FIRST(\beta_n)$ 均含有 $\varepsilon$ ，则 $\varepsilon\in FIRST(A)$ ；

这里的额外处理事实上是有一个专门的术语：NULLABLE 集合，即所有可直接或间接推导出空串的集合：

NULLABLE 集合的构造方法：对于非终结符 $X$ ，若满足 $X\Rightarrow^*\varepsilon$ ，则 $X\in NULLABLE$ 。

上述对 $\varepsilon$ 产生式的处理可以简化为：如果 $A\rightarrow XY$ 且 $X\in NULLABLE$ ，则 $FIRST(A)=FIRST(X)\cup FIRST(Y)$ ；

显然，这个过程是一个当任何集合有变化就要检查其他集合的动态更新过程。

对于 FIRST 集合的理解？FIRST 集合是后续用来构造分析表的，这里构建一个个人的理解视角，给定输入的记号流 $S = abc$ ：

假如推导的第一步是 $S\rightarrow ABC$ ，而 FIRST 集合的作用就是用于判断该推导能否满足文法要求，判断方式就是输入的字符 $a$ 是否在 $FIRST(A)$ 中，那么这一步推导是可以接受的，推导变为 $S\rightarrow aBC$ ，之后同理。

并且，由于前面对于文法的要求，非终结符号 $A$ 的所有候选式的开头终结符号集两两互不相交，所以有且只有这种选择，避免了回溯。

预测分析程序的转换图构造方法#

1. 消除左递归

这里主要以消除直接左递归为主，实际题目中很少出现间接左递归。

消除直接左递归：假如有 $A_i\rightarrow A_i\alpha\mid \beta$ ，则引入一个新的非终结符 $A^\prime_i$ ，并添加产生式：

\begin{aligned} A_i&\rightarrow \beta A^\prime_i\\ A^\prime_i&\rightarrow \alpha A^\prime_i\mid\varepsilon \end{aligned}

消除间接左递归：在消除 $A_i$ 后面的 $A_j$ 的直接左递归之前，发现有 $A_j\rightarrow A_i\gamma$ ，则用所有已经在新文法产生式中的 $A_i\rightarrow \delta$ 替换 $A_i$ ，即将产生式 $A_j\rightarrow A_i\gamma$ 替换为：

A_j\rightarrow \delta\gamma

直至 $\delta$ 最前面为终结符或大于等于 $A_j$ 的非终结符。

2. 提取左公因子

如果有产生式形如： $A\rightarrow\alpha\beta_1\mid\alpha\beta_2$ ，则提取左公因子 $\alpha$ ，将产生式替换为：

\begin{aligned} A&\rightarrow\alpha A^\prime\\ A^\prime&\rightarrow\beta_1\mid\beta_2 \end{aligned}

3. 绘制转换图

对于每一个非终结符号 $A$ ，创建一个初态和终态，对于每个产生式 $A\rightarrow X_1X_2\cdots X_n$ 构造一条创建一条从初态到终态的路径，有向边依次为 $X_i,i=1,2,\cdots,n$ 。

4. 化简状态转换图

总之就是反复代入化简。

5. 预测分析程序的实现

以下图为例：

1
void procE(void) {
2
  procT();
3
  if (char == '+') {
4
    forward pointer;
5
    procE();
6
  }
7
}

简单来说：

对于 $\varepsilon$ 的有向边一般不做任何处理；
遇到终结符则移动记号流的指针指向后一个待读如的字符；
遇到非终结符则调用它的对应函数；

2.3 非递归预测分析/LL(1) 分析算法#

分析过程#

上面的方法中，虽然不存在回溯和死循环，但函数的调用还是存在嵌套的，所以引入非递归预测分析方法，它通过分析表和分析栈联合控制，消除递归。

按照网上的说法，似乎基本鲜有关于递归调用预测分析的介绍，而是直接介绍 LL(1) 分析算法，对应我们教材上的非递归预测分析。

按照个人理解，分析表是用来解决回溯的，而符号栈则是用来解决函数的递归调用的。

输入：符号串 $\omega$ （词法分析输出的记号流）；文法的预测分析表 $M$ （手动构造，方法见下/通过语法分析器自动生成）；

初始化：

将符号串 $\omega$ 放入输入缓冲区，注意后面要添加一个 $；
将 $ 放入符号栈，再将文法的起始符号 $S$ 入栈，此时栈顶元素 $X=S$ ；
pointer 指向输入缓冲区的第一个符号，代表当前输入符号 $a$ ；

执行分析：

根据符号栈栈顶元素 $X$ 和输入符号 $a$ 执行如下循环过程：

若 $X=a=$ $，则分析成功，停止；
若 $X=a\ne$ $，说明当前栈顶的终结符命中输入，匹配成功，将 $X$ 弹出，同时 pointer 前移指向下一个输入符号；
若 $X\in V_T,X\ne a$ ，说明发现错误；
若 $X\in V_N$ $X \in V_{N}$ ，则访问分析表 $M[X,a]$ $M [X, a]$ ，即找到对应的需要被调用的产生式，根据产生式分情况执行：
1. 若 $M[X,a]=X\rightarrow Y_1Y_2\cdots Y_n$ ，则将 $X$ 弹栈，然后按照 $Y_n,\cdots,Y_2,Y_1$ 的顺序压入栈（ $Y_n$ 显然是被最后调用的，所以先入栈，放在底下），
2. 若 $M[X,a]=X\rightarrow \varepsilon$ ，则将 $X$ 弹栈；
3. 若 $M[X,a]=X\rightarrow error$ ，即分析表中没有任何内容，出错；

输出：每次命中分析表对应的产生式时，输出产生式，最终结果为依次调用的产生式序列，相当于一个最左推导的过程。

预测分析表的构造#

1. 改写文法：消除左递归 + 消除左公因子；（见前面）

2. 构造 FIRST 集合：使用前面提到的方法；

3. 构造 FOLLOW 集合：

Note

FOLLOW 集合的定义：假定 $S$ 是文法 $G$ 的开始符号，对于 $G$ 的任何非终结符号 $A$ ，集合 $FOLLOW(A)$ 是在所有句型中，紧跟 $A$ 之后出现的终结符号或 $ 组成的集合，即所有可以合法的站在此非终结符后面的终结符（可以包括结束符 $ ，但不包括 $\varepsilon$ ）的集合。

FOLLOW(A)=\{a\mid S\Rightarrow^* \cdots Aa\cdots,a\in V_T\}

特别地，若有 $S\Rightarrow^*\cdots A$ ，则规定 $ $\in FOLLOW(A)$ 。

FOLLOW 集合的构造方法：

对于起始符号 $S$ ，$ $\in FOLLOW(S)$ ；
若有 $A\rightarrow\alpha B\beta$ ，则 $FIRST(\beta)\subseteq FOLLOW(B)$ ，注意除去 $\varepsilon$ ；
若有 $A\rightarrow\alpha B$ 或 $A\rightarrow\alpha B\beta,\beta\Rightarrow^*\varepsilon$ ，则 $FOLLOW(A)\subseteq FOLLOW(B)$ ；

FOLLOW 集合的意义？确定某个非终结符可能出现在产生式右侧的上下文环境。举个例子，当栈顶为 $X$ ，读入的符号为 $a$ ，但 $a$ 不在任何 FIRST 集合中，如果有 $X \rightarrow\varepsilon$ ，那么 $a$ 必须是 $X$ 的后继字符才能保证最终句子是一个符合语法的句子，即此时调用 FOLLOW 集合。

4. 预测分析表的构造：对于每条产生式 $A\rightarrow \alpha$ ：

对所有终结符 $a\in FIRST(\alpha)$ ， $\{A\rightarrow\alpha\}\subseteq M[A,a]$ ；
对 $\varepsilon\in FIRST(\alpha)$ ，则对所有 $b\in FOLLOW(A)$ ， $\{A\rightarrow\alpha\}\subseteq M[A,b]$ ；

最终留空处均为 error。

LL(1) 文法#

可以用上述方法解析的文法称之为 LL(1) 文法，即从左 (L) 向右读入一个程序，最左 (L) 推导，采用一个 (1) 前看符号。要求对应的预测分析表不含多重表项，也就是要求：对所有产生式 $A\rightarrow u_1\mid u_2\mid \cdots\mid u_n$ ，有：

\begin{aligned} &FIRST(u_1)\cap \cdots \cap FIRST(u_n)=\emptyset,\text{即 FIRST 集合互不相交}\\ u_i\Rightarrow^*\varepsilon,&FIRST(u_i)\cap FOLLOW(A)=\emptyset,i=1,2,\cdots,n,\text{即 FOLLOW(A) 与所有 FIRST 集合互不相交} \end{aligned}

3. 自底向上分析方法#

LL(1) 分析法的优点是不需要回溯，构造方法较简单，且分析速度非常快，每读到第一个符号就可以预测出整个产生式来。缺点是对语法的限制太强，能满足此要求的语法相当少，而将一个不满足此要求的语法改写到满足要求也相当不容易。因此， LL(1) 分析法目前已经应用的比较少了。基于此，我们引入现在被广泛使用的自底向上分析方法。

对输入串的扫描：自左向右；
分析树的构造：自底向上；
分析过程：
- 从输入符号串开始分析
- 查找当前句型的“可归约串”
- 使用规则，把它归约成相应的非终结符号
- 重复

以下列文法为例，输入串为 id + id * id：

1
E → E + T | T
2
T → T * F | F
3
F → (E) | id

一种自底向上的过程如下：

步骤	当前句型	可归约串	使用的产生式	归约结果
1	id + id * id	id	F → id	F
2	F + id * id	F	T → F	T
3	T + id * id	id	F → id	F
4	T + F * id	F	T → F	T
5	T + T * id	id	F → id	F
6	T + T * F	T * F	T → T * F	T
7	T + T	T	E → T	E
8	E + T	E + T	E → E + T	E
9	E	-	-	结束

从上述例子可见，分析过程的关键在于如何找出“可归约串”。

3.1 “移进-归约”分析方法#

“移进-归约”分析过程#

把输入符号逐个地移进符号栈中；（即“移进”，把下一个输入符号移入栈顶）
当栈顶的符号串形成某个产生式的一个候选式（右部）时，在一定条件下，把该符号串替换（归约）为该产生式的左部符号；（即“归约”）
重复步骤 2 直到栈顶符号串不再是“可归约串”为止；
重复步骤 1 ～ 3 直到归约出文法起始符号 $S$ ；
接收：宣布分析成功，停止分析；
错误处理：调用错误处理程序进行诊断和恢复；

简单来说，“移进”相当于“往栈里装符号，等待形成句法单位”，“归约”相当于“识别出一个语法成分，用它的非终结符替代”。通过不断循环“读符号 + 识别结构”，最终构建整个语法树。

规范归约#

假定 $\alpha$ 为文法 $G$ 的一个句子，若右句型序列 $\alpha_n,\alpha_{n-1},\cdots,\alpha_1,\alpha_0$ 满足：

$\alpha_n=\alpha$ ， $\alpha_0=S$ ；
$\forall 0<i\le n$ ， $\alpha_{i-1}$ 是经过把 $\alpha_i$ 的句柄替换为相应产生式的左部符号而得到的；

规范归约相当于最右推导的逆过程，每次只归约当前句型中的句柄（handle），也就是恰好能还原出上一步最右推导的右部的那一部分。

3.2 LR 分析方法#

LR 分析是移进-归约分析的一种规范化、自动化的实现方法。即从左 (L) 向右扫描输入符号串，为输入符号串构造一个最右 (R) 推导的逆过程，采用 k 个前看符号。

LR 分析法的基本思想是在归约的过程中，一方面记住移入和归约的整个符号串（历史信息），另一方面通过产生式推测未来可能碰到的输入符号（预测信息）。在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看 k 个输入符号，就能确定栈顶的符号串是否构成相对于某一产生式的句柄，从而确定当前所应采取的分析动作（是移进还是按某一产生式进行归约等）。

LR 分析程序的模型及工作过程#

栈包括：（两者同步变化）

状态栈 S；
符号栈 X；

分析表包括：

动作表 action：用于指导分析器在遇到不同输入符号时应采取的动作；
- $action[S_m,a_i]$ $a c t i o n [S_{m}, a_{i}]$ ： $S_m$ $S_{m}$ 遇到输入符号 $a_i$ $a_{i}$ （包括终结符和非终结符）时的动作；
  - shift $S$ （移进）：将当前输入符号 $a_i$ 和状态 $S=goto[S_m,a_i]$ 压入栈；
  - reduce by $A\rightarrow\beta$ （归约）：若 $\left|\beta\right|=r$ ，则从栈中弹出 $r$ 项，栈顶变为 $S_{m-r}$ ，然后把 $A$ 和状态 $S=goto[S_{m-r},A]$ 压入栈；
  - accept：宣布分析成功，停止分析；
  - error：调用出错处理程序，进行错误恢复；
状态转移表 goto：用于指导分析器在采取归约动作后应转移到的新状态。
- $goto[S_m,X]$ ： $S_m$ 经过 $X$ 的后继状态；

工作过程如下，初始二元式为 $(S_0,a_1a_2\cdots a_n\$ ) $，分析过程中的每步的结果均可以表示为$ (S_0S_1\cdots S_m,a_ia_{i+1}\cdots a_n$)$：

若 $action[S_m,a_i]=shift\space S,S=goto[S_m,a_i]$ ，则二元式变为 $(S_0S_1\cdots S_mS,a_{i+1}\cdots a_n\$ )$；
若 $action[S_m,a_i]=reduce\space by\space A\rightarrow\beta$ ，则二元式变为 $(S_0S_1\cdots S_{m-r}S,a_ia_{i+1}\cdots a_n\$ )$；
若 $action[S_m,a_i]=accept$ ，则分析成功；
若 $action[S_m,a_i]=error$ ，则调用错误处理程序；

Note

活前缀：一个规范句型的一个前缀，如果不含句柄之后的任何符号，则称它为该句型的一个活前缀。

同样，分析方法的核心在于构造分析表，不同 LR 算法构造方法不同，下文将具体展开介绍。

LR(0) 算法#

关键概念#

Note

形态/LR(0) 项目：一个产生式的解析程度，用一个产生式加一个位置黑点 $\cdot$ 来表示，黑点左边表示已解析的部分，右部表示待解析的部分，一般也称为 LR(0) 项目。

产生式 $A\rightarrow XYZ$ 有 4 种 LR(0) 项目：

$A\rightarrow\cdot XYZ$ ：起始形态，
$A\rightarrow X\cdot YZ$ ；
$A\rightarrow XY\cdot Z$ ；
$A\rightarrow XYZ\cdot$ $A \to X Y Z \cdot$ ：已完成形态/可折叠/形态，即归约项目；
- 文法起始符号 $S$ 的归约项目又称之为接收项目；

注：产生式 $A\rightarrow\varepsilon$ 只有一个归约项目 $A\rightarrow\cdot$ 。

前三种根据圆点 $\cdot$ 后的第一个符号为终结符/非终结符又可以分为：

移进项目：圆点后第一个符号为终结符号的 LR(0) 项目；
待约项目：圆点后第一个符号为非终结符号的 LR(0) 项目；

Note

拓广文法：是对原始文法的一种扩展，通过在原始文法中添加一个新的开始符号 $S^\prime$ 和产生式 $S^\prime\rightarrow S$ ，使得文法开始符号仅出现在一个产生式的左边，从而使分析器只有一个接受状态。（接收项目唯一）

教材上还讲了有效项目的定义，但没什么用，直接略去。

Note

闭包 $closure(I)$ 的定义和构造：设 $I$ 是文法 $G$ 的一个 LR(0) 项目集合，则 $closure(I)$ 是从 $I$ 出发，并使用以下方法构造的项目集合：

$I$ 中的每一个 LR(0) 项目均属于 $closure(I)$ ；
若 $A\rightarrow\alpha\cdot B\beta\in closure(I)$ ，且有产生式 $B\rightarrow \eta$ ，若 $B\rightarrow\cdot\eta\notin closure(I)$ ，则将 $B\rightarrow\cdot\eta$ 加入 $closure(I)$ ；
重复步骤 2 直至 $closure(I)$ 不再增大；

注： $B\rightarrow\cdot\eta$ 称之为 $A\rightarrow\alpha\cdot B\beta$ 的延伸形态，延伸的方向是单向的。

上述过程就是把集合 $I$ 里所有形态的所有延伸形态全部添加进这个集合。

Note

状态：设 $I$ 是文法 $G$ 的一个 LR(0) 项目集合，状态即为 $closure(I)$ ，即状态是进行过闭合操作的 LR(0) 项目（形态）集合。

Note

转移函数 go：若 $I$ 是文法 $G$ 的一个 LR(0) 项目集， $X$ 是一个文法符号，定义

go[I,X]=closure(J)

其中， $J=\{A\rightarrow\alpha X\cdot\beta\mid\text{当 }A\rightarrow\alpha\cdot X\beta\in I\text{ 时}\}$ 。

$A\rightarrow\alpha X\cdot\beta$ 为 $A\rightarrow\alpha\cdot X\beta$ 遇到符号 $X$ 时的后继形态，

构造文法 G 的 LR(0) 项目集规范族#

输入为文法 $G$ ，输出为 $G$ 的 $LR(0)$ 项目集规范族 $C$ ：

构造文法 $G$ 的拓广文法 $G^\prime$ ；
$C=\{closure(\{S^\prime\rightarrow\cdot S\})\}$ ；
对于 $C$ 中的每一个项目集 $I$ 和每一个文法符号 $X$ ，如果 $go[I,X]$ 不为空且不在 $C$ 中，则将 $go[I,X]$ 加入 $C$ ；
重复步骤 2 直至 $C$ 不再更新；

简单来说，就是从初始项目集 $I_0 = closure(\{S^\prime\rightarrow\cdot S\})$ 开始（事实上 $I_0$ 就是起始状态），按以上方法，不断的生成新的项目集（状态），直到不再出现新的项目集（状态）。

如上图所示，这个状态转移图和有限状态自动机的运行图很相似，一般称之为识别文法 $G^\prime$ 所有活前缀的 DFA。不过解析过程并不能按照 DFA 运行，上下文无关文法需要下推自动机来进行识别。

LR(0) 项目集中的冲突及解决#

Note

可折叠形态：某状态/项目集中，只有一个项目，且该项目为归约项目。

语法分析中，如果遇到不可折叠状态，就会发生冲突，即：

一个项目集 $I$ $I$ 中，既包含 $X\rightarrow\alpha\cdot b\beta$ $X \to α \cdot b β$ ，又存在 $A\rightarrow\alpha\cdot$ $A \to α \cdot$ ，即既包含不可折叠形态，又包含可折叠形态（归约项目）；
- 这会造成“移进-归约”冲突，也就是无法判断出应该 shift，还是应该 reduce；
一个项目集中，既包含 $A\rightarrow\alpha\cdot$ $A \to α \cdot$ ，又包含 $B\rightarrow\beta\cdot$ $B \to β \cdot$ ，即包含多条可折叠形态（归约项目）；
- 这会造成“归约-归约”冲突，也就是无法判断出应该采用哪条产生式来归约；

解决方法见下，即 SLR(1) 算法。

判断某文法是否属于 LR(0) 文法#

一个文法是LR(0)文法，每个状态/项目集中：

要么所有 LR(0) 项目都是“移进-待约项目”；（即不能同时含有可折叠和不可折叠形态）
要么只含有唯一的归约项目（可折叠形态）；
起始符号不出现在任何产生式右部（一般通过拓广文法已经解决了）；

SLR(1) 算法#

LR(0) 冲突的解决#

由于 LR(0) 不向前看下一个符号，大大增加了冲突的可能，因此这种冲突通过向前看若干个输入符号或许能够解决。

还是考虑上面的冲突场景，即 $I=\{X\rightarrow\alpha\cdot b\beta,A\rightarrow\alpha\cdot,B\rightarrow\beta\cdot\}$ 。现在，如果下一个要读入的符号为 $x$ ，假设此时允许使用 $B\rightarrow\beta\cdot$ 进行归约，那么进行归约后，符号 $x$ 紧随 $B$ 之后，即 $X\in FOLLOW(B)$ 。

所以，当

$FOLLOW(A)\cap FOLLOW(B)=\emptyset$ ；
终结符号 $b\notin FOLLOW(A),b\notin FOLLOW(B)$ ；

则上述冲突全部消失，决策如下：

当下一个读入符号 $x=b$ 时，用 $X\rightarrow\alpha\cdot b\beta$ 移进 $b$ ，即将 $b$ 入栈；
当下一个读入符号 $x\in FOLLOW(A)$ 时，用 $A\rightarrow\alpha$ 归约；
当下一个读入符号 $x\in FOLLOW(B)$ 时，用 $B\rightarrow\beta$ 归约；

上述思路即为 SLR(1) 分析表构造的形式化描述。SLR(Simple LR) 算法的核心思想是利用“FOLLOW集”来解决冲突。

SLR(1) 分析表的构造算法#

输入：拓广文法 $G^\prime$ ；输出： $G^\prime$ 的 SLR 分析表

构造 $G^\prime$ 的 LR(0) 项目集规范族 $C=\{I_0,I_1,\cdots,I_n\}$ ；
对于状态 $I_i$ $I_{i}$ 的分析动作如下：
1. 若 $A\rightarrow \alpha\cdot a\beta\in I_i$ ，且 $go(I_i,a)=I_j$ ，则 $action[i,a]=S_j(shift\space I_j)$ ；
2. 若 $A\rightarrow \alpha\cdot\in I_i$ ，则对 $\forall a\in FOLLOW(A)$ ，则 $action[i,a]=R\space A\rightarrow\alpha$ ；
3. 若 $S^\prime\rightarrow S\cdot\in I_i$ ，则 $action[i,\$ ]=accept$，表示分析成功；
若 $go(I_i,A)=I_j$ ， $A$ 为非终结符，则 $goto[i,A]=j$ ；
剩余空白项均置为 error；
分析程序的初态为包含 $S^\prime\rightarrow\cdot S$ 的有效项目集/状态；

判断某文法是否属于 SLR(1) 文法#

法一（一般用于证明是）：若文法 G 的 SLR(1) 分析表中没有多重定义项，则该文法是 SLR(1) 文法。

法二（一般用于证明不是）：不一定要全部计算出 SLR 分析表，可以挑选状态中存在“移进-归约”冲突的，计算一下应用 FOLLOW 集合后是否能解决冲突，如果仍存在冲突（即对应的动作表位置存在多重表项），则该文法不是 SLR(1) 文法。

定理：每一个 SLR(1) 文法都是无二义的文法，但并非无二义的文法都是 SLR(1) 文法。

LR(1) 算法#

SLR(1) 算法向前查看下一个符号，并利用 FOLLOW 集进行识别，但这样仍然不准确（不能确保一定能归约），仍会导致冲突。

而 LR(1) 算法更加强大，利用了下一个读入的符号的信息（lookahead，展望符），或者也被称为预测先行（预测下一个应该出现的输入符号）。

关键概念#

Note

LR(1) 项目： $[A\rightarrow\alpha\cdot\beta,a]$ ， $a$ 即为展望符，表示在当前处理到 $A\rightarrow\alpha\cdot\beta$ 时，下一个读入的终结符必须是 $a$ 才能进行正确归约。

由于项目引入了展望符，后续的一些计算也发生了一些改变，但构造过程基本一致。

Note

后继形态：形态/项目 $C=[A\rightarrow X\cdot YZ,a]$ 遇到符号 $Y$ 转移到后继形态 $C^\prime=[A\rightarrow XY\cdot Z,a]$ 。（这里的区别只是 LR(1) 项目的变化）

Note

转移函数 go：若 $I$ 是文法 $G$ 的一个 LR(1) 项目集， $X$ 是一个文法符号，定义

go[I,X]=closure(J)

其中， $J=\{[A\rightarrow\alpha X\cdot\beta,a]\mid\text{当 }[A\rightarrow\alpha\cdot X\beta,a]\in I\text{ 时}\}$ 。

Note

延伸形态：若一个形态的黑点后是非终结符，形如 $C=[A\rightarrow\alpha\cdot B\beta,a]$ ，且有 $B\rightarrow\eta,b\in FIRST(\beta a)$ ，则 $C^\prime=[B\rightarrow\cdot\eta,b]$ 是 $C$ 的延伸形态。

简单记忆的话，延伸形态的产生式左部是黑点后的非终结符 $B$ ，展望符是非终结符 $B$ 之后的符号串 $\beta$ + 原展望符 $a$ 的 FIRST 集合。

为什么呢？形态 $C=[A\rightarrow\alpha\cdot B\beta,a]$ 表示，当前符号栈为 $\alpha$ ，期待遇到符号 $B$ ，再遇到符号串 $\beta$ ，最后遇到 $a$ 才能进行归约。我们现在准备“识别”非终结符 $B$ ，接下来要读入能推导出 $B$ 的符号串，即对 $B$ 的每个产生式建立相应的“延伸形态”。

当我们识别完 B 后，会继续识别 $\beta$ ，所以延伸形态的展望符号应该是 $FIRST(\beta)$ ，不过由于 $FIRST(\beta)$ 可能包含 $\varepsilon$ ，那么再后面就是 $a$ 了，所以展望符号即为 $B$ 的后继终结符集合，即 $FIRST(\beta a)$ 。

同理闭包的构造方法也进行微调即可：

Note

闭包的定义及构造方式：

$I$ 中的每一个 LR(1) 项目均属于 $closure(I)$ ；
若 $[A\rightarrow\alpha\cdot B\beta,a]$ ，且有产生式 $B\rightarrow \eta$ ，且 $b\in FIRST(\beta a)$ ，若 $[B\rightarrow\cdot\eta,b]\notin closure(I)$ ，则将 $[B\rightarrow\cdot\eta,b]$ 加入 $closure(I)$ ；
重复步骤 2 直至 $closure(I)$ 不再增大；

构造文法 G 的 LR(1) 项目集规范族#

输入为文法 $G$ ，输出为 $G$ 的 $LR(1)$ 项目集规范族 $C$ ：

构造文法 $G$ 的拓广文法 $G^\prime$ ；
$C=\{closure(\{[S^\prime\rightarrow\cdot S,\$ ]})}$；
对于 $C$ 中的每一个项目集 $I$ 和每一个文法符号 $X$ ，如果 $go[I,X]$ 不为空且不在 $C$ 中，则将 $go[I,X]$ 加入 $C$ ；
重复步骤 2 直至 $C$ 不再更新；

这里和 LR(0) 项目集规范族的构造过程是完全一致的（除了项目的表示形式不同）。同理，识别文法所有活前缀的 DFA 的构造方法也是一致的。

LR(1) 分析表的构造算法#

输入：拓广文法 $G^\prime$ ；输出： $G^\prime$ 的 SLR 分析表

构造 $G^\prime$ 的 LR(1) 项目集规范族 $C=\{I_0,I_1,\cdots,I_n\}$ ；
对于状态 $I_i$ $I_{i}$ 的分析动作如下：
1. 若 $[A\rightarrow \alpha\cdot a\beta,b]\in I_i$ ，且 $go(I_i,a)=I_j$ ，则 $action[i,a]=S_j(shift\space I_j)$ ；
2. 若 $[A\rightarrow \alpha\cdot,a]\in I_i$ ，且 $A\ne S^\prime$ ，则 $action[i,a]=R\space A\rightarrow\alpha$ ；
3. 若 $[S^\prime\rightarrow S\cdot,\$ ]\in I_i $，则$ action[i,$]=accept$，表示分析成功；
若 $go(I_i,A)=I_j$ ， $A$ 为非终结符，则 $goto[i,A]=j$ ；
剩余空白项均置为 error；
分析程序的初态为包含 $[S^\prime\rightarrow\cdot S,\$ ]$ 的有效项目集/状态；

相较于 SLR(1) 分析表，LR(1) 分析表的状态数量和每个状态中包含的项目数量都是及其恐怖的。不过状态数的增加带来的是分析能力的提升。

LR(1) 文法#

Warning

不要求。

相比于 LR(0) 文法，LR(1) 文法允许：

一个状态/项目集中同时出现可折叠状态和不可折叠状态；
- 只要可折叠形态的展望符不和不可折叠形态中黑点后面的符号冲突，不然遇到该输入，又分不清该移进还是归约了；
也可以含有多条可折叠状态（归约状态）；
- 这些可折叠状态的展望符也不能冲突；

即要求：

起始符号 S 不能位于任何产生式的右边；(一般通过拓广文法来解决)
要求每个状态中：
1. 不能同时含有 $[A\rightarrow\alpha\cdot a\beta,b]$ $[A \to α \cdot a β, b]$ 和 $[B\rightarrow\eta\cdot,a]$ $[B \to η \cdot, a]$ ；
  - 否则会引起“移进-归约”冲突；
2. 不能同时含有 $[A\rightarrow\alpha\cdot,a]$ $[A \to α \cdot, a]$ 和 $[B\rightarrow\beta\cdot,a]$ $[B \to β \cdot, a]$ ；
  - 否则会引起“归约-归约”冲突；

解决冲突的一种方法是利用符号的优先级，不过此处略。

LALR(1) 算法#

前面已经提到，LR(1) 构造算法复杂且状态、形态数量多。而 LALR(1) 算法对此进行了一定的优化，其基本思想是将一些相似的状态进行 merge。一种 merge 方法是将 LR(1) 项目集规范族中的所有同心状态集合并，合并时，对应项目的搜索符（展望符）也会合并。原先各自接收的有向边，都改为由合并后的项目集接收；原先各自发出的有向边，都改为由合并后的项目集发出。

关键概念#

Note

同心集：如果两个 LR(1) 项目集去掉搜索符号（展望符）之后是相同的，则称这两个项目集具有相同的心（core），即这两个项目集是同心集。

Note

项目集的核（kernal）：除去初态项目集外，一个项目集的核（kernel）是由该项目集中那些圆点不在最左边的项目组成。

其中，初态项目集的核只有 $[S^\prime\rightarrow\cdot S,\$ ]$。

LALR(1) 的项目集规范族#

先得到 LR(1) 的项目集规范族；
合并 LR(1) 项目集规范族中的同心集；（减少分析表状态数）
用核代替项目集；（减少项目集的存储空间）
转移函数 go 同样进行合并修改；

LALR(1) 项目集中的冲突#

合并可能导致“归约-归约”冲突，但不会引入新的“移进-归约”冲突，因为：

如果合并后产生“移进-归约”冲突，例如 $[A\rightarrow\alpha\cdot a\beta,b]$ 和 $[B\rightarrow\eta\cdot,a]$ 被合并到一个项目集中，这说明原来 $[B\rightarrow\eta\cdot,a]$ 所在的项目集中还含有形如 $[A\rightarrow\alpha\cdot a\beta,c]$ 的项目，而这两者原来存在于一个项目集，即原来已经存在“移进-归约”冲突。

LALR(1) 分析表的构造算法#

输入：拓广文法 $G^\prime$ ；输出： $G^\prime$ 的 SLR 分析表

构造 $G^\prime$ 的 LR(1) 项目集规范族 $C=\{I_0,I_1,\cdots,I_n\}$ ；
合并同心集。得到 $C^\prime=\{J_0,J_1,\cdots,J_m\}$ $C^{'} = {J_{0}, J_{1}, \dots, J_{m}}$ ；
- 分析程序的初态为包含 $[S^\prime\rightarrow\cdot S,\$ ] $的$ J_k$；
构造 action 子表，对于状态 $J_i$ $J_{i}$ 的分析动作如下：
1. 若 $[A\rightarrow \alpha\cdot a\beta,b]\in J_i$ ，且 $go(J_i,a)=J_j$ ，则 $action[i,a]=S_j(shift\space J_j)$ ；
2. 若 $[A\rightarrow \alpha\cdot,a]\in J_i$ ，则 $action[i,a]=R\space A\rightarrow\alpha$ ；
3. 若 $[S^\prime\rightarrow S\cdot,\$ ]\in J_i $，则$ action[i,$]=accept$，表示分析成功；
构造 goto 子表：设合并后 $J_k=\{I_{i1},I_{i2},\cdots,I_{it}\}$ $J_{k} = {I_{i 1}, I_{i 2}, \dots, I_{i t}}$ ，原来这些 $I_i$ $I_{i}$ 是同心集，那么显然 $go(I_{i1},X),go(I_{i2},X),\cdots,go(I_{it},X)$ $g o (I_{i 1}, X), g o (I_{i 2}, X), \dots, g o (I_{i t}, X)$ 也是同心集，把后继状态组成的同心集合并后的集合记为 $J_i$ $J_{i}$ ，那么 $go(J_k,X)=J_i$ $g o (J_{k}, X) = J_{i}$ 。
- 若 $go(J_k,A)=I_i$ ， $A$ 为非终结符，则 $goto[k,A]=i$ ；
- 其实就是前面用文字描述的，原先各自接收的有向边，都改为由合并后的项目集接收；原先各自发出的有向边，都改为由合并后的项目集发出。
剩余空白项均置为 error；

基本与 LR(1) 分析表的构造算法一致，只需对同心集和对应的后继状态组成的同心集进行合并。

LALR(1) 文法#

先判断是否属于 LR(1) 文法。（构造 LR(1) 分析表，采用前面的方法判断是否有冲突）
如果不存在冲突，则是 LR(1) 文法，继续判断：
1. 如果不存在同心集，即不用合并，那么显然也还是 LALR(1) 文法；
2. 如果存在，则先进行合并，再检查合并后是否有冲突（即判断是否有“归约-归约”冲突）；
  1. 无冲突，是 LALR(1) 文法；
  2. 有冲突，不是 LALR(1) 文法；

LALR(1) vs. LR(1)#

形式上与 LR(1) 相同；
大小上与 SLR(1)/LR(0) 相当；
分析能力介于 SLR(1) 与 LR(1) 之间；

3.3 LR 分析的错误处理与恢复#

略。

4. 总结#

“二义性文法”表示那些无论如何都无法消除二义性的文法，它们不可能被任何确定性分析方法识别。我们在上面介绍的均为确定性分析方法，即左侧这些。

左侧的分析方法又可以分为左侧（自顶向下）和右侧（自底向上），其中越外层表示的能处理的文法范围越大，分析能力越强，越内层针对文法的限制越多。

TMD，很久没碰上这么一坨大的了💩。

1. 语法分析简介#

2. 自顶向下分析方法#

2.1 递归下降分析#

2.2 递归调用预测分析#

预测分析程序的转换图构造方法#

2.3 非递归预测分析/LL(1) 分析算法#

分析过程#

预测分析表的构造#

LL(1) 文法#

3. 自底向上分析方法#

3.1 “移进-归约”分析方法#

“移进-归约”分析过程#

规范归约#

3.2 LR 分析方法#

LR 分析程序的模型及工作过程#

LR(0) 算法#

关键概念#

构造文法 G 的 LR(0) 项目集规范族#

LR(0) 项目集中的冲突及解决#

判断某文法是否属于 LR(0) 文法#

SLR(1) 算法#

LR(0) 冲突的解决#

SLR(1) 分析表的构造算法#

判断某文法是否属于 SLR(1) 文法#

LR(1) 算法#

关键概念#

构造文法 G 的 LR(1) 项目集规范族#

LR(1) 分析表的构造算法#

LR(1) 文法#

LALR(1) 算法#

关键概念#

LALR(1) 的项目集规范族#

LALR(1) 项目集中的冲突#

LALR(1) 分析表的构造算法#

LALR(1) 文法#

LALR(1) vs. LR(1)#

3.3 LR 分析的错误处理与恢复#

4. 总结#

文章分享

评论区