讲稿第7章LR分析.doc

第7章 LR分析（9学时，10分钟）
复习：移进——归约。
接下来我们介绍一种自左而右、自下而上的语法分析技术，它可用于大多数CFG的语法分析，称为LR分析法：L表示从左至右扫描输入串，R表示构造一个最右推导的逆过程。
LR分析法显然也是自下而上的“移进－归约”，但它比算符优先和其他的“移进－归约”法更加广泛，效率也不比它们差；比一般不带回溯的自上而下分析（如LL(1)分析）也要好一些，而且在自左而右扫描输入串时就能发现其中的任何错误，并能准确地指出出错位置。
LR分析法主要的缺点是：LR分析器的手工构造工作量相当大，因此一般要借助于自动产生器。
本章首先讨论LR分析器的工作过程。然后学习四种不同分析表的构造方法。
第一种，也是最简单的，叫LR(0)分析法，在分析过程中不需要向右查看输入符号，因而它对文法的限制比较大，但它是建立其它LR分析法的基础。
第二种是简单LR分析法（简称SLR）。虽然有些文法构造不出SLR分析表，但这是一种比较容易实现又极具使用价值的方法。
第三种是规范LR分析法（即LR(1)）。这种分析表能力最强，能够适用一大类文法，但实现代价过高，或者说分析表的体积太大。
第四种是向前LR分析法（简称LALR）。这种分析表的能力介SLR和LR(1)之间，稍加努力即可高效率地实现。
教学内容：
7.1 LR分析法的概述；
7.2 LR(0)分析；
7.3 SLR(1)分析；
7.4 LR(1)分析；
7.5 LALR(1)分析；
教学要求：
要求理解有效项目的基本概念；掌握LR(0)文法的判断及LR(0)分析表的构造与分析方法、SLR(1)文法的判断与SLR(1)分析方法和LR(1)文法的判断与LR(1)分析方法。
教学重点：
LR分析法。
7.1 LR分析概述（55分钟）
根据前面的介绍我们知道：自下而上分析的中心思想是“移进－归约”，关键问题就是“寻找规范句型的句柄”。当一貌似句柄的符号串呈现于分析栈顶时，如何确定用哪一个产生式来归约？这是我们一直未能解决的问题。
对于算符优先文法的特殊情况，我们借助算符间的优先关系解决了这一问题。但对于更一般的情况，该如何来做呢？仔细分析问题产生的原因，我们会发现，在分析过程中我们没有利用到已移进和归约出的整个符号串——“历史资料”，也没有根据产生式去“瞻望”未来可能遇到的输入符号，而LR分析法就是在这些方面对“移进－归约”进行改造的。
LR分析法的基本思想：根据“历史资料”、“现实输入符号”以及对未来的“展望”等三个方面来确定栈顶的符号是否构成了相对于某一产生式的句柄。它是由Knuth在1965年首先提出的，后经Aho等人改造而成。
一、LR分析器
一个LR分析器实质上是一个带先进后出栈的DFA。
前面讲过，状态的变化可以反映出处理前后的经过，因此这儿我们应把“历史”和“展望”材料都综合为“状态”，存入分析栈，使得任何时候，栈顶都代表了从分析开始以来的全部“历史”和已推测出的“展望”。这样一来，在任何时候都可从栈顶来了解一切，栈顶状态和当前输入符号就唯一决定了LR分析器的每一步工作。
栈中每一项内容包括状态s和文法符号X两部分。栈的初始值为(s0,#)。栈顶状态为sm，符号串X1X2…Xm是至今已移进归约出的部分。如下页图所示。
二、分析表
LR分析器的核心是一张分析表。这张表包括两部分：“动作”(Action)和“状态转换”(Goto) ，它们都是二维数组。
Action[s,a]规定了状态s面临输入符号a时应该采取什么动作；Goto[s,X]则指出状态s面对文法符号X（终结符或非终结符）时下一状态是什么。显然，Goto[s,X]定义了一个以文法符号为字母表的DFA。

LR分析器模型图
每一项Action[s,a]所规定的动作无非是下述四种可能之一：
a.移进：把(s,a)的下一状态s'=Goto[s,a]和输入符号a推进栈，下一输入符号变成现行输入符号；
b.归约：指用某一产生式Aàβ进行归约。若|β|＝r，则把栈顶r个项托出，栈顶状态变成Sm-r，然后把(Sm-r,A)的下一状态s'=Goto[Sm-r,A]和A进栈。归约动作不改变现行输入符号。执行归约动作意味着β=Xm-r+1 …Xm已呈现与栈顶而且是一个相对于A的句柄。
c.接受：宣布分析成功，停止分析器的工作；
d.报错：发现源程序含有错误，调用出错处理程序。
LR分析器的总控程序本身的工作是非常简单的。它的任何一步只需按栈顶状态s和当前输入符号a执行Aciton[s,a]所规定的工作。不管什么分析表，总控程序都是一样地工作。
对于一个文法一个分析器常有若干不同的分析表，但不管什么分析表都将恰好识别文法的全部句子。本章将要讨论四种分析方法各自对应的分析表。这些分析表的构造后面再讲。下边先看一下LR分析器的工作过程。
三、LR分析器的工作过程
一个LR分析器的工作过程可以看成是栈里的状态序列、已归约串和输入串所构成的三元式的变化过程：
初始三元式： (s0, #, a1a2…an#)
中间三元式： (s0s1..sm, #X1X2…Xm, aiai+1…an#)
接受: (s0…sk,#X,#) (X为开始符号，而Action[sk,#]为接受)
分析器的下一步动作完全由sm和ai唯一决定，即执行Action[sm,ai]。经执行每种可能的动作之后，三元式的变化情形是：
1、若action[sm,ai]为移进且s=goto[sm,ai]，则三元式变为：
(s0s1…sms, #X1X2…Xmai, ai+1…an#)
2、若action[sm,ai]={Aàβ}，则按产生式Aàβ进行归约，此时三元式变为：
(s0s1…sm-rs', #X1X2…Xm-rA, aiai+1…an#)
此处s'=goto[sm-r,A]，r为β的长度，β=Xm-r+1…Xm。
3、若action[sm,ai]为接受，则三元式不再变化，过程终止，分析成功。
4、若action[sm,ai]为报错，则三元式的变化过程终止，报告错误。
LR分析器的工作过程就是一步一步地变换三元式，直至执行“接受”或“报错”为止。再看前面的例子：
教材P124例7.1文法G[S]：
(1) S à aAcBe
(2) A àb
(3) A àAb
(4) B àd

这是前面讲过的对输入串abbcde#的移进——分析过程，下面我们来看如何用LR分析法来分析该句子。
Si:移进：将下一状态i和当前输入符号进栈；
ri:归约：用第i个产生式归约，同时状态栈与符号栈退出相应的符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。
LR分析表如下：

对输入串abbcde#的LR分析过程：

如：第3）步，状态4面对b，Action[4,b]=r2=Aàb，状态栈退|b|＝1位是状态2，Goto[2,A]=3，相应地有：
第5）步，状态6面对c，Action[6,c]=r3＝AàAb，Goto[2,A]=3
第8）步，状态8面对e，Action[6,c]=r4＝Bàd，Goto[5,B]=7
第10）步，状态9面对＃，Action[9,#]=r1＝SàaAcBe，Goto[0,S]=1
四、LR文法
对于一个文法，如果能够构造出一张分析表，使得它的每个入口均是唯一的，则称该文法为LR文法。
注意：并非所有上下文无关文法都是LR文法，例：二义性文法 SàiCtS|iCtSeS。但是对于多数程序语言来说，一般都可用LR文法描述。
直观上说，对于一个LR文法，当分析器对输入串进行自左而右扫描时，一旦句柄呈现于栈顶，就能及时对它进行归约。
一个LR分析器有时需要“展望”未来的k个输入符号才能决定应采取什么样的“移进－归约”决策。于是又有如下定义: 对于文法G，若能用一个每步顶多向前查看k个输入符号的LR分析器进行分析，则称之为LR(k)文法。但是对大多数的程序语言来说，k=0或1就足够了。因此，我们只考虑k≤1的情况。
7.2 LR(0)分析（135分钟）
首先讨论一种只概括“历史”资料而不包含推测性“展望”材料的分析法——LR(0)分析法。我们希望仅由这种简单状态就能识别呈现在栈顶的某些句柄。而LR(0)项目集就是这样的简单状态。
7.2.1 LR(0)项目集
一、活前缀
例7.1中的文法G[S]：
(1) S à aAcBe[1] (序号[i]不属于文法符号)
(2) A à b[2]
(3) A à Ab[3]
(4) B à d[4]
对输入串abbcde进行推导时把序号也带上，做最右推导，形成如下形式：
S aAcBe[1]
aAcd[4]e[1]
aAb[3]cd[4]e[1]
ab[2]b[3]cd[4]e[1]
进行最右推导的逆过程——最左归约（规范归约），可以看出每次归约句型的前部分依次为：
ab[2]
aAb[3]
aAcd[4]
aAcBe[1]
规范句型的这种前部分符号串称为可归前缀，它不含句柄之后的任何符号。
字的前缀：字的任意首部，如abc: a, ab, abc。
我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀。之所以称之为活前缀，是因为在其右边添加一些终结符号后就可以形成规范句型。
活前缀例： e,a,ab
e ,a,aA,aAb
e ,a,aA,aAc,aAcd
e ,a,aA,aAc,aAcB,aAcBe
在LR分析过程中的任何时候，栈里的文法符号（自栈底向上）X1X2…Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（当然，这个输入串必须确实是文法的一个句子，再回头看7.1 LR分析的例子）。反过来说，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着扫描过的部分没有错误。
这样来看，如果我们能构造出一个FA，它能识别某文法G的所有活前缀（我们可以把文法的终结符和非终结符都看成FA的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态），那么我们就可以通过这个FA来构造G的LR分析表了，这个FA的每个状态都是下面定义的一个“项目”。
二、LR(0)项目
文法G的每一个产生式的右部添加一个圆点称为G的一个LR(0)项目（简称项目）。
例7.2，产生式AàXYZ对应四个项目：
Aà•XYZ AàX•YZ
AàXY•Z AàXYZ•
当然，Aàε只对应一个项目：Aà• 。在计算机中，每个项目可用一个整数对表示：第一个整数代表产生式编号，第二个指出圆点的位置。
项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分，圆点右部表示待识别的部分。
为了方便，我们根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种：
1、移进项目，形如 Aàa • ab
2、归约项目，形如 Aàa • ，对于b＝ε的项目为Aà•（对应的产生式Aàε），相应状态为归约状态。
3、待约项目，形如 Aàa • Bb，这表明用产生式A的右部归约时，首先要将B的产生式右部归约为B，对A的右部才能继续进行分析，也就是期待着继续分析过程中首先能进行归约得到B。
4、接受项目，形如 S'àS •
其中S'为开始符号，a、b∈V*，a∈VT, A、B∈VN 。
这里介绍项目是为了以项目作为要构造的FA的状态。
7.2.2 构造识别活前缀的DFA
（1）通过项目构造一个NFA
1、把项目编号，所有编号构成NFA的状态集；
2、以开始符号Sàα所对应的项目Sà•α为唯一初态
3、若项目i为：XàX1…Xi-1•Xi…Xn而项目j为：XàX1…Xi•Xi+1…Xn，则从i到j画一条标记为Xi的弧；若Xi∈VN，则从状态i画ε弧到所有的Xià•γ状态；
4、除初态外的任何状态都认为是终态（活前缀识别态）。
（2）用子集法把NFA确定化为DFA
这是建立LR分析算法的基础。
下面我们来看一个例子：（见教材P131）
例7.3文法G[S']： (0)S'àE (1) EàaA (2) EàbB (3)AàcA (4) Aàd (5) BàcB (6) Bàd
它的项目有：
1. S'à•E 2. S'àE• 3. Eà•aA 4. Eàa•A 5. EàaA• 6. Aà•cA 7. Aàc•A 8. AàcA•
9. Aà•d 10. Aàd• 11. Eà•bB 12. Eàb•B 13. EàbB• 14. Bà•cB 15. Bàc•B 16. BàcB• 17. Bà•d 18. Bàd•
1、构造NFA

2、确定化

DFA的项目集的全体称为文法G[S']的LR(0)项目集规范族；也就是说：构成识别一个文法G的活前缀的DFA的项目集的全体，称为G的LR(0)项目集规范族。
如：0,1,2,3,4,5,6,7,8,9,10,11分别为项目集；
{0,1,2,3,4,5,6,7,8,9,10,11}称为项目集规范族。
前面构造方法中，NFA确定化为DFA的工作量较大，我们考虑直接构造出项目集作为DFA的状态，就可直接构造DFA。下面我们就简单谈一下通过闭包函数(CLOSURE)来求DFA一个状态的项目集，进而构造DFA的方法。
7.2.3 LR(0)项目集规范族的构造
这是建立DFA的另一方法，要重点掌握。
下面我们用第4章NFA的确定化中所引进的ε－Closure(闭包)的办法来构造一个文法G的LR(0)项目集规范族。
为使“接受状态”唯一且易于识别，构造文法G的拓广文法G': 引进一个新的初态S'，增加产生式S'àS
VN'=VN∪{S'} , VT'=VT , P'=P∪{S'àS}
很显然，L(G')=L(G)。
定义项目集I的闭包函数CLOSURE(I)（见教材P132）：
①I的任何项目都属于CLOSURE(I)；
②若Aàα•Bβ属于CLOSURE(I)，那么，对任何关于B的产生式Bàγ，项目Bà•γ也属于CLOSURE(I)；
③重复执行上述步骤直至CLOSURE(I)不再增大为止。
例如7.3，若I＝{ S'à•E } closure(I)={ S'à•E , Eà•aA , Eà•bB }，这就是DFA中状态0所代表的项目集。
例7.4：（0）S'à•S （1）S'àS• （2）Sà•aS （3）Sàa•S
（4）SàaS• （5）Sà•b （6）Sàb•
I= { S'à•S} closure(I)={ S'à•S , Sà•aS , Sà•b }
I= { Sàa•S} closure(I)={S'àa•S , Sà•aS , Sà•b }
定义状态转换函数GO（见教材P133）：对于项目集I和文法符号X∈V*，GO(I,X)=CLOSURE(J)，其中:
J={形如AàαX•β的项目∣Aàα•Xβ∈I}
GO(I,X)的直观意义是：从状态I(项目集)出发，经过X弧所应该到达的状态(项目集) 。
例如7.4文法：
I= {S'à•S , Sà•aS , Sà•b }
GO(I,b)=Closure({Sàb•})={ Sàb•}
GO(I,a)=Closure({Sàa•S})={ Sàa•S , Sà•aS , Sà•b }
通过闭包和状态转换函数，则我们很容易就可以求出G'的LR(0)项目集规范族：
①从S'à•S开始，得到DFA的初态项目集；
②然后通过状态转换函数GO求其所有的后继项目集，直到不出现新的项目集为止。
例7.5文法G[S′]： S′àS
SàaS | b
I0= { S'à•S , Sà•aS , Sà•b }
I1 = GO(I0,S)=closure({S'àS•})={ S'àS•}
I2 = GO(I0,a)=closure({Sàa•S})={ Sàa•S , Sà•aS , Sà•b }
I3 = GO(I0,b)=closure({Sàb•})={ Sàb•}
I4 = GO(I2,S)=closure({{ SàaS•}})={ { SàaS•}}
文法G[S′]的LR(0)项目集规范族就是{I1,I2,I3,I4}，我们把它表示成矩阵的形式，如下图所示。

转换函数GO把这些集合联结成一张DFA转换图。如果令I0为DFA的初态，那么下图的DFA就是恰好识别文法G[S′]的全部活前缀的有限自动机。

7.2.4 有效项目
我们希望从识别文法的活前缀的DFA建立LR分析器（带栈的DFA），因此需要研究这个DFA的每个项目集（状态）中的项目的不同作用。
（1）若有规范推导S' * αAγ αβ1β2γ (γ∈VT*) ，则称项目Aàβ1•β2对活前缀αβ1是有效的。
直观上说，αβ1在符号栈栈顶时是移进还是归约，可根据αβ1的有效项目Aàβ1•β2来判断。如果β2＝ε，那么应把β1归约为A，即用产生式Aàβ1归约。如果β2≠ε，那么它暗示句柄还没有完全进栈，动作应该是移进。
当然，同一个活前缀的两个有效项目可能告诉我们做不同的事情，有些这样的冲突可以通过向前多看几个输入符号，或许可以解决。我们将在下节讨论这种情况。但是对于非LR文法，这种冲突有些是无法解决的，不论超前多看几个输入符号都无济于事。
我们可以计算出能够出现在符号栈中的每一个活前缀r的有效项目集。这个集合刚好就是从DFA的初态出发，沿着标记为r的路径所能到达的那个项目集。于是有下面的定理：
（2）定理： 任何时候符号栈中的活前缀X1X2…Xm的有效项目集正是栈顶状态Sm所代表的那个项目集。
这是LR分析理论的一条基本定理。实际上，栈顶的项目集（状态）体现了栈里的一切有用信息。
下面再来看一下例子7.3:
文法G[S']：(0)S'àE (1) EàaA (2) EàbB (3)AàcA (4) Aàd (5) BàcB (6) Bàd
识别其活前缀的DFA的一部分如下图所示：

我们说bc是一个活前缀，DFA从0状态开始读出bc后到达5状态，这个状态集5对bc是有效的。为什么？
为了证明这一点，考虑下面三个规范推导：
1、S’ E bB bcB
2、S’ E bB bcB bccB
3、S’ E bB bcB bcd
推导1说明了Bàc•B对bc的有效性，推导2说明了Bà•cB对bc的有效性，推导3说明了Bà•d对bc的有效性。显然对于活前缀bc不再存在别的有效项目了。
7.2.5 LR(0)文法的定义
若一个文法G的拓广文法G'的活前缀识别自动机中的每个状态不存在下述情况（见教材P135）：
1、既含移进项目又含归约项目（移进—归约冲突）；
2、含有多个归约项目（归约—归约冲突）
则称G是一个LR(0)文法。也就是说，LR(0)文法规范族的每个项目集不包含任何冲突项目。
7.2.6 LR(0)分析表的构造
对于LR(0)文法，我们可直接从它的项目集规范族C={I0,I1,…In}和活前缀识别自动机的状态转换函数GO构造出LR(0)分析表。下面是构造LR(0)分析表的算法（见教材P135）：
我们用每个项目集Ik的下标k作为分析器的状态。特别地，令含有S'à•S的项目集Ik的下标k作为初态。于是如下构造子表Action、Goto：
①若项目Aàα•aβ∈Ik且GO(Ik,a)=Ij，a∈VT，则置Action[k,a]为“把(j,a)移进栈”，简记为“sj”；
②若项目Aàα•∈Ik，那么对任意a∈VT(或#)，置Action[k,a]为“用产生式Aàα进行归约”，简记为“rj” (设Aàα是文法G'的第j个产生式)；
③若项目S'àS•∈Ik，则置Action[k,#]为“接受”，简记为 “acc”；
④若GO(Ik,A)=Ij，A∈VN，则Goto[k,A]=j；
⑤分析表中凡不能用上述4条规则填入信息的，空白格均置“报 错标志”。
由于LR(0)文法规范族的每个项目集都不含冲突项目，因此，按上述方法构造的分析表的每个入口都是唯一的（即不含多重定义），我们称如此构造的分析表是一张LR(0)分析表，使用LR(0)分析表的分析器是LR(0)分析器。
例7.6求文法G[E]的LR(0)分析表
G[E] ：EàaA|bB
AàcA|d
BàcB|d
第一步：拓广文法并对产生式编号
(0)S'àE (1) EàaA (2) EàbB (3)AàcA
(4) Aàd (5) BàcB (6) Bàd
第二步：写出拓广后的文法的项目：
1. S'à•E 2. S'àE• 3. Eà•aA 4. Eàa•A 5. EàaA• 6. Aà•cA 7. Aàc•A 8. AàcA•
9. Aà•d 10. Aàd• 11. Eà•bB 12. Eàb•B 13. EàbB• 14. Bà•cB 15. Bàc•B 16. BàcB• 17. Bà•d 18. Bàd•
第三步：从S'à•E开始求项目集规范族和状态转换表
状态
项目集
经过符号
到达的状态
0
S'à•E
E
1
Eà•aA
a
2
Eà•bB
b
3
1
S'àE•

2
Eàa•A
A
4
Aà•cA
c
5
Aà•d
d
6
3
Eàb•B
B
7
Bà•cB
c
8
Bà•d
d
9
4
AàaA•

5
Aàc•A
A
10
Aà•cA
c
5
Aà•d
d
6
6
Aàd•

7
EàbB•

8
Bàc•B
B
11
Bà•cB
c
8
Bà•d
d
9
9
Bàd•

10
AàcA•

11
BàcB•

第四步：构造LR(0)分析表
状态
ACTION
GOTO
a
b
c
d
#
E
A
B
0
S2
S3

1

1

acc

2

S5
S6

4

3

S8
S11

7
4
r1
r1
r1
r1
r1

5

S5
S6

10

6
r4
r4
r4
r4
r4

7
r2
r2
r2
r2
r2

8

S8
S9

11
9
r6
r6
r6
r6
r6

10
r3
r3
r3
r3
r3

11
r5
r5
r5
r5
r5

7.3 SLR(1)分析（50分钟）
7.3.1 问题的提出
LR(0)分析要求条件很苛刻，而常见程序设计语言都不是LR(0)的，即使是简单的表达式文法也不是LR(0)文法，因此实用性较差。要想使识别其活前缀的DFA的每个状态都不含冲突项目也不可能，因此，有必要研究一种带一点“展望”材料的LR分析法，也就是要对冲突的状态向前看一个符号，以确定做哪种动作，所以称这种分析方法为简单的LR(1)分析法，用SLR(1)表示，能用这种分析法的文法就是SLR(1)文法。
我们将会看到，许多冲突性的动作都可能通过考察有关非终结符的FOLLOW集而获得解决。例如，I={Xàα•bβ,Aàα•,Bàα•}，第一个项目为移进项目，第二、三项是归约项目。到底应该采取哪种动作是不清楚的。如果我们分析一下该文法中所有含A、B的句型，考察Follow(A)和Follow(B)，若Follow(A)∩Follow(B)=φ且都不含有b，则问题就解决了。当状态I面临输入a时，我们就可以采取如下的“移进—归约”策略（见教材P139）：
①若a=b，则移进；
②若a∈Follow(A)，则用Aàα来归约；
③若a∈Follow(B)，则用Bàα来归约；
④此外，报错。
一般而言，若LR(0)规范族的一个项目集I中含有m个移进项目和n个归约项目：
I={ A1àα•a1β1, A2àα•a2β2, ..., Amàα•amβm,
B1àα•, B2àα•, ..., Bnàα• }
若集合：{a1,a2,...,am}∩Follow(B1)∩...∩Follow(Bn)=φ，则通过查看现行输入符号a属于哪个集合就可以解决问题。
①若a=ai (i=1,2,…m)，则移进；
②若a∈Follow(Bi) (i=1,2,…n)，则用Biàα来归约；
③此外，报错。
这种方法称为SLR(1)解决法。若一个文法的LR(0)分析表中所含有的动作冲突都能用上述方法解决，则称这个文法是SLR(1)文法。
7.3.2 SLR分析表的构造
这个构造算法与LR(0)分析表的构造算法基本类似（参见7.2.6 LR(0)分析表的构造），只有些许改动之处（加黑画线处，见教材P141）：
①若项目Aàα•aβ∈Ik且GO(Ik,a)=Ij，a∈VT，则置Action[k,a]为“把(j,a)移进栈”，简记为“sj”；
②若项目Aàα•∈Ik，那么对任意a∈VT(或#)，且满足a∈Follow(A)时，置Action[k,a]为“用产生式Aàα进行归约”，简记为“rj” (设Aàα是文法G'的第j个产生式)；
③若项目S'àS•∈Ik，则置Action[k,#]为“接受”，简记为 “acc”；
④若GO(Ik,A)=Ij，A∈VN，则Goto[k,A]=j；
⑤分析表中凡不能用上述4条规则填入信息的，空白格均置“报 错标志”。
按照上述算法构造出的分析表，如果不含多重入口，则称之为G'的SLR分析表；G'称为一个SLR(1)文法，使用SLR分析表的分析器称为SLR分析器。每个SLR文法都是无二义的，但也存在许多无二义文法不是SLR(1)的,因为没有足够多的“展望”信息。
教材P140例7.7文法：（0）S'àE （1）EàE+T （2）EàT
（3）TàT*F （4）TàF （5）Fà(E) （6）Fài
直接从S'à•E开始求项目集规范族和状态转换表
状态
项目集
经过符号
到达的状态
0
S'à•E
E
1
Eà•E+T
E
1
Eà•T
T
2
Tà•T*F
T
2
Tà•F
F
3
Fà•(E)
(
4
Fà•i
i
5
1
S'àE•

EàE•+T
＋
6
2
EàT•

TàT•*F
*
7
3
TàF•

4
Fà(•E)
E
8
Eà•E+T
E
8
Eà•T
T
2
Tà•T*F
T
2
Tà•F
F
3
Fà•(E)
(
4
Fà•i
i
5
5
Fài•

6
EàE+•T

9
Tà•T*F
T
9
Tà•F
F
3
Fà•(E)
(
4
Fà•i
i
5
7
TàT*•F

10
Fà•(E)
(
4
Fà•i
i
5
8
Fà(E•)
)
11
Eà•E+T
+
6
9
E+T•

TàT•*F
*
7
10
TàT*F•

11
Fà(E)•

不难看出I1、I2、I9中存在移进—归约冲突，因而这个文法不是LR(0)文法，也就不能构造LR(0)分析表。
在I1中，归约项目为S'àE•，移进项目为EàE•+T，由于FOLLOW(S')={#}，所以有{#}∩{+}=φ。
在I2中，归约项目为EàT•, 移进项目为TàT•*F，由于FOLLOW(E)={#,+,)}，所以有{#,+,)}∩{*}=φ。
在I9中，归约项目为EàE+T•，移进项目为TàT•*F，由于FOLLOW(E)={#,+,)}，所以有{#,+,)}∩{*}=φ。
这样所有的移进—归约冲突都可以用FOLLOW集解决，因此该文法是SLR(1)的。
构造SLR(1)分析表如下：
状态
ACTION
GOTO
i
+
*
(
)
#
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

7.4 LR(1)分析法（70分钟）
尽管SLR(1)分析表简单实用，但还不能解决所有问题：
例如例7.7，在I2={EàT•, TàT•*F }中存在移进—归约冲突，若栈顶状态为2，栈中符号为#T，当前输入符号为“)”，“)”∈FOLLOW(E)，这时按照SLR(1)分析法应该用产生式EàT进行归约，归约后栈顶符号为#E，再加上当前输入符号“)”，栈顶为#E)不是该文法规范句型的活前缀。由此可以看出SLR(1)分析法虽然相对于LR(0)分析法有所改进，但仍然存在着多余归约（或称无效归约）。
再来看教材P142最下面的例子，文法G’为：
S’àS
SàaAd | bAc | aec | bed
Aàe
在项目集I5和I7中存在移进—归约冲突：
I5={Sàae•c, Aàe•}，I7={Sàbe•d, Aàe•}
FOLLOW(A)={c,d}
在I5中，FOLLOW(A)∩{c}≠φ，在I7中，FOLLOW(A)∩{d}≠φ，都存在公共元素，用SLR(1)分析不能解决冲突。
怎么解决呢？我们看I5={Sàae•c, Aàe•}，包括了活前缀为a的所有句型的最右推导有：
S’ S aAd aed
S’ S aec
不难看出对活前缀ae来说，面临输入符号为c时应移进，面临d时应用产生式Aà归约。根据项目集的构造原则有：
若Aàα•Bβ∈I，则Bà•γ∈I
由此不妨考虑把First(β)作为用产生式Bàγ归约的搜索符，称为向前搜索符，作为归约时查看的符号集合，用以替代SLR(1)分析中的Follow集，把此搜索符号的集合也放在相应的项目后面，这种处理方法就是LR(1)方法。
7.4.1 LR(k)项目
LR(k)项目：形如[Aàα•β，a1a2...ak]的项目。
其中，Aàα•β是一个LR(0)项目，每个ai∈VT。而a1a2...ak称为该LR(k)项目的向前搜索串（展望串）。类似的，[Aàα•, a1a2...ak]表示在下面k个输入符号为a1a2...ak时，要按Aàα归约，称为LR(k)归约项目，而[Aàα•Xβ, a1a2...ak]或者是LR(k)移进项目(X∈VT)，或者是LR(k)待约项目(X∈VN)。
可以想到，向前搜索串只是对LR(k)归约项目有意义，而对任何移进或待约没有作用。由于对大多数程序语言的语法来说，一般向前搜索一个符号就可以确定“移进”或“归约”，因此，我们只对k≤1的情况感兴趣。
7.4.2 有效项目
一个LR(1)项目[Aàα•β,a]对于活前缀γ是有效的，如果存在：
S * δAω δαβω
其中①γ=δα；②a是ω的第一个符号，或者a=#而ω=ε 。
例7.8 考虑文法G[S]：SàBB
BàaB∣b
它有一个规范推导S * aaBab aaaBab，我们看到项目[Bàa•B,a]对于活前缀γ=aaa是有效的。因为，δ=aa，A=B，ω=ab，α=a，β=B。同样，由于规范推导S * BaB BaaB，项目[Bàa•B,#]对于活前缀Baa是有效的。
7.4.3 构造有效的LR(1)项目集族
构造有效的LR(1)项目集规范族的办法本质上和构造LR(0)项目集规范族的办法是一样的。类似地，我们也需要两个函数CLOSURE和GO（见教材P144）。
以项目[S′à•S,#]属于初始项目集中，把“＃”作为向前搜索符，表示活前缀为γ要归约成S时，必须面里输入符号为“＃”才行。我们对初始项目[S′à•S,#]求闭包后再用转换函数逐步求出整个文法的LR(1)项目集规范族。
（1）构造有效LR(1)项目集的闭包
设I是一个项目集,
①I的任何项目∈CLOSURE(I)；
②若项目[Aàα•Bβ,a]∈CLOSURE(I)，Bàγ是一个产生式，则对于任何终结符b∈FIRST(βa)，[Bà•γ,b]∈CLOSURE(I)；
③重复步骤②，直至CLOSURE(I)不再增大为止 。
为什么呢？因为[Aàα•Bβ,a]属于对活前缀γ=δα有效的项目集，则意味着存在一个规范推导
S * δAaλ δαBβaλ
又因为b∈First(βa)，故βaλ可以推导出bω，于是对于Bàτ形式的产生式，我们有
S * δαBβaλ * γBbω γτbω
这正好说明了[Bà•τ,b]对γ也是有效的。注意：b可能是从β推导出的第一个终结符，或者，若β推出ε，则b就是a，把这两种可能性结合在一起，我们说b∈First(βa)。
（2）定义GO函数
对任一项目集I和文法符号X，函数GO(I,X)定义为
GO(I,X)=CLOSURE(J)，其中
J={任何形如[AàαX•β,a]的项目 ∣ [Aàα•Xβ,a]∈I}
现在可以对教材P142上的例子出现的冲突构造它的LR(1)项目集规范族了，如下：

这样一来，在I5中，输入符号为d时归约，为c时移进，而在I7中输入符号为d时移进，为c时归约，冲突可以全部解决，因此该文法是LR(1)文法。
7.4.4 规范LR(1)分析表的构造
与LR(0)分析表的构造在形式上基本一样，只是归约项目的归约动作取决于该归约项目的向前搜索符集，即只有当面临的输入符属于向前搜索符的集合，才做归约动作，其它情况均出错。具体构造算法如下（见教材P145）：
①若项目[Aàα•aβ,b]∈Ik且GO(Ik,a)=Ij，a∈VT，则置Action[k,a]为 “sj”，sj的含义是把输入符号a和状态j分别移入文法符号栈和状态栈；
②若[Aàα• ,a]∈Ik，则置Action[k,a]为“rj”，其中a∈VT，rj的含义是把