第6章1LR分析程序

1、第6章 分析程序及其自动构造6.16.1 自下而上自下而上分析及其分析及其LRLR分析概述分析概述6.26.2 LR (0) LR (0) 分析分析6.36.3 SLR(1) SLR(1) 分析分析6.46.4 LRLR（1 1）分析分析6.56.5 LALRLALR分析分析6.66.6 使用二义文法使用二义文法自下而上分析算法自下而上分析算法 能力强能力强 构造复杂构造复杂 最常用和最有效的模型最常用和最有效的模型-移进归约移进归约(动作）动作）总控程序outputInput#栈状态文法符号分析表产生式表将输入分成两部分：未消化和半消化的总控程序outputInput#未消化半消化的分析表产

2、生式表S E E T | E + T T int | (E)Reduce: 如能找到一产生式如能找到一产生式 A w 且栈中的内容是 qw (q 可能为空), 则可以将其归约为 qA.即倒过来用这个产生式.如上例, 若栈中内容是 (int ，我们使用产生式 T int并把栈中内容归约为(T Shift: 如不能执行一个归约且在未消化的输入中还有如不能执行一个归约且在未消化的输入中还有 token ，就把它从输入移到栈中. 如上例,假定栈中内容是 ( ,输入中还有输入中还有 int+int)#.不能不能对对( 执行一个归约，因为它不和任何产生式的右端匹执行一个归约，因为它不和任何产生式的右端匹配

3、配.所以把输入的第一个符号移到栈中,于是栈中内容是 (int ，而余留的输入是 +int)# .Reduce的一个特殊情况：栈中的全部内容w归约为开始符号S （即施用 S w） ，且没有余留输入了，意味着已成功分且没有余留输入了，意味着已成功分析了整个输入串析了整个输入串.移进归约分析中还会出现一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试分析 int+)时就会发生错误.移进移进-归约模型分析归约模型分析(int + int)的过程的过程 STACK REMAINING INPUT PARSER ACTION 1 (int + int)# Shift2

4、 ( int + int)# Shift3 (int + int)# Reduce: T int 4 (T + int)# Reduce: E T5 (E + int)# Shift6 (E + int)# Shift7 (E + int )# Reduce: T int8 (E + T )# Reduce: E E + T9 (E )# Shift10 (E) # Reduce: T (E)11 T # Reduce: E T12 E # Reduce: S E13 S #(E + T )# Reduce:E E + T why?不用 E T(E ) # 若使用了E T，在栈中形成的(E+E

5、不是规范句型的活前缀（viable prefixes）（E+E不能和任何产生式的右端匹配 （E+E）不是规范句型 活前缀 是规范句型（右句型）的前缀，但不超过句柄移进归约分析的栈中出现的内容加上余留输入构成规范句型规范推导 规范句型 规范归约最右推导：在推导的任何一步最右推导：在推导的任何一步，其中其中、是句型，都是对是句型，都是对中中的最右非终结符进行替换的最右非终结符进行替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型GS： SE E EE+T|T T(E)|intEE+T|T T(E)|intS SE T (E) (E+

6、T) (E+int) (T+int) (int+int)规范归约规范归约假定假定是是G G的一个句子，称序列的一个句子，称序列n n , ,n-1n-1 ,0 0是是 的一个的一个规范归约规范归约如果该序列满足：如果该序列满足：（1） n n = = （2 2） 0 0为文法的开始符号为文法的开始符号（3 3）对任何）对任何j,0j=n, j,0j if E then S | if E then S else S如输入if E then if E then S else S分析某一时刻，栈的内容:if E then if E then S而 else 是下一 token 归约还是移进？ 特定的

7、一种shift-reduce实现技术分析L R 最右推导最右推导分析器模型和分析算法分析器模型和分析算法分析特征讨论分析特征讨论分析器模型总控程序outputInput#S1 XmS1X1S0 #栈状态文法符号ACTION GOTOLR分析表产生式表ACTION GOTOa c e b d # S A B0 S2 11 acc2 S4 33 S5 S64 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 r1 LR分析算法置ip指向输入串w的第一个符号令S为栈顶状态 a是ip指向的

8、符号重复 beginif ACTIONS,a=Sj then begin PUSH j,a(进栈) ip 前进(指向下一输入符号) endelse if ACTIONS,a=rj (第j条产生式为A)分析程序then beginpop | 项令当前栈顶状态为Spush GOTOS,A和A(进栈)endelse if ACTIONs,a=accthen return (成功）else errorend.重复例6.1:GS: S a A c B e 1 A b2 A Ab3 B d4w=abbcde#Step states. Syms. The rest of inputaction goto1

9、0 # abbcde# s22 02 #a bbcde# s43 024 #ab bcde# r2 goto(2,A)4 023 #aA s65 0236 #aAb cde# r36 023 #aA s57 0235 #aAc de# s88 02358 #aAcd e# r4 9 02357 #aAcB s910 023579 #aAcBe # r111 01 #S acc文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进A

10、 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#的移进的移进-规约分析过程规约分析过程SaAcBe aAcde aAbcde abbcde步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde#

11、 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 4） #aA bcde# 移进移进 023 S6 6） #aA cde# 移进移进 023 S5 7） #aAc de# 移进移进 0235 S8 9） #aAcB e# 移进移进 02357 S911） #S # 接受接受 01 acc对输入串对输入串abbcde#的的LR分析过程分析过程 3） #ab bcde# 归约归约(Ab) 024 r2 3 5） #aAb cde# 归约归约(AAb) 0236 r3 3 8） # aAcd e# 归约归约(Bd) 02358 r4 710） #aAcBe # 归约归约(SaAc

12、Be) 023579 r1 1ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1状态栈状态栈ACTIONGOTO文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dSi:移进，将状态移进，将状态i和和输入符输入符进栈进栈ri:归约，用第归约，用第i个产生式归约，同个产生式归约，同时状态栈与符号栈退出相应个符时状态栈与符号栈退出相应个符号，并把号，并把GOTO表相应状态和第表相应状态和第i个产生式的个产生式的左部非终结非终结符入栈

13、。符入栈。推导过程S aAcBe1 aAcd4e1 aAb3cd4e1ab2b3cd4e1规约时在栈里的句型的前缀规约前可在栈里的规范句型(不含句柄)的前缀ab2aaAb3a,aAaAcd4a,aA,aAcaAcBe1a,aA,aAc,aAcBRLR 文法文法对于一个对于一个cfg 文法文法, 如果能够构造一张如果能够构造一张 LR 分析表分析表, 使得它的每一个入口均是唯一的使得它的每一个入口均是唯一的（Sj,rj,acc,空白），则称该空白），则称该 cfg 是是LR 文文法法分析特征特征:规范的规范的符号栈中的符号是规范句型的前缀，且不符号栈中的符号是规范句型的前缀，且不含句柄以后的任何

14、符号含句柄以后的任何符号(活前缀活前缀)分析决策依据分析决策依据栈顶状态和现行输入符栈顶状态和现行输入符号？识别活前缀的号？识别活前缀的 DFA.四种技术LR(0) SLR(1) LR(1) LALR(1)LR(0) 分析 LR(0)文法文法 能力最弱，理论上最重要能力最弱，理论上最重要存在存在FA 识别活前缀识别活前缀识别活前缀的识别活前缀的DFA如何构造如何构造（LR(0)项目集规范族的构造）项目集规范族的构造）LR(0)分析表的构造分析表的构造活前缀G=(Vn,Vt,P,S),若有S A , 是的前缀,则称是文法G的活前缀.其中S是对原文法扩充(SS)增加的非终结符. ? 为使S不出现在

15、任何产生式的右部.如G=(S,a,SSa,Sa,S)RR*识别活前缀的DFA启示:LR分析使用的信息之一是句柄左部 的内容.定义(非终结符的左文)LC(A)= | SA, V*, Vt*,对拓广文法的开始符号S:LC(S)=若BA 则:LC(A)LC(B).R*GS: (0) SS (1) S a A c B e (2)A b (3) A Ab (4)B d每个非终结符的左文方程组LC(S)=LC(S)=LC(S).LC(A)=LC(S).a LC(A)LC(B)=LC(S).aAc化简为：S= S=SA=Sa+A B=SaAc用代入法求解得：S= S= A=a+A B=aAc令 =S，S，A

16、， B，a，A,c则方程两边都是上的正规式而A=a+A 即为 A=a | A 由正规式所表示的正规集得： A=a GS: (0) SS (1) S a A c B e (2)A b (3) A Ab (4)B d定义(产生式的LR(0)左文)LR(0)LC(A)=| =且SA , Vt*有推论：LR(0)LC(A )=LC(A).则有:LR(0)LC(SS)=SLR(0)(LC(SaAcBe)=aAcBeLR(0)LC(Ab)=abLR(0)LC(AAb)=aAbLR(0)LC(Bd)=aAcd ( =VnVt)上的正规式R*Rx59214306710111216151718SaaaaAAAb

17、ccbdeB B DFAx235789641AbaSbcBed构造LR(0)项目集规范族LR(0)项目集规范族项目集规范族(构成识别一个文法的活前缀的构成识别一个文法的活前缀的DFA的状态的全体的状态的全体) 。 LR（0）项目或配置（项目或配置（ item or configuration）.-在右端某一位置有圆点的在右端某一位置有圆点的G的产生式的产生式 A xyz A.xyz Ax.yz Axy.z Axyz. 如：如：SaAd SaAd S.aAd Sa .Ad SaA .d SaAd . S.aAd Sa .Ad SaA .d SaAd . 活前缀与句柄的关系：GS:若若S = A

18、A = r是是的前缀，则的前缀，则称称r是是G的一个活前缀的一个活前缀1.活前缀已含有句柄的全部符号，表明产生式活前缀已含有句柄的全部符号，表明产生式A的的 右右部部已出现在栈顶已出现在栈顶2.2.活前缀只含句柄的一部分符号表明活前缀只含句柄的一部分符号表明A1 12 2的右部子的右部子串串1 1已出现在栈顶，期待从输入串中看到已出现在栈顶，期待从输入串中看到2 2推出的推出的符符号号3. 活前缀不含有句柄的任何符号，此时期望活前缀不含有句柄的任何符号，此时期望A的右部的右部所推出的符号串所推出的符号串R*R活前缀,与句柄 ,与 LR(0)项目为刻划这种分析过程中的文法为刻划这种分析过程中的文

19、法G的每一个产生式的右部符号已的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。点的产生式来指示位置。 A刻划产生式刻划产生式A的的 右部右部已出现在栈顶已出现在栈顶 A1 12 2 刻划刻划A1 12 2的右部子串的右部子串1 1已出现在栈顶，已出现在栈顶，期待从输入串中看到期待从输入串中看到2 2推出的推出的符号符号 A 刻划没有句柄的任何符号刻划没有句柄的任何符号在栈顶在栈顶，此时期望，此时期望A的右部所推出的符号串的右部所推出的符号串对于对于A的的LR(0)LR(0)项目只有项目只有A

20、构造识别活前缀的DFALR（0） 项目集的闭包项目集的闭包LOSURE, GO 函数，函数， function CLOSURE (I); /* I 是项目集是项目集*/ J:= I;repeat for J 中的每个项目中的每个项目A .B 和产生式和产生式 B ，若若B . 不在不在J中中 do 将将 B . 加到加到J中中 until 再没有项目加到再没有项目加到J中中return J; GO (I,x)= CLOSURE(J) ; 其中，其中， I:项目集，项目集，x: 文法符号，文法符号， J=任何形如任何形如A x. 的项目的项目|A .x ILR（0） 项目集的闭包LOSURE若当

21、前处于A XYZ刻划的情况，期望移进 First(Y)中的某些符号，假如有产生式 Y u | w . 那么Y u和Y w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况.A XYZY uY w 这三个项目对应移进归约分析的同一个状态,这三个项目构成一个配置集, 对应每个配置集，分析表将有一个状态.LR(0)项目集规范族计算计算LR（0）项目集规范族项目集规范族 C=I0 ，I1 , . In Procedure itemsets(G); Begin C := CLOSURE (S.S) Repeat For C 中每一项目集中每一项目集I和每一文法符号和每一文法符号x Do if

22、 GO(I,x) 非空且不属于非空且不属于C Then 把把 GO(I,x) 放入放入C中中 Until C 不再增大不再增大End;例例6.26.2文法文法G G: :（0 0）SE (1) EaA (2) EbBSE (1) EaA (2) EbB (3) AcA (4) Ad (5) BcB (3) AcA (4) Ad (5) BcB (7) Bd (7) Bd LR(0) LR(0) 项目集规范族（项目集规范族（识别识别G G的活前缀的的活前缀的DFA)DFA)： I I0:0: S SE IE I1 1: SE: SE I I2 2: Ea: EaA A E EaA A.cA aA

23、 A.cA E EbB AbB Ad d I I3 3: Eb: EbB IB I4 4: : Ac.A Ac.A I5: B BcB AcB AcA BccA BcB B B Bd A .d Bd A .d BcB cB B Bd d I6: I7: I I8 8: : EaAaA EbBbB AcAcA I9: BcBcB I I1010: Ad: Ad I I1111: BcB: BcB LR(0)分析表的构造假定假定C=I0, I1,，In，令每个项目集令每个项目集Ik的下标的下标k 为分析为分析器的一个状态，因此，器的一个状态，因此，G 的的LR(0)分析表含有状态分析表含有状态0，

24、1，n。令那个含有项目令那个含有项目SS的的Ik的下标的下标k为为初态。初态。ACTION和和GOTO可按如下方法构造：可按如下方法构造：若项目若项目Aaa属于属于Ik且且GO (Ik, a)= Ij, a为终结符，则置为终结符，则置ACTIONk, a为为“把状态把状态j和符号和符号a移进栈移进栈”，简记为，简记为“sj”;若项目若项目A属于属于Ik, 那么，对任何终结符那么，对任何终结符a, 置置ACTIONk, a为为“用产生式用产生式A进行规约进行规约”，简记为，简记为“rj”;其中，假定其中，假定A为为文法文法GG的第的第j j个产生式；个产生式；若项目若项目SSS属于属于Ik, 则

25、置则置ACTIONk, #为为“接受接受”，简记为，简记为“acc”;若若GO (Ik, A)= Ij, A为非终结符，则置为非终结符，则置GOTO(k, A)=j;分析表中凡不能用规则分析表中凡不能用规则1至至4填入信息的空白格均置上填入信息的空白格均置上“出错标志出错标志”。按上述算法构造的含有按上述算法构造的含有ACTION和和GOTO两部分的分析两部分的分析表，如果每个入口不含多重定义，则称它为文法表，如果每个入口不含多重定义，则称它为文法G的的一张一张LR(0)表。具有表。具有LR(0)表的文法表的文法G称为一个称为一个LR（0）文法。文法。LR(0)文法是无二义的。文法是无二义的。

26、例例6.26.2文法文法G G: :（0 0）SE (1) EaA (2) EbBSE (1) EaA (2) EbB (3) AcA (4) Ad (5) BcB (3) AcA (4) Ad (5) BcB (7) Bd (7) Bd ACTION GOTOa c b d # E A B0 S2 S3 11 acc2 S4 S10 63 S5 S11 74 S4 S10 85 S5 S11 9 6 r1 r1 r1 r1 r17 r2 r2 r2 r2 r28 r3 r3 r3 r3 r3 r39 r5 r5 r5 r5 r5 r510 r4 r4 r4 r4 r4 r411 r6 r6

27、r6 r6 r6 r6 LR(0)项目根据根据圆点所在的位置圆点所在的位置和和圆点后圆点后是是终结符终结符还是还是非终结符非终结符或为或为空空把项目分为以把项目分为以下几种：下几种：移进移进项目，形如项目，形如 A a a是是终结符终结符, , , V* 以下同以下同待约待约项目，形如项目，形如 A B 归约归约项目，形如项目，形如 A 接受接受项目，形如项目，形如 S S A的的LR(0)LR(0)项目只有项目只有A 是是归约归约项目项目作用？作用？例例6.16.1GS为为: S a A c B e A b A Ab B d 1)构造识别活前缀的构造识别活前缀的DFA 2)构造它的构造它的L

28、R(0)分析表。分析表。 3)分别给出对输入分别给出对输入符号串符号串abbcdeabbcde和和 1) Abbbce Abbbce的的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 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

29、SaAbbcBedGL= ab+ cde例6. 1 GS的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 #aA bcde# s6 5 0236 #aAb cde# r3 3 6 023 #aA cde# s5 7 023

30、5 #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 0236 #aAb ce# r3 3 6 023 #aA ce# s5 7 0235 #aAc e# 出错出错说明说明

31、abbce#abbce#不是例不是例6.1 6.1 文法文法 GSGS的的句子句子 对输入串对输入串abbce#的分析过程的分析过程Real a,b,例例6.36.3 ：（：（0 0）SS (1)SS (1)SrDSrD (2) DD,i (3) Di (2) DD,i (3) DiLRLR（0 0）项目项目1. 1. SSS 2. SSS 2. SS 3. S 3. SrD rD 4. Sr4. SrD 5. SrDD 5. SrD 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. D

32、ii 11. Di 例：（例：（0 0）SS (1)SS (1)SrDSrD(2) DD,i (3) Di(2) DD,i (3) DiLRLR（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 I i I6 6: DD: DD，i i D Di i其中其中I I3 3中含有移进中含有移进/ /归约冲突归约冲突 文法不是文法不是LR(0)LR(0)的，如何解

33、决？的，如何解决？I I3 3: Sr D: Sr D DD，i例例6.3文法的文法的LR（0）分析表有多重入口分析表有多重入口 状态状态 ACTION GOTO r , i # S D 0 S2 1 1 acc 2 S4 3 3 r1 S5 r1 r1 r1 4 r3 r3 r3 r3 5 S6 6 r2 r2 r2 r2I I3 3: Sr D: Sr D DD，i使用使用FOLLOW(S) FOLLOW(S) , = 信息信息 解决冲突解决冲突例例6.3文法的文法的SLR（1）分析表分析表 状态状态 ACTION GOTO r , i # S D 0 S2 1 1 acc 2 S4 3

34、3 r1 S5 r1 r1 4 r3 r3 r3 r3 5 S6 6 r2 r2 r2 r2SLR(1)技术如果如果 LR(0) 项目集规范族中某个项目集项目集规范族中某个项目集IK含含 移进移进/归约归约 归约归约/归约归约 冲突：冲突：IK : .A.b ,.b , P . , Q . , 若若FOLLOW(Q) FOLLOW(P) = FOLLOW(P) b = FOLLOW(Q) b =则解决冲突的SLR(1)技术： action k,b = 移进对a FOLLOW (P) 则 action k,a =用 P 归约归约 对a FOLLOW (Q) 则 action k,a =用 Q 归

35、约归约能用能用SLR(1)技术技术解决冲突的文法称为SLR(1)文法。SLR(1)文法是无二义的。 SLR表假定假定C=I0, I1,，In，令每个项目集令每个项目集Ik的下标的下标k 为分析器的一个状态，因为分析器的一个状态，因此，此，G 的的SLR分析表含有状态分析表含有状态0，1，n。令那个含有项目令那个含有项目SS的的Ik的下标的下标k为初态。为初态。ACTION表和表和GOTO表可按如下方法构造：表可按如下方法构造：若项目若项目Aaa属于属于Ik且且GO (Ik, a)= Ij, a为终结符，则置为终结符，则置ACTIONk, a为为“把状态把状态j和符号和符号a移进栈移进栈”，简记

36、为，简记为“sj”;若项目若项目A属于属于Ik, 那么，对任何输入符号那么，对任何输入符号a, aFOLLOW(A),FOLLOW(A),置置ACTIONk, a为为“用产生式用产生式A进行规约进行规约”，简记为，简记为“rj”;其中，其中，假定假定A为文法为文法GG的第的第j j个产生式；个产生式；若项目若项目SSS属于属于Ik, 则置则置ACTIONk, #为为“接受接受”，简记为，简记为“acc”;若若GO (Ik, A)= Ij, A为非终结符，则置为非终结符，则置GOTO(k, A)=j;分析表中凡不能用规则分析表中凡不能用规则1至至4填入信息的空白格均置上填入信息的空白格均置上“出

37、错标志出错标志”。按上述算法构造的含有按上述算法构造的含有ACTION和和GOTO两部分的分析表，如果每两部分的分析表，如果每个入口不含多重定义，则称它为文法个入口不含多重定义，则称它为文法G的一张的一张SLR表。具有表。具有SLR表表的文法的文法G称为一个称为一个SLR（1）文法。文法。（0）SS (1)SrD(2) DD,i (3) Di例例6.3文法的文法的SLR（1）分析表分析表 状态状态 ACTION GOTO r , i # S D 0 S2 1 1 acc 2 S4 3 3 S5 r1 4 r3 r3 5 S6 6 r2 r2二义性文法在分析中的应用例例6.4表达式文法：表达式文

38、法： E E E E+E E E*EE (E)E i 二义性文法不是二义性文法不是LR文法，文法，但是对某些二义性文法，但是对某些二义性文法， 人为人为地给出优先性和结合性可能构地给出优先性和结合性可能构造出更有效的造出更有效的LR分析器分析器如：如：规定在表达式文法中规定在表达式文法中i的的优先性最高优先性最高 * *和和 都都服从左结合服从左结合 当前符号状态 + * ( ) i # EI0:EEEE+EEE*EE(E)EiI2:E(E)EE+EEE*EE(E)EiI3:EiI1:EEEE+EEE*EI1:I4:EE+EEE+EEE*EE(E)EiI5:EE*EEE+EEE*EE(E)Ei

39、acc算术表达式二义性文法的算术表达式二义性文法的 LR(0)项目集及状态转换矩阵项目集及状态转换矩阵 当前 符号状态 + * ( ) i # EI2:I2:I3:I6:E(E)EE+EEE*EI3:I4:I2:I3:I7:EE+EEE+EEE*EI5:I2:I3:I8:EE*EEE+EEE*EI6:I4:I5:I9:E(E) I7:I4:I5:I8:I4:I5:I9:在在I1，I7，I8中中 存在存在移进移进 -归约归约冲突冲突 在I1，I7，I8中 存在移进 -归约冲突I1：E E E E+E E E*E I7 ： E E+E E E+E E E*E I8 ： E E*E E E+E E

40、E*EI1 ：移进移进和和接受接受无无冲突冲突I7， I8用用优先关系优先关系和和结合性结合性解解决冲突。决冲突。规定：规定：*优先于优先于+，都服从都服从左左结合结合I7 ：遇：遇*移进移进 遇遇+归归约约I8 ：遇：遇+，* 都都归归约约 0 S2 S3 1 1 S4 S5 acc 2 S2 S2 6 3 r4 r4 r4 r4 4 S2 S3 7 5 S2 S3 8 6 S4 S5 S9 7 r1 S5 r1 r1 8 r2 r2 r2 r1 9 r3 r3 r3 r3ACTIONGOTO+*()i#E状态二义性表达式文法的二义性表达式文法的LR分析表分析表 1 0 # i+i*i# S

41、3 2 03 #i +i* i# r4 1 3 01 #E +i*i# S4 4 014 #E+ i*i# S3 5 0143 #E+i *i# r4 6 0147 #E+E *i# S5 7 01475 #E+E* i# S3 8 014753 #E+E*i # r4 8 9 014758 #E+E*E # r2 10 0147 #E+E # r1 1 11 01 #E # acc步骤状态栈符号栈输入串ACTIONGOTO 对输入串对输入串i+i*i的分析过程的分析过程 SLR（1）的局限的局限例例6.56.5：文法：文法G G: :（0 0）SS (1) SaAd (2) SbAcSS (

42、1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae (3) Saec (4) Sbed (5) AeLR(0) LR(0) 项目集规范族项目集规范族： I I0:0: S SS IS I1 1: SS: SS I I2 2: Sa: SaAd Ad S SaAd SaaAd Saec ec S SbAc AbAc Ae e S Saec aec S Sbedbed ? SLR 0）SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae I I3 3: Sb: SbAc IAc I4 4: : I5: Sb Sbed SaAed

43、 SaAd d Saeaec c A Ae Ae e Ae I6: I7: I I8 8: : SbASbAc c SbeSbed d SaAdSaAd Ae Ae I9: Saecaec I I1010: SbAc: SbAc I I1111: Sbed: Sbed ACTION GOTOa c e b d # S A 0 S2 S3 11 acc2 S5 43 S7 64 S85 r5 r5S9 r5 r5 r5 r5 6 S107 r7 r7 r7 r7 r7 S11 r78 r1 r1 r1 r1 r1 r19 r3 r3 r3 r3 r3 r310 r2 r2 r2 r2 r2 r2

44、11 r4 r4 r4 r4 r4 r4（0）SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae I I5 5: S: S aeaec Ic I7 7: S: S bebed d A A ee A A ee S=S=aAd=aed S=S=bAc=bec =S=aAd=aed S=S=bAc=bec S=S=aec S=S=bed S=S=aec S=S=bed ？信息？信息 在特定的规范推导中，哪些输入符号能跟在句柄之后在特定的规范推导中，哪些输入符号能跟在句柄之后GS:若若S = A A = r是是的前缀，则的前缀，则称称r是是G的一个活前缀的一个活

45、前缀. 哪个项目在什么条件下对某个活前缀有效哪个项目在什么条件下对某个活前缀有效RRRRRRRRRRRR例6.6GS:(0) SS (1) SL=R (2) SR(3) L *R (4) Lid (5) RLLR(0)LR(0)项目集规范族项目集规范族I0: S S I5: L id S L = R S R I6: S L =R L *R R L L id L *R R L L idI1: S S I7: L *RI2: S L = R I8: R L R L I9: S L=RI3: S RI4: L *R R L L *R L idI2: S L = R R L 考虑分析表达式 id =

46、id时，在工作到 I2 处已经把第一个 id 归约到 L了, 看到下一个输入 = 要作决策，第一个项目设置 Action2,= 为S6, 即把赋值的其它部分找到. 但 =也是属于 Follow(R) 的. 第二个项目要用 RL归约.出现 shift-reduce 冲突. SLR 分析程序没有记住足够的左文以决定当见到一个能归约到 L的串而在输入中碰上 = 时会发生什么.虽然在栈顶的符号序列可以归约到 R,但我们不能要这个选择，因为不可能有规范句型以 R = 开头 (有以 *R = . 开头的规范句型).SLR（1）的局限的局限 follow 集包含了在任何句型中跟在 R 后的符号但没有严格地指

47、出在一个特定的推导里哪些符号跟在 R后.所以需要扩充状态以包含更多的信息：follow 集的哪些部分 才是进到该状态最恰当的归约依据. 处在状态 2时，试图构建句子有两条路： 1.S L = R 或 2.S R L. 如下一符号是 =, 那就不能用第二个选择，必须用第一个,即移进. 只有下一个符号是#时才能归约. 尽管 = 属于 Follow(R) ，那是因为一个 R 可以出现在别的上下文中，在现在这个特定的情况，它不合适,因为在用S R L推导句子时, = 不能跟在R后.讨论例讨论例6.66.6后有以下结果：后有以下结果：不是不是LR(0)LR(0)文法文法 I I2 2 SL SL=R R

48、 L.=R R L.中存在移进中存在移进/ /归约冲突归约冲突SLR能否能否解决解决I I2 2中的冲突中的冲突 FOLLOWFOLLOW（R R）=#,=#,=与与=交不为空交不为空 不是不是SLR（1）文法文法 想想早知信息早知信息. . 若用若用 RL L 归约归约 则形成则形成 R=R= 而而 R=R=不是活前缀不是活前缀LR（1）方法方法若若 A .B I则则 B . （ B 是一产生式）是一产生式） I把把FIRST（ ）中的符号作为用中的符号作为用B 归约的搜索符，归约的搜索符，向前搜索向前搜索符符 LR（1）项目项目( 配置）的一般形式配置）的一般形式 A . ， a 意味着处

49、在栈顶是 的相应状态，期望相应的相应状态，期望相应 在栈顶的状态，然后只有当跟在跟在 后的token是终结符a时进行归约时进行归约 。 a 称作该项目项目( 配置）配置） 的向前搜索符（ lookahead ）向前搜索符（ lookahead ）只对圆点在最后的项目起作用A , a.意味着处在栈中是 的相应状态，但的相应状态，但只有当下一个输入符是a时才能进行归约时才能进行归约. a 要么是一个终结符，要么是输入结束标记#有多个向前搜索符，比如a,b,c时，可写作 A u, a/b/c 构造LR(1)项目集规范族和G0函数closure(I)按如下方式构造按如下方式构造(1) I的任何项目属的

50、任何项目属closure(I)；(2)若若A1 1BB2 2，aaclosure(I)，B是一产生式，那么是一产生式，那么对于对于FIRST(2 2a a)中的每个终结符中的每个终结符b，如果如果B,b,b不在不在closure(I)中，则把它加进去；中，则把它加进去；(3)重复（重复（1）（）（2），直至），直至closure(I)不再增大。不再增大。GO函数：函数：若若I是一个项目集，是一个项目集，X是一个文法符号是一个文法符号GO(I, X)= closure(J) 其中其中 J= 任何形如任何形如AXX,a,a的项目的项目A.X,aI.X,aILR(I)LR(I)项目规范族项目规范族C

51、 C的构造算法类同的构造算法类同LR(0)LR(0)的，只是初始时：的，只是初始时：C= closure(SSS,#);S,#);例6.5的LR(1)项目集规范族I0: S SS,S, # I5: S aeaec,c,# S aAd, aAd, # A ee,d ,d S S bAc, bAc, # I6: S bAbAc, c, # S aec, aec, # I7: S bebed, d, # S bed, bed, # A ee,c ,c I I1 1: S: S SS, ,# I I8 8: S: S aAdaAd, , # I2: S aaAd, Ad, # I9: S aecaec

52、, , # S aaec, ec, # I10: S bAcbAc, , # A e, d Ie, d I1111: : S bedbed, , # I3: S bbAc, Ac, # S bbed, ed, # Ae,c e,c I I4 4: S: S aAaAd, d, # 规范的LR(1)分析表的构造假定假定LR(1)项目集规范族项目集规范族C=I0, I1,，In，令每个项目集令每个项目集Ik的下标的下标k 为分析器的一为分析器的一个状态，个状态，G 的的LR（1）分析表含有状态分析表含有状态0，1，n。1.令那个含有项目令那个含有项目SS ，#的的Ik的下标的下标k为状态为状态0（

53、初态）（初态）.ACTION表和表和GOTO表表可按如下方法构造可按如下方法构造2.若项目若项目A,b,b属于属于Ik, 那么那么置置ACTIONk, b为为“用产生式用产生式A进行进行规约规约”，简记为，简记为“rj”;其中，假定其中，假定A为文法为文法GG的第的第j j个产生式个产生式3.3.若项目若项目AA,bA,b属于属于Ik且且GO (Ik, b)= Ij,则置则置ACTIONk, b为为“把状把状态态j和符号和符号b移进栈移进栈”，简记为，简记为“sj”;4.若项目若项目SSS,#,#属于属于Ik, 则置则置ACTIONk, #为为“接受接受”，简记为，简记为“acc”; 5.若若

54、GO (Ik, A)= Ij, A为非终结符，则置为非终结符，则置GOTO(k, A)=j;分析表分析中凡不能用规则分析表分析中凡不能用规则1至至5填入信息的空白格均置上填入信息的空白格均置上“出错标志出错标志”。按上述算法构造的含有按上述算法构造的含有ACTION和和GOTO两部分的分析表，如果每个入口不两部分的分析表，如果每个入口不含多重定义，则称它为文法含多重定义，则称它为文法G的一张的一张规范的LR(1)分析分析表。具有表。具有规范的LR(1)表的文法表的文法G称为一个称为一个LR（1）文法。文法。LR(1) 文法满足下面两个条件1.如果一个项目集里有项目 A uxv , a ， x是

55、终结符，那就不会有项目B u, x 2.项目集里所有归约项目 的向前搜索符不相交，即不能同时含有项目 A u, a 和B v , aLR（K）项目项目 A . ， a1 a2 aK LR(1)比SLR（1）能力强例例 (0) SS (1)SL=RL=R(2)SR(2)SR(3)L (3)L * *R R(4)Lid(4)Lid(5)RL(5)RL不能用SLR（1）技术解决，但能用LR（1）I1:SS ,#I5:Li ,=/#I7:L*R ,=/#I8:RL ,=/#I9:SL=R ,#I3:SR ,#I12:Li ,#I10:RL ,#I13:L*R ,#I0:S S,# S L=R,# S R,# L *R,=/#L i,=/# R L,# I4: L *R,=/# R L,=/#L i,=/# L *R,=/#I6:S L= R,# R L,# L *R,# L i,# I11:L * R,# R L,# L *R,# L i,# I2:S L =R,# R L,# sR=LRii*iiRLLRL*例6.6的 LR(1)项目集及转换函数每个每个SLR（1）文法都是文法都是LR（1）的，一个的，一