《slr分析表的构造》ppt课件

《《slr分析表的构造》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图5.7p106识别文法活前缀的DFA从初态出发,经读出活前缀γ后,而到达的项目集称为活前缀γ的有效项目集I0:S'•EE•aAE•bBI5:Bc•BB•cBB•dI3:Eb•BB•cBB•dI2:Ea•AA•cAA•dI1:S'E•I4:Ac•AA•cAA•dI8:AcA•I10:Ad•I6:EaA•I7:EbB•I11:Bd•I9:BcB•bEaccccddddAABB有效项目如果存在规范推导则项目A1·2对活前缀1是有效的。如果2，应该移进如果2=，应该用产生式A1归约*RR12A

2、S'LR分析理论的一条基本定理:在任何时候，分析栈中的活前缀X1X2...Xm的有效项目集正是栈顶状态Sm所代表的那个集合。I0:S'•EE•aAE•bBI5:Bc•BB•cBB•dI3:Eb•BB•cBB•dI2:Ea•AA•cAA•dI1:S'E•I4:Ac•AA•cAA•dI8:AcA•I10:Ad•I6:EaA•I7:EbB•I11:Bd•I9:BcB•bEaccccddddAABBG':S'→EE→aA

3、bBA→cA

4、dB→cB

5、d项目集I5对活前缀bc有效考虑如下规范推导(1)SEbBbcB(2)S

6、EbBbcBbccB(3)SEbBbcBbcdI0:S'•EE•aAE•bBI5:Bc•BB•cBB•dI3:Eb•BB•cBB•dI2:Ea•AA•cAA•dI1:S'E•I4:Ac•AA•cAA•dI8:AcA•I10:Ad•I6:EaA•I7:EbB•I11:Bd•I9:BcB•bEaccccddddAABB同一个项目可能对好几个活前缀都有效G':S'→EE→aA

7、bBA→cA

8、dB→cB

9、d同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。这种冲突通过向前多看几

10、个输入符号,或许能够获得解决。5.3.3SLR分析表的构造SLR(1)分析法的引入:LR(0)文法的活前缀识别自动机的每一状态(项目集)都不含冲突性的项目大多数的程序设计语言的文法不能满足LR(0)文法的条件用向前查看一个符号的办法解决冲突例：设文法G的LR(0)项目集规范族中含有如下一个项目集（状态）I：I={X•b/*移进项目*/A•/*归约项目*/Bγ•/*归约项目*/}移进－归约冲突归约－归约冲突解决冲突策略（1）若a=b，则移进（2）若a∈Follow(A),则用A归约（3）若a∈Follow(B),则用Bγ归约（4）此外，报错用SLR(1

11、)方法解决冲突假定LR(0)规范族的一个项目集I中含有m个移进项目:A1→α·a1β1，A2→α·a2β2，…，Am→α·amβm同时含有n个归约项目:B1→α1·,B2→α2·,…,Bn→αn·如果集合｛a1,…,am｝、FOLLOW(B1)、…、FOLLOW(Bn)两两不相交，a是现行输入符号，则:（1）若a是某个ai，i=1,2,…,m，则移进；（2）若a∈FOLLOW(Bi)，i=1,2,…,n，则用产生式Bi→αi进行归约；（3）此外，报错。例5.11p111考虑下面的拓广文法(文法5.8)（0）SE（1）EE+T（2）ET（3）TT*F（4）T

12、F（5）F(E)（6）FI构造其LR(0)项目集规范族I0:S·EE·E+TE·TT·T*FT·FF·(E)F·iI1:SE·EE·+TI2:ET·TT·*FI3:TF·I4:F(·E)E·E+TE·TT·T*FT·FF·(E)F·iI5:Fi·I6:EE+·TT·T*FT·FF·(E)F·iI7:TT*·FF·(E)F·iI8:F(E·)EE·+TI9:EE+T·TT·*FI10:TT*F·I11:F(E)·移进-接受冲突移进-归约冲突移进-归约冲突DFA图5.8p112FOLLOW(S′)

13、={#},{#}∩{+}＝φ，因此I1中的冲突可解决。遇‘+’移进，遇‘#’接受其它情况则报错。I1:SE·EE·+T（0）SE（1）EE+T（2）ET（3）TT*F（4）TF（5）F(E)（6）FISLR(1)解决方法FOLLOW(E)={+,),#}FOLLOW(E)∩{*}=φ,因此I2中的冲突可解决。I2:ET·TT·*F（0）SE（1）EE+T（2）ET（3）TT*F（4）TF（5）F(E)（6）FIFOLLOW(E)={+,),#}FOLLOW(E)∩{*}=φ,因此I9中的冲突可解决。I9:E