《编译原理5.3.4-规范LR分析表的构造.ppt》由会员分享，可在线阅读，更多相关《编译原理5.3.4-规范LR分析表的构造.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、5.3.4 规范规范LR分析表的构造分析表的构造通过例子引入通过例子引入LR(kLR(k)项目项目1.LR(k)1.LR(k)项目定义项目定义2.2.有效有效LR(1)LR(1)项目项目3.3.构造构造LR(1)LR(1)项目集规范族项目集规范族4.4.构造构造LR(1)LR(1)分析表分析表5.LR(1)5.LR(1)文法文法 文法文法5.9 p113(0)S S (1)S L=R(2)S R (3)L*R(4)L i (5)R LI2 2:移进移进-归归约冲突约冲突例例:I0:SS S L=R S R L*R L i R LI6:SL=R R L L*R L iI2:SL=R R L I4
2、:L*R R L L*R L iI1:SSI3:SRI7:L*RI8:RLI5:Li I9:SL=R=R*R L i R S*i iL*LFOLOW(R)=#,=文法不含有以文法不含有以 R=R=为前缀的规范句型为前缀的规范句型,因此不能用因此不能用 R RL L 对于栈顶的对于栈顶的L L进行归约进行归约 (0)S S(1)S aAd(2)S bAc(3)S aec(4)S bed(5)A eI0:SS S aAd S bAc S aec S bedI1:SSSI2:S aAd S aec A eI3:S bAc S bed A eabAeI4:S aAd I5:S aec A eAeI6:
3、S bAc I7:S bed A edI8:S aAdcI9:S aeccI10:S bAcdI11:S bedFOLLOW(A)=c,d I I5 5,I,I7 7中冲中冲突不能用突不能用SLR(1)SLR(1)方方法解决法解决 补充例补充例1(0)S S(1)S aAd(2)S bAc(3)S aec(4)S bed(5)A eI5:S aec A eI7:S bed A e所有可能的规范推导序列所有可能的规范推导序列:S=S=aAd=aedS=S=bAc=becS=S=aecS=S=bedI I5 5识别活前缀识别活前缀aeae,不存在规范句型不存在规范句型aAcaAc,当面临输入符号为
4、当面临输入符号为c c时应移进时应移进面临面临d d时应用产生式时应用产生式AeAe归约归约 I I7 7识别活前缀识别活前缀bebe,不存在规范句型不存在规范句型bAdbAd,当面临输入符号为当面临输入符号为d d时应移进时应移进面临面临c c时应用产生式时应用产生式AeAe归约归约 结论结论:并不是并不是FOLLOW(A)FOLLOW(A)的每个元素的每个元素,在含在含A A的所有句型中的所有句型中,在在A A的后面都会出现的后面都会出现 小结小结:SLR(1)分析法中的无效归约分析法中的无效归约I2:SL=R R L(0)S S (1)S L=R(2)S R (3)L*R(4)L i (
5、5)R LFOLLOW(R)=#,=(0)S S(1)S aAd(2)S bAc(3)S aec(4)S bed(5)A eI5:S aec A eI7:S bed A eFOLLOW(A)=c,d 在在SLR(1)SLR(1)方法中方法中,若若项项目集目集I Ik k含有含有 AA,则则在状在状态态k k时时,只只要所面要所面临临的的输输入符号入符号aFOLLOW(AaFOLLOW(A)，就用，就用AA归约归约 栈栈里的符号串所构成的里的符号串所构成的活前活前缀缀未必允未必允许许把把归约为归约为A A，因，因为为可能没有一个可能没有一个规规范句型含有前范句型含有前缀缀AaAa。因此，在。因此
6、，在这这种情况下，种情况下，用用AA进进行行归约归约未必有效。未必有效。1.LR(K)1.LR(K)项目项目定义定义重新定义项目重新定义项目:AA，a a1 1a a2 2a ak k AA是一个是一个LR(0)LR(0)项目项目,称为称为心心,a a1 1a a2 2a ak k 称为称为它的它的向前搜索符串向前搜索符串(展望串展望串),a ai i是终结符是终结符,这样的一个项目称为一个这样的一个项目称为一个LR(kLR(k)项目项目。向前搜索符串仅对向前搜索符串仅对归约项目归约项目 AA，a a1 1a a2 2a ak k 有意义有意义.对于任何对于任何移进移进或或待约项目待约项目不不
7、起作用。起作用。若存在规范推导若存在规范推导则项目则项目 A A 对活前缀对活前缀 是有效的。是有效的。若若a a FirstFirst()，若若=则则 a=#a=#则则LR(1)LR(1)项目项目 A A ,a,a对于活前缀对于活前缀 是有效的。是有效的。注注:1)1)如果如果a a FirstFirst(),),即使即使a a Follow(AFollow(A),),项目项目 A A ,a,a也是无效的。也是无效的。2)2)规范规范LRLR分析法仅考虑有效的分析法仅考虑有效的LR(1)LR(1)项目。项目。2.2.有效有效LR(1)LR(1)项目项目*RR A S例例5.12:S BBB
8、aB|bS RBBRBaB RBabRaBab RaaBabRaaaBabRS*RaaBabaaaBabBaB,a 对活前缀对活前缀 =aaa是有效的是有效的*RR A SRS*R BaBBaaBBaB,#对活前缀对活前缀 =Baa是有效的是有效的3.3.构造构造LR(1)LR(1)项目集规范族项目集规范族一、项目集一、项目集I I的闭包的闭包CLOSURE(I)CLOSURE(I)(1)(1)I I的任何项目都属于的任何项目都属于CLOSURE(I)CLOSURE(I)(2)(2)若项目若项目 AAB B，a a 属于属于CLOSURE(I)CLOSURE(I)如果如果 B B,b b 原来
9、不在原来不在CLOSURE(I)CLOSURE(I)中，中，则把它加进去。则把它加进去。BB是一个产生式是一个产生式,b bFIRST(aFIRST(a)(3)(3)重复执行步骤重复执行步骤(2)(2),直到直到CLOSURE(I)CLOSURE(I)不再增大为止不再增大为止二、二、GOGO函数函数令令I I是一个项目集，是一个项目集，X X是一个文法符号，是一个文法符号，GO(I,X)GO(I,X)=CLOSURE(J)=CLOSURE(J)，其中其中J=J=任何形如任何形如 A AX X ,a a 的项目的项目|A A X X,a a I I 注：注：在执行转换函数在执行转换函数GOGO时
10、，搜索符并不改变。时，搜索符并不改变。三、构造三、构造G G的的LR(1)LR(1)项目集族项目集族C C的算法的算法 BEGIN C:=CLOSURE(SS,#);REPEAT FOR C中的每个项目集中的每个项目集I和和G 的每个文法符号的每个文法符号X IF GO(I,X)非空非空 且不属于且不属于 C THEN 把把GO(I,X)加入加入C中；中；UNTILL C不再增大；不再增大；END例例5.135.13 考虑如下拓广文法考虑如下拓广文法 p115p115 (0)S(0)S S S (1)S(1)S BB BB(2)B(2)B aBaB (3)B(3)B b b 构造构造LR(1)
11、LR(1)项目集规范族项目集规范族I I0 0:CLOSURE(:CLOSURE(SS S,#S,#)SS S S,#S S B BB B,#B B aBaB,a/ba/bB B b,b,a/ba/b S 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图图5.10 5.10 LR(1)LR(1)项目集和项目集和GOGO函
12、数函数 p116p116更正教材更正教材(0)S S (1)S BB(2)B aB(3)B b I1：S S,#4.4.构造构造LR(1)LR(1)分析表分析表(1)(1)若项目若项目 AAaa,bb I Ik k 且且GO(IGO(Ik k,a,a)=)=I Ij j ，置置 ACTIONk,aACTIONk,a 为为 s sj j。(2)(2)若项目若项目 AA ,a a I Ik k ，j j是产生式是产生式AA的编号的编号 置置 ACTIONk,ACTIONk,a a 为为r rj j ，(3)(3)若项目若项目 SSSS ，#I Ik k，置置 ACTIONkACTIONk,#,#为
13、为 accacc。(4)(4)若若GO(IGO(Ik k,A,A)=)=I Ij j，置置 GOTOk,AGOTOk,A=j j。(5)(5)分析表中凡不能用规则分析表中凡不能用规则(1)(1)(4)(4)填入的空白格均置填入的空白格均置为为“出错标志出错标志”。表表5.5 5.5 例例5.135.13 的的 LRLR分析表分析表 p116p116状状 态态ACTIONGOTOab#SB0s3s4121acc2s6s753s3S484r3r35r16s6s797r38r2r29r25.LR(1)5.LR(1)文法文法若文法若文法G按构造按构造LR(1)分析表分析表算法构造出来的算法构造出来的分
14、析表不包含多重定义项，则该文法分析表不包含多重定义项，则该文法G是是LR(1)文法。文法。注注:1）每个）每个SLR(1)文法都是文法都是LR(1)文法，文法，反之不一定成立；反之不一定成立；2）一个文法的）一个文法的规范规范LR分析表分析表比其比其SLR分分析表含有更多的状态。在严重的情况下，状析表含有更多的状态。在严重的情况下，状态数可能成倍增长。因此需要简化。态数可能成倍增长。因此需要简化。文法文法5.9 p113(0)S S (1)S L=R(2)S R (3)L*R(4)L i (5)R L例例求求LR(1)项目集规范族项目集规范族S S,#SL=R,#SR,#L*R,=/#L i,
15、=/#RL,#I0初态初态简化为简化为S S,#SL=R,#SR,#L*R,=L i,=RL,#L*R,#L i,#I0初态初态I1:Go(I0,S)S S ,#I2:Go(I0,L)SL =R,#RL,#I3:Go(I0,R)SR,#I4:Go(I0,*)L*R,=/#R L,=/#L *R,=/#L i,=/#I5:Go(I0,i)L i,=/#I6:Go(I2,=)SL=R,#R L,#L *R,#L i,#I7:Go(I4,R)L*R,=/#I8:Go(I4,L)R L,=/#Go(I4,*)同同 I4 Go(I4,i)同同 I5 I9:Go(I6,R)SL=R,#I10:Go(I6,
16、L)R L,#I11:Go(I6,*)L*R,#R L,#L *R,#L i,#I12:Go(I6,i)L i,#I13:Go(I11,R)L*R,#Go(I11,L)同同 I10 Go(I11,*)同同 I11 Go(I11,i)同同 I12 S S,#SL=R,#SR,#L*R,=/#L i,=/#RL,#I0初态初态状态状态ACTIONGOTO=i*#SLR0S5S41231acc2S6r53r24S5S4875r4r46S12S111097r3r38r5r59r110r511S12S11101312r413r3补充练习补充练习wLR(0)LR(0)分析分析,归约时向前查看的符号为归约时向前查看的符号为_wSLR(1)SLR(1)分析分析,归约时向前查看的符号为归约时向前查看的符号为_wLR(1)LR(1)分析分析,归约时向前查看的符号为归约时向前查看的符号为_向前搜索符向前搜索符无无FOLLOWFOLLOW集集