编译原理课件04(6)SLR(1)分析法

4.5.3SLR（1）分析法这个条件比较苛刻，对于大多数程序设计语言来说，一般都不能满足LR(0)文法的条件，即使是描述一个算述表达式的简单文法也不是LR(0)文法。例考虑算术表达式的文法：每一个LR(0)项目集中都不含有冲突的项目，由于LR(0)文法要求文法的E→E+T|TT→T*F|FF→(E)|id4.5.3SLR（1）分析法将文法拓广并对规则进行编号直接构造出识别文法规范句型活前缀的DFA下如图所示。0.E'→E1.E→E+T2.E→T3.T→T*F4.T→F5.F→(E)6.F→idE'→·EE→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI0:EI1:E'→E·E→E·+TI2:E→T·T→T·*FTI3:T→F·FF→(·E)E→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI4:((FTI5:F→id·idE→E+·TT→·T*FT→·FF→·(E)F→·idI6:+F(idI7:T→T*·FF→·(E)F→·id(idid*I8:F→(E·)E→E·+TE+0E'→E1E→E+T2E→T3T→T*F4T→F5F→(E)6F→idE→E+·TT→·T*FT→·FF→·(E)F→·idI6:idI8:F→(E·)E→E·+TE+TI9:E→E+T·T→T·*T*FI10:T→T*F·I11:F→(E)·)识别表达式文法活前缀的DFAE'→·EE→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI0:EI1:E'→E·E→E·+TI2:E→T·T→T·*FTI3:T→F·FF→(·E)E→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI4:((FTI5:F→id·id+F(idI7:T→T*·FF→·(E)F→·id(idid*E+4.5.3SLR（1）分析法不难看出在I1，I2，I9中既含有移进项目，又含有归约项目，因而这个表达式的文法不是LR(0)文法。根据构造LR(0)分析表的方法，构造出的LR(0)分析表中在2状态和9状态下面临输入符号‘*’时含多重定义元素，见下表。表达式文法的LR(0)分析表012345S5S4S6accS5S4r2r2S7r2r2r2r2r4r4r4r4r4r4123823r6r6r6r6r6r6GOTO状态ACTIONid+*()$ETF678910S5S4S5S4S6S11r1r1S7r1r1r1r1r3r3r3r3r3r3r5r5r5r5r5r51193104.5.3SLR（1）分析法为了对语言句子进行确定性的分析，需要解决移进—归约或归约—归约冲突。我们采用对含有冲突的项目集向前查看一个输入符号的办法来解决冲突，这种分析法称为简单的LR分析法，即SLR(1)分析法。4.5.3SLR（1）分析法仔细分析构造LR(0)分析表的方法，容易看出使分析表出现多重定义的原因在于其中的规则2，即对于每一个项目集Ik中的归约项目A→α•，不管当前输入符号是什么，都将ACTION表中第K行的各个元素均置为rj，其中j为规则A→α的编号。4.5.3SLR（1）分析法因此，当一个LR(0)项目集规范族中存在一个含移进—归约冲突和归约—归约冲突的项目集时则在分析表第K行中遇输入符号b必然会出现多重定义元素。IK={X→δ·bB,A→α·,B→r·}对含冲突的项目集，仅根据LR(0)项目本身的信息是无法解决冲突的。需要向前查看一个输入符号以考察当前所处的环境。4.5.3SLR（1）分析法对归约项目A→α•和B→γ•，只需要考察当将句柄α或γ归约为A或B时，直接跟在A或B后的终结符的集合即FOLLOW(A)和FOLLOW(B)互不相交且不包含移进符号b，即满足：IK={X→δ·bB,A→α·,B→r·}FOLLOW(A)∩FOLLOW(B)=ΦFOLLOW(B)∩{b}=ΦFOLLOW(A)∩{b}=Φ4.5.3SLR（1）分析法那么，当状态K面临输入符号a时，可按以下规则解决冲突：(1)若a=b则移进(2)若aFOLLOW(A)，则用规则A进行归约。(3)若aFOLLOW(B)，则用规则Br进行归约。(4)此外报错。4.5.3SLR（1）分析法一般而言，若一个LR(0)项目集I中有m个移进项目和n个归约项目时：对所有移进项目向前看一符号集合{a1,a2,…,am}和FOLLOW(B1),FOLLOW(B2),…，FOLLOW(Bn)两两相交为Φ时，则项目集I中冲突仍可用下述规则解决冲突。I:{A1→α1·a1β1,A2→α2·a2β2,…,Am→αm·amβm,B1→r1·,B2→r2·,…,Bn→rn·}4.5.3SLR（1）分析法设a为当前输入符：(1)若a∈{a1,a2,…,am}则移进。(3)此外报错。(2)若a∈FOLLOW(Bi),i=1,2,…,n,则用Bi→ri进行归约。这种用来解决分析动作冲突的方法称为SLR(1)方法。4.5.3SLR（1）分析法现在分别考察上例中的三个项目集I1,I2,I9中冲突能否用SLR(1)方法解决。由于FOLLOW(E')={$}∩{+}=Φ，且E'→E•是“接受”项目，所以I1中的接受—移进冲突可以用SLR(1)方法解决。如果对于一个文法的某些LR(0)项目集或LR(0)分析表中所含有的动作冲突都能用SLR(1)方法解决，则称这个文法是SLR(1)文法。I1={E'→E·,E→E·+T}4.5.3SLR（1）分析法由于FOLLOW(E)={+,),$}∩{*}=Φ,因此面临输入符为‘＋’,‘）’,‘$’时，用规则E→T进行归约，当面临输入符‘*’时，则移进，I2中移进—归约冲突可以用SLR(1)方法解决。与I2中情况类似，其项目集中移进—归约冲突可用SLR(1)方法解决。因此该文法是SLR(1)文法。I2={E→T·,T→T·*F}I9={E→E+T·,T→T·*F}4.5.3SLR（1）分析法SLR(1)分析表的构造与LR(0)分析表的构造基本相同。仅对LR(0)分析表构造算法中的规则2进行如下修改：若归约项目A→α•属于Ik，则对任何终结符a∈FOLLOW(A)置ACTION[k,a]=rj，其中A→α为文法的第j条规则。4.5.3SLR（1）分析法按上述方法对前例中的算术表达式文法构造出SLR(1)分析表如表所示：FOLLOW(E')={$}FOLLOW(E)={+,),$}0E'→E1E→E+T2E→T3T→T*F4T→F5F→(E)6F→idFOLLOW(T)={+,),$,*}E→E+·TT→·T*FT→·FF→·(E)F→·idI6:idI8:F→(E·)E→E·+TE+TI9:E→E+T·T→T·*T*FI10:T→T*F·I11:F→(E)·)识别表达式文法活前缀的DFAE'→·EE→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI0:EI1:E'→E·E→E·+TI2:E→T·T→T·*FTI3:T→F·FF→(·E)E→·E+TE→·TT→·T*FT→·FF→·(E)F→·idI4:((FTI5:F→id·id+F(idI7:T→T*·FF→·(E)F→·id(idid*E+G[E]的SLR(1)分析表GOTO状态ACTIONid+*()$ETF012345S5S4S6accS5S4r2S7r2r2r4r4r4r4123823r6r6r6r6678910S5S4S5S4S6S11r1S7r1r1r3r3r3r3r5r5r5r51193104.5.3SLR（1）分析法若文法的SLR(1)分析表不含多重定义元素，则称文法G为SLR(1)文法。例1设有拓广文法G[S´]0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→a4.5.3SLR（1）分析法(1)构造识别文法规范句型活前缀的DFA。(2)判断该文法是否SLR(1)文法，若是，构造SLR(1)分析表，若不是，请说明理由。该文法的LR(0)项目集规范族及转换函数如下图所示:I0:S'→·SS→·SbS→·bAaSI1:S'→S·S→S·bbI2:S→b·AaA→·aScA→·aSbA→·aI3:S→Sb·bI4:S→bA·aS→·SbS→·bAaA→a·ScA→a·SbA→a·I5:abAaI6:S→bAa·I7:S→S·bA→aS·cA→aS·bSI8:A→aSc·文法G[S']LR(0)项目集及转换函数I9:A→aSb·S→Sb·cb0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→a4.5.3SLR（1）分析法分析所有这些项目集，可知在项目集I1，I5中存在移进—归约冲突，I9中存在归约—归约冲突，因此该文法不是LR(0)文法。考虑含冲突的项目集能否用SLR(1)方法解决。0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→aFOLLOW(A)={a}FOLLOW(S)={b,c,$}FOLLOW(S')={$}4.5.3SLR（1）分析法由于有FOLLOW(S')∩{b}={$}∩{b}=Φ，I1中的移进—归约冲突可以用SLR(1)方法解决。由于有FOLLOW(A)∩{b}={a}∩{b}=Φ，I5中的移进—归约冲突可以用SLR(1)方法解决。I1={S'→S·,S→S·b}I5={A→a·,S→·bAa}4.5.3SLR（1）分析法由于有FOLLOW(A)∩FOLLOW(S)={a}∩{b,c,$}=Φ,I9中的归约—归约冲突也可用SLR(1)方法解决。所以该文法是SLR(1)文法。相应的SLR(1)分析表如下表:I9={A→aSb·,S→Sb·}4.5.3SLR（1）分析法0S2112345r1r1r1r2r2r2S5r4r1r1r146789S3accS9S8S6r5S2r37状态GOTOACTIONabc$SAG[S]的SLR(1)分析表0.S'→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→aI0:S′→·SS→·SbS→·bAaSI1:S′→S·S→S·bbI2:S→b·AaA→·aScA→·aSbA→·aI3:S→Sb·bI4:S→bA·aS→·SbS→·bAaA→a·ScA→a·SbA→a·I5:abAaI6:S→bAa·I7:S→S·bA→aS·cA→aS·bSI8:A→aSc·文法G[S’]LR(0)项目集及转换函数I9:A→aSb·S→Sb·cb0.S′→S1.S→Sb2.S→bAa3.A→aSc4.A→aSb5.A→a4.5.3SLR（1）分析法SLR(1)分析法是一种简单而实用的方法,其造表演算法简单,状态数目少,且大多数程序设计语言都可以用SLR(1)文法来定义。但是仍存在这样一些文法，其项目集中的移进一归约冲突或归约—归约冲突不能用SLR(1)方法解决。4.5.3SLR（1）分析法例2下列拓广文法G´为我们首先用S'→•S作为初态集的项目，然后用闭包函数和转换函数构造识别文法G'活前缀的DFA如下图所示。0.S'→S1.S→L=R2.S→R3.L→*R4.L→i5.R→LI0:S→L=·RL→·*RL→·iR→·LS'→·SS→·L=RS→·RL→·*RL→·iR→·LSI1:S'→S·I2:S→L·=RR→L·LI3:S→R·RL→*·RL→·iR→·LL→·*RI4:**iiI5:L→i·I6:=*I7:L→*R·RiLI8:R→L·LRI9:S→L=R·LR(0)识别G'活前缀的DFA0.S′→S1.S→L=R2.S→R3.L→*R4.L→i5.R→L4.5.3SLR（1）分析法可以发现项目集I2中存在移进和归约冲突：因此，I2中移进和归约冲突不能用SLR(1)方法解决。SL=R*R=RSRI2={S→L·=RR→L·}由于FOLLOW(R)∩{=}＝{=,$}∩{=}≠Ф0.S′→S1.S→L=R2.S→R3.L→*R4.L→i5.R→L4.5.3SLR（1）分析法1.SLR(1)方法为什么不能解决I2中的移进和归约冲突?2.怎样解决I2中的移进和归约冲突?问题: