编译原理第7章

1、第第7 7章章 分析法分析法LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。本章主要介绍LR(K)分析技术L从左到右扫描输入串R构造一个最右推导的逆过程K向右顺序查看输入串的K个(K0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约7.1 7.1 LRLR分析概述分析概述 一个LR分析器由3个部分组成：(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将也不同，分析表又可分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可

2、用二维数组表示。(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。分析器的动作就是由栈顶状态和当前输入符号所决定。LRLR分析器工作过程示意图如图所示。分析器工作过程示意图如图所示。总控程序outputInput#S1XmS1X1S0#栈状态文法符号ACTIONGOTOLR分析表产生式表SP其中其中SPSP为栈指针，为栈指针，SiSi为状态栈，为状态栈，XiXi为文法符号栈。为文法符号栈。状态转换表用状态转换表用GOTOGOTOS Si i,X,XS Sj j 表示，规定当栈顶状态表示，规定当栈顶状态为为S Si i遇到当前文法符

3、号为遇到当前文法符号为X X时应转向状态时应转向状态S Sj j。X X为终结符为终结符或非终结符。或非终结符。ACTIONACTIONSiSi,a,a规定了栈顶状态为规定了栈顶状态为SiSi时遇到输入符号时遇到输入符号a a应应执行的动作。动作有执行的动作。动作有4 4种可能：种可能： 移进移进 归约归约 接受接受accacc 报错报错 移进：移进：把Sj=GOTOSi，a移入到状态栈，把a移入到文法符号栈。其 中i，j表示状态号。 归约：当在栈顶形成句柄为时，则用归约为相应的非终结符A， 即文法中有A的产生式，若的长度为r(即|=r)，则从 状态栈和文法符号栈中自栈顶向下去掉r个符号，即栈

4、指针SP 减去r。并把A移入文法符号栈内，Sj=GOTOSi，A移进状态， 其中Si为修改指针后的栈顶状态。 接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符 号串已结束即当前输入符是#，则为分析成功。 报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则 报错，说明输入串不是该文法能接受的句子。7.2 7.2 LR(0)LR(0)分析分析 LR(0)分析表构造的思想和方法是构造其它LR分析表的基础。我们回顾在第6章中曾给出例6.1文法GS为：(1) SaAcBe(2) Ab(3) AAb(4) Bd文法文法GS：(1) S aAcBe(2) A b(3) A Ab(

5、4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进A 3） #ab bcde# 归约归约(Ab) 4） #aA bcde# 移进移进A 5） #aAb cde# 归约归约(AAb) 6） #aA cde# 移进移进 7） #aAc de# 移进移进B 8） # aAcd e# 归约归约(Bd) 9） #aAcB e# 移进移进11） #S # 接受接受S10） #aAcBe # 归约归约符号串符号串abbcdeabbcde是否是是否是GSGS的子的子对输入串对输入串abbcde#的移进的移进-

6、规约分析过程规约分析过程SaAcBe aAcde aAbcde abbcde对输入串abbcde#用自底向上归约的方法进行分析，当归约到第5步时栈中符号串为#aAb，我们采用了产生式(3)进行归约而不是用产生式(2)归约，而在第3步归约时栈中符号串为#ab时却用产生式(2)归约，虽然在第2步和第5步归约前栈顶符号都为b，但归约所用产生式却不同，为什么？其原因在于已分析过的部分在栈中的前缀不同，为了说明这个问题并引进一些概念和术语。1、文法的规范句型的活前缀和可归前缀的概念字的前缀是指该字的任意首部。例：字abc 的前缀有 ，a,ab,abc在LR分析工作过程中的任何时候，栈里的符号（自栈底而向

7、上）X1X2Xn应该构成活前缀，把输入串的剩余部分配上就成为规范句型。所谓活前缀：是指规范句型的一个前缀，这种前缀不所谓活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。含句柄之后的任何符号。可归前缀：每次归约动作之前的活前缀称为可归前缀问问abbcdeabbcde是否是它的句子？是否是它的句子？最右推导过程最右推导过程S S aAcBe1 aAcBe1 aAcd4e1 aAcd4e1 aAb3cd4e1aAb3cd4e1ab2b3cd4e1ab2b3cd4e1归约前句型的前缀（可归前缀）归约前句型的前缀（可归前缀） 归约前可在栈里的规范句型归约前可在栈里的规范句型( (不含句柄

8、之不含句柄之后后 的任何符号的前缀称为活的任何符号的前缀称为活前缀）前缀）ab2ab2 , ,a,aba,abaAb3aAb3 , ,a,aA,aAba,aA,aAbaAcd4aAcd4 , ,a,aA,aAc,aAcda,aA,aAc,aAcdaAcBe1aAcBe1 , ,a,aA,aAc,aAcB,aAcBea,aA,aAc,aAcB,aAcBe例：文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d活前缀与句柄之间的关系有三种情况：（1）活前缀已经含有句柄的全部符号,表明产生式表明产生式AA的右部的右部已出现在栈顶已出现在栈顶（2）活前缀只含有句柄的部分符号

9、,表明表明AA1 12 2的右的右部子串部子串1 1已出现在栈顶，期待从输入串中看到已出现在栈顶，期待从输入串中看到2 2推出的推出的符号符号（3）活前缀不含句柄的任何符号,此时期望此时期望AA的右部的右部所推出的符号串所推出的符号串为了刻划这种分析过程中文法G中的每个产生式的右部已有多大部分被识别（已经出现在栈顶）我们在产生式某处加上圆点“.”来指示位置，对上述三种情况标出圆点的产生式：（1）A . (2) A 1. 2 (3) A . 构造构造LR(0)项目集规范族项目集规范族(1) LR(0)项目项目在文法在文法G中每个产生式的右部适当位置添加一个圆点构中每个产生式的右部适当位置添加一个

10、圆点构成项目。成项目。 例：例：A xyz 对应对应4个项目：个项目： A.xyz Ax.yz Axy.z Axyz. 如：如：SaAdSaAd 对应的项目：对应的项目： S.aAdS.aAd Sa .Ad Sa .Ad SaASaA .d .d SaAdSaAd . . 对于对于A的的LR(0)LR(0)项目只有项目只有A注意：注意：（1）凡是圆点在最右端的项目，称为归约项目。）凡是圆点在最右端的项目，称为归约项目。 如：如：Axyz. 用用r表示归约表示归约（2）对文法开始符号的归约项目称为接受项目，用）对文法开始符号的归约项目称为接受项目，用acc表示表示 如：如：S . S 是开始符是

11、开始符（3）形如）形如A . B 的项目称为待归约项目，即表明所对的项目称为待归约项目，即表明所对 应状态正等待分析完非终结符应状态正等待分析完非终结符B B所能推出的串归约成所能推出的串归约成B B， 才能分析才能分析A A的右部的右部（4 4）形如形如A . a 的项目称为移进项目，即终结符的项目称为移进项目，即终结符a a移进移进 符号栈。移进用符号栈。移进用S S表示表示2) 构造识别活前缀的构造识别活前缀的NFA如果把文法的所有产生式的项目都引出，每个项目都为NFA的一个状态。将文法G拓展为G,目的是为了使文法有且仅有一个接受项目。 例 ：文法G： EaA|bB AcA|d BcB|

12、d拓展后变为：(1)SE(2)EaA(3)EbB(4)A cA(5)A d(6)B cB (7) B d构造该文法的项目有：1 SE 10. Ad2 SE 11. EbB3 EaA 12. EbB4 EaA 13. EbB5 EaA 14. BcB6 AcA 15. BcB7 AcA 16. BcB8 AcA 17. Bd9 Ad 18. Bd识别活前缀的NFA 1 SE 10. Ad2 SE 11. EbB3 EaA 12. EbB4 EaA 13. EbB5 EaA 14. BcB6 AcA 15. BcB7 AcA 16. BcB8 AcA 17. Bd9 Ad18. Bd对于图中识别活

13、前辍的NFA我们可以利用第4章讲过的子集法将其确定化。对确定化后的DFA如果把每个子集中所含状态集对应的项目写在新的状态中，结果见P132如7.8图所示。(3) (3) LR(0)LR(0)项目集规范族的构造项目集规范族的构造对于构成识别一个文法活前缀的对于构成识别一个文法活前缀的DFADFA项目集项目集( (状态状态) )的全的全体称为这个文法的体称为这个文法的LR(0)LR(0)项目集规范族，我们可以分析图项目集规范族，我们可以分析图7.87.8中每个状态中项目集的构成，不难发现如下规律：中每个状态中项目集的构成，不难发现如下规律：若状态中包含形如若状态中包含形如AABB的项目，则形如的项

14、目，则形如BB的项目的项目也在此状态内。例如：也在此状态内。例如：0 0状态中项目集为状态中项目集为 SSE E，EEaAaA, , EEbBbB 。若文法若文法G G已拓广为已拓广为GG，而而S S为文法为文法G G的开始符号，拓广后增的开始符号，拓广后增加产生式加产生式SS,SS,如果如果I I是文法是文法GG的一个项目集，定义和构的一个项目集，定义和构造造I I的闭包的闭包CLOSURE(I)CLOSURE(I)如下：如下：a) Ia) I的项目均在的项目均在CLOSURE(I)CLOSURE(I)中。中。b) b) 若若AABB属于属于CLOSURE(I)CLOSURE(I)，则每一形

15、如则每一形如BB 的项目也属于的项目也属于CLOSURE(I)CLOSURE(I)。c) c) 重复重复b)b)直到不出现新的项目为止。即直到不出现新的项目为止。即CLOSURE(I)CLOSURE(I)不不 再扩大。再扩大。 由此，我们可以很容易构造出初态的闭包，即由此，我们可以很容易构造出初态的闭包，即 S SS S 属于属于I I，再按上述三点求其闭包。再按上述三点求其闭包。有了初态的项目集，其它状态的项目集如何求出有了初态的项目集，其它状态的项目集如何求出？由于识别活前缀的DFA的每个状态是一个项目集，项目集中的每个项目都不相同，每个项目圆点后的符号不一定相同，因每个项目圆点后的符号不

16、一定相同，因而对每个项目圆点移动一个位置后，箭弧上的标记也不会完而对每个项目圆点移动一个位置后，箭弧上的标记也不会完全相同，这样，对于不同的标记将转向不同的状态。全相同，这样，对于不同的标记将转向不同的状态。例如初态SE，EaA,EbB对第一个项目圆点右移一个位置后变为SE箭弧标记应为E，对第二个项目EaA，圆点右移一个位置后，项目变为EaA，箭弧标记为a,同样第三个项目为圆点右移一个位置后变为EbB，箭弧标记为b，显然，初态可发出三个不同标记的箭弧，因而转向三个不同的状态，也就由初态派生出三个新的状态，对于每个新的状态我们又可以利用前面的方法，若圆点后为非终结符则可对其若圆点后为非终结符则可

17、对其求闭包，得到该状态的项目集。圆点后面为终结符或在一个求闭包，得到该状态的项目集。圆点后面为终结符或在一个产生式的最后，则不会再增加新的项目。产生式的最后，则不会再增加新的项目。由前面可知LR(0)项目集规范族的项目类型分为四种：a) 移进项目b) 归约项目c) 待约项目d) 接受项目一个项目集中可能包含以上四种不同的项目，但是一个项目集中不能有下列情况存在：1 1) ) 移进和归约项目同时存在：移进和归约项目同时存在：形如：AaB由于这时面临输入符号为a时不能确定移进a还是把归约为B，因为LR(0)分析是不向前看符号，所以对归约的项目不管当前符号是什么都应归约。对于在一个项目集中同时存在移

18、进和归约项目时称该状态含有移进-归约冲突。2) 2) 归约和归约项目同时存在。归约和归约项目同时存在。形如：AB因这时不管面临什么输入符号都不能确定归约为A，还是归约为B，对于在一个项目集中同时存在两个以上归约项目时称该状态含有归约-归约冲突。对一个文法的对一个文法的LR(0)LR(0)项目集规范族不存在移进项目集规范族不存在移进- -归约，或归约归约，或归约- -归归约冲突时，称这个文法为约冲突时，称这个文法为LR(0)LR(0)文法。文法。构造上例文法的LR(0)分析表见P136表7.3所示对输入串bccd#的LR(0)分析过程见P136表7.4所示按上述方法建立识别活前缀的DFA结果与7

19、.8图相同例例: :GS为为: S a A c B e A b A Ab B d 1)构造识别活前缀的构造识别活前缀的DFA 2)构造它的构造它的LR(0)分析表。分析表。 3)分别给出对输入分别给出对输入符号串符号串abbcdeabbcde和和 abbbceabbbce的的LR(0)分析步骤。分析步骤。GS拓广拓广为为: S S S a A c B e A b A Ab B dI I0 : S S S a A c B e I I1 : S S I I2 : S a A c B e A b A AbI I3 : S a A c B e A A bI I4 : A b I I5 : S a A

20、c B e B dI I7 : S a A c B eI I8 : B d I I9 : S a A c B e I I6 : A A b SaAbbcBedGS的的LR(0)分析表分析表ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1Step states. Syms. The rest of inputaction goto 1 0 # abbcde# s2 2 02 #a bbcde# s4 3 024 #ab bcde# r2 3 4 023 #

21、aA bcde# s6 5 0236 #aAb cde# r3 3 6 023 #aA cde# s5 7 0235 #aAc de# s8 8 02358 #aAcd e# r4 7 9 02357 #aAcB e# s9 10 023579 #aAcBe # r1 1 11 01 #S # acc 对输入串对输入串abbcde#的分析过程的分析过程Step states. Syms. The rest of inputaction goto 1 0 # abbce# s2 2 02 #a bbce# s4 3 024 #ab bce# r2 3 4 023 #aA bce# s6 5 02

22、36 #aAb ce# r3 3 6 023 #aA ce# s5 7 0235 #aAc e# 出错出错说明说明abbceabbce# #不是不是文法文法 GSGS的的句子句子 对输入串对输入串abbce#的分析过程的分析过程SLR(1)SLR(1)分析分析 由于大多数适用的程序设计语言的文法不能满足LR(0)文法的条件，即使是描述一个实数变量说明这样简单的文法也不一定是LR(0)文法。将该文法缩写后并拓广为G如下：(0) SS(1) SrD(2) DD,i(3) Di 现举实型变量说明文法为例：实型变量说明 real标识符表标识符表标识符表，i标识符表iLRLR（0 0）项目项目1. 1.

23、 SSS 2. SSS 2. SS 3. S 3. SrD rD 4. Sr4. SrD 5. SD 5. SrDrD 6. D 6. DD,i D,i 7. DD7. DD,i 8. DD,i 8. DD,i 9. DD,ii 9. DD,i 10. D10. Di 11. Dii 11. Di LRLR（0 0）项目集规范族项目集规范族I I0 0: S: SS IS I3 3: Sr D: Sr D S Sr D DDr D DD，i iI I1 1: SS: SS I I4 4: Di: Di I I2 2: Sr: SrD ID I5 5: DD: DD，i i D DD D， i

24、I i I6 6: DD: DD，i i D Di i 其中其中I I3 3中含有移进中含有移进/ /归约冲突归约冲突 文法不是文法不是LR(0)LR(0)的，如何解决？的，如何解决？首先构造该文法首先构造该文法G的识别活前缀的的识别活前缀的DFA如图如图I0:S S SS .S .rDrDrI2:S r.Dr.DD .D,iD .D,iD .iD .iI1:S S.S.I3:S rDrD. .D D.,iD D.,iSD ，I5:D D,.iD,.iI4:D i.i.I6:D D,i.D,i.ii实数说明文法的实数说明文法的LR(0)分析表分析表 状态状态ACTIONGOTOr，i#SD01

25、23456S2.r1r3.r2.r1, S5r3.r2.S4r1r3S6r2.acc.r1r3.r21.3因此本节将介绍对于因此本节将介绍对于LR(0)LR(0)规范族中有冲突的项目集规范族中有冲突的项目集( (状状态态) )用向前查看一个符号的办法进行处理，以解决冲突。用向前查看一个符号的办法进行处理，以解决冲突。这种办法将能满足一些文法的需要，因为只对有冲突的因为只对有冲突的状态才向前查看一个符号，以确定做那种动作，因而称状态才向前查看一个符号，以确定做那种动作，因而称这种分析方法为简单的这种分析方法为简单的LR(1)LR(1)分析法，用分析法，用SLR(1)SLR(1)表示。表示。因此假

26、定一个LR(0)规范族中含有如下的项目集(状态)II=Xb,A,B也就是在该项目集中含有移进-归约冲突和归约-归约冲突。其中,为文法符号串，b为终结符。那么只要在所有含有A或B的句型中，直接跟在A或B后的可能终结符的集合即FOLLOW(A)和FOLLOW(B)互不相交，且都不包含b，也就是只要满足FOLLOW(A)FOLLOW(B)= FOLLOW(A)b= FOLLOW(B)b= 那么，当在状态I时面临某输入符号为a时，则动作可由下规定决策。1) 若a=b，则移进。2) 若aFOLLOW(A)，则用产生式A进行归约。3) 若aFOLLOW(B)，则用产生式B进行归约。4) 此外，报错。I=X

27、b,A,BI3：SrD. DD，i在上例中的I3如下：因为I3中存在移进个归约的冲突，采用SLR（1）的方法看看是否可以解决：Follow(S) ,=# ,= 所以遇到，就移进，遇到就归约。实数说明文法的SLR(1)分析表 状态ACTIONGOTOr,i#SD0123456S2.r3.r2.S5r3.r2.S4.r3S6r2.acc.r1r3.r21.3如果对于一个文法的如果对于一个文法的LR(0)LR(0)项目集规范族的某些项目集或项目集规范族的某些项目集或LR(0)LR(0)分析表中所含有的动作冲突都能用上述方法解决，分析表中所含有的动作冲突都能用上述方法解决，则称这个文法是则称这个文法是

28、SLR(1)SLR(1)文法，文法，所构造的分析表为SLR(1)分析表，使用SLR(1)分析表的分析器称为SLR(1)分析器。例如，我们可以构造算术表达式文法的LR(0)项目集规范族，然后分析它是LR(0)文法还是SLR(1)文法，现将表达式文法拓广如下：(0) SE(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) FiI0： SE EE+T ET TT*F TF F(E) FiI1： SE EE+TI2： ET TT*FI3： TFI4： F(E) EE+T ET TT*F TF F(E) FiI5： FiI6： EE+T TT*F TF F(E) Fi I7：

29、 TT*F F(E) Fi I8： F(E) EE+T I9： EE+T TT*F I10： TT*FI11：F(E) 该文法的LR(0)项目集规范族为：与此相应的识别该文法活前缀的有限自动机如P139图7.10所示。 不难看出在I1，I2，I9中存在移进-归约冲突，因而这个表达式文法不是LR(0)文法，也就不能构造LR(0)分析表，现在分别考查这三个项目集(状态)中的冲突是否能用SLR(1)方法解决。在I1中：SEE E+T由于FOLLOW(S)=#,而SE是唯一的接受项目，所以当且仅当遇到句子的结束符#号时才被接受。又因#+ ，因此I1中的冲突可解决。在I2中： ET TT*F我们可计算非

30、终结符E的FOLLOW集为：FOLLOW(E)=+,),#所以FOLLOW(E)*=+,),#* ，因此面临输入符为+，)或#号时，则用产生式ET进行归约。当面临输入符为*号时，则移进，其它情况则报错。在I9中： EE+T TT*F与I2中的情况类似因归约项目的左部非终结符E的后跟符集合FOLLOW(E)=+,),#与移进项目圆点后终结符不相交，所以冲突可以用SLR(1)方法解决，与I2不同的只是在面临输入符为+，)或#号时用产生式EE+T归约。由以上考查该文法在I1，I2，I9三个项目集(状态)中存在的移进-归约冲突都可以用SLR(1)方法解决，因此该文法是SLR(1)文法。 SLR(1)分

31、析表的构造与LR(0)分析表的构造类似，仅在含有冲突的项目集中分别进行处理。如果对所有归约项目都采如果对所有归约项目都采取取SLR(1)SLR(1)的处理思想，即对所有非终结符都求出其的处理思想，即对所有非终结符都求出其FOLLOWFOLLOW集合集合，这样凡是归约项目仅对面临输入符号包含在该归约项目左部，这样凡是归约项目仅对面临输入符号包含在该归约项目左部非终结符的非终结符的FOLLOWFOLLOW集合中，才采取用该产生式归约的动作。这集合中，才采取用该产生式归约的动作。这种处理的好处是对某些不该归约的动作可提前发现错误。对于种处理的好处是对某些不该归约的动作可提前发现错误。对于这样构造的这

32、样构造的SLR(1)SLR(1)分析表我们不访称它为改进的分析表我们不访称它为改进的SLR(1)SLR(1)分析表分析表, ,我们可构造上例中相应的改进的SLR(1)分析表P142表7.8所示。 对输入串i+i*i#进行分析见P142表7.9所示LR(1) 分析分析本节介绍比SLR(1)功能更强的LR(1)分析法。例如下列文法G为：(0) SS(1) SaAd(2) SbAc(3) Saec(4) Sbed (5)A e我们首先用SS作为初态集的项目，然后用闭包函数和转换函数构造识别文法G的识别活前缀的有限自动机识别活前缀的有限自动机DFADFA见见P143P143如图如图7.117.11所示

33、，所示，可以发现在项目集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)方法解决。 由于用SLR(1)方法解决动作冲突时，对于归约项目A，只要当前面临输入符为aFOLLOW(A)时，就确定采用产生式A进行归约，但是如果栈中的符号串为，归约后变为A，再移进当前符a，则栈里变为Aa，而实际上Aa未必为文法规范句型的活前缀。例如：在识别表达式文法的活前缀DFA中，

34、(见图7.10)在项目集I2存在移进-归约冲突，即ET TT*F若栈顶状态为2，栈中符号为#T，当前输入符为)，而)属FOLLOW(E)中，这时按SLR(1)方法应用产生式ET进行归约，归约后栈顶符号为#E，而再加当前符)后，栈中为#E)不是表达式文法规范句型的活前缀。 因此这个归约是多余的。因此可以看出SLR(1)方法虽然相对LR(0)有所改进，但仍然存在着多余归约，也说明SLR(1)方法向前查看一个符号的方法仍不够确切，LR(1)方法恰好是要解决SLR(1)方法在某些情况下存在的无效归约问题。若AB项目集I，则B(B为一产生式)也包含在I中，不妨考虑，把把FIRST()FIRST()作为用

35、产生式作为用产生式BB归约归约的搜索符，称为向前搜索符，作为归约时查看的符号集合，的搜索符，称为向前搜索符，作为归约时查看的符号集合，用以代替用以代替SLR(1)SLR(1)分析中的分析中的FOLLOWFOLLOW集，集，把此搜索符号的集合也把此搜索符号的集合也放在相应项目的后面，放在相应项目的后面，这种处理方法即为这种处理方法即为LR(1)LR(1)方法。方法。LR(1)LR(1)项目集族的构造项目集族的构造 构造LR(1)项目集的闭包函数CLOSURE(I)按如下方式构造:a) I 的任何项目都属于CLOSURE(I)b) 若有项目AB,a 属于CLOSURE(I)， B 是文法中的产生式

36、，V*，bFIRST(a)， 则 B,b也属于CLOSURE(I)中。c) 重复b)直到CLOSURE(I)不再增大为止。ecAdI0:SS,# SaAd,# SbAc,# Saec,#Sbed,#I2： SaAd,# Saec,# Ae,daI1： SS,#SI3: SbAc,# Sbed,# Ae,cbI6:SbAc,# AI7： Sbed,# Ae,cI11：Sbed,#dI10：SbAc,# I4： SaAd,#I5： Saec,# Ae,deI8： SaAd,#I9： Saec,#c(0) SS(1) SaAd(2) SbAc构造LR(1)分析表:例:已知拓展文法为:(3) Saec

37、(4) Sbed (5)A eLR(1)项目集和转换函数如下:状态 action gotoa bcde# S A 0S2S3 1 1acc 2S5 4 3S7 6 4S8 5S9r5 6S10 7r5S11 8 r1 9 r3 10 r2 11 r4如果一个文法的如果一个文法的LR(1)LR(1)分析表中不含多重入口时分析表中不含多重入口时( (或任何一个或任何一个LR(1)LR(1)项目集中无移进项目集中无移进归约或归归约或归约约归约的冲突归约的冲突, ,则称该文法为则称该文法为LR(1)LR(1)文法文法. .例：G(S):S BB BaB B b I0:S.S S .BB B .aB B

38、 .bI1:S S.I2:S B.B B.aB B.bI3:Ba.B B.aB B.b I4:BaB. I5: Bb.I6: SBB.I0:S S,# S BB,#B aB,a/bB b,a/b I1:S S ,#I2:S B B,# B aB,#B b,# I5:S BB ,#I6:S a B,# B aB,#B b,# I3:B a B,a/b B aB,a/b B b,a/b I4:B b ,a/bI7:B b ,#I9:B aB ,#I8:B aB ,a/bsBBabbbBBaaaLR(1)项目集和转换函数b例：G(S):S BB BaB B b 拓展文法 : ( (0)0)S S S

39、 (1) S (1) S S BB (2) B BB (2) BaB aB (3) B (3) B b b 对于该例题,只要仔细分析该文法的LR(1)每个项目集的项目,不难发现,即使不考察搜索符,它的任何项目都没有冲突,因此它实际上是一LR(0)文法,可以构造一个LR(0)项目集.可以得知它的LR(0)分析器只含7个状态，而现在LR(1)分析器却含有10个状态，其中I3和I6，I4和I7，I8和I9分别为同心集。LALR(1) 分析: 合并同心集I36 I47 I89I3:B aB,a/b B aB,a/b B b,a/b I6:S aB,# B aB,#B b,# I4:B b,a/bI7:

40、B b,#I8:B aB,a/bI9:B aB,#ACTIONGOTOab#SB状态0 S3 S4 1 21 acc2 S6 S7 53 S3 S4 84 r3 r3 5 r1 6 S6 S7 97 r38 r2 r2 9 r2 上例的上例的LR(1)分析表分析表0 S3,6 S4,7 1 21 acc2 S3,6 S4,7 53,6 S3,6 S4,7 8,94,7 r3 r3 r35 r18,9 r2 r2 r2ab#SBACTIONGOTO状态合并同心集后LALR(1)分析表同心集合并后仍不包含冲突，因此该文法满足LALR(1) 要求。合并同心集有几个问题需要说明。(1) 同心集是指心相

41、同的项目集合并在一起，因此同 心集合并后心仍相同，只是超前搜索符集合为各 同心集超前搜索符集合的和集。(2) 对于合并同心集后的项目集的转换函数仍为同心集，因为相同的心之转换函数的心仍相同，即仍属同心集，所以合并同心集后转换函数为自动合并，如例中I3和I6为同心集，它们的转换函数分别为：I3： GO(I3，a)= I3 GO(I3，b)= I4 GO(I3，B)= I8I6： GO(I6，a)= I6 GO(I6，b)= I7 GO(I6，B)= I9然而，I3和I6，I4和I7，I8 和I9分别都为同心集。(3) 若文法是若文法是LR(1)LR(1)文法，合并同心集后若有冲突也只可能是归约文

42、法，合并同心集后若有冲突也只可能是归约- -归约冲突，归约冲突，而不可能产生移进而不可能产生移进- -归约冲突归约冲突对(3)的证明不防假设某LR(1)文法的项目集Ik 与Ij为同心集， 其中：Ik 为：A，u1 Ba,bIj 为：A,u2 Ba,c 其中u1，u2分别为超前搜索符集合，因为假设文法是LR(1)的，所以不可能有移进-归约冲突，也就是在Ik 中u1a= ，在Ij中有u2a= ，显然合并同心集后(u1u2)a= (4) 合并同心集后对某些错误发现的时间会产生推迟现象，但错误的出现位置仍是准确的。这意味着LALR(1)分析表比LR(1)分析表对同一输入串的分析可能会有多余归约。这个问

43、题将在后面用例子来说明。构造文法的LALR(1)分析表 n对于一个文法是否为LALR(1)文法，通常所采用的方法是首先构造它的LR(1)项目集族，若不含任何冲突，则合并同心集，若仍不产生归约-归约冲突，则该文法便是LALR(1)文法，那么就可以根据合并同心集后的项目集族构造该文法的LALR(1)分析表，其构造步骤如下： LALR(1)分析表构造步骤n(1) 构造文法G的LR(1)项目集族，C=I0，I1，Inn(2) 合并所有的同心集，使C变为C=J0，J1，Jm，便是LALR(1)的项目集族。由于构造LALR(1)分析表，通常所采用的方法是首先构造它的LR(1)项目集族，若不含任何冲突，则合

44、并同心集，若仍不产生归约-归约冲突，则该文法便是LALR(1)文法，再根据合并同心集后的项目集族构造该文法的LALR(1)分析表。所以LALR(1)分析表的构造除了步骤（2）外，其余步骤与LR(1)分析表的构造相同n(3) 由C构造动作(ACTION)表，其方法与LR(1)分析表的构造相同。LALR(1)分析表构造步骤na) 若Aa,bJk，且GO(Jk,a)Jj，其中aVT，则置ACTIONk,a=Sj，其Sj的含义是把输入符号a和状态j分别移入文法符号栈和状态栈。b) 若项目A,a属于Jk ，则置ACTIONk,a=rj，其中aVT，rj的含义是设A是文法的第j个产生式，此时为把栈顶符号串

45、归约为A。c) 若项目SS，#属于Ik 则置ACTIONk,#=acc，表示分析成功、接受。LALR(1)分析表构造步骤nd) GOTO表的构造，对于不是同心集的项目集，转换函数的构造与LR(1)的相同，对同心集项目，由于合并同心集后，新集的转换函数也为同心集，所以，转换函数的构造也相同。具体步骤：假定Ii1,Ii2，Iin是同心集，合并后的新集为Jk，转换函数GO(Ii1,X)，GO(Ii2,X)，GO(Iin,X)也为同心集，将其合并后记作Ji，因此，有GO(Jk,X)= Ji，所以当X为非终结符时，GO(Jk,X)=Ji，则置GOTOk,X=i，表示在k状态下遇非终结符X时，把X和i分别

46、移到文法符号栈和状态栈，当X为终结符时，和ACTION表重合。ne) 分析表中凡不能用(a)(d)填入信息的空白均填出错标志。 对例输入串对例输入串ab#用用LR(1)分析的过程分析的过程1 0 # ab# S3 2 03 #a b# S43 034 #ab # 出错 步骤状态栈符号栈输入串ACTIONGOTO现在我们举例说明由于合并同心集可能对某些错误发现的时间产生推迟现象。上例所给文法识别的句子集合是正规式，a*ba*b，也就是该文法可推出的句子必须含有两个b且以b为结尾。因而输入串若为ab#，显然不是这个文法能推出的句子。但用LR(1)分析表分析和用LALR(1)分析表分析时发现错误的时间