SLR（1）分析-《编译原理与实践》学习成果

LR（0）文法是一类很简单的文法，很多程序设计语言的文法都无法满足LR（0）文法的条件，无法进行LR（0）分析。对于这类文法，可以通过考察有关非终结符的FOLLOW集，即向前查看一个输入符号，来协助解决LR（0）项目集规范族中的一些冲突动作。

例如，假定一个LR（0）项目集规范族中含有如下的项目集I

I={A→α·bβ,B→γ·,C→δ·}

其中，第一个项目是移进项目，后两个项目是不同的归约项目。项目集中含有移进-归约和归约-归约两种冲突。第一个项目指出应将下一个输入符号b移进栈，第二个项目指出应将栈顶部的γ归约为B，栈顶的第三个项目指出应将顶部的δ归约为C。

解决冲突的一种简单的办法是考察FOLLOW（B）和FOLLOW（C）。如果这两个集合不相交，而且也不包含b，那么，当状态Ii面临某输入符号a，才可以采取如下的冲突解决策略：

（1）若a=b，则移进；

（2）若a∈FOLLOW（B），则用产生式B→γ进行归约；

（3）若a∈FOLLOW（B），则用产生式B→δ进行归约；

（4）否则，报错。

一般的，假设LR（0）项目集规范族的项目集I中有m个移进项目

{A1→α1·a1β1,A2→α2·a2β2,…,Am→αm·amβm}

和n个归约项目

{B1→γ1·,B2→γ2·,…,Bn→γn·}

那么，只要

{a1,a2,…,am}∩FOLLOW(Bi)=φ i=1,2,…,n

FOLLOW(Bi)∩FOLLOW(Bj)=φ i,j=1,2,…,n

就可以通过检查当前输入符号a属于上述n+1个集合中的哪一个集合来解决冲突，即

（1）若a∈{a1，a2，…，am}，则移进a；

（2）若a∈FOLLOW（Bi），i=1，2，…，n，则用产生式Bi→γi进行归约；

（3）否则，报错。

上述冲突解决方法称为SLR（1）方法，也就是简单LR分析。数字1表示在分析过程中最多向前看一个符号。如果文法的LR（0）项目集规范族的某些项目集或LR（0）分析表中的动作冲突都能用SLR（1）方法进行解决，则称文法是SLR（1）文法，所构造的分析表为SLR（1）分析表。使用SLR（1）分析表的分析器称为SLR（1）分析器。

SLR（1）分析表的构造与LR（0）分析表的构造类似，只是需要在含有冲突的项目集中进行冲突处理。SLR（1）分析表的构造如算法5.6所示。

算法5.6 构造SLR（1）分析表。

首先，构造出文法的LR（0）项目集规范族，并计算所有非终结符的FOLLOW集。假定项目集规范族C={I0，I1，…，In}，Ik表示项目集的名字，k表示状态。包含S→·S项目的状态k为分析器的初态。

（1）若项目A→α·Xβ∈Ik且GOTO（Ik，X）=Ij(www.xing528.com)

①若X∈VT，则置ACTION[k，X]=Sj，即将（j，a）进栈；

②若X∈VN，则置GOTO[k，X]=j。

（2）若项目A→α·∈Ik，则对任何a∈VT（或结束符#），若a∈FOLLOW（A）时，置ACTION[k，a]=rj（设A→α是文法G的第j个产生式），即用A→α归约。

（3）若项目S→S·∈Ik，则置ACTION[k，#]=acc，即接受。

（4）分析表中凡不能用规则（1）～（3）填入的空白均置为“出错标志”。

按照算法5.6构造的分析表含有ACTION和GOTO两部分，如果表的每个入口不含多重定义，则称为文法G的SLR（1）分析表。

例5.13 构造例5.12中文法的SLR（1）分析表。

利用SLR（1）方法解决例5.12中含有冲突的3个项目集。

在I1中，S→E·，E→E·+T。由于FOLLOW（S）={#}，而S→E·是唯一的接受项目，因此，当且仅当遇到句子的结束符‘#’时，句子才被接受。又因{#）∩{+}=φ，所以，I1中的冲突可以解决。

在I2中，E→T·，T→T·*F。由于FOLLOW（E）={+，），#}，FOLLOW（E）∩{*}=φ，因此，当面对输入符+、）或#时，用产生式E→T进行归约；当面对输入符*时移进；其他情况则报错。

在I9中，E→E+T·，T→T·*F。与I2类似，由于FOLLOW（E）∩{*}=φ，因此，当面对输入符+、）或#时，用产生式E→E+T进行归约；当面对输入符*时，移进；其他情况报错。

所有冲突均可以使用SLR（1）方法解决，因此文法G5.2是SLR（1）文法。依据算法5.6构造的文法SLR（1）分析表如表5-13所示。

表5-13　例5.12文法的SLR（1）分析表

尽管SLR（1）方法能够解决某些LR（0）项目集规范族中冲突的项目集。但是，大多数实用的程序设计语言的文法还是无法满足SLR（1）文法的条件，无法使用SLR（1）方法解决项目集规范族中的动作冲突。

例5.14 判断如下拓广文法是否为SLR（1）文法：

(0)S→S (3)L→*R

(1)S→L=R (4)L→i

(2)S→R (5)R→L

首先构造文法的LR（0）项目集规范族，如下所示。

从中可以发现在项目集I2中存在移进-归约冲突。归约项目R→L·左部非终结符R的FOLLOW（R）={=，#}，移进项目S→L·=R移进下一个输入符号‘=’。由于

FOLLOW(R)∩{=}≠φ

I2中的移进-归约冲突无法使用SLR（1）方法解决。这个无二义性的文法不是SLR（1）文法。