教育学第7章LR分析法课件

1、第七章 LR 分析法 1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。 LR(K)分析是指自左向右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈中当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相当于某一产生式右部符号的句柄是否已在分析栈的顶部形成。从而也就可以确定所应采取的分析动作（是移进输入符号还是按某产生式进行归约）。当前扫描到Xn+1,向前查看k个符号，来确定是把Xn+1移进栈，还是把XiXn作为句柄进行归约。1） 要归约时，则根据某产生式UXiXi+1Xn进行归约： #X1X2Xi-1UXn+1Xn+2Xn+k#例：#X1X

2、2Xi Xn Xn+1Xn+2Xn+kXn+k+1#栈顶第1页，共85页。（续页）LR(0) 表示在每一步分析时都不用向前输入符号LR(1) 表示在每一步分析时都向前看一个输入符号来决定当 前的动作。SLR(1) 表示简单的LR(1)，即只在动作不唯一的地方向前看一个符号，在动作唯一时则不向前看输入符号。2） 要移进时，即把Xn+1进栈，并读下一符号： #X1X2XiXnXn+1 Xn+2Xn+k# 在栈中当前扫描符栈顶第2页，共85页。7.1 LR分析概论一 .LR分析器的逻辑结构及工作过程 从逻辑上来说，一个LR分析器如图7.1 所示。 输入串#aia1SpX1#S1S0XmSm总 控 程

3、 序输出ACTION 表GOTO 表其中S栈为状态栈 X栈为符号栈栈产生式 表图7.1 LR分析器的逻辑结构第3页，共85页。 即一个LR(k)分析器主要由：总控程序，分析栈（状态栈和符号栈）输入队列和分析表组成。一般来说所有LR分析器的总控程序基本上是大同小异。只有分析表各不相同。一般主要讨论三种不同的分析表的构造方法。 第一种称为规范LR分析表构造法。用此法构造的分析表功能最强而且也适合于很多文法，但实现代价比较高。 第二种称为简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。但SLR分析表的功能太弱，而且对某些文法可能根本就构造不出相应的SLR分析表。 第三种称为向前LR（即

4、LALR）分析表构造法。这种方法构造的分析表功能介于规范LR分析表SLR分析表之间。这种表适用于绝大多数程序语言的文法。而且也可以设法有效的实现。第4页，共85页。二、LR 分析器的分析过程如下：1.首先将初始状态 S0及句子的左界限#分别压入状态栈和符号栈中。 则用栈顶状态Sm和当前扫描符 ai组成符号对（ Sm, ai)去查分析动作表，根据ACTIONSm, ai的指示完成相应的分析动作。表中每一表元素所规定的动作仅能是下列四种动作之一： S0S1 S2 Sm Sm+1 ai+1 ai+2 an # # X1 X2 Xm ai 2.设在分析中的某一步，分析栈及余留的输入串为如下格局： S0

5、S1 Sm ai ai+1an #X1 Xm （1） ACTIONSm, ai= Sm+1 （移进）表明句柄尚未在栈顶形成，此时正期待移进输入符号以便形成句柄。故将当前的输入符号和表元素Sm+1分别压入栈中，有第5页，共85页。（2） ACTIONSm, ai= Rj (归约） 表明此时应按文法的第j个产生式A Xm-k+1Xm-k+2 Xm进行归约。即栈顶符号串Xm-k+1Xm-k+2 Xm已成为当前句型的句柄。所谓按第j个产生式归约，就是将分析栈中从顶向下的k个符号退栈，然后将文法符号A压入符号栈中。此时分析的格局为： S0S1 Sm-k ai ai+1an # # X1 Xm-k A 然

6、后以（ Sm-k,A)去查状态转移表，设GOTOSm-k,A= Sl ,则将此新状态压入状态栈中，则有如下格局： S0S1 Sm-k Sl ai ai+1an # # X1 Xm-k A 第6页，共85页。（3） ACTIONSm, ai=acc （接受） 表明当前的输入串已被成功地分析完毕，应停止分析器的工作。其中Z为文法开始符号S为使ACTIONS ，#=acc的 唯一状态（接受状态）（4） ACTIONSm, ai=ERROR（空白）。 表明当前的输入串中含有错误，也应终止当前的分析工作。转出错处理。3. 重复上述第2步的工作，直到分析栈顶出现“接受状态”或“出错状态“为止。对接受状态，

7、分析栈的格局为： S0 S # # Z 第7页，共85页。例：有文法GS:1：SaAcBe 2：Ab 3：AAb 4：Bd其ACTION表和GOTO表为：考察对输入串abbcde# 的分析过程。r1r1r1r1r1r1r4r4r4r4r4r4S9r3r3r3r3r3r37S8r2r2r2r2r2r2S6S53S4acc1S2BAS#dbecaGOTOACTION0123456789 S a A c B e A b d b图7.2 abbcde# 的语法树第8页，共85页。对输入串abbcde# 的分析过程为： ACTION GOTO步骤 状态栈 符号栈 输入流 分析动作 下一状态1 0 # a

8、bbcde# S2(0,a)2 02 #a bbcde# S4(2,b)3 024 #ab bcde# r2(4,b) GOTO2,A=34 023 #aA bcde# S6(3,b) 6 023 #aA cde# S5(3,c)5 0236 #aAb cde# r3(6,b) GOTO2,A=37 0235 #aAc de# S8(5,d)8 02358 #aAcd e# r4(8,d) GOTO5,B=79 02357 #aAcB e# S9(7,e)10 023579 #aAcBe # r1(9,#) GOTO0,S=111 01 #S # acc(1,#)图7.3 abbcde#的分析

9、过程第9页，共85页。LR分析过程中的性质与特点：栈中的文法符号串并上剩余的输入串构成一个右句型（规范句型）当该右句型的句柄出现在栈顶时，归约，否则，移进栈中的文法符号串是当前句型的前缀，该前缀不包含句型句柄后面的符号，称之为活前缀（Viable Prefixes）第10页，共85页。7.2 LR(0) 分析表的构造为了给出构造LR(0)分析表的算法，引出一些术语：1、规范句型的活前缀 前缀：一个符号串的前缀是指该串的任意首部（包括）。例如 abc的前缀有： ,a,ab,abc abcd的前缀有：,a,ab,abc,abcd 由此可知，对于符号串 而言，其前缀的数量为+1。例：有文法GS:Sa

10、AcBe1 Ab2 这里在每条产生式后加上了产 AAb3 生式的序号i当进行推导时把 Bd4 序号带上，以便说明问题。对输入串abbcde进行推导如下（最右推导）： S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1由此可知，abbcde是该文法的句子。由于LR方法是自底向上的分析，故应采用归约。第11页，共85页。最左归约为： ab2b3cd4e1 用2式归约 aAb3cd4e1 3 aAcd4e1 4 aAcBe1 1 S其中表示归约符 从归约的过程可看出，每次归约时，归约前和归约后的被归约部分与剩余部分合起来仅构成文法的规范句型，而用哪个产生式归约仅取决于当前句型

11、的前面部分；X1X2Xnp 其中Xi为文法的符号，p为第p个产生式序号。 如上例中每次归约前句型的前面部分为： ab2 aAb3 aAcd4 aAcBe1我们把规范句型的这种前端部分的串称为可归前缀。实际上，它们恰好是符号栈栈顶形成句柄时符号栈中的内容。SaAcBe1Ab2AAb3Bd4第12页，共85页。 这是因为一旦句型的句柄在符号栈顶形成，将会立即被归约之故。所以我们将把规范句型具有上述性质（即不含句柄之后的任何符号）的前缀称之为可归前缀。 对各规范句型有前缀：ab2b3cd4e1 ,a,abaAb3cd4e1 ,a,aA,aAbaAcd4e1 ,a,aA,aAc,aAcdaAcBe1

12、,a,aA,aAc,aAcB,aAcBe可以发现前缀a,ab,aA,aAc是多个规范句型的前缀，因此我们可进一步把形成可归前缀前和形成可归前缀时的所有规范句型的前缀都称为活前缀。可归前缀：是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。活前缀：可归前缀的任意首部。特指在分析过程中对于在栈顶形成句柄之前和恰好形成句柄时，每一步中符号栈中的那些符号组成的符号串。第13页，共85页。活前缀定义： 在前面例中对输入串abbcde的归约分析过程中，在规范归约过程中的任何时候只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，它表明输入串的已被分析过的部分是该文法某规范句型的一个

13、正确部分。由此可形式地定义活前缀如下： 定义 7.1：若S * A 是 文法G中的一个规范推导， 如果符号串是的前缀，则称是G的一个活前缀。 其中 S为文法开始符号。 RR第14页，共85页。LR分析分析过程可以看作是识别文法规范句型活前缀的过程。只要每一时刻栈中的文法符号串是某规范句型的活前缀，则说明已分析的部分是正确的一个文法的规范句型的所有活前缀构成一个语言，而且是正规语言，可以用一个 DFA 来识别第15页，共85页。例子：文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d014235769SabAbcBed8*第16页，共85页。每个状态都是活前缀的识别态，

14、双圈状态是可归前缀（句柄）识别态，标识了*的状态是句子识别态分析句子的过程可以看作在上面这个 DFA 上运行的过程014235769SabAbcBed8*(1) S aAcBe(2) A b(3) A Ab(4) B d第17页，共85页。例子：步骤栈输入串ACTIONGOTO1#0abbcde#S2014235769SabAbcBed*8第18页，共85页。例子：步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S4014235769SabAbcBed8*第19页，共85页。例子：步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43

15、#0a2b4bcde#R23014235769SabAbcBed8*第20页，共85页。例子：步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R234#0a2A3bcde#S6014235769SabAbcBed8*第21页，共85页。例子：步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R234#0a2A3bcde#S65#0a2A3b6cde#R33014235769SabAbcBed8*第22页，共85页。例子：步骤栈输入串ACTIONGOTO3#0a2b4bcde#R23

16、4#0a2A3bcde#S65#0a2A3b6cde#R336#0a2A3cde#S5*014235769SabAbcBed8第23页，共85页。例子：步骤栈输入串ACTIONGOTO4#0a2A3bcde#S65#0a2A3b6cde#R336#0a2A3cde#S57#0a2A3c5de#S8*014235769SabAbcBed8第24页，共85页。例子：步骤栈输入串ACTIONGOTO5#0a2A3b6cde#R336#0a2A3cde#S57#0a2A3c5de#S88#0a2A3c5d8e#R47014235769SabAbcBed8*第25页，共85页。例子：步骤栈输入串ACTI

17、ONGOTO6#0a2A3cde#S57#0a2A3c5de#S88#0a2A3c5d8e#R479#0a2A3c5B7e#S9014235769SabAbcBed8*第26页，共85页。例子：步骤栈输入串ACTIONGOTO7#0a2A3c5de#S88#0a2A3c5d8e#R479#0a2A3c5B7e#S910#0a2A3c5B7e9#R11014235769SabAbcBed8*第27页，共85页。例子：步骤栈输入串ACTIONGOTO8#0a2A3c5d8e#R479#0a2A3c5B7e#S910#0a2A3c5B7e9#R1111#0S1#Acc014235769SabAbcB

18、ed8*第28页，共85页。2、LR（0）项目 由上述分析和定义可知，活前缀与句柄间的关系不外乎下述 三种情况：（1）活前缀中已含有句柄的全部符号（句柄的最后符号就是 活前缀的最后符号）。（2）活前缀中只含有句柄的前部分符号（句柄的最左子串 为活前缀的最右子串）。（3）活前缀中全然不包含句柄的任何符号。第一种情况表明：此时某一产生式A的右部已出现在符号栈顶，因此此时相应的分析动作应当是用此产生式进行归约。第二种情况表明：形如A12的产生式的 右部子串已在符号栈栈顶，如1，正期待着从余留的输入串中看到能由推出的 符号串，即期待2 进栈以便能进行归约。故此时分析动作是“移进”当前输入符号。第三种情

19、况则意味着：期望从余留输入串中能看到由某产生式A的右部，即所代表的符号串(即句柄) 。所以此时分析的动作也是读输入符进符号栈。第29页，共85页。 为了刻画在分析过程中，文法的一个产生式右部符号串有多大部分已被识别，我们可在该产生式的右部相应位置上加一个圆点“.”，来指示位置，标明在“.”前的部分已被识别。如上述三种情况，可分别标注为：A.； A1 .2 ; A. 。 我们把右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。特别地，对形如A 的产生式，相应的LR(0)项目表示为A.。显然不同的LR(0)项目，反映了分析过程中符号栈顶的不同情况。例如：产生式SaAcBe对应有六个项目

20、。0 S.aAcBe1 Sa.AcBe2 SaA.cBe3 SaAc.Be4 SaAcB.e5 SaAcBe.第30页，共85页。例如：产生式SaAcBe对应有六个项目。0 S.aAcBe1 Sa.AcBe2 SaA.cBe3 SaAc.Be4 SaAcB.e5 SaAcBe. 一个产生式可对应的项目的数量为它的右部符号串长度加1，值得注意的是对空产生式，即A仅有项目A. 每个项目的含义与圆点的位置有关。概括地说，圆点左边的子串表示在分析过程的某一时刻用该产生式归约时句柄中已识别过的部分，圆点右边的子串表示待识别的部分。 文法的全部LR(0)项目将是构造识别它的所有活前缀的有穷自动机的基础。第

21、31页，共85页。3、LR(0)项目的分类：例：考虑文法GS=(S,A,B, a,b,c,d,P,S),构造其分析表：其中P: (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d解：求该文法的项目集规范族C：为了方便起见，我们在上述文法中引起一个新的开始符号S,且将S S作为第0个产生式添加到文法G中，从而得到了所谓G的拓广文法G。显然L(G)=L(G)，则对于文法G，其LR(0)项目为： 1) S .S 2) S S. 3) S.A 4) SA . 5) S.B 6) SB. 7) A.aAb 8) Aa .Ab 9) AaA .b 10) AaAb

22、. 11) A.c 12) Ac . 13) B.aBd 14) Ba .Bd 15) BaB .d 16) BaBd . 17)B.d 18) Bd .G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d第32页，共85页。如前所述，由于不同的项目反映了分析过程中栈顶的不同情况，因此，我们可根据它们不同的作用，将一个文法的全部LR(0)项目进行分类：移进项目：A a待约项目：A B归约项目： A 接受项目： S S 圆点的左部表示分析过程中的某时刻用该产生式归约时句柄已识别过的部分，圆点右部表示待识别部分第33页，共85页。4、构造识别活

23、前缀的DFA 在LR方法实际过程中，并不是去直接分析符号栈中的符号是否已形成句柄，但它给我们一个启示，我们可以把终结符和非终结符都可看成一个有限自动机的输入符号，每把一个符号进栈时看成已识别过该符号，而状态进行转换（到下一状态），当识别到可归前缀时相当于栈顶已形成了句柄，则认为到达了识别句柄的终态。 在作出文法的全部LR(0)项目之后，现在将用它们来构造识别全部活前缀的DFA。这种DFA中的中每一个状态由若干个LR(0)项目所组成的集合（称为项目集）来表示。 下面以上例中的文法为例来说明构造DFA的方法。 G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B a

24、Bd (6)B d第34页，共85页。首先我们用I0表示这个DFA的初态，它预示着整个分析过程的开始，并且期待着将给定的输入串逐步归约为文法的开始符号S。或者反过来说，我们所期待的是，从使用产生式SS开始，能够逐渐推导出所给定的输入串。因此，我们应将项目S.S列入项目集I0之中。换言之，也就是我们正期待将要扫描的输入串正好就是能由S推导出的任何终结符串。然而，我们不能从输入串中直接读出非终结符号S，因此我们也应将项目S.A和S.B加入I0中。由于A和B同样是非终结符，所以也应将A.aAb和A.c和B.aBb, B.d加入I0中。G：(0)SS (1)S A (2)S B (3)A aAb (4

25、)A c (5)B aBd (6)B d 由于最后加入I0的项目在圆点之后已都是终结符了，故I0已经“封闭”，宣告项目集I0构造结束。 这样，表示初态的项目集I0将由如下项目组成：I0 : S.S, S.A, S.B, A.aAb, A.c, B.aBd, B.d第35页，共85页。I0 : S.S, S.A, S.B, A.aAb, A.c, B.aBd, B.d 我们将LR(0)项目S.S称为项目集I0的基本项目，上述从S.S出发构造项目集I0的过程，可用一个对其基本项目集S .S的闭包运算，即closure(S.S)来表示。一般地，设I为项目集，I的闭包closure(I)的定义为：Cl

26、osure(I)=IA.AGK .Aclosure(I)V*V*故构造closure(I)的算法为：1）I中的每一个项目都属于closure(I);2）若形如K.A的项目属于I，且A是文法的一个产生式， 则关于产生式A的任何形如A.的项目也应加到closure(I)中 （若它们不在closure(I)中）；3）重复上述过程，直至不再有新的项目加入到closure(I)中为 止。 第36页，共85页。 有了初态项目集I0之后，我们来说明如何确定从I0可能转移到的下一状态。设A为一文法符号(AV)，若I0中有圆点位于A左边的项目K .A(其中可能为)，则当分析器从输入串识别出(即移进或归约出)文法

27、符号A后，分析器将进入它的下一状态。设此状态为Ii ，显然Ii中必含有全部形如KA .的项目，我们将这样的项目称为K .A的后继项目。对于每一个文法符号A，如果存在这样的后继项目，则可能不只一个，设其组成集合J，则J中的每个项目都是项目集Ii的基本项目，因此，按照与上面构造项目集I0相类试的讨论，我们有： Ii =closure(J) 为了指明Ii是“I0关于文法符号A的后继状态”这一事实，我们可定义一个状态转移函数： GO(I0,A)=closure(J) = Ii 其中，I是当前状态，A为文法符号，J是I中所有形如K.A的项目之后继项目KA.所组成的集合，而closure(J)就是项目集I

28、（即状态I)关于符号A的后继项目集（即后继状态）。 第37页，共85页。 状态转移函数： GO(I0,A)=closure(J) = Ii 其中，I是当前状态，A为文法符号，J是I中所有形如K.A的项目之后继项目KA.所组成的集合，而closure(J)就是项目集I（即状态I)关于符号A的后继项目集（即后继状态）。即： GO(I,A)=closure(所有形如KA .的项目K .AI) 对于上例，我们有： I1 =GO(I0,S)=closure(SS.) I1 : SS . ; I2 =GO(I0,A)=closure(SA.) I2 :SA . ; I3 =GO(I0,B)=closure

29、(SB.) I3 : SB . ; I4 =GO(I0,a)=closure(Aa . Ab,Ba . Bd)G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d第38页，共85页。I4 : Aa.Ab Ba.Bd A.aAb B.aBd A.c B.d I5=GO(I0,c)=closure(Ac.) I5 : Ac. I6=GO(I0,d)=closure(Bd.) I6 :Bd. 此时，我们求出了I0的全部后继项目集I1, I2,I3,I4,I5,I6,而I1, I2,I3,I5,I6均无后继项目集，仅I4有后继项目集： I7 =GO

30、(I4,A)=closure(AaA.b)=AaA.b I9 =GO(I4,B)=closure(BaB.d)=BaB.d此外，还有： GO(I4,a)=closure(Aa.Ab, Ba.Bd)= I4 GO(I4,c)=closure(Ac.)= I5 GO(I4,d)=closure(Bd.)= I6 这些项目集均不产生新的项目集。另外还有:G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d第39页，共85页。 I8 =GO(I7,b)=closure(AaAb.)=AaAb. I10 =GO(I9,b)=closure(BaBd.

31、)=BaBd.此时I8 ， I10也已无后继项目集，故我们已求出文法GS的全部项目集I0 I10 。 通常我们将这些项目集的全体称为文法GS的LR(0)项目集规范族，并记为C=(I0, I1, I10) 于是，我们所要构成的识别文法GS的全部活前缀的DFA为 M=(C,V,GO, I0,Z) 其中CM的状态集，即文法GS的LR(0)项目集规范族, C=(I0, I1, I10); V M的字母表，即V=S,S,A,B,a,b,c,d； GOM的映射函数，即上面定义的状态转移函数GO； I0M的唯一初态； ZM的终态集， ZC，为规范族中所有含有归约项目的 那些项目集。第40页，共85页。DFA

32、:I0 : S.S S.A S.B A.aAb A.c B.aBd B.dI1 :SS.I2 :SA.I3 :SB.I4 :Aa.Ab Aa.Bd A.aAb A.c B.aBd B.dI8 :A aAb.I7 :A aA.bI9 :B aB.dI10 :B aBd.I5 :Ac.I6 :Bd.ABdbcd dacSABaG：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d图7.4 文法GS项目集规范族第41页，共85页。DFA:即：I0I1I2I3I4I5I6I7I9I8I10SABacdcdABbdG：(0)SS (1)S A (2)S

33、 B (3)A aAb (4)A c (5)B aBd (6)B da图7.5 识别文法GS活前缀的DFA第42页，共85页。5、LR(0)分析表的构造 对于一个文法G的拓广文法G，当识别它的全部活前缀的DFA作出之后，我们可以据此构造相应的LR(0)分析表了。 然而，要注意的是，用前述方法所构造的每一个LR(0)项目集实质上表征了在分析过程中可能出现的一种分析状态；再根据前面对LR(0)项目的分类，项目集中的每一个项目又与某一种分析动作相关联，因此，就要求每一个项目集中的的诸项目应当是相容的。所谓相容，是指在一个项目集中不出现下列的情况：（1）移进项目和归约项目并存，即存在移进归约冲突；（2

34、）多个归约项目并存，即存在归约归约冲突。 如果一个文法G满足上述条件，也就是它的每个LR(0)项目集中都不含有冲突的项目，则称G为LR(0)文法。 显然，只有当一个文法是LR(0)文法时，才能对它构造不含冲突动作的LR(0)分析表来。第43页，共85页。 为了方便起见，我们用整数0，1，2， 表示状态I0 , I1, I2, ;分析表的内容由两部分组成，一部分为动作(ACTION)表，它表示当前状态下所面临的输入符号应做的动作是移进、归约、接受或出错。另一部分为状态转移（GOTO)表，它表示在当前状态下面临文法符号时应转向的下一个状态，相当于识别活前缀的有限自动机DFA的状态转换矩阵。分析表的

35、行标为状态号，动作表的列标为只包含终结符和“#”；状态转移表的列标为非终结符，而将其有关终结符的各列并入到ACTION表的各列中去，也就是把当前状态下面临终结符应作的动作和状态转移用同一数组元素表示，以便节省存储空间。 构造LR(0)分析表的算法为： (1)对于每一项目集Ii中形如A.X的项目，且有GO(Ii,X)=Ij, 若X为一终结符号 a 时，则置ACTIONi,a=Sj; 若X为一非终结符号时，则仅置GOTOi,X=j (2)若Ii中有归约项目A. ,设A为文法第j个产生式，则对 文法的任何终结符和“#”（均记为a）置ACTIONi,a=Rj第44页，共85页。(3)若接受项目SS .

36、属于Ii ,则置ACTIONi,#=acc。(4)在分析表中,凡不能按上述规则填入信息的元素,均置为“出错”。 如上例可构造分析表为： ACTION GOTO a b c d # S A B0 S4 S5 S6 1 2 3 Acc R1 R1 R1 R1 R1 R2 R2 R2 R2 R2 S4 S5 S6 7 9 R4 R4 R4 R4 R4 R6 R6 R6 R6 R6 S8 R3 R3 R3 R3 R3 S1010 R5 R5 R5 R5 R5 构造LR(0)分析表的算法为： (1)对于每一项目集Ii中形如A.X的项目，且有GO(Ii,X)=Ij, 若X为一终结符号 a 时，则置ACTI

37、ONi,a=Sj; 若X为一非终结符号时，则仅置GOTOi,X=j (2)若Ii中有归约项目A. ,设A为文法第j个产生式，则对 文法的任何终结符和“#”（均记为a）置ACTIONi,a=Rj第45页，共85页。6、LR(0)分析器的工作过程 对于一个文法构造了它的LR(0)分析表就可以在LR分析器的总控程序控制下对输入串进行分析，即根据输入串当前符号a和分析栈栈顶状态i查找分析表应采取的动作，对状态栈和符号栈进行相应的操作即移进、归约、接受或报错。具体为：1）若ACTIONi,a=Sj, aVT,则把a移进符号栈，j移进状态栈。2）若ACTIONi,a=Rj，aVT或#，则用第j个产生式归约

38、。并将两个栈的指针减去K(其中K为第j 个产生式右部的串长度），并把产生式的左部符号A压入符号栈，同时用符号对（ Si-k,A)去查GOTO表（其中Si-k为状态栈当前栈顶元素，若GOTOSi-k,A=j,则j压入状态栈，使得两个栈内的元素一样多。3）若ACTIONi,a=Acc,（此时a应为“#”号），则表明分析成功，结束分析。4）若ACTIONi,a=空白，转出错处理。第46页，共85页。7.3 SLR(1)分析 因大多数程序设计语言的文法不能满足LR(0)文法的条件，即使是描述一个变量这样简单的文法也不是LR(0)文法。因此下面将介绍对LR(0)规范族中有冲突的项目集（状态）用向前查 看

39、一个（输入）符号的办法进行处理，以解决冲突。这种分析方法因为只对有冲突的状态才向前查看一个符号，以确定做什么动作，故称这种分析方法为简单的LR(1)分析法，用SLR(1)表示。 假定有一个LR(0)规范族中含有如下项目集(状态)I: I=X.b,A., B.其中,为符号串，bVT, 显然I中含有移进归约和归约归约冲突。那么只要在所有含有A或B的句型中，直接跟在A或B后面的可能终结符集合FOLLOW(A)和FOLLOW(B)互不相交，且都不包含b,即只要满足： FOLLOW(A)FOLLOW(B)=FOLLOW(A)b=FOLLOW(B)b=即：FOLLOW(A)FOLLOW(B)b =第47页

40、，共85页。 那么，当在状态I面临某输入符号为a时，则动作可由下述规定决策：1）若a = b,则移进。2）若a FOLLOW(A),则用产生式A归约。3）若a FOLLOW(B),则用产生式B归约。 一般地，对于LR(0)规范族的一个项目集I可能含有多个移进项目和多个归约项目，我们可假设项目集I中有m个移进项目： A11. b11, A2 2. b22, , Am m. bmm;同时含有n个归约项目：B11. , B2 2. , Bn n. ,只要集合b1, b2,bm和FOLLOW(B1),FOLLOW(B2),FOLLOW(Bn)两两交集都为空，则我们仍可用上述归则来解决冲突： 1）若ab

41、1, b2,bm,则移进。 2）若aFOLLOW(Bi),i=1,n,则用Bi i进行归约。 3）此外，则报错。第48页，共85页。所以，我们只须把构造LR(0)分析表算法中的规则(2)，即：(2)若Ii中有归约项目A. ,设A为文法第j个产生式，则对 文法的任何终结符和“#”（均记为a）置ACTIONi,a=Rj 。修改为：即：(1)对于每一项目集Ii中形如A.X的项目，且有GO(Ii,X)=Ij, 若X为一终结符号a时，则置ACTIONI,a=Sj; 若X为一非终结符号时，则仅置GOTOi,X=j；(2)若归约项目A.属于Ii,设A为文法第j个行产生式，则对任何属于FOLLOW(A)的输入

42、符号a,置ACTIONi,a=Rj；(3)若接受项目S S.属于Ii ,则置ACTIONi,#=acc。(4) 在分析表,凡不能按上述规则填入信息的元素,均置为“出错”。（2）若归约项目A.属于Ii,设A为文法第j个行产生式，则对任何属于FOLLOW(A)的输入符号a,置ACTIONi,a=Rj 。其余的规则不变，就得到了构造SLR(1)分析表的算法。第49页，共85页。例如： 有算术表达式文法GE,构造其LR(0)项目规范簇和SLR(1)分析表。GE: EE+TT TT*FF F(E) i解：1、拓广文法为GS :(0) SEEE+TETTT*FTFF(E)Fi第50页，共85页。2、再求识

43、别G的全部活前缀的DFA（即LR(0)的项目集规范簇）：I0: S.E GO(I0,E)=I1 E.E+T GO(I0,E)=I1 E.T GO(I0,T)=I2 T.T*F GO(I0,T)=I2 T.F GO(I0,F)=I3 F.(E) GO(I0,( )=I4 F.i GO(I0,i )=I5I1: SE. EE.+T GO(I1,+)=I6I2: ET. TT.*F GO(I2,*)=I7I3: TF.第51页，共85页。I4: F(.E) GO(I4,E)=I8 E.E+T GO(I4,E)=I8 E.T GO(I4,T)=I2 T.T*F GO(I4,T)=I2 T.F GO(I

44、4,F)=I3 F.(E) GO(I4,( )=I4 F.i GO(I4,i)=I5I5: Fi.I6: EE+.T GO(I6,T)=I9 T.T*F GO(I6,T)=I9 T.F GO(I6,F)=I3 F.(E) GO(I6,( )=I4 F.i GO(I6,i)=I5I7: TT*.F GO(I7,F)=I10 F.(E) GO(I7,( )=I4 F.i GO(I7,i )=I5I8: F(E.) GO(I8,) )=I11 EE.+T GO(I8,+)=I6I9: EE+T. TT.*F GO(I9,)=I7I10: TT*F.I11: F(E).第52页，共85页。DFA:I0

45、: S.E E.E+T E.T T.T*F T.F F.(E) F.iI2: ET. TT.*FI5: Fi.I1: SE. EE.+TI3: TF.I4: F(.E) E.E+T E.T T.T*F T.F F.(E) F.iI7: TT*.F F.(E) F.iI6: EE+.T T.T*F T.F F.(E) F.iI8: F(E.) EE.+TI11: F(E).I9: EE+T . TT.*FI10: TT*F.i*EF(TiiiT+)*F(+F(E(FT图7.6 识别文法GS活前缀的DFA第53页，共85页。3、解决冲突 可以看到，项目I1， I2， I9中都同时包含有移进项目和归

46、约项目。存在移进归约冲突，因而该文法不属于LR(0)文法，故不能构造LR(0)分析表。 FOLLOW(S)= # FOLLOW(E)= +，)，# FOLLOW(T)= +，*，)，# FOLLOW(F)= +，*，)，# 现在分别考虑上述三个冲突项目中的冲突是否能用SLR(1)方法解决。 在I1中，由于FOLLOW(S)=#).而SE.是唯一的接受项目，所以当且仅当遇到句子的结束符“#”号时才被接受,又因#+=，故I1中的冲突可解决。 对于I2,因FOLLOW(E)=+,),#*=,因此当面临输入符号为“+”，“ ）”或“#”号时，则用产生式ET归约。当面临输入符为“*”时，则移进；其它情况

47、则报错。 对于I9,与I2类似，当面临输入符号为“+”，“）”或“#”时，则用产生式EE+T归约；当面临输入符号为“*”时，则移进，其余情况报错。第54页，共85页。4、构造SLR(1)分析表对于上述三个冲突项目等均可用SLR(1)方法解决冲突。因此该文法是SLR(1)文法。我们可造成其相应的SLR(1)分析表为： i + * （ ） # E T F0 S5 S4 1 2 31 S6 acc2 R2 S7 R2 R23 R4 R4 R4 R44 S5 S4 8 2 35 R6 R6 R6 R66 S5 S4 9 37 S5 S4 108 S6 S11 9 R1 S7 R1 R110 R3 R3

48、 R3 R311 R5 R5 R5 R5第55页，共85页。下面给定输入串i+i*i #，使用上述SLR(1)分析进行分析：步 状态栈 符号栈 输入串 ACTION GOTO1 0 # i+i*i # S52 05 #i +i*i # R6 3 3 03 #F +i*i # R4 24 02 #T +i*i # R2 1 5 01 #E +i*i # S66 016 #E+ i*i # S57 0165 #E+i *i # R6 38 0163 #E+T *i # R4 99 0169 #E+T *i # S710 01697 #E+T* i # S511 016975 #E+T*i # R6

49、 1012 0169710 #E+T*F # R3 913 0169 #E+T # R1 114 01 #E # acc第56页，共85页。本 章 作 业P165：题1，题2(1) 第57页，共85页。7.4 LR(1) 分析 本节介绍比SLR(1)功能更强的LR(1)分析法。例7.4:有下列文法G,构造构造识别文法G的识别活前缀的有限自动机。(0) SS(1) SaAd(2) SbAc(3) Saec(4) Sbed (5) Ae我们首先用SS作为初态集的项目，然后用闭包函数和转换函数构造识别文法G的识别活前缀的有限自动机DFA如图7.7所示。第58页，共85页。图 7.7 LR(0)识别G

50、的活前缀的DFA第59页，共85页。如图7.7所示，可以发现在项目集I5和I7中存在移进和归约冲突。I5：SaecI7：SbedAe Ae而归约项目左部非终结符的FOLLOW(A)=c,d在I5中，FOLLOW(A)c=c,dc在I7中，FOLLOW(A) d=c,dd因此I5，I7中冲突不能用SLR(1)方法解决。只能考虑用下面将要介绍的LR(1)方法解决。 第60页，共85页。由于用SLR(1)方法解决动作冲突时，对于归约项目A，只要当前面临输入符为aFOLLOW(A)时，就确定采用产生式A进行归约，但是如果栈中的符号串为，归约后变为A，再移进当前符a，则栈里变为Aa，而实际上Aa未必为文

51、法规范句型的活前缀。 现在我们再看图7.7在I5，I7项目集中的移进-归约冲突，不能用SLR(1)方法解决的原因如下：I5： Saec 因 AeRRRS SaAdaedRRS Saec(0) S S(1) SaAd(2) SbAc(3) Saec(4) Sbed(5) Ae 这两个最右推导已包括了活前缀为a的所有句型，因此，不难看出对活前缀ae来说，当面临输入符号为c时应移进，面临d时应用产生式Ae归约。因为 RRS SaAc第61页，共85页。这说明从S出发不能用最右推导（规范推导）推出aAc句型，所以aAc不是该文法的规范句型。回顾LR分析过程，若输入符号串是所给文法的句子，那么分析过程的

52、任何时刻在文法符号栈中的符号和剩余的输入串符号合起来总是构成该文法的规范句型。 这也说明了并不是FOLLOW(A)的每个元素在含A的所有句型中在A的后面都会出现，例中d只在规范句型aAd中A的后面出现，因此面临输入符为d才应归约。再看在I7中。I7： Sbed 而 AeRRRSS bAc bec(0) S S(1) SaAd(2) SbAc(3) Saec(4) Sbed(5) AeRRS Sbed 这两个最右推导，包含了活前缀为b的所有句型，因此FOLLOW(A)中的c只能跟在句型bAc中A的后面，这样在I7中当面临输入符为c时才能归约，根据项目集的构造原理有：第62页，共85页。若AB项目

53、集I，则B(B为一产生式)也包含在I中。不妨考虑，把FIRST()作为用产生式B归约的搜索符，称为向前搜索符，作为归约时查看的符号集合，用以代替SLR(1)分析中的FOLLOW集，把此搜索符号的集合也放在相应项目的后面，这种处理方法即为LR(1)方法。 其原因是：一个非终结符号的FOLLOW集合，包含了所有含该非终结符的任一句型中在该非终结符后的向前搜索符集合。如在项目集I中有项目：AB， B。当分析经过若干步后在项目集J中含有项目B需要用产生式B归约，这时向前查看的符号集合是FIRST()，而FIRST() FOLLOW（B）。第63页，共85页。7.4.1 LR(1)项目集族的构造 一个L

54、R(1)项目可以看成两个部分组成，一部分和LR(0)项目相同部分我们称它为心，另一部分为向前搜索符集合。如让SS，#属于初始项目集中，把#号作为向前搜索符，表示活前缀为(若是有关S产生式的某一右部)要归约成S时，必须面临输入符为#号才行。因此对初始项目SS，#求闭包后再用转换函数逐步求出整个文法的LR(1)项目集族。具体构造步骤如下： (1) 构造LR(1)项目集的闭包函数。a) 项目集I的任何项目都属于CLOSURE(I)；b) 若有项目AB,a属于CLOSURE(I)，B是文法中的产生式，V*，bFIRST(a)，则B,b也属于CLOSURE(I)中。c) 重复b)直到CLOSURE(I)

55、不再增大为止。 第64页，共85页。(2) 转换函数的构造 LR(1)转换函数的构造与LR(0)的相似，GO(I,X)CLOSURE(J)其中I是LR(1)的项目集，X是文法符号：J=任何形如AX,a的项目|AX,aI现给出直接由产生式构造识别活前缀的DFA的LR（1）项目集的闭包CLOSURE的算法：function CLOSURE (I)； /* I是项目集*/ J:= I；repeat 对J中的每个项目AB,a和产生式 B； ，V*；b FIRST(a), 若B，b不在J中Do 将B，b加到J中 until 再没有项目加到J中return J； 第65页，共85页。对项目AB,a，计算B

56、的向前搜索符时，应为FIRST(a)，这是因为V*，即可能为，而a是用产生式AB归约时的向前搜索符，而现在为，就等于用AB归约，向前搜索符为a，那么用AB归约前，必须先用产生式B归约成B，因此，B的向前搜索符时也应为a。对文法G的LR(1)项目集族的构造仍以SS,#为初态集的初始项目，然后对其求闭包和转换函数，直到项目集不再增大。 也就是对状态I经过符号X后转向状态J，求出J的基本项目后，对基本项目求闭包即为CLOSURE(J)。现在我们可以对上面7.4例中不能用SLR(1)方法解决I5，I7中移进-归约冲突的文法构造它的LR(1)项目集规范族如下：第66页，共85页。I0：SS,# SaAd

57、,# SbAc,# Saec,#Sbed,#I1：SS,#I2：SaAd,#Saec,# Ae,dI3：SbAc,# Sbed,# Ae,cI4： SaAd,#I5： Saec,# Ae,d I6： SbAc,# I7： Sbed,# Ae,c I8： SaAd,# I9： Saec,# I10：SbAc,# I11：Sbed,# (0) S S(1) SaAd(2) SbAc(3) Saec(4) Sbed(5) Ae第67页，共85页。这样LR(1)方法构造的项目集规范族在项目集I5和I7中的移进-归约冲突，由于归约项目的搜索符集合与移进项目的待移进符号不相交，所以在I5中，当面临输入符为

58、d时归约，为c时移进，而在I7中则当面临输入符为c时归约，为d时移进，冲突已全部可以解决，因此该文法为LR(1)文法。 第68页，共85页。7.4.2 LR(1)分析表的构造 由于一个LR(1)项目可以看成两个部分组成，一部分和LR(0)项目相同部分我们称它为心，另一部分为向前搜索符集合，因而LR(1)分析表的构造与LR(0)分析表的构造大部分相同，仅对归约项目的归约动作取决于该归约项目的向前搜索符集，只有当面临输入符属于向前搜索符的集合，才做归约动作，其它情况均出错。具体构造过程如下：若已构造出某文法的LR(1)项目集族C。CI0,I1,In，其中Ik的k为分析器的状态，则动作ACTION表

59、和状态转换GOTO表构造方法如下： 第69页，共85页。(1) 若项目Aa,b属于Ik，且GO（Ik,a）=Ij，其中aVT,则置ACTIONk,a=Sj。其Sj的含义是把输入符号a和状态j分别移入文法符号栈和状态栈。(2) 若项目A,a属于Ik，则置ACTIONk,a= rj 其中aVT，rj 的含义为把当前栈顶符号串归约为A(即用产生式A归约)。j为在文法中对产生式A的编号。(3) 若项目SS，#属于Ik，则置ACTIONk，#acc，表示接受。(4) 若GO(Ik，A)Ij，其中AVN，则置GOTOk,Aj。表示转入j状态，置当前文法符号栈顶为A，状态栈顶为j。(5) 凡不能用规则(1)

60、(4)填入分析表中的元素，均置“报错标志”。我们用“空白”表示之。 LR(1)分析表的构造除 (2) 外，其余同LR(0)或SLR(1)。即 若项目A,a属于Ik，则置ACTIONk,a= rj。也就是归约时向前查看的符号为向前搜索符。 第70页，共85页。根据上述规则，我们对7.4例中文法的LR(1)项目集族构造其相应的LR(1)分析表如表7.10。 状态ACTIONGOTOabcde#SA01234567891011 S2S3.S9S10r5.S8r5.S11.S5S7.acc.r1r3r2r41. 46表 7.10 LR(1)分析表 第71页，共85页。由表7.10可以看出对LR(1)的