编译原理——第4章(1)

Chapter 4 语法分析

4.1 语法分析程序的功能

语法分析程序的功能是以词法分析器生成的单词符号序列作为输入，根据语言的语法规则（描述程序语言语法结构的上下文无关文法），识别出各种语法成分（表达式、语句、程序段乃至整个语法等），并在分析过程中进行语法检查，检查所给单词符号序列是否是该语言的文法的一个句子。若是则以该句子的某种形式的语法树作为输出，若不是则表明有错误，并指出错误的性质和位置。

4.2 自上而下分析法

4.2.1 非确定的自上而下分析法的思想

自上而下分析法的基本思想：对于任何输入串$W$试图用一切可能的方法，从文法的开始符号出发，自上而下地为它建立一棵语法树。或者说为语法树寻找一个最左推导。

4.2.2 文法的左递归性和回溯的消除

文法左递归：如果文法中存在非终结符$A$有推导$A\stackrel{+}\Rightarrow A\alpha$，那么在自上而下进行分析的过程中对于非终结符$A$，其下就会构建一棵子树，子树中包含有以$A$为根结点的子树和$b$结点，而$A$下面的$A$还会分出一个以$A$为根的子树，这就形成了无限递归，这是不允许的。因此在自上而下分析法中对文法的基本要求是：不能存在左递归。

消除左递归的方法：

1. 引入新的非终结符，将含有左递归的规则改写为右递归

这种方法与上一章词法分析中提到的一个技巧异曲同工。

技巧：左/右线性正规文法对$ab^*$和$a^*b$的处理
对于左线性正规文法而言

• 处理$ab^*$：$A\rightarrow Ab|a$。
• 处理$a^*b$：必须使用两条语句：$A\rightarrow Bb,B\rightarrow Ba|\varepsilon$

对于右线性正规文法而言

• 处理$ab^*$：必须使用两条语句：$A\rightarrow aB,B\rightarrow bB|\varepsilon$
• 处理$a^*b$：$A\rightarrow aA|b$。

为了消除诸如$A\rightarrow Ab|a$这样的左递归，可以将其转化为：$A\rightarrow aB,B\rightarrow bB|\varepsilon$来解决。更一般的情况如下：
将$A\rightarrow A\alpha_1|A\alpha_2|...|A\alpha_m|\beta_1|\beta_2|...|\beta_n$改写为：
$A\rightarrow\beta_1A'|\beta_2A'|...|\beta_nA'$
$A'\rightarrow\alpha_1A'|\alpha_2A'|...|\alpha_mA'|\varepsilon$

2. 使用扩充BNF表示法改写含有直接左递归的规则

BNF表示法中：

• 可以使用$\{\alpha\}$表示符号串$\alpha$可以出现0次或多次（即$\alpha^*$）
• 可以使用$[\alpha]$表示符号串$\alpha$出现可有可无，表示可供选择的符号串
• 使用$(\alpha)$可以在规则中提取因子，类似于分配律，如$A\rightarrow ab|ac$可以写成$A\rightarrow a(b|c)$

如此进行表示就可以很方便地消除左递归。公式如下：
将$A\rightarrow A\alpha_1|A\alpha_2|...|A\alpha_m|\beta_1|\beta_2|...|\beta_n$改写为：
$A\rightarrow(\beta_1|\beta_2|...|\beta_n)\{\alpha_1|\alpha_2|...|\alpha_m\}$

回溯：当存在如$A\rightarrow \alpha_1|\alpha_2|...$这样的规则时，对于一次匹配需要对所有候选式进行试配，如果试配错误需要回溯到一开始配对的位置重新匹配。这样会增加程序执行的时间，且让程序编写更加繁琐。当同一个左部的规则的右部串有相同前缀或为$\varepsilon$时可能会产生回溯。如对于规则$S\rightarrow aAb, A\rightarrow de|e|\varepsilon$而言，输入串为$ab$时选择的是第3个候选式，输入串为$adeb$时选择的是第1个候选式，输入为$adb$时选择的是第2个候选式。这其中涉及对候选式的选择。

为避免分析时出现回溯，需要保证文法为LL(1)型文法。对于LL(1)型文法需要首先说明下面的定义才能给出定义：

$\operatorname{FIRST}$集

$\operatorname{FIRST}$集是针对任一符号串而言的。对于符号串$\alpha$，$\operatorname{FIRST}(\alpha)$定义为：

$$\operatorname{FIRST}(\alpha)=\{a|\alpha\stackrel{*}\Rightarrow a...\&a\in V_T\}$$

即一个符号串的$\operatorname{FIRST}$集中的元素全为终结符，且等于该符号串可以推导出的所有第一个符号为终结符的符号串的第一个终结符构成的集合。

$\operatorname{FOLLOW}$集

$\operatorname{FOLLOW}$集针对任一非终结符，对于非终结符$A$，$\operatorname{FOLLOW}(A)$定义为：

$$\operatorname{FOLLOW}(A)=\{a|S\stackrel{*}\Rightarrow ...Aa...\&a\in V_T\}$$

如果有$S\stackrel{*}\Rightarrow ...A$，则规定$ $\in\operatorname{FOLLOW}(A)$，这里的$表示输入终结符号。即一个非终结符的$\operatorname{FOLLOW}$集就是该文法表示语言的所有符号串中所有跟在$A$后面的终结符构成的集合。

$\operatorname{SELECT}$集

$\operatorname{SELECT}$集针对任一规则，对于规则$A\rightarrow\alpha$，$\operatorname{SELECT}(A\rightarrow\alpha)$定义为：

\begin{equation} \operatorname{SELECT}(A\rightarrow\alpha)=\left\{ \begin{array}{l} \operatorname{FIRST}(\alpha)\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:,\alpha\stackrel{*}\nRightarrow\varepsilon\\ \operatorname{FIRST}(\alpha)\backslash\{\varepsilon\}\cup\operatorname{FOLLOW}(A),\alpha\stackrel{*}\Rightarrow\varepsilon \end{array} \right. \end{equation}

$\operatorname{SELECT}$集的含义最难理解。当$\alpha$不可能推导出空串时，说明$A$一定能够推导出非空串，这时$\operatorname{SELECT}(A\rightarrow\alpha)$就等于由$A$推导出的所有第一个符号为终结符的符号串的第一个终结符。如果$\alpha$可能推导出空串，那么除了$\operatorname{FIRST}(\alpha)\backslash\{\varepsilon\}$外还有一个$\operatorname{FOLLOW}(A)$，这就是当$A$推导出空串时$A$后面推导出来的内容中紧跟在$A$后面的终结符。也就是$A$及其后面所有符号串能够推导出来的所有的第一个符号为终结符的符号串的第一个终结符所构成的集合，也即当发现规则$A\rightarrow \alpha$时，所有下一个可能的符号构成的集合。更进一步地理解：

如果一条规则右部可以推导出$\varepsilon$，那么右部要么是$\varepsilon$，要么是由若干非终结符构成，且这些终结符均可以推导出$\varepsilon$，绝不可能包含终结符。设$\alpha=A_1A_2...A_n$，根据上面的对于$\operatorname{SELECT}$集的含义的理解，当$A_1$推导出$\varepsilon$时，第一个终结符就可能出现在$A_2$推导出来的符号串中。当$A_1$和$A_2$都推导为$\varepsilon$时，第一个终结符就可能出现在$A_3$推导出来的符号串中……这些都包含在$\operatorname{FIRST}(\alpha)$集中。而当$A$推导为$\varepsilon$时，$\operatorname{SELECT}(A\rightarrow\alpha)$的值就不再由$A$推导而来，而是由$A$后面的符号串推导而来。

LL(1)型文法定义：

一个2型文法为LL(1)型文法当且仅当其中每一个非终结符$A$的任何两个不同规则$A\rightarrow \alpha|\beta$都满足$\operatorname{SELECT}(A\rightarrow\alpha)\cap\operatorname{SELECT}(A\rightarrow\beta)=\empty$，且两条规则右部不能同时推出$\varepsilon$。

这条规则能够保证在每一次将一个非终结符向下扩展语法树时，总是能够根据下一个符号准确判断出应该使用哪一个候选式，这样也就不会产生回溯。如果文法不是LL(1)型文法，那么一次扩展语法树读取后面一个符号时很可能不能唯一确定候选式。

实际上LL(1)文法中第一个L指的是left to right，即从左向右扫描输入串，第二个L指的是leftmost，即左递归。1指的是只需要向右看一个字符就知道应该如何进行规约。这个条件是相当严格的。

4.2.3 某些非LL(1)文法到LL(1)文法的转换

在前面已经给出了消除左递归的方法，现在只需要消除移进一个符号后选择候选式的歧义即可，这可以通过不断提取公共左因子实现。公式：
将$A\rightarrow\alpha\beta_1|\alpha\beta_2|...|\alpha\beta_n$替换为
$A\rightarrow \alpha A'$
$A'\rightarrow \beta_1|\beta_2|...|\beta_n$

需要注意的是，不是所有文法都能够转换为LL(1)文法。最简单的判断方式就是消除左递归和提取所有公共左因子之后再求每一条规则的$\operatorname{SELECT}$集。

4.2.4 递归下降分析法

递归下降分析法是一种确定的自上而下分析法，需要文法是LL(1)文法。基本思想是对文法中的每一个非终结符编写一个函数或子程序，每个函数的功能是识别由该非终结符所表示的语法成分。这些函数常常以递归的形式被调用，因此被称为递归下降分析法。

对于普通形式表示的文法，如果其中有规则$A\rightarrow bB$，则定义一个函数$A$和$B$，函数声明如下：

A(){
	if(sym == 'b'){
		B();
	}
	else
		error();
}
B(){
	...
}

即每一个函数处理好这个函数对应的非终结符的识别工作。

对于扩充的BNF形式表示的文法，需要对循环、条件等规则中的符号串进行另外的判断。具体的实例在本文最后详细说明。

4.2.5 预测分析法与预测分析表的构造

预测分析法又称为LL(1)分析法，是确定的自上而下的一种分析法，采用这种方法要求语义分析的文法是LL(1)文法。

一个预测分析器由一张预测分析表（LL(1)分析表）、一个先进后出分析栈和一个总控程序3部分组成。输入缓冲区中保存有待分析的输入符号串，以右界符$作为结束。分析栈中保存替换当前非终结符的某规则右部符号串，句子左界符$放入栈底。预测分析表是一个M[A,a]形式的矩阵，其中$A$为非终结符，$a$为终结符，M[A,a]表示当$A$面临输入符号$a$时当前推导应该采用的候选式。当元素内容为出错标志时则表明$A$不应该面临符号$a$。

构造预测分析表的方法：

• 求出所有非终结符的$\operatorname{FIRST}$集和$\operatorname{FOLLOW}$集
• 对于文法每一条规则$A\rightarrow\alpha$，如果$a\in\operatorname{FIRST}(\alpha)$，则$M[A,a]=A\rightarrow\alpha$
• 如果$\varepsilon\in\operatorname{FIRST}(\alpha)$，则对于任何$b\in\operatorname{FOLLOW}(\alpha)$，$M[A,b]=A\rightarrow\alpha$
• 将表中没有定义的元素全部标上error符号。

4.3 自下而上分析法的一般原理

所有的自下而上分析法都是按照“移进-规约”法的原理建立起来的语法分析方法。基本思想是用一个寄存文法符号的先进后出栈，将输入符号一个个按从左到右顺序扫描入栈，边移入边分析。当栈中符号串形成某条规则右部时就进行一次归约。将栈顶被归约的这一串符号称为可归约串。重复这一个过程直到分析完毕。如果栈中最终只剩下右界符则输入句子是一个正确的句子，否则报错。

4.4 算符优先分析法

4.4.1 方法概述

按照算数表达式的四则运算过程而设计的一种语法分析方法。这种方法首先需要规定运算符之间的优先关系和结合性质，然后借助这种关系比较相邻运算符的优先级来确定句型的可规约串并进行规约。

定义任意两个终结符号$a$和$b$之间的优先关系（共3种）

• $a\lessdot b$表示$a$的优先级低于$b$
• $a\eqcirc b$表示$a$的优先级等于$b$
• $a\gtrdot b$表示$a$的优先级高于$b$

注意这个优先关系可能并不具备交换律，其与出现的左右次序有关。即$a\lessdot b$不一定有$b\gtrdot a$。

使用算符优先分析法需要保证描述语言的文法为算符优先文法：若文法$G$中不存在形如$U\rightarrow ...VW...$的规则，其中$V$和$W$为非终结符，则称$G$为算符文法（OG文法）。也即任何一个右式都不存在两个非终结符相邻的情况。

两个终结符优先级的定义

• $a\eqcirc b$当且仅当$G$中含有形如$P\rightarrow ...ab...$或$P\rightarrow ...aQb...$的规则。
• $a\lessdot b$当且仅当$G$中含有形如$P\rightarrow ...aR...$的规则且$R\stackrel{+}\Rightarrow b...$或$R\stackrel{+}\Rightarrow Qb...$
• $a\gtrdot b$当且仅当$G$中含有形如$P\rightarrow ...Rb...$的规则且$R\stackrel{+}\Rightarrow ...a$或$R\stackrel{+}\Rightarrow ...aQ$

理解：联想在前面提到的对于四则运算语言进行定义的文法，其中加减是位于第一条规则，乘除位于第二条规则，而括号位于第三条规则，可见运算符优先级越低，其需要进行归约的次数就越多。如对于上面提到的$a\lessdot b$而言，$a$的归约次数比$b$少，因此$a$的优先级低。

如果对于任意两个终结符号对$(a,b)$在上述的3种关系中只有一种成立，则称该文法为OPG文法（算符优先文法）。如四则运算就不属于算符优先文法，因为加和减可能满足两种关系：加的优先级低于减、加的优先级高于减，这取决于加和减这两个符号哪一个在前面。

4.4.3 算符优先关系表的构造

首先需要定义下面两个概念：

FIRSTVT集和LASTVT集

两个集合均针对于非终结符而言：

$$\operatorname{FIRSTVT}(A)=\{b|A\stackrel{+}\Rightarrow b...||A\stackrel{+}\Rightarrow Bb...,b\in V_T,B\in V_N\}\\ \operatorname{LASTVT}(A)=\{a|A\stackrel{+}\Rightarrow ...a||A\stackrel{+}\Rightarrow ...aB,a\in V_T,B\in V_N\}$$

可以以字面意思来理解这两个集合的含义：$\operatorname{FIRSTVT}$集合指的就是一个非终结符可能推导出来的所有符号串中的第一个终结符构成的集合。而$\operatorname{LASTVT}$集合指的就是一个非终结符可能推导出来的所有符号串中的最后一个终结符构成的集合。

根据上面的两个集合的定义以及优先级运算符的定义来构造算符优先关系表：

• 找到所有形如$P\rightarrow ...ab...$或$P\rightarrow ...aQb...$的规则，然后为其赋值为相等运算优先级。
• 找到终结符在左边，非终结符在右边的符号对$aB$，有$a\lessdot\operatorname{FIRSTVT}(B)$。
• 找到终结符在右边，非终结符在左边的符号对$Ab$，有$\operatorname{LASTVT}(A)\gtrdot b$（不能写$b\gtrdot \operatorname{LASTVT}(A)$！！！）
• 定义$ $\eqcirc$ $以及$ $\lessdot\operatorname{FIRSTVT}(S)$、$\operatorname{LASTVT}(S)\gtrdot$ $，其中$S$为开始符号。

4.5 LR分析法

这是一类自下而上进行规范规约的语法分析方法。L指from left to right从左到右，而R指rightmost构造最右推导的逆过程。

LR分析法的关键在于如何确定分析栈顶符号串是否能够形成句柄。根据事先定义好的文法，可以通过输入的前面一部分来预测输入的后面一部分，并在读入后续输入时进行进一步的操作。

4.5.1 工作原理和流程

LR分析法需要一个分析栈和分析表。分析栈用于存放分析过程中的历史和展望信息，而分析表则规定了状态机的转换方式。分析表由分析动作表（ACTION）和转换表（GOTO）组成，均为二维数组。其中状态转换表规定了某个状态遇到文法符号X时应该转移到的下一个状态，分析动作表规定了某个状态遇到输入符号时应该执行的动作。需要注意的是这里的文法符号和输入符号的区别。文法符号表示的是所有符号，而输入符号只可能是终结符。

ACTION表可能会有4种动作执行：

• 移进：将最近一个即将输入的符号移入栈中，并转移到相应的步骤
• 规约：若栈中符号串形成句柄$\alpha$且有文法规则$A\rightarrow\alpha$，则需要从栈中代表$\alpha$的所有文法符号和状态全部移除，并将A移入栈中，同时进行状态转移。
• 接受：分析成功，此时分析栈中只应有文法开始符号和输入结束符号“$”。
• 报错：输入串中含有错误，遇到的不应该输入的符号。

下面所介绍到的4种LR分析法都是在计算机层面对上述步骤进行规范化和程序化处理。

4.5.2 LR(0)分析法

需要理解这里0的含义：它表示需要向前查看输入符号的数量，即在LR(0)分析法中不需要向前提前查看输入符号，后面的LR(1)分析法中需要向前看一个输入符号。

活前缀

活前缀指的是不含句柄右边任何符号的前缀，这是所有LR分析法中至关重要的一个概念。一般使用下面的形式进行表示：

• 如果一个活前缀含有一个句柄中的所有符号，此时该活前缀就是该语句的最长的活前缀，表示为$A\rightarrow\alpha\cdot$。这里的“·”可以理解为此时分析到了什么地方。如果已经识别出句柄的所有成分，那么必然有一条规则$A\rightarrow\alpha$中的右部符号串是该活前缀的后缀，此时该右部符号串应该全部入栈，故分析位置就在该右部符号串的后面，即在$\alpha$后面加上一个点。
• 如果一个活前缀含有一个句柄的部分符号，那么必然存在一条规则$A\rightarrow\alpha_1\alpha_2$，此时有$\alpha_1$已经全部入栈而$\alpha_2$还未入栈，因此表示为$A\rightarrow\alpha_1\cdot\alpha_2$。
• 如果一个活前缀不含有句柄的任何符号，那么此时期望从剩余的符号串中获取到规则$A\rightarrow\alpha$中右部所有符号，因此表示为$A\rightarrow\cdot\alpha$。
• 特别地，对于空规则$A\rightarrow\varepsilon$，其对应的带点的规则只有$A\rightarrow\cdot$。

LR(0)项目

这个名字起的很让人迷惑，可能是直译过来的，很别扭。它表示文法G右部标有点的规则称为G的一个LR(0)项目。注意：这个点只是用来表示规则中的符号串有多少已经被识别。

一个LR(0)项目指明了对文法规范句型活前缀的不同识别状态，文法G的全部LR(0)项目是构造识别文法所有规范句型活前缀的DFA的基础。

LR(0)项目分类

根据点的位置和点后面是终结符还是非终结符，可以将项目分为4类：

• 规约项目：即应该根据对应规则进行规约的项目，形如$A\rightarrow\alpha\cdot, \alpha\in(V_N\cup V_T)$，点在最右端，说明已经完全读取了一个规则的右部符号串，可以将其进行规约产生左部非终结符。
• 移进项目：即下一步应该继续移进符号的项目，形如$A\rightarrow\alpha\cdot a\beta; \alpha,\beta\in(V_N\cup V_T), a\in V_T$，说明已经识别了一个规则中的一部分，而且规则中的下一个符号是一个终结符，所以期待移进一个终结符进行继续匹配。
• 待约项目：即期待读入其他符号规约成B好进行A的规约，形如$A\rightarrow \alpha\cdot B\beta$，只有读取后面的符号并规约成B才有可能使A规约成功。
• 接收项目：整个符号串识别完成，形如$S'\rightarrow S$，其中$S'$为文法开始符号。

闭包函数CLOSURE

CLOSURE闭包函数是构造DFA的关键函数，需要理解。
首先需要拓广原文法，实际上就是添加一个新的开始符号$S'$。
闭包函数的定义如下：
设$I$为拓广文法$G'$的一个LR(0)项目集，定义和构造$I$的闭包$\operatorname{CLOSURE}(I)$如下：

1. $I$中的任何一个项目都属于$\operatorname{CLOSURE}(I)$
2. 若$A\rightarrow \alpha\cdot B\beta$属于$\operatorname{CLOSURE}(I)$，那么每一个形如$B\rightarrow \cdot r$的项目也属于$\operatorname{CLOSURE}(I)$
3. 重复第2步直到$\operatorname{CLOSURE}(I)$不再增加为止。

理解：与第3章DFA的闭包类似，$\operatorname{CLOSURE}(I)$实际上定义了一个在文法分析过程中的某一步或某几步不需要进行其他操作就可以到达的步骤。如对于文法$S'\rightarrow S; S\rightarrow A$，那么在初始状态，即没有任何符号移进时，表示的状态应该是$S'\rightarrow\cdot S$，但由于$S\rightarrow A$，因此这个状态就等价于$S\rightarrow \cdot A$，此时，“等待移进以期待规约$S$”就等价于“等待移进以期待规约$A$”。CLOSURE函数能够让我们求出规范句型活前缀的DFA的一个结点内都有哪些项目。

例：文法$G$如下，求$\operatorname{CLOSURE}(\{A\rightarrow a\cdot Ab\})$。
$0. S'\rightarrow S\\1. S\rightarrow A\\2.S\rightarrow B\\ 3.A\rightarrow aAb\\4.A\rightarrow c\\5.B\rightarrow aBb\\ 6.B\rightarrow d$
解析：根据规则1可得$(A\rightarrow a\cdot Ab) \in\operatorname{CLOSURE}(\{A\rightarrow a\cdot Ab\})$
根据规则2可得$(A\rightarrow\cdot c) \in\operatorname{CLOSURE}(\{A\rightarrow a\cdot Ab\})$
故$\operatorname{CLOSURE}(\{A\rightarrow a\cdot Ab\})=\{A\rightarrow a\cdot Ab, A\rightarrow\cdot c\}$

状态转移函数GO

这个函数定义了DFA中不同结点之间的状态转移关系，与CLOSURE函数进行结合使用就可以求出一个文法的状态转移DFA。
定义：
$\operatorname{GO}(I,X)=\operatorname{CLOSURE(J)}\\J=\{A\rightarrow aX\cdot \beta|A\rightarrow\alpha\cdot X\beta\in I\}$
这里的$X$是任意一个文法符号。

理解：这里实际上就是指移进了一个符号或成功规约了一个非终结符，这样点的位置就能够向后移动一位。根据CLOSURE函数和GO函数，我们可以构造出一个文法的LR(0)分析表。

LR(0)分析表构造

1. 将DFA中的每一个结点均赋给一个序号，分析表的行数等于结点的数量，代表有多少种不同的状态。
2. 若从状态$I_k$到状态$I_j$有转换函数$\operatorname{GO}(I_k, x)=I_j$（$x$为终结符），那么$\operatorname{ACTION}[k, x]=S_j$。这里的$S_j$就表示状态转换，$\operatorname{ACTION}[k, x]$表示行索引为$k$列索引为$x$的项，注意$\operatorname{ACTION}$表的行是状态编号，列是终结符，在表中查到之后就应该更换聚焦的行。
3. 若从状态$I_k$到状态$I_j$有转换函数$\operatorname{GO}(I_k, A)=I_j$（$A$为终结符），则在$\operatorname{GOTO}$表中行索引为$k$列索引为$A$的项设为$j$，表示成功规约了一个项目，规约之后应该转移到哪一个状态。
4. 若某状态中包含规约项目，找到该项目对应的文法编号$i$，并在该状态对应的$\operatorname{ACTION}$表的行的所有项都添加$r_i$，表示到达该状态后期待进行规约。注意：到达该状态后应立即进行规约，将文法右部符号串及其对应的状态号全部出栈，然后将左部非终结符入栈，看此时状态栈的顶端的状态编号，再查询$\operatorname{GOTO}$表顶端状态编号对应行，非终结符对应列的项跳转到对应状态，然后将该状态压栈。
5. 如果接收项目包含于某状态，则该状态对应行中列索引为终结标志“$”的值为“acc”，表示接受项目。

4.5.3 SLR(1)分析法

LR(0)分析法对文法的要求较为严格，分析过程中很容易出现移进-规约冲突和规约-规约冲突。产生冲突的项目集为：

$$I_k=\{X\rightarrow \delta\cdot bB,A\rightarrow\alpha\cdot,B\rightarrow r\cdot\}$$

其中第1/2和第1/3个项目构成移进-规约冲突，在不知道下一个符号的情况下，分析器不知道这里到底应该等待下一个符号移入还是直接规约产生A或B。第2/3个项目构成规约-规约冲突，在需要规约的时候分析器不知道到底应该规约成A还是B。

因此SLR(1)分析法通过FOLLOW集，等同于是向前看了一个符号，以尝试消除冲突。

如对于上面的项目集，求出FOLLOW(A)和FOLLOW(B)，在这两个集合无交集且均不包含下一个移进的符号b时，可以通过下列判断消除冲突：

• 若下个符号$a=b$，则移进，参考第1个项目。
• 若下个符号$a\in\operatorname{FOLLOW(A)}$，则按照第2个项目规约。
• 若下个符号$a\in\operatorname{FOLLOW(B)}$，则按照第3个项目规约。
• 此外报错。

4.5.4 LR(1)分析法

上面的SLR(0)分析法在当FOLLOW(A)和FOLLOW(B)不满足条件时，一样无法分析。如有项目集$\{X\rightarrow aB\cdot b, Y\rightarrow aB\cdot bC\}$，如果仅使用第一个项目进行规约很可能会产生无效规约情况，导致后面无法匹配。因此引入LR(1)分析法。

LR(1)项目为二元组$[A\rightarrow \alpha\cdot\beta,a]$，其中a为终结符，称为搜索符。当$\beta\ne\varepsilon$时搜索符无意义，否则明确指出当$[A\rightarrow \alpha\cdot,a]$为栈顶的LR(1)项目时，仅在输入符号为a时才以此项目进行规约。

LR(1)的CLOSURE和GO函数

求项目集I的CLOSURE函数步骤：

1. $I$中的任何一个项目都属于$\operatorname{CLOSURE}(I)$
2. 若$[A\rightarrow \alpha\cdot B\beta, a]$属于$\operatorname{CLOSURE}(I)$，那么每一个形如$[B\rightarrow \cdot r, b]$的项目也属于$\operatorname{CLOSURE}(I)$，其中$b\in\operatorname{FIRST}(\beta a)$
3. 重复第2步直到$\operatorname{CLOSURE}(I)$不再增加为止。

求GO函数：
$\operatorname{GO}(I,X)=\operatorname{CLOSURE(J)}\\J=\{[A\rightarrow aX\cdot \beta, a]|[A\rightarrow\alpha\cdot X\beta,a]\in I\}$

4.5.5 LALR(1)分析法

LALR(1)分析法相比LR(1)分析法只修改了一个内容：合并。

同心LR(1)项目集

两个LR(1)项目集除搜索符不同外其他部分相同，则称两个项目集同心。

LALR(1)将所有同心的LR(1)项目集进行合并，减少了DFA的状态数。合并后，搜索符也进行合并，以’/'分隔。

不存在冲突的以上述方式生成的项目集组为基础的分析方法称为LALR(1)分析法。