《编译原理》课程简介 (41).pdf

《《编译原理》课程简介 (41).pdf》由会员分享，可在线阅读，更多相关《《编译原理》课程简介 (41).pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编 译 原 理C O M P I L A T I O N P RIN C IP LE 第五章 语法分析自下而上分析5.3.7 SLR(1)分析表的构造5.3.7 SLR(1)分析表的构造n在构造SLR(1)分析表时，根据不同的向前看符号，将Si中的各项目所对应的动作加以区分，从而即可使冲突动作得到解决。v2、SLR(1)分析表的构造方法思想n假定一个LR(0)规范族中含有如下的项目集（状态）Si,Si=Xb,A,Bn也就是在该项目集中含有移进-归约冲突和归约-归约冲突。其中,为文法符号串，b为终结符。方法如下：p对于归约项目A，B分别求Follow(A)和Follow(B)，Follow(A)

2、是所有句型中出现在紧接A之后的终结符或“#”。5.3.7 SLR(1)分析表的构造n如果满足如下条件：pFOLLOW(A)FOLLOW(B)n那么，当在状态Si时面临某输入符号为a时，则构造分析表时用以下方法即可解决冲突动作。pFOLLOW(A)bpFOLLOW(B)b(1)若a=b，则移进。(2)若aFollow(A),则用产生式 A 进行归约。(3)若aFollow(B),则用产生式B 进行归约。(4)此外，报错。5.3.7 SLR(1)分析表的构造n如果对于一个文法的LR(0)项目集规范族所含有的动作冲突都能用以上方法来解决，则称该文法为SLR(1)文法。v3、SLR(1)分析表的构造p

3、例如文法：(0)SE (1)EE+T (2)ET (3)TT*F(4)TF (5)F(E)(6)Fi 5.3.7 SLR(1)分析表的构造n状态描述序列如下：状态项目集后继符号后继状态S0 S E E E+T E T *F F F (E)F EETTF(iS1S1S2S2S3S4S5S1 SE E E +T#SE+S12S65.3.7 SLR(1)分析表的构造状态项目集后继符号后继状态S2ET TT*F#ET*S12S7S3TF#TFS12S4F(E)E E+T E T TT*F T F F(E)Fi EETTF(iS8S8S2S2S3S4S55.3.7 SLR(1)分析表的构造状态项目集后继

4、符号后继状态S5Fi#FiS12S6 EET T T*F T F F(E)Fi TTF(iS9S9S3S4S5S7TT*F F(E)F i F(iS10S4S55.3.7 SLR(1)分析表的构造状态项目集后继符号后继状态S8F(E)EE +T)+S11S6S9EE+T TT *F#EE+T*S12S7S10TT*F#TT*F S12S11F(E)#F(E)S12S12 n由上图可见，S1、S2和S9的项目集均不相容，其有移进项目和归约项目并存，构造LR(0)分析表如下：5.3.7 SLR(1)分析表的构造状态ACTIONGOTOi+*()#ETFS0S5S4123S1S6accS2r2r2r

5、2 S7r2r2r2S3r4r4r4r4r4r4S4S5S4823S5r6r6r6r6r6r6S6S5S493S7S5S410S8S6S11S9r1r1r1 S7r1r1r1S10r3r3r3r3r3r3S11r5r5r5r5r5r55.3.7 SLR(1)分析表的构造n从上表也可见在S,S,S中存在移进-归约冲突。这个表达式不是LR(0)文法，也就不能构造LR(0)分析表，现在分别考查这三个项目（状态）中的冲突是否能用SLR(1)方法解决。p对于S1：SE ,EE T n由于Follow(S)=，而S E是唯一的接受项目，所以当且仅当遇到句子的结束符“”号时才被接受。又因=，因此S1中的冲突

6、可解决。p对于S2:S2=E T ,TT *F n计算Follow(E)=#,+,),所以Follow(E)*=n因此面临输入符为+，)或号时，则用产生式ET进行归约。n当面临输入符为*号时，则移进,其它情况则报错。5.3.7 SLR(1)分析表的构造p对于S9:S9=E E+T ,TT *F n计算Follow(E)=#,+,),所以Follow(E)*=n因此面临输入符为+，)或号时，则用产生式EE+T进行归约。n当面临输入符为*号时，则移进。其它情况则报错。n 由以上考查，该文法在S，S，S三个项目集(状态)中存在的移进-归约冲突都可以用SLR(1)方法解决，因此该文法是SLR(1)文法

7、。我们可构造其相应的SLR(1)分析表。n SLR(1)分析表的构造与LR(0)分析表的构造类似，仅在含有冲突的项目集中分别进行处理。5.3.7 SLR(1)分析表的构造n进一步分析我们可以发现如下事实：例如在状态S3中，只有一个归约项目TF，按照SLR(1)方法，在该项目中没有冲突，所以保持原来LR(0)的处理方法，不论当前面临的输入符号是什么都将用产生式TF进行归约。n但是很显然T的后跟符没有（符号，如果当前面临输入符是（，也进行归约显然是错误的。因此我们对所有归约项目都采取SLR(1)的思想，即对所有非终结符都求出其Follow集合，这样凡是归约项目仅对面临输入符号包含在该归约项目左部非

8、终结符的Follow集合中，才采取用该产生式归约的动作。n对于这样构造的SLR(1)分析表我们称它为改进的SLR(1)分析表。5.3.7 SLR(1)分析表的构造n改进的SLR(1)分析表的构造方法如下：对于A X，GO Si,X Sj ，若X Vi ，则置actionSi,X=Sj，若X Vn，则置gotoSi,X=j 对于归约项目A Si,若A为文法的第j个产生式，则对任何输入符号a，若aFollow(A)，则置actionSi,a=rj若S Si，则置actionSi,#=acc其它情况均置出错。5.3.7 SLR(1)分析表的构造状态ACTIONGOTOi+*()#ETFS0S5S41

9、23S1S6accS2r2S7r2r2S3r4r4r4r4S4S5S4823S5r6r6r6r6S6S5S493S7S5S410S8S6S11S9r1S7r1r1S10r3r3r3r3S11r5r5r5r5n改进的SLR(1)分析表如下：5.3.7 SLR(1)分析表的构造n例：文法：SxAy|xBz AaA|a BbB|an解：p1、拓广(1)SS (2)SxAy (3)SxBz (4)AaA(5)Aa (6)BbB (7)Bap2、构造DFA5.3.7 SLR(1)分析表的构造SSS xAy S xBz 0：1：SSS xAy S xBz AaAA aB bB Ba2：3：SxAy 7：SxAy 4：SxBz 8：SxBz AaAA aBaA aAaA5：9：AaAA aAaAAaAAA10：11：BbB12：Ba6：BbBBbBBaSxABaAayzBabbaA5.3.7 SLR(1)分析表的构造p3、求有关集合FOLLOW(S)=#FOLLOW(S)=#FOLLOW(A)=y FOLLOW(B)=zp4、构造SLR(1)分析表 状态ACTIONGOTOxyzab#EAB0s211acc2s5s6343s74s85r5r7s1096s12s6117r28r39r410r5s10911r612r7|编译原理谢 谢Thanks