九九归一。

自底向上的语法分析过程被称为归约

与自顶向下语法分析即推导类似，归约的关键在于如何降低“归约哪个子串”和“选择哪个产生式”带来的非确定性复杂度

短语

降低归约复杂度的第一步为选择可归约串，即短语：

若 $S\stackrel{*}{\Rightarrow}\alpha A\delta$ 且 $A\stackrel{+}{\Rightarrow}\beta$ ，则称 $\beta$ 是句型 $\alpha A\delta$ 相对于非终结符 $A$ 的短语

简单来说，短语就是一个句型中由一个非终结符推导出的子串

特别地，若 $A\Rightarrow\beta$ ，即 $\beta$ 为非终结符一步推导得到，则称之为直接短语

句柄

句柄是一类特殊的短语，其定义为：

对右句型 $\alpha Aw$ ，其中 $w$ 是终结符串，若 $A\Rightarrow\beta$ ，则称 $\beta$ 是 $\alpha\beta w$ 相对 $A$ 的句柄

注：这里要求句柄是满足条件中最左的直接短语，因为要求产生对应于最右推导的最左归约

事实上，句柄是最右推导过程中得到 $\alpha\beta w$ 的最后一步推导的产生式右端

句柄不一定唯一，因为对二义文法，最右推导可能不唯一

短语与分析树

直观地讲，短语是语法分析树中某个非终结符对应的一棵完整子树

而句柄则是以最右推导得到这棵语法分析树时最后一步被扩展出的子树

移进-归约(shift-reduce)分析技术

移进-归约分析器是一台具有一个下推栈的有限状态控制的分析引擎，分析引擎根据：

当前状态
下推栈
剩余输入单词序列

来确定以下动作之一：

Reduce：归约栈顶短语
Shift：从输入序列移进一个单词
Error：发现语法错误，进行错误处理、恢复
Accept：分析成功

LR分析

LR的含义：从左向右扫描输入单词序列，产生最右推导

LR分析表

包含两张表：ACTION表和GOTO表，例如：

1729939286999

其中ACTION表的表项ACTION[S,a]表示当栈顶状态为S，当前输入符号为a时做什么，共有以下几种可能：

sj，表示向栈内压入状态j，再移进一个单词
rj，表示按照第j条产生式进行归约，然后从栈顶弹出等于此产生式右端串长度数目的状态后，根据弹出后的栈顶状态和产生式左端查询GOTO表，转到GOTO表指示的状态
acc，表示接受当前串

加入符号栈的LR分析

可以发现：上述过程中归约过程每个符号对应一个栈中状态，因此可以引入符号栈，栈内存储二元组(状态, 符号)，则可以通过归约过程栈结构产生最右推导过程

几种获得LR表的分析方法

LR(0)
SLR(1)
LR(1)
LALR(1)

LR(0)分析

核心概念

增广文法：在原文法中加入 $S'\rightarrow S$ ，使得新的开始符号 $S'$ 不存在于任何产生式右部
活前缀：若 $S\stackrel{*}{\Rightarrow} \alpha\beta w$ $S \Rightarrow * α βw$ 且 $\beta$ $β$ 是句柄，则 $\alpha\beta$ $α β$ 的任何前缀 $\gamma$ $γ$ 都是文法的活前缀
- 即：此前缀可以完整“存活”在LR分析过程中的符号栈里而不被归约
- 右句型的活前缀不超过右句型的任何一个句柄

LR(0) FSM

LR(0) FSM的形状

每个上下文无关文法 $G=(V_N,V_T,P,S)$ 都对应一个LR(0) FSM，可以通过增广文法来构造，其实际上是一个字母表为 $V_N \cup V_T$ 的DFA

LR(0) FSM的状态是LR(0)项目组成的集合，一个LR(0)项目是在产生式右端某一位置插入圆点得到的东西，如对产生式 $A\rightarrow xyz$ ，以下都是项目：

$A\rightarrow .xyz$
$A\rightarrow x.yz$
$A\rightarrow xy.z$
$A\rightarrow xyz.$

圆点的作用是标志当前已经识别到的位置

LR(0)项目可以分为以下四类：

移进项目：圆点后是终结符
待约项目：圆点后是非终结符
归约项目：圆点在产生式结尾，且不是增广文法的增广产生式 $S'\rightarrow S$
接受项目：圆点在产生式结尾，且是增广产生式

LR(0) FSM的状态是一个LR(0)项目集 $I$ 的闭包 ${\rm Closure}(I)$ ，计算闭包所用的规则为：

若 $A\rightarrow \alpha .B\beta\ \in {\rm Closure}(I)$ ，且 $B\rightarrow \gamma\ \in P$ ，则 $B\rightarrow .\gamma\ \in {\rm Closure}(I)$

从增广文法构造LR(0) FSM

下面我们将介绍LR(0) FSM的构造方法：

LR(0) FSM的初态是 ${\rm Closure}(\{S'\rightarrow .S\})$
LR(0) FSM的转移函数定义为 $\delta(I,X)={\rm Closure}(J)$ $δ (I, X) = Closure (J)$ ，其中
- $X$ 为文法符号
- $J=\{A\rightarrow\alpha X.\beta\ |\ A\rightarrow\alpha.X\beta\ \in I\}$ ，即 $J$ 是 $I$ 中项目“对 $X$ 移进”组成的集合

遍历每个状态和每个符号，应用上述转移函数规则，直到状态集不再变大，即完成状态机构造

LR(0) FSM的语言

如果认为LR(0) FSM所有上述生成状态均为状态，则它可以看成某正规语言的DFA

可以证明：该DFA的语言是增广文法的活前缀组成的集合

LR(0) FSM状态与活前缀的关系为：

每个活前缀对应唯一的状态，即从初态经过此活前缀得到的状态
此状态内所有项目对此活前缀都是有效的，即存在某种最右推导，使得此活前缀的上一步推导使用的是此项目的产生式，且位于此项目的圆点的位置
针对这些活前缀的所有有效项目均隶属于此状态

从LR(0) FSM构造LR(0)分析表

给所有FSM状态编号，将编号作为LR(0)分析栈的状态，其中初态编为0号

考虑每个状态 $I_k$ 中的每个项目，按以下规则构造分析表：

对移进项目 $A\rightarrow \alpha.a\beta$ ，若 $\delta(I_k, a)=I_j$ ，则令ACTION[k, a]为sj
对归约项目 $A\rightarrow \alpha.$ ，则对任何 $a$ ，令ACTION[k, a]为rj，其中j为 $A\rightarrow \alpha$ 的产生式编号
对接受项目，令ACTION[k, #]为acc

对于每一条非终结符的转移边 $\delta(I_k, A)=I_j$ ，令GOTO(k, A)=j

LR(0)文法

若按上述算法构造的分析表，每一表项都没有多重定义，则称该文法是一个LR(0)文法，这等价于说：

任何状态不同时含有移进项目和归约项目
- 同时含有的情况会发生移进-归约冲突
任何状态不含有两个以上归约项目
- 同时含有的情况会导致产生式选择不确定，即归约-归约冲突

可以看出，ACTION表每一行不同时存在移进和归约，即只根据栈顶状态就可以判断需要移进还是归约；同时ACTION表需要根据当前符号进行判断时，当前符号一定已被移进或将要被移进，所以LR(0)分析不需要向前察看

SLR(1)分析

Simple LR(1)

核心思想：通过向前查看一个符号来解决移进-归约或归约-归约冲突

因此，虽然SLR(1)可以分析非LR(0)的文法，但也需要对文法进行一些要求：

要可以解决归约-归约冲突，则要求每个状态中所有归约项目的待归约非终结符的FOLLOW集互不相交
要可以解决移进-归约冲突，则要求每个状态中所有归约项目的待归约非终结符的FOLLOW集不包含移进项目的移进符号

SLR(1)分析表的构造只需要把LR(0)分析表构造中对归约项目的处理进行更改，改为只对FOLLOW(A)中的非终结符放置表项

注这引入了“向前察看一个单词”的要求

LR(1)分析

尽管SLR(1)比LR(0)强大，但它仍然存在一些理论上可以通过向前察看一个单词解决的冲突没有被解决

例子：

1729946703669

此时由于 $)\ \in {\rm Follow}(E)$ ，根据SLR(1)的算法无法解决冲突

但实际上，由于 $(E)$ 不是合法句型，若状态达到 $I_7$ 且下一个字符是)，归约是不可能的，否则将会出现不合法的句型 $(E)$

即：如果此 $F$ 作为 $E$ 的句柄存在（即需要归约），那么它的下一个字符一定不会是)

故上面例子的移进-归约冲突是可解决的

LR(1)项目

LR(1)项目比LR(0)项目增加了一个称为向前搜索符的终结符，即形如：

A\rightarrow \alpha.\beta,a

其中 $a\in V_T\cup\{\#\}$

在进行这个定义更改之后，我们需要对LR(0) FSM的构造过程进行重写

LR(1) FSM

首先是项目集闭包的求法

若 $A\rightarrow \alpha .B\beta,a\ \in {\rm Closure}(I)$ ，且 $B\rightarrow \gamma\ \in P$ ，则对每一个 $b \in {\rm First}(\beta a)$ ， $B\rightarrow .\gamma,b\ \in {\rm Closure}(I)$

即，这里不止要求向前搜索符是当前产生式左侧非终结符FOLLOW集中的元素（这说明在任何可能的句型中，存在一个句型，此非终结符的后面是此向前搜索符），还要求此向前搜索符必须能够在某个符合当前已有推导过程的句型中存在于此非终结符的后面

具体意思比较难以表述，总之就是，对SLR(1)使用FOLLOW集作为归约条件的做法进行了加强，对归约的使用有了更严格的约束

如此约束后，上面例子中的）将不再是 $I_7$ 第二条产生式的合法向前搜索符

下面我们将介绍LR(1) FSM的构造方法：

LR(1) FSM的初态是 ${\rm Closure}(\{S'\rightarrow .S, \#\})$
LR(1) FSM的转移函数定义为 $\delta(I,X)={\rm Closure}(J)$ $δ (I, X) = Closure (J)$ ，其中
- $X$ 为文法符号
- $J=\{A\rightarrow\alpha X.\beta,a\ |\ A\rightarrow\alpha.X\beta, a\ \in I\}$ ，即 $J$ 是 $I$ 中项目“对 $X$ 移进”组成的集合

LR(1)分析表

相比FSM构造，LR(1)分析表构造就简单得多了，它和SLR(1)分析表构造只有一点不同：将SLR(1)对归约项目的处理中使用FOLLOW集合的元素进行约束修改为使用向前搜索符进行约束

LR(k)分析

如果我们将向前搜索符改为长度为k的向前搜索符号串，则可以构造出LR(k)分析

然而，LR(k)分析的状态数会随着k的增大暴涨，故k>1的情况没有应用价值；且对于任何正整数k，LR(k)的语言类是相同的

LALR(1)分析

Look Ahead LR(1)

LR(1) FSM的状态数远多于LR(0) FSM，LALR(1)通过合并相似状态来简化LR(1) FSM，但代价是会丧失一定的分析能力

同芯状态合并

LR(1)项目中不包括向前搜索符的部分（即LR(0)项目）称为其芯(core)

如果两个LR(1) FSM状态的芯集合完全相同，则是同芯状态

合并同芯状态即将同芯状态的向前搜索符集合取并，得到新的状态

此过程不会产生新的移进-归约冲突
但会产生新的归约-归约冲突

LALR(1)分析构造

构造LALR(1)分析的蛮力算法为先构造LR(1)，再进行同芯合并

杂项

二义文法的LR分析

二义文法一定不是LR文法，但可以通过一些手段（如强制左结合、强制算符优先级顺序）来消除LR表中的冲突

LR分析的出错处理

可以在LR分析表中对错误项进行分类，以给出更有用的报错信息

LR(k)文法

LR(k)文法的条件：

任意合法的分析树对应的句柄，可以由句型中该句柄左边的符号串和右边k个终结符组成的串唯一确定

LR(k)文法的理论结论：

给定k>0，CFG是否为LR(k)文法是可判定的
给定CFG，是否存在k>0使CFG是LR(k)文法是不可判定的
LR(k)文法无二义
LR(k)文法的语言是DPDA的语言；DPDA的语言是LR(1)文法的语言（即：LR(k)文法不强于LR(1)文法；且其表达能力相当于DPDA）
两个LR(k)文法是否相等是可判定的
LL(k)文法都是LR(k)文法

1729948785151