第七章 LR分析

1、第七章第七章 LR分析分析重点：重点：LR(0)、SLR(1)、LR(1)、LALR(1)自底向上分析自底向上分析n思想：思想：n从输入串出发，反复利用产生式进行归约，如果最从输入串出发，反复利用产生式进行归约，如果最后归约到开始符号，则输入串为句子，否则出错。后归约到开始符号，则输入串为句子，否则出错。n核心：核心：n寻找句型中的当前归约对象寻找句型中的当前归约对象-“句柄句柄”进行归约，进行归约，用不同的方法寻找句柄，就可获得用不同的方法寻找句柄，就可获得不同的分析方法不同的分析方法 第七章第七章 LR分析分析nLR分析是一种自底向上分析方法分析是一种自底向上分析方法n过程：移进过程：移进

2、归约归约nLR分析的关键问题？分析的关键问题？n如何确定句柄？如何确定句柄？nLR分析法的归约过程是规范推导（最右推导）的逆过分析法的归约过程是规范推导（最右推导）的逆过程，为规范归约（最左归约）程，为规范归约（最左归约）nL：从左到右扫描输入串：从左到右扫描输入串nR：最右推导对应的最左归约：最右推导对应的最左归约nk：向右顺序查看输入串的：向右顺序查看输入串的k个符号就可确定是个符号就可确定是移进移进还还是是归约归约7.1 LR分析概述分析概述nLR分析器组成分析器组成n总控程序：对所有的总控程序：对所有的LR分析器总控程序都是相同的。分析器总控程序都是相同的。n分析表分析表n不同文法的分

3、析表不同，同一文法采用的不同文法的分析表不同，同一文法采用的LR分分析器不同时，分析表也不同。析器不同时，分析表也不同。n分为动作表分为动作表(ACTION)和状态转换表和状态转换表(GOTO)n分析栈：文法符号栈和状态栈分析栈：文法符号栈和状态栈总控程序总控程序状态状态符号符号SmXmS1X1S0#分析栈分析栈ACTION GOTO LR分析表分析表a1a2ai an# #输入串输入串 输出输出LR分析器的工作过程分析器的工作过程SP7.1 LR分析概述分析概述nLR分析器的核心是一张分析表：分析器的核心是一张分析表：nACTIONACTIONS S，a a ：当状态：当状态S S面临输入符

4、号面临输入符号a a时，应采取时，应采取什么动作什么动作. .nGOTOGOTOS S，XX：状态：状态S S面对文法符号面对文法符号X X时，下一状态是时，下一状态是什么什么7.1 LR分析概述分析概述n每一项每一项ACTIONS，a所规定的四种动作所规定的四种动作:l移进移进 把把(S，a)的下一状态的下一状态S和输入符号和输入符号a推进栈推进栈.l归约归约 指用某产生式指用某产生式A进行归约进行归约. 假若假若 的长度为的长度为r，状态栈的栈顶状态为，状态栈的栈顶状态为Sm。 归约动作是去除栈顶归约动作是去除栈顶r个项，使状态个项，使状态Sm-r变成栈顶状态，然后把变成栈顶状态，然后把(

5、Sm-r, A)的下一状态的下一状态S=GOTOSm-r, A和文法符号和文法符号A推进栈推进栈.l接受接受 宣布分析成功，停止分析器工作宣布分析成功，停止分析器工作.l报错报错7.2 LR(0)分析分析关键：分析表的构造关键：分析表的构造分析表的构造思想和方法分析表的构造思想和方法步骤步骤 符号栈符号栈 剩余剩余输入符号串输入符号串 动作动作1 # abbcde# 移进移进2 #a bbcde# 移进移进3 #ab bcde# 归约归约(A b )4 #aA bcde# 移进移进5 #aAb cde# 归约归约(A Ab )6 #aA cde# 移进移进7 #aAc de# 移进移进8 #a

6、Acd e# 归约归约(B d )9 #aAcB e# 移进移进 10 #aAcBe # 归约归约(S aAcBe)11 #S # accept 例：例：GS: S a A c B e A b|Ab B d输入串为输入串为 w=abbcde#LR：状态栈的栈顶：状态栈的栈顶状态不同状态不同简单优先分析法简单优先分析法ACTION GOTO a c e b d # S A B0 S2 11 acc2 S4 33 S5 S6 4 r2 r2 r2 r2 r2 r25 S8 76 r3 r3 r3 r3 r3 r37 S98 r4 r4 r4 r4 r4 r49 r1 r1 r1 r1 r1 r1n

7、步骤步骤 状态栈状态栈 符号栈符号栈 输入串输入串 ACTION GOTOn1 0 # abbcde# S2 n2 02 #a bbcde# S4n3 024 #ab bcde# r2 3n4 023 #aA bcde# S6n5 0236 #aAb cde# r3 3n6 023 #aA cde# S5n7 0235 #aAc de# S8n8 02358 #aAcd e# r4 7n9 02357 #aAcB e# S9n10 023579 #aAcBe # r1 1 n11 01 #S # acc (1)S a A c B e (2) A b (3)AAb (4)B d输入串为输入串为

8、w=abbcde#7.2.1 可归前缀和子前缀可归前缀和子前缀n最右推导和最左规约的关系最右推导和最左规约的关系n对于文法对于文法GS的每个产生式编上序号的每个产生式编上序号in S a A c B e1n A b2n AAb3 n B d4符号串符号串abbcde的最右推导过程的最右推导过程S aAcBe1 aAcd4e1 aAb3cd4e1ab2b3cd4e1符号串符号串abbcde的最左归约过程的最左归约过程ab2b3cd4e1 =aAb3cd4e1 =aAcd4e1 =aAcBe1 A= =A= 是文法中的一个是文法中的一个规范推导规范推导。如果如果是是的前缀，则称的前缀，则称是是G

9、G的一个活前缀。的一个活前缀。活前缀活前缀：是指：是指规范句型规范句型的一个前缀，这种前缀不含的一个前缀，这种前缀不含句柄句柄之后的任何符号。之后的任何符号。文法文法GS: SaAd A bB B c7.2.2 识别活前缀的有限自动机识别活前缀的有限自动机nGS的拓广文法：的拓广文法：为使开始符号不出现在产生式的右为使开始符号不出现在产生式的右部部，对文法，对文法G进行扩展，增加进行扩展，增加SS，其中其中S是对原文是对原文法扩充而增加的非终结符法扩充而增加的非终结符. nGS=(S,a,SSa,Sa,S)nG S= (S，S,a,SSa,Sa，S S, S )7.2.2 识别活前缀的有限自动

10、机识别活前缀的有限自动机nLR分析过程：分析过程：n不是直接分析文法符号栈中是否形成句柄不是直接分析文法符号栈中是否形成句柄n而是识别符号栈中是否形成可归前缀，相当于形成句柄而是识别符号栈中是否形成可归前缀，相当于形成句柄n把终结符和非终结符看成是一个有限自动机的输入符号，把终结符和非终结符看成是一个有限自动机的输入符号，每把一个符号入栈看成已识别过了该符号，而状态进行每把一个符号入栈看成已识别过了该符号，而状态进行转换转换GS: S a A c B e 1 A b2 A Ab3 B d4对该文法进行拓广：对该文法进行拓广：G S: SS0 S a A c B e 1 A b2 A Ab3 B

11、 d4现对句子现对句子abbcde的可归前缀列出：的可归前缀列出：ab2 aAb3 aAcd4 aAcBe1S0现对句子现对句子abbcde的可归前缀列出：的可归前缀列出：S0 ab2 aAb3 aAcd4 aAcBe1可构造识别其活前缀可构造识别其活前缀及可归前缀的有限自动机及可归前缀的有限自动机x59214306710111216151718SaaaaAAAbccbdeB B *识别活前缀的有限自动机将上面得到的将上面得到的NFA进行确定化：进行确定化：识别活前缀的识别活前缀的DFA7.2.4 LR(0)项目集规范族的构造项目集规范族的构造n一个语言都有哪些一个语言都有哪些活前缀活前缀?n

12、哪些字符串是哪些字符串是活前缀活前缀?n能不能构造一个能不能构造一个DFA来识别来识别活前缀活前缀?7.2.4 LR(0)项目集规范族的构造项目集规范族的构造（1）LR(0)项目项目n文法文法G的每个产生式的右部添加一个圆点称为的每个产生式的右部添加一个圆点称为G的的LR(0)项目项目n如如:AXYZ有四个项目：有四个项目： A.XYZ AX.YZ AXY.Z AXYZ.n圆点的左部表示分析过程的某一时刻欲用该产生式归圆点的左部表示分析过程的某一时刻欲用该产生式归约时已识别过的句柄部分，圆点的右部表示期待的后约时已识别过的句柄部分，圆点的右部表示期待的后缀部分。缀部分。7.2.4 LR(0)项

13、目集规范族的构造项目集规范族的构造n根据圆点所在的位置和圆点后是终结符还是非终结符根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为：把项目分为：FA . 称为称为归约项目归约项目F归约项目归约项目 S . 称为称为接受项目接受项目FA .a (a VT) 称为称为移进项目移进项目F A .B (B VN) 称为称为待约项目待约项目.7.2.4 LR(0)项目集规范族的构造项目集规范族的构造n(2)构造识别活前缀的构造识别活前缀的NFAn把文法的所有产生式的项目都列出，并使每个项目都作为把文法的所有产生式的项目都列出，并使每个项目都作为NFA的一个状态。的一个状态。n方法：方法： 若若状

14、态状态i为为XX1 Xi-1.Xi Xn ， 状态状态j为为XX1 Xi-1Xi .Xi+1 Xn ， 则从状态则从状态i画一条标志为画一条标志为Xi的有向边到状态的有向边到状态j； 若状态若状态i为为X .A ，A为非终结符，为非终结符， 则从状态则从状态i画一条画一条 边到所有状态边到所有状态A. 。n把识别文法所有活前缀的把识别文法所有活前缀的NFA确定化。确定化。n文法文法G(S ) S E EaA|bB AcA|d BcB|d n 该文法的项目有：该文法的项目有：1. S E2. S E3. EaA 4. EaA5. EaA6. AcA7. AcA8. AcA9. Ad 10. Ad

15、 11. EbB 12. EbB13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bdl项目项目1为初态为初态l圆点在最后的项目为句柄识别态圆点在最后的项目为句柄识别态l第一个产生式的句柄识别态为句第一个产生式的句柄识别态为句子识别态子识别态678910453121112131415161817 a AEbBBcAcd识别活前缀的识别活前缀的NFAS E 2. S EEaA 4. EaA5. EaA6. AcAAcA8. AcA9. Ad 10. Ad 11. EbB12. EbBEbB 14. BcB15. BcB 16. BcB 17. Bd 18. B

16、d方法：方法： 若若状态状态i i为为X XX1 Xi-1.Xi XnX1 Xi-1.Xi Xn ， 状态状态j j为为X XX1 Xi-1Xi .Xi+1 X1 Xi-1Xi .Xi+1 XnXn ，则从状态则从状态i i画一条标志为画一条标志为XiXi的有向边到状的有向边到状态态j j； 若状态若状态i i为为X X .A .A ，A A为非终结符，为非终结符， 则从状态则从状态i i画一条画一条 边到所有状态边到所有状态A A. . 识别活前缀的识别活前缀的DFA0: S E EaA EbB 4: AcA AcA Ad 2: EaA AcA Ad1: S E3: EbB BcB Bd5:

17、 BcB BcB Bd 11: Bd9: BcB7: EbB10: Ad6: EaA 8: AcAccbEadAccdddBAB将将NFA确定化确定化7.2.4 LR(0)项目集规范族的构造项目集规范族的构造n(3)LR(0)项目集规范族的构造项目集规范族的构造n构成识别一个文法活前缀的构成识别一个文法活前缀的DFA的项目集的项目集(状态状态)的的全体称为文法的全体称为文法的LR(0)项目集规范族项目集规范族。n上面求上面求LR(0)项目集规范族项目集规范族的方法的方法:复杂复杂n列出拓广文法的所有项目列出拓广文法的所有项目n构造构造NFAn确定化确定化0: S E EaA EbB 4: Ac

18、A AcA Ad 2: EaA AcA Ad1: S E3: EbB BcB Bd5: BcB BcB Bd 11: Bd9: BcB7: EbB10: Ad6: EaA 8: AcAccbEadAccdddBAB分析：分析：若状态中包含形若状态中包含形如如A.B的项的项目，则形如目，则形如B.的项目也在此状的项目也在此状态中。态中。LR(0)项目集规范族的构造项目集规范族的构造n假定文法假定文法G已拓广为已拓广为G ，拓广后增加一个新产生式，拓广后增加一个新产生式S S，而这个，而这个S 是是G 的开始符号。如果的开始符号。如果I是文法是文法G 的一个项目集，定义和构造的一个项目集，定义和构

19、造I的闭包的闭包CLOSURE(I)如下：如下：nI的任何项目都属于的任何项目都属于CLOSURE(I)；n若若A B 属于属于CLOSURE(I)，那么，那么 项目项目B 也属于也属于CLOSURE(I)；n重复执行上述两步骤直至重复执行上述两步骤直至CLOSURE(I) 不再增大为止。不再增大为止。n这样有了初态的项目集，其他状态的项目集如何求出？这样有了初态的项目集，其他状态的项目集如何求出？0: S E EaA EbB 4: AcA AcA Ad 2: EaA AcA Ad1: S E3: EbB BcB Bd5: BcB BcB Bd 11: Bd9: BcB7: EbB10: Ad

20、6: EaA 8: AcAccbEadAccdddBAB文法文法G(S ) S E EaA|bB AcA|d BcB|dn为了识别活前缀，我们定义一个状态转换函数为了识别活前缀，我们定义一个状态转换函数GO。I是一个项目集，是一个项目集，X是一个文法符号。函数值是一个文法符号。函数值GO(I，X)定义为：定义为：GO(I，X)CLOSURE(J) 其中其中 J任何形如任何形如A X 的项目的项目| A X 属于属于I。n直观上说，若直观上说，若I是对某个活前缀是对某个活前缀 有效的项目集，那么，有效的项目集，那么，GO(I，X)便是对便是对 X 有效的项目集。有效的项目集。0: S E EaA

21、 EbB 4: AcA AcA Adc5: BcB BcB Bd c3: EbB BcB Bdb1: S EE2: EaA AcA Ada11: Bdd8: AcAAccd10: Addd9: BcBB6: EaA A7: EbBB文法文法G(S )S EEaA|bBAcA|dBcB|dLR(0)文法定义文法定义n对一个文法的对一个文法的LR(0)项目集规范族不存在移进项目集规范族不存在移进-归约，归约，或归约或归约-归约冲突的文法称为归约冲突的文法称为LR(0)文法。文法。n移进移进-归约冲突：归约冲突：n一个项目集中同时存在形如：一个项目集中同时存在形如：nA.a和和B.n归约归约-归约冲

22、突：归约冲突：n一个项目集中同时存在形如：一个项目集中同时存在形如：nA.和和B.LR(0)分析表的构造分析表的构造n 假定假定C=I0, I1,，In，令每个项目集，令每个项目集Ik的下标的下标k为分析为分析器的一个状态，因此，器的一个状态，因此，G 的的LR(0)分析表含有状态分析表含有状态0，1，n。令那个含有项目。令那个含有项目S .S的的Ik的下标的下标k为初态。为初态。ACTION和和GOTO可按如下方法构造：可按如下方法构造：n1.若项目若项目Aa属于属于Ik且且GO (Ik, a)= Ij, a为终结符，为终结符，则置则置ACTIONk, a为为“把状态把状态j和符号和符号a移

23、进栈移进栈”，简记为简记为“Sj”;n2.若项目若项目A属于属于Ik, 那么，对任何终结符那么，对任何终结符a和和”#”, 置置ACTIONk, a为为“用产生式用产生式A进行归进行归约约”，简记为，简记为“rj”;其中，假定其中，假定A为文法为文法G的第的第j个产生式；个产生式；3.若项目若项目SS属于属于Ik, 则置则置ACTIONk, #为为“接接受受”，简记为，简记为“acc”;4.若若GO (Ik, A)= Ij, A为非终结符，则置为非终结符，则置GOTOk, A=j;分析表中凡不能用规则分析表中凡不能用规则1至至4填入信息的空白格均填入信息的空白格均置上置上“出错标志出错标志”。

24、 按上述算法构造的含有按上述算法构造的含有ACTION和和GOTO两部分的分两部分的分析表，如果每个入口不含多重定义，则称它为文法析表，如果每个入口不含多重定义，则称它为文法G的一张的一张LR(0)表。表。 具有具有LR(0)表的文法表的文法G称为一个称为一个LR（0）文法。）文法。0: S E EaA EbB 4: AcA AcA Adc5: BcB BcB Bd c3: EbB BcB Bdb1: S EE2: EaA AcA Ada11: Bdd8: AcAAccd10: Addd9: BcBB6: EaA A7: EbBB文法文法G(S )S EEaA|bBAcA|dBcB|dnLR(

25、0)分析表为A C T IO NG O T O状状 态态abcd#EAB0s2s311acc2s4s1063s5s1174s4s1080: S E EaA EbB 5: BcB BcB Bd c3: EbB BcB Bdb1: S EE2: EaA AcA Ada文法文法G(S ) S E(0) EaA(1)|bB(2) AcA(3)|d(4) BcB(5)|d(6)6: EaA 文法文法G(S ) S E(0) EaA(1)|bB(2) AcA(3)|d(4) BcB(5)|d(6)ACTIONGOTO状态状态abcd#EAB0s2s311acc2s4s1063s5s1174s4s1085s

26、5s116r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r69ACTIONGOTO状态状态abcd#EAB0s2s311acc2s4s1063s5s1174s4s1085s5s116r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r69文法文法G(S ) S E(0) EaA(1)|bB(2) AcA(3)|d(4) BcB(5)|d(6)对对bccd#进行分析进行分析n步骤步骤 状态栈状态栈 符号栈符号栈 输入串输入串 ACTI

27、ON GOTOn1 0 # bccd# S3 n2 03 #b ccd# S5n3 035 #bc cd# S5 n4 0355 #bcc d# S11n5 0355(11) #bccd # r6 9n6 03559 #bccB # r5 9n7 0359 #bcB # r5 7n8 037 #bB # r2 1n9 01 #E # acc0: S E EaA EbB 4: AcA AcA Ad 2: EaA AcA Ad1: S E3: EbB BcB Bd5: BcB BcB Bd 11: Bd9: BcB7: EbB10: Ad6: EaA 8: AcAccbEadAccdddBAB文法

28、文法G(S )：S E(0)EaA(1)|bB(2)AcA(3)|d(4)BcB(5)|d(6)对对bccd#进行分析进行分析例：例： (0) SS (1)SrD (2) DD,i (3) Di 构造识别此文法活前缀的构造识别此文法活前缀的DFA0: S S S.rD 4: Di. i2: Sr.D DD,i Dir1: S SS5: DD，.i3: SrD. DD.，iD,6: DD，i.i该文法的项目集规范族如下：该文法的项目集规范族如下：0: S S S.rD 4: Di. 2: Sr.D DD,i Di1: S S5: DD，.i3: SrD. DD.，i6: DD，i. 状态状态 A

29、CTION GOTOn r ， i # S Dn 0 S2 1 n 1 accn 2 S4 3n 3 r1 S5 r1 r1 r1n 4 r3 r3 r3 r3n 5 S6n 6 r2 r2 r2 r20: S S S.rD 4: Di. i2: Sr.D DD,i Dir1: S SS5: DD，.i3: SrD. DD.，iD,6: DD，i.i构造构造LR(0)分析表分析表文法文法 (0) S S (1)SrD (2) DD,i (3)Di 7.3 SLR(1)分析分析nSLR(1)分析：对分析：对LR(0)规范族中有冲突的项目集状态规范族中有冲突的项目集状态用向前看一个符号的办法进行处

30、理，以解决冲突用向前看一个符号的办法进行处理，以解决冲突n只需要考查当用只需要考查当用rD进行归约成进行归约成S时，时，S的后跟符号集合的后跟符号集合中不包含当前所有移进项目的移进符号的集合中不包含当前所有移进项目的移进符号的集合，则移，则移进进-规约冲突便可解决。规约冲突便可解决。 使用使用FOLLOW(S)FOLLOW(S)， = 信息信息 解决冲突解决冲突3: SrD. DD.，i7.3 SLR(1)分析分析 SLR（1）分析表）分析表3: SrD. DD，i 状态状态 ACTION GOTOn r ， i # S Dn 0 S2 1 n 1 accn 2 S4 3n 3 S5 r1n

31、4 r3 r3 r3 r3n 5 S6n 6 r2 r2 r2 r2l如果如果 LR(0) 项目集规范族中某个项目集项目集规范族中某个项目集IK含含移进移进/归归约和归约约和归约/归约冲突归约冲突：lIK : .A.b,.b, P . ，Q .， l若若 FOLLOW(Q) FOLLOW(P)= l FOLLOW(P) b = l FOLLOW(Q) b= l则解决冲突的则解决冲突的SLR(1)技术：技术：l action k，b = 移进移进l对对a FOLLOW (P) 则则 action k，a =用用 P 归约归约 l对对a FOLLOW (Q) 则则 action k,a =用用 Q

32、 归约归约n通常对于通常对于LR(0)项目集规范族的一个项目项目集规范族的一个项目I中可能含有多个移中可能含有多个移进项目和多个归约项目。进项目和多个归约项目。n假定假定LR(0)规范族的一个项目集规范族的一个项目集I=A1 a1 1，A2 a2 2，Am am m，B1 1，B2 2，Bn nn 如果集合如果集合a1，am，FOLLOW(B1)，FOLLOW(Bn)两两不相交，则：两两不相交，则：n若若a a1，am，则移进，则移进n若若a FOLLOW(Bi)，i=1,2,n，则用产生式，则用产生式Bi i进行归约；进行归约；n此外，报错。此外，报错。n如果一个文法的如果一个文法的LR(0

33、)分析表中所含有的动作冲突都能分析表中所含有的动作冲突都能用上述方法解决，则这个文法是用上述方法解决，则这个文法是SLR（1）文法）文法0: S S S.rD 4: Di. i2: Sr.D DD,i Dir1: S SS5: DD，.i3: SrD. DD.，iD,6: DD，i.i文法文法 (0) S S (1)SrD (2) DD,i (3)Di SLR（1）分析表）分析表 状态状态 ACTION GOTOn r ， i # S Dn 0 S2 1 n 1 accn 2 S4 3n 3 S5 r1n 4 r3 r3 r3 r3n 5 S6n 6 r2 r2 r2 r20: S S S.r

34、D 4: Di. i2: Sr.D DD,i Dir1: S SS5: DD，.i3: SrD. DD.，iD,6: DD，i.i文法文法 (0) S S (1)SrD (2) DD,i (3)Di SLR（1）分析表）分析表 状态状态 ACTION GOTOn r ， i # S Dn 0 S2 1 n 1 accn 2 S4 3n 3 S5 r1n 4 r3 r3n 5 S6n 6 r2 r2改进的改进的构造改进的构造改进的SLR(1)分析表方法分析表方法:n首先把首先把G拓广为拓广为G ，对，对G 构造构造LR(0)项目集规范项目集规范族族C和识别活前缀的有限自动机和识别活前缀的有限自动

35、机.n 按下面的算法构造按下面的算法构造SLR分析表：分析表：n令每个项目集令每个项目集Ik的下标的下标k作为分析器的状态，作为分析器的状态，包含项目包含项目S S的集合的集合Ik的下标的下标k为分析器的为分析器的初态。初态。n分析表的分析表的ACTION和和GOTO子表构造方法子表构造方法：1. 若项目若项目A a 属于属于Ik且且GO(Ik,a)=Ij，a为终结符，则置为终结符，则置ACTIONk,a为为 “sj”；2. 若项目若项目A 属于属于Ik，那么，对任何终结符，那么，对任何终结符a，a FOLLOW(A)，置，置ACTIONk,a为为 “rj”；其中，假定；其中，假定A为文法为文

36、法G 的第的第j个产生式；个产生式；3. 若项目若项目S S属于属于Ik，则置，则置ACTIONk,#为为“acc”;4. 若若GO(Ik,A)Ij，A为非终结符，则置为非终结符，则置GOTOk,A=j；5. 分析表中凡不能用规则分析表中凡不能用规则1至至4填入信息的空白格均置上填入信息的空白格均置上“出出错标志错标志”。 按上述方法构造出的按上述方法构造出的ACTION与与GOTO表如果表如果不含多重入口不含多重入口，则称该文法为则称该文法为SLR(1)文法文法。n例：例： 考察下面的拓广文法：考察下面的拓广文法：(0) S E(1) EE+T(2) ET(3) TT*F(4) TF(5)

37、F(E)(6) Fin这个文法的这个文法的LR(0)项目集规范族为：项目集规范族为：I0: S E EE+T ET TT*F TF F (E) FiI1: S E EE+TI2: ET TT*FI3: TF I4: F(E) EE+T ET TT*F TF F (E) FiI5 :FiI6: EE+T TT*F TF F(E) FiI7: TT*F F(E) FiI8: F(E) EE+TI9: EE+T TT*FI10: TT*FI11: F(E)(0) S E(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) FiI0I1I2I3I4I5I6I7I8I9I10I

38、11E+T*TTiF(i( FE(Fi+F*()n识别该文法活前缀的识别该文法活前缀的DFAI2: ET TT*FI1: S E EE+TI9: EE+T TT*FI1、I2、I9存在移进、归约冲突存在移进、归约冲突解决？解决？ I1：S E. FOLLOW(S )=# 遇遇#接受接受 E E.+T 遇遇+移进移进 I2: E T. 遇遇FOLLOW(E)=+,),#归约归约 T T. *F 遇遇* 移进移进 I9：E E+T .遇遇FOLLOW(E)=+,),#归约归约 T T.*F 遇遇* 移进移进(0) S E(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6)

39、 Fi改进的改进的SLR(1)分析表如下分析表如下:I0I1I2I3I4I5I6I7I8I9I10I11E+T*TTiF(i(FE(Fi+F*()I0: S E EE+T ET TT*F TF F (E) Fir6R6R6R65 4 3 2 1321S4S50FTE#)(*+iGOTOACTIONI0I1I2I3I4I5I6I7I8I9I10I11E+T*TTiF(i(FE(Fi+F*()I1: S E EE+TI2: ET TT*FFOLLOW(E)=+,),#r6R6R6R65 4 3 r2 r2S7 r22 acc S61321S4S50FTE#)(*+iGOTOACTION改进的改进的

40、SLR(1)分析表如下分析表如下:I0I1I2I3I4I5I6I7I8I9I10I11E+T*TTiF(i(FE(Fi+F*()FOLLOW(T)=+,),#，*I3: TF r6R6R6R65 4 r4 r4 r4 r43 r2 r2S7 r22 acc S61321S4S50FTE#)(*+iGOTOACTION改进的改进的SLR(1)分析表如下分析表如下:ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7R2r23R4R4R4r44S5S48235R6R6R6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5利

41、用利用SLR(1)分析表分析表 对对i）#进行分析进行分析(0) S E(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi文法文法G:（0）SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) AeFOLLOW(A)=c,d不能用不能用SLR（1）方法解决）方法解决LR(0)识别识别G的活前缀的的活前缀的DFA7.4 LR(1)分析分析n文法文法G:n（0）SS (1) SaAd (2) SbAcn (3) Saec (4) Sbed (5) AenI5、I7存在移进存在移进-归约冲突，不能用归约冲突，不能用SLR（1）方法解决

42、）方法解决nFOLLOW(A)=c,dn在在5状态，遇见状态，遇见c，移进，移进(S9)、归约、归约(r5)n在在7状态，遇见状态，遇见d，移进，移进(S11)、归约、归约(r5)分析：分析：nS=S=aAd=aed S=S=bAc=bec nS=S=aec S=S=bed n状态状态5，遇见，遇见d归约，遇见归约，遇见c移进；状态移进；状态7，遇见，遇见c归约，遇见归约，遇见d移移进；进；7.4 LR(1)分析分析nFOLLOW(A) 包含了在包含了在任何句型任何句型中跟在中跟在 A 后的符号，后的符号，但没有严格地指出在但没有严格地指出在一个特定的推导一个特定的推导里哪些符号跟在里哪些符号

43、跟在A后后.nFOLLOW集合提供的信息太泛！集合提供的信息太泛！n根据项目集的构造原则有：根据项目集的构造原则有：n若若 A .B I 则则 B . （ B 是一产生式）是一产生式） I 不防考虑，把不防考虑，把FIRST（ ）中的符号作为用）中的符号作为用B 归约归约的搜索符，的搜索符，向前搜索符向前搜索符7.4.1 LR(1)项目集族的构造项目集族的构造lLR（1）项目的一般形式）项目的一般形式：A . ， a l意味着处在栈顶是意味着处在栈顶是 的相应状态，期望相应的相应状态，期望相应 在栈顶的状在栈顶的状态，然后只有当跟在态，然后只有当跟在 后的符号是终结符后的符号是终结符a时进行归

44、约时进行归约l a 称作该项目的向前搜索符称作该项目的向前搜索符 l向前搜索符只对向前搜索符只对归约项目归约项目起作用，起作用，对于任何对于任何移进移进或或待约项目待约项目不起作用不起作用lA , a:意味着处在栈中是意味着处在栈中是 的相应状态，但只有的相应状态，但只有当下一个输入符是当下一个输入符是a时才能进行归约时才能进行归约. la 要么是一个要么是一个终结符终结符，要么是，要么是输入结束标记输入结束标记#l有多个向前搜索符，比如有多个向前搜索符，比如a,b,c时，可写作时，可写作 A u, a/b/c7.4.1 LR(1)项目集族的构造项目集族的构造n为构造有效的为构造有效的LR(1

45、)项目集族我们需要两个函数项目集族我们需要两个函数CLOSURE（闭包）和（闭包）和GO（转换）。（转换）。n初始时：初始时： C= closure(S SS,#S,#); ; LR（1）项目集的构造：）项目集的构造：n对初始项目对初始项目S SS,#S,#求闭包后再用转换函数逐步求闭包后再用转换函数逐步求出整个文法的求出整个文法的LR(1)项目集项目集（1）构造）构造LR(1)项目集的闭包函数项目集的闭包函数 I的任何项目属的任何项目属closure(I)；若若A1 1BB2 2，aaclosure(I)，B是一产生是一产生式，那么对于式，那么对于FIRST(2 2a a)中的每个终结符中的

46、每个终结符b，如果，如果B,b,b不在不在closure(I)中，则把它加进去；中，则把它加进去；重复重复 ，直至，直至closure(I)不再增大。不再增大。（2）构造转换函数）构造转换函数n若若I是一个项目集，是一个项目集，X是一个文法符号是一个文法符号 GO(I, X)= closure(J) n其中其中 J= 任何形如任何形如AXX,a,a的项目的项目A.X,aI.X,aI n文法的文法的LR(1)LR(1)项目集项目集: :反复利用（反复利用（1 1）（）（2 2），直到项目），直到项目集不在扩大集不在扩大文法文法G:（0）SS (1) SaAd (2) SbAc (3) Saec

47、(4) Sbed (5) AeI0:S.S,#S.aAd ,#S. .bAcbAc,#,#S. .aecaec,#,#S. .bedbed,#,#I1:SS.,#SI2: Sa.Ad,#Sa a. .ecec,#,#A A. .e e, ,d daI3: Sb b.Ac,#Sb b. .eded,#,#A A. .e e, ,c cbI4: SaA.d,#AI6: Sb bA.c,#AI5: Saeae. .c c,#,#A Ae e. ., ,d deI7: Sbebe. .d d,#,#A Ae e. ., ,c ceI9: Saecaec. .,#,#cI8: SaAd.,#dI10:

48、Sb bAc.,#cI11: Sbedbed. .,#,#dLR(1)的项目集和转换函数的项目集和转换函数7.4.2 LR(1)分析表的构造分析表的构造 假定假定LR(1)项目集规范族项目集规范族C=I0, I1,，In，令每个项目，令每个项目集集Ik的下标的下标k为分析器的一个状态，为分析器的一个状态，G的的LR（1）分析表）分析表含有状态含有状态0，1，n。1.令含有项目令含有项目SS ，#的的Ik的下标的下标k为状态为状态0（初态）。（初态）。ACTION表和表和GOTO表可按如下方法构造：表可按如下方法构造：2.若项目若项目A,b属于属于Ik, 那么那么置置ACTIONk, b为为 “

49、rj”;其其中，假定中，假定A为文法为文法G的第的第j个产生式个产生式3.3.若项目若项目Aa,ba,b属于属于Ik且且GO (Ik, a)= Ij,则置则置ACTIONk, a为为 “sj”;4.若项目若项目SSS,#,#属于属于Ik, 则置则置ACTIONk, #为为 “acc”; 5.若若GO (Ik, A)= Ij, A为非终结符，则置为非终结符，则置GOTO(k, A)=j6.分析表分析中凡不能用规则分析表分析中凡不能用规则1至至5填入信息的空白格均填入信息的空白格均置上置上“出错标志出错标志”。 n 按上述算法构造的含有按上述算法构造的含有ACTION和和GOTO两部两部分的分析表

50、，如果每个入口不含多重定义，则分的分析表，如果每个入口不含多重定义，则称该文法称该文法G 为一个为一个LR（1）文法。）文法。ACTION GOTOa b c d e # S A 0 S2 S3 11 acc LR(1)分析表分析表ACTION GOTOa b c d e # S A 0 S2 S3 11 acc2 S5 43 S7 64 S85 S9 r5 6 7 8 r19 r310 r211 r4LR(1)分析表分析表文法文法G:（0）SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Aen每个每个SLR（1）文法都是）文法都是LR（1）文法。）文法。

51、n LR(1)比比SLR（1）能力强）能力强n一般情况下，一个一般情况下，一个LR（1）文法的项目集的个数比其）文法的项目集的个数比其SLR（1）的状态要多。）的状态要多。G(S): （0）S S (1)S BB (2) BaB (3) B b I0:S S,# S BB,#B aB,a/bB b,a/b I1:S S,#I2:S BB,# B aB,#B b,# I5:S BB,#I6:B aB,# B aB,#B b,# I3:B aB,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)项

52、目集和转换函数项目集和转换函数bLR(1)LR(1)项目集和转换函数项目集和转换函数(0)S S (1)S BB(2)B aB (3)B bS I0：S S, # S BB, # B aB, a/b B b, a/bB I2：S BB, # B aB, # B b, # I4：B b, a/bb I3：B aB, a/b B aB, a/b B b, a/bbb I7：B b, # I8：B aB, a/baB I5：S BB, # I6：B aB, # B aB, # B b, #Baa I9：B aB, #baB I1：S S , #7.5 LALR(1)分析分析n对对 LR(1)来说，存

53、在着某些状态，这些状态除向前搜来说，存在着某些状态，这些状态除向前搜索符不同外，索符不同外， 其核心部分都是相同的其核心部分都是相同的.n同心集同心集: 两个两个LR(1)项目集具有项目集具有相同的心相同的心, 即除去搜索即除去搜索符之后，这两个集合是相同的。符之后，这两个集合是相同的。n能否将核心部分相同的诸状态合并为一个状态能否将核心部分相同的诸状态合并为一个状态? ? nLALR方法方法 : 在在LR(1)项目集规范族基础上项目集规范族基础上, 合并同心集合并同心集. I7：B b, # I4：B b, a/b合合并并同同心心集集 I4：B b, a/b I3：B aB, a/b B a

54、B, a/b B b, a/b I7：B b, # I8：B aB, a/b I6：B aB, # B aB, # B b, # I9：B aB, #I47: Bb , a/b/# I89: BaB , a/b/# I36: BaB , a/b/# BaB , a/b/# Bb , a/b/# 7.5 LALR(1)分析分析n合并同心集的几个问题：合并同心集的几个问题：n合并同心集合并同心集是指心相同的项目集合并在一起，相应是指心相同的项目集合并在一起，相应的超前搜索符合并的超前搜索符合并n同心集的项目经转换函数所达仍为同心集同心集的项目经转换函数所达仍为同心集LR(1)LR(1)项目集和转换

55、函数项目集和转换函数(0)S S (1)S BB(2)B aB (3)B bS I0：S S, # S BB, # B aB, a/b B b, a/bB I2：S BB, # B aB, # B b, # I4：B b, a/bb I3：B aB, a/b B aB, a/b B b, a/bbb I7：B b, # I8：B aB, a/baB I5：S BB, # I6：B aB, # B aB, # B b, #Baa I9：B aB, #baB I1：S S , #7.5 LALR(1)分析分析n合并同心集的几个问题：合并同心集的几个问题：n合并同心集合并同心集是指心相同的项目集合并

56、在一起，相应是指心相同的项目集合并在一起，相应的超前搜索符合并的超前搜索符合并n同心集的项目经转换函数所达仍为同心集同心集的项目经转换函数所达仍为同心集n若文法是若文法是LR(1)文法，合并同心项目集可能会引起文法，合并同心项目集可能会引起冲突冲突n同心集的合并不会引起新的同心集的合并不会引起新的移进移进 归约冲突归约冲突n同心集的合并有可能产生新的同心集的合并有可能产生新的归约归约 归约冲突归约冲突同心集的合并不会引起新的同心集的合并不会引起新的移进移进 归约冲突归约冲突n是否存在移进是否存在移进-规约冲突？规约冲突？ 不存在不存在nu1 ，u2a=u1 a u2 a =Ik:A-.， u1

57、 B-.a ，bIm:A-. ，u1 /u2 B-.a ，b/cIj:A-. ，u2 B-.a ，c同心集的合并有可能产生新的同心集的合并有可能产生新的归约归约 归约冲突归约冲突G :(0) S S(1) S aAd (2) S bBd (3) S aBe (4) S bAe(5) A c (6) B cA c , dB c , e A c , eB c , d 合并同心集合并同心集A c , d/eB c , d/e 产生归约产生归约- -归约冲突归约冲突LR(1)LR(1)项目集和转换函数项目集和转换函数(0)S S (1)S BB(2)B aB (3)B bS I0：S S, # S B

58、B, # B aB, a/b B b, a/bB I2：S BB, # B aB, # B b, # I4：B b, a/bb I3：B aB, a/b B aB, a/b B b, a/bbb I7：B b, # I8：B aB, a/baB I5：S BB, # I6：B aB, # B aB, # B b, #Baa I9：B aB, #baB I1：S S , #合并的具体实例：合并的具体实例：LALR(1)LALR(1)项目集和转换函数项目集和转换函数(0)S S (1)S BB(2)B aB (3)B bS I0：S S, # S BB, # B aB, a/b B b, a/bB

59、 I2：S BB, # B aB, # B b, # I47：B b, a/b/#b I36：B aB, a/b/# B aB, a/b/# B b, a/b/#bb I89：B aB, a/b/#aB I5：S BB, #Baa I1：S S , #合并的具体实例：合并的具体实例：(1)构造文法的构造文法的LR(1)项目集族项目集族 C=I0,I1, ,In(2)把所有的同心集合并在一起，把所有的同心集合并在一起， 记记 C =J0, J1, , Jm为合并后的新族，为合并后的新族， 含有项目含有项目 SS, # 的的Jk为分析表的初态。为分析表的初态。构造构造 LALR(1)分析表算法分析

60、表算法(3) (3) 从从C C 构造构造ACTIONACTION表表若若AaB, bJk ，且，且GO(Jk, a)= Jj， 则置则置ACTIONk, a为为 sj 若若A, aJk，j是产生式是产生式A的编号的编号则置则置ACTIONk, a为为 rj， 若若SS, # Jk，则置，则置ACTIONk, #为为 acc(4) GOTO(4) GOTO表的构造表的构造若若GO(Jk, A)=Ji，则置，则置GOTOk, A = i(5) (5) 分析表中凡不能用分析表中凡不能用(3)(3)、(4)(4)填入信息的空白格均填上填入信息的空白格均填上“出出错标志错标志”。n若表中不存在冲突，则