Dknuth首先提出了LR(K)文法及LR(K)分析技术.ppt

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+

2、k#,（续页）,LR(0) 表示在每一步分析时都不用向前输入符号 LR(1) 表示在每一步分析时都向前看一个输入符号来决定当 前的动作。 SLR(1) 表示简单的LR(1)，即只在动作不唯一的地方向前看一 个符号，在动作唯一时则不向前看输入符号。,6.1 LR分析概论,一 .LR分析器的逻辑结构及工作过程 从逻辑上来说，一个LR分析器如图：,即一个LR(k)分析器主要由：总控程序，分析栈（状态栈和符号栈）输入队列和分析表组成。一般来说所有LR分析器的总控程序基本上是大同小异。只有分析表各不相同。一般主要讨论三种不同的分析表的构造方法。,第一种称为规范LR分析表构造法。用此法构造的分析表功能最强

3、而且也适合于很多文法，但实现代价比较高。,第二种称为简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。但SLR分析表的功能太弱，而且对某些文法可能根本就构造不出相应的SLR分析表。,第三种称为向前LR（即LALR）分析表构造法。这种方法构造的分析表功能介于规范LR分析表SLR分析表之间。这种表适用于绝大多数程序语言的文法。而且也可以设法有效的实现。,二、LR 分析器的分析过程如下：,1.首先将初始状态 S0及句子的左界限#分别压入状态栈和符号栈中。,则用栈顶状态Sm和当前扫描符 ai组成符号对（ Sm, ai)去查 分析动作表，根据ACTIONSm, ai的指示完成相应的分析动作。

4、 表中每一表元素所规定的动作仅能是下列四种动作之一：,2.设在分析中的某一步，分析栈及余留的输入串为如下格局： S0S1 Sm ai ai+1an #X1 Xm ,（1） ACTIONSm, ai= Sm+1 （移进） 表明句柄尚未在栈顶形成，此时正期待移进输入符号以便形成 句柄。故将当前的输入符号和表元素Sm+1分别压入栈中，有,（2） ACTIONSm, ai= Rj (归约） 表明此时应按文法的第j个产生式A Xm-k+1Xm-k+2 Xm 进行归约。即栈顶符号串Xm-k+1Xm-k+2 Xm已成为当前句型的句 柄。所谓按第j个产生式归约，就是将分析栈中从顶向下的k个符 号退栈，然后将文

5、法符号A压入符号栈中。此时分析的格局为： S0S1 Sm-k ai ai+1an # # X1 Xm-k A ,然后以（ Sm-k,A)去查状态转移表，设GOTOSm-k,A= Sl ,则将此新状态压入状态栈中，则有如下格局： S0S1 Sm-k Sl ai ai+1an # # X1 Xm-k A ,（3） ACTIONSm, ai=acc （接受）,表明当前的输入串已被成功地分析完毕，应停止分析器的工作。,其中Z为文法开始符号 S为使ACTIONS ，#=acc的 唯一状态（接受状态）,（4） ACTIONSm, ai=ERROR（空白）。 表明当前的输入串中含有错误，也应终止当前的分析工

6、作。转出错处理。,3. 重复上述第2步的工作，直到分析栈顶出现“接受状态”或“出错状态“为止。对接受状态，分析栈的格局为： S0 S # # Z ,例：,有文法GS:1：SaAcBe 2：Ab 3：AAb 4：Bd 其ACTION表和GOTO表为： 考察对输入串abbcde# 的分析过程。,对输入串abbcde# 的分析过程为：,6.2 LR(0) 分析表的构造,为了给出构造LR(0)分析表的算法，引出一些术语： 1、规范句型的活前缀 前缀：一个符号串的前缀是指该串的任意首部（包括）。,例如 abc的前缀有： ,a,ab,abc abcd的前缀有：,a,ab,abc,abcd 由此可知，对于符

7、号串 而言，其前缀的数量为+1。 例：有文法GS:SaAcBe1 Ab2 这里在每条产生式后加上了产生 AAb3 式的序号i当进行推导时把序号 Bd4 带上，以便说明问题。 对输入串abbcde进行推导如下（最右推导）： S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 由此可知，abbcde是该文法的句子。由于LR方法是自底向上的 分析，故应采用归约。,最左归约为： ab2b3cd4e1 用2式归约, aAb3cd4e1 3, aAcd4e1 4, aAcBe1 1, S,其中表示归约符,从归约的过程可看出，每次归约时，归约前和归约后的被 归约部分与剩余部分合起来仅

8、构成文法的规范句型，而用哪个 产生式归约仅取决于当前句型的前面部分；X1X2Xnp 其中Xi为文法的符号，p为第p个产生式序号。 如上例中每次归约前句型的前面部分为： ab2 aAb3 aAcd4 acABe1,我们把规范句型的这种前端部分的串称为可归前缀。实际上，它们恰好是符号栈栈顶形成句柄时符号栈中的内容。,SaAcBe1 Ab2 AAb3 Bd4,这是因为一旦句型的句柄在符号栈顶形成，将会立即被归约 之故。所以我们将把规范句型具有上述性质（即不含句柄之后的 任何符号）的前缀称之为可归前缀。 对各规范句型有前缀：,ab2b3cd4e1 ,a,ab aAb3cd4e1 ,a,aA,aAb a

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

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

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

12、生式SaAcBe对应有六个项目。,0 S.aAcBe 1 Sa.AcBe 2 SaA.cBe 3 SaAc.Be 4 SaAcB.e 5 SaAcBe.,例如：产生式SaAcBe对应有六个项目。,0 S.aAcBe 1 Sa.AcBe 2 SaA.cBe 3 SaAc.Be 4 SaAcB.e 5 SaAcBe.,一个产生式可对应的项目的数量为它的右部符号串长度加1，值得注意的是对空产生式，即A仅有项目A. 每个项目的含义与圆点的位置有关。概括地说，圆点左边的子串表示在分析过程的某一时刻用该产生式归约时句柄中已识别过的部分，圆点右边的子串表示待识别的部分。 文法的全部LR(0)项目将是构造识别

13、它的所有活前缀的有穷自动机的基础。,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)

14、AaA .b 10) AaAb . 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,如前所述，由于不同的项目反映了分析过程中栈顶的不同情况，,因此，我们可根据它们不同的作用，将一个文法的全部LR(0)项目 进行分类： 对于形如A. 的项目，因为它表明右部符号串已出现在栈顶，此 时相应的分析动作应当是按此产生式进行归约，故我们将此种项目 称为归约项目。上例中的项目2) ,4),6),10

15、),12),16),18)均是归约项目。 其中项目2)显然仅用于分析过程中的最后一次归约，它表明整个分 析过程已成功地完成，所以我们特别地将它称为接受项目。对于拓 广文法而言，接受项目是唯一的。由此可看出到我们为什么要首先 将文法拓广的原因。 对于形如A. X 的项目（其中 可以是 ），根据前面的讨论 可知，当X为终结符时，相应的分析动作应将当前的输入符号移入 栈中，故我们将此种项目称为移进项目。上例中的项目7) ,9), 11), 13) ,15) ,17)就都是移进项目； 当X为非终结符时，由于我们期待着从余留的输入符中进行归 约后而得到X，因此将此类项目称为待约项目。上例中的1), 3)

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

17、示这个DFA的初态，它预示着整个分析过程的开始，并且期待着将给定的输入串逐步归约为文法的开始符号S。或者反过来说，我们所期待的是，从使用产生式SS开始，能够逐渐推导出所给定的输入串。因此，我们应将项目S.S列入项目集I0 之中。换言之，也就是我们正期待将要扫描的输入串正好就是能由S推导出的任何终结符串。然而，我们不能从输入串中直接读出非终结符号S，因此我们也应将项目S.A和S.B加入I0中。由于A 和B同样是非终结符，所以也应将A.aAb和A.c和B.aBb, B.d加入I0中。由于最后加入I0的项目在圆点之后已都是终结符 了，故I0已经“封闭”，宣告项目集I0构造结束。这样，表示初态的 项目

18、集I0将由如下项目组成： 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)的定义为：,Closure(I)=IA.AGK .Aclosure(I)V*V*,故构造closure(I)的算法为： 1）I中的每一个项目都属于closure(I); 2）若形如K.A的项目属于I，且A是文法的一个产生式， 则关于产生式A的任何形如A.的项目也应加到c

19、losure(I)中（若 它们不在closure(I)中）； 3）重复上述过程，直至不再有新的项目加入到closure(I)中为止。,有了初态项目集I0之后，我们来说明如何确定从I0可能转移到 的下一状态。设A为一文法符号(AV)，若I0中有圆点位于A左边 的项目K .A(其中可能为)，则当分析器从输入串识别出(即 移进或归约出)文法符号A后，分析器将进入它的下一状态。设此 状态为Ii ，显然Ii中必含有全部形如KA .的项目，我们将这样 的项目称为K .A的后继项目。对于每一个文法符号A，如果 存在这样的后继项目，则可能不只一个，设其组成集合J，则J中的 每个项目都是项目集Ii的基本项目，因

20、此，按照与上面构造项目集 I0相类试的讨论，我们有： Ii =closure(J),为了指明Ii是“I0关于文法符号A的后继状态”这一事实，我们 可定义一个状态转移函数：GO(I,A)=closure(J) 其中，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(S

21、A.) I2 :SA.; I3 =GO(I0,B)=closure(SB.) I3 : SB.; I4 =GO(I0,a)=closure(Aa.Ab,Ba.Bd),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(I4,A)=closure(AaA.b)=AaA.b I9 =GO

22、(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 这些项目集均不产生新的项目集。另外还有:,I8 =GO(I7,b)=closure(AaAb.)=AaAb. I10 =GO(I9,b)=closure(BaBd.)=BaBd. 此时I8 ， I10也已无后继项目集，故我们已求出文法GS的全部 项目集I0 I10 。 通常我们将这些项目集的全体称为文法GS的LR(0)项目集规范 族，并记为C=(I0,

23、I1, I10) 于是，我们所要构成的识别文法GS的全部活前缀的DFA为 M=(C,V,GO, I0,Z) 其中CM的状态集，即文法GS的LR(0)项目集规范族I0 I10 V M的字母表，即V=S,S,A,B,a,b,c,d； GOM的映射函数，即上面定义的状态转移函数GO； I0M的唯一初态； ZM的终态集， ZC为规范族中所有含有归约项目的 那些项目集。,DFA:,DFA,即：,4、LR(0)分析表的构造,对于一个文法G的拓广文法G，当识别它的全部活前缀的DFA 作出之后，我们可以据此构造相应的LR(0)分析表了。 然而，要注意的是，用前述方法所构造的每一个LR(0)项目集 实质上表征了

24、在分析过程中可能出现的一种分析状态；再根据前 面对LR(0)项目的分类，项目集中的每一个项目又与某一种分析 动作相关联，因此，就要求每一个项目集中的的诸项目应当是相 容的。所谓相容，是指在一个项目集中不出现下列的情况： （1）移进项目和归约项目并存，即存在移进归约冲突； （2）多个归约项目并存，即存在归约归约冲突。 如果一个文法G满足上述条件，也就是它的每个LR(0)项目集 中都不含有冲突的项目，则称G为LR(0)文法。 显然，只有当一个文法是LR(0)文法时，才能对它构造不含冲 突动作的LR(0)分析表来。,为了方便起见，我们用整数0，1，2， 表示状态I0 , I1, I2, ;分析表的内

25、容由两部分组成，一部分为动作(ACTION)表，它表示当前状态下所面临的输入符号应做的动作是移进、归约、接受或出错。另一部分为状态转移（GOTO)表，它表示在当前状态下面临文法符号时应转向的下一个状态，相当于识别活前缀的有限自动机DFA的状态转换矩阵。分析表的行标为状态号，动作表的列标为只包含终结符和“#”；状态转移表的列标为非终结符，而将其有关终结符的各列并入到ACTION表的各列中去，也就是把当前状态下面临终结符应作的动作和状态转移用同一数组元素表示，以便节省存储空间。,构造LR(0)分析表的算法为： (1)对于每一项目集Ii中形如A.X的项目，且有GO(Ii,X)=Ij, 若X为一终结符

26、号 a 时，则置ACTIONi,a=Sj; 若X为一非终结符号时，则仅置GOTOi,X=j (2)若Ii中有归约项目A. ,设A为文法第j个产生式，则对 文法的任何终结符和“#”（均记为a）置ACTIONi,a=Rj,(3)若接受项目SS .属于Ii ,则置ACTIONi,#=acc。 (4)在分析表中,凡不能按上述规则填入信息的元素,均置为“出错”。 如上例可构造分析表为：,ACTION GOTO a b c d # S A B 0 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

27、R6 R6 R6 R6 S8 R3 R3 R3 R3 R3 S10 10 R5 R5 R5 R5 R5,5、LR(0)分析器的工作过程,对于一个文法构造了它的LR(0)分析表就可以在LR分析器的总 控程序控制下对输入串进行分析，即根据输入串当前符号a和分析 栈栈顶状态i查找分析表应采取的动作，对状态栈和符号栈进行相 应的操作即移进、归约、接受或报错。具体为： 1）若ACTIONi,a=Sj, aVT,则把a移进符号栈，j移进状态栈。 2）若ACTIONi,a=Rj，aVT或#，则用第j个产生式归约。并将 两个栈的指针减去K(其中K为第j 个产生式右部的串长度），并 把产生式的左部符号A压入符号

28、栈，同时用符号对（ Si-k,A)去查 GOTO表（其中Si-k为状态栈当前栈顶元素，若GOTOSi-k,A=j, 则j压入状态栈，使得两个栈内的元素一样多。 3）若ACTIONi,a=Acc,（此时a应为“#”号），则表明分析成功， 结束分析。 4）若ACTIONi,a=空白，转出错处理。,6.3 SLR(1)分析,因大多数程序设计语言的文法不能满足LR(0)文法的条件，即 使是描述一个变量这样简单的文法也不是LR(0)文法。因此下面 将介绍对LR(0)规范族中有冲突的项目集（状态）用向前查 看一 个（输入）符号的办法进行处理，以解决冲突。这种分析方法 因为只对有冲突的状态才向前查看一个符号

29、，以确定做什么动作 ，故称这种分析方法为简单的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)b =,那么，当在状态I面临某输入符号为a时，则动作可由下述规定决策： 1）若a = b,则移进。 2）若a FOLLOW(A),则用产生式A归约。 3）若a FOLLOW(B),则用

30、产生式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）若ab1, b2,bm,则移进。 2）若aFOLLOW(Bi),i=1,n,则用Bi i进行归约。 3）此外，则报错。,所以，我们只须把构造LR(0)分析表算法中的规则(2)，即： (

31、2)若Ii中有归约项目A. ,设A为文法第j个产生式，则对 文法的任何终结符和“#”（均记为a）置ACTIONi,a=Rj 。 修改为：,即： (1)对于每一项目集Ii中形如A.X的项目，且有GO(Ii,X)=Ij, 若X为一终结符号a时，则置ACTIONI,a=S; 若X为一非终结符号时，则仅置GOTOi,X=j； (2)若归约项目A.属于Ii,设A为文法第j个行产生式，则 对任何属于FOLLOW(A)的输入符号a,置ACTIONi,a=Rj； (3)若接受项目S S.属于Ii ,则置ACTIONi,#=acc。 (4) 在分析表,凡不能按上述规则填入信息的元素,均置为“出错”。,（2）若归

32、约项目A.属于Ii,设A为文法第j个行产生式，则对任何属于FOLLOW(A)的输入符号a,置ACTIONi,a=Rj 。 其余的规则不变，就得到了构造SLR(1)分析表的算法。,例如： 有算术表达式文法GE,构造其LR(0)项目规范簇和SLR(1)分析表。GE: EE+TT TT*FF F(E) i,解：1、拓广文法为GS : (0) SE EE+T ET TT*F TF F(E) Fi,2、再求识别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,I1: SE. EE.+T GO(I1,+)=I6,I2: ET. TT.*F GO(I2,*)=I7,I3: TF.,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,F)=I2 T.F GO(I4,F)=I3 F.(E) GO(I4,( )=I4 F.i GO(I4,i)=I5,I5: Fi.,I6: EE+.T GO(I6,T)=I9 T.T*F GO(I6,T)=I9 T.F GO(I6,F)=I3 F.(E)