编译原理LR分析法ppt课件

7自底向上分析(Bottom-upParsing),LR分析器,1,7.1LR分析器自底向上分析(Bottom-upParsing),“L”:left-to-rightscanning自左向右扫描“R”:rightmostderivationinreverse最右推导的逆,5.3.4.1LR分析方法概述5.3.4.2LR(0)分析器5.3.4.3SLR(1)分析器5.3.4.4LR(1)分析器5.3.4.5LALR(1)分析器,2,7.1.1LR(0)分析器,例：考虑文法GSSaAAcA|d识别accd是否该文法的句子。,Ac.AA.cAA.ds2,Sa.AA.cAA.ds1,S.aAs0,start,AcA.s4,SaA.s5,Ad.s3,A,d,d,A,c,a,c,3,Ac.AA.cAA.ds2,Sa.AA.cAA.ds1,S.aAs0,start,AcA.s4,SaA.s5,Ad.s3,A,d,d,A,c,a,c,s0accd#shifts0as1ccd#shifts0as1cs2cd#shifts0as1cs2cs2d#shifts0as1cs2cs2ds3#reduceAds0as1cs2cs2As4#reduceAcAs0as1cs2As4#reduceAcAs0as1As5#reduceSaAs0S#accept,GS:1:SaA2:AcA3:AdaccdL(GS)?,4,根据上述例子，可以总结如下：一、概念产生式右部符号被识别的多少,在产生式右部加上.指示位置。项目：在文法产生式右部某个位置标有.的产生式，称为文法的一个LR(0)项目。为了叙述方便，形如A.的项目称为归约项目；形如A.B的项目称为待约项目(基本项目)；形如A.a的项目称为移进项目。,5,定义(有效项目)：项目A1.2对活前缀=1是有效的，如果存在规范推导S*Aw12w。若项目A1.B2对活前缀=1是有效的，且B是产生式，则项目B.对活前缀=1也是有效的。,据假设，存在一个规范推导S*Aw1B2w设2w*xw,则对任何B有规范推导rmS*Aw1B2w1Bxw1xw所以B.对活前缀1也是有效的。,：伽马：艾塔,6,定义(有效项目集，项目集规范族)：文法G的某个活前缀的所有有效项目组成的集合，称为活前缀的LR(0)有效项目集。文法G的所有有效项目集组成的集合，称为G的LR(0)项目集规范族。,7,定义(项目闭包)：设I是文法G的一个LR(0)项目集合，I的项目闭包closure(I)定义如下：1、Iclosure(I)。2、若项目A.Bclosure(I)，且B是G的产生式，则项目B.closure(I)。3、closure(I)仅包含上述两条规则确定的LR(0)项目。,8,定义(转移函数)：若I是文法G的一个LR(0)项目集，X是G中的文法符号。定义go(I,X)=closure(J)其中J=AX.|A.XI称函数go(I,X)为转移函数。项目AX.称为项目A.X后继。,9,二、识别句柄和活前缀的自动机,若文法G=(VT,VN,S,P)，则识别G的句柄的自动机为DFAM=(=VTVN，Q=G的LR(0)项目集规范族,q0=closure(S.S)，F=所有含归约项目的有效项目集组成的集合，=go(I,X)。若将所有状态均视为终态，则识别活前缀的自动机DFAM=(=VTVN,Q=G的LR(0)项目集规范族,q0=closure(S.S)，F=Q，=go(I,X)。,10,定理：对于拓广文法G的每一个活前缀，它的有效项目集恰好是从识别G活前缀的自动机的初态出发，经过路径所到达的那个状态所代表的项目集合。,11,例：设拓广文法GS的产生式为：SSSaA|bBAcA|dBcB|d,12,Ac.AA.cAA.dI4,Sa.AA.cAA.dI2,Sb.BB.cBB.dI3,Bc.BB.cBB.dI5,S.SS.aAS.bBI0,start,SS.I1,AcA.I8,SaA.I6,Ad.I10,A,d,d,A,c,a,b,S,SbB.I7,BcB.I6,Bd.I11,B,d,d,B,c,c,c,识别文法活前缀的DFA,13,LR(0)分析表,14,三、LR分析器的结构和工作过程,LR分析器的结构如图，它的工作过程由算法1描述。,输入,a1.ai.an#,LR驱动程序,分析表,输出,栈,smXmsm-1Xm-1.s0,图4.19一个LR分析器的模型,actiongoto,15,算法1:LR分析算法,输入：一个输入串w和文法G的一张LR分析表M。输出：若wL(G),输出w的一个自底向上的分析；否则，输出一个出错表示。方法：分别置放s0到栈中和w#到输入缓冲器中;置ip指向w#的第一个符号；repeatforeverbegin令s是栈顶状态且a是ip所指向的符号ifactions,a=shiftsthenbegin将a和s先后压入栈内；使ip指向输入串中的下一个符号；end,16,算法1:LR分析算法,elseifactions,a=reduceAthenbegin从栈顶弹出2*|个符号；令s是当前栈顶状态；把A和gotos,A先后入栈；输出产生式Aendelseifactions,a=acceptthenreturnelseerror()end,17,7.1.2SLR(1)分析,若有效项目集中存在冲突动作:I=X.b,A.,B.,设当前输入符号为a,1.若a=b,则移进;2.若aFollow(A),则用A进行归约;3.若aFollow(B),则用B进行归约;4.其余情况报错.,18,SLR分析算法,算法2(构造SLR分析表)输入：一个拓广文法G输出：对于G的分析表的action子表和goto子表方法：1.构造G的LR(0)项目集规范族。2.对于状态Ii的分析动作如下：(a)若A.aBIi且go(Ii,a)=Ijactioni,a=shiftj(b)若A.Ii,对于所有aFollow(A)actioni,a=reduceA,AS(c)若SS.Ii,actioni,#=accept3.若go(Ii,A)=Ij,AVN,则gotoi,A=j4.分析表其余位置为error,19,SLR(SLR(1)算法：如果文法G按上述算法构造出的分析表不存在冲突动作，则称G为SLR文法。类似地，不难定义LR(0)文法。,若将上述算法的2(b)步中的aFollow(A)改为aVT#，则由此修改后的算法所定义的文法，称为LR(0)文法。,问题.如何定义LR(0)文法？,20,例：设文法GE的产生式为,EE+T|TTT*F|FF(E)|id并用SLR(1)方法分析id*id+idL(GE)?G的拓广文法GE：(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fid(3)TT*F,21,I0:E.EE.E+TE.TT.T*FT.FF.(E)F.idI1(I0E):EE.EE.+TI2(I0T)(I4T):ET.TT.*F,I3(I0F)(I4F)(I6F):TF.I4(I0()(I4()(I6()(I7():F(.E)E.E+TE.TT.T*FT.FF.(E)F.id,I5(I0id)(I4id)(I6id)(I7id):Fid.I6(I1+)(I8+)EE+.TT.T*FT.FF.(E)F.id,I7(I2*)(I9*):TT*.FF.(E)F.idI8(I4E):F(E.)EE.+TI9(I6T):EE+T.TT.*FI10(I7F):TT*F.I11(I8):F(E).,G：(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fid(3)TT*F,22,EE,EE+T,ET,TT*F,TF,F(E),Fid,E,EEEE+T,T,ETTT*F,(,F(E)EE+TETTT*FTFF(E)Fid,I0,I1,I2,I6,F,TF,I3,Fid,id,I5,T,I2,F,I3,id,I5,(,EE+TTT*FTFF(E)Fid,+,*,TT*FF(E)Fid,I7,F(E)EE+T,E,I8,T,EE+TTT*F,I9,F,I3,id,I5,(,F,TT*F,I10,id,I4,(,I4,*,I7,),F(E),+,I6,I11,23,EE,EE+T,ET,TT*F,TF,F(E),Fid,E,EEEE+T,T,ETTT*F,(,F(E)EE+TETTT*FTFF(E)Fid,I0,I1,I2,I6,F,TF,I3,Fid,id,I5,T,I2,F,I3,id,I5,(,EE+TTT*FTFF(E)Fid,+,*,TT*FF(E)Fid,I7,F(E)EE+T,E,I8,T,EE+TTT*F,I9,F,I3,id,I5,(,F,TT*F,I10,id,I4,(,I4,*,I7,),F(E),+,I6,I11,24,I0,I1,I6,I9,E,+,T,*,toI7,F,toI3,(,toI4,id,toI5,I2,I7,I10,T,*,F,(,toI4,id,toI5,I3,F,I4,I8,I11,(,E,),+,toI6,T,toI4,F,toI5,I5,id,id,(,图4.24识别文法(4.22)的活前缀的DFA,25,I1:EEI2:ETI9:EE+TEE+TTT*FTT*FI=Xb,A,B若bFOLLOW(A)FOLLOW(B)=则，面对当前读入符号a，状态I的解决方法：1.若a=b,则移进。2.若ab,且aFOLLOW(A),则用A进行归约。3.若ab,且aFOLLOW(B),则用B进行归约。4.此外，报错。这种解决方法是比较简单的，因此称作SLR分析，由此构造的分析表，称作SLR分析表。,26,对于表达式文法的例子，FOLLOW集如下：,I1:EEEE+TI2:ETTT*FI9:EE+TTT*F,G：(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fid(3)TT*F,I1:FOLLOW(E)+=I2:FOLLOW(E)*=I9:FOLLOW(E)*=可用SLR(1)方法实现,27,表4.11文法(4.22)的SLR分析表,Follow(E)=#,+,),28,表：关于id*id+id的LR分析过程,29,7.1.3LR(1)分析,例：设文法G的产生式为(1)SL=R(2)SR,拓广文法G的LR(0)项目集规范族为:I0=S.S,S.L=R,S.R,L.*R,L.id,R.LI1=SS.I2=SL.=R,RL.I3=SR.I4=L*.R,R.L,L.*R,L.idI5=Lid.I6=SL=.R,R.L,L.*R,L.idI7=L*R.I8=RL.I9=SL=R.,(3)L*R(4)Lid(5)RL,30,I1,I0,I3,I2,I6,I9,I8,I7,I5,I4,start,S,R,L,id,*,=,id,id,L,L,R,*,*,R,图:识别文法GS活前缀的DFA,GS:(0)SS(1)SL=R(2)SR,(3)L*R(4)Lid(5)RL,31,LR(1)分析表的构造,问题分析：当识别出句柄时，活前缀中与句柄相关的非终结符号A的后继符号集合，一般是非终结符号A的Follow集合的真子集。例如在前例中，若活前缀L是句柄，则它的后继符号集合为#，而Follow(L)=,#。所以，只有在输入符号为#时,用RL进行归约,而输入符号为=时,移进。可见用Follow集合来消除分析表的多重入口还是略嫌粗糙。,32,LR(1)项目:由LR(0)项目和一个lookahead符号组成A.,a,LR(1)分析法的思想：用活前缀中与句柄相关的非终结符号A的后继符号(亦称为搜索符)集合，而不是Follow(A)，来避免分析表的多重入口。重新定义项目，使每个项目附带一个向前搜索符,33,定义(LR(1)有效项目)：LR(1)项目A.,a(aVT#)对活前缀是有效的，如果存在规范推导S*Aww且aFirst(w#)。定理：若LR(1)项目A.B,a对活前缀是有效的，且B是一个产生式，则对任何bFirst(a)，项目B.,b也是活前缀的有效项目。,34,例.构造文法GS的LR(1)分析表。LR(1)项目集规范族,I0:S.S#S.L=R#S.R#L.*R=/#L.id=/#R.L#I1:(I0S)SS.#I2:(I0L)SL.=R#RL.#I3:(I0R)SR.#,I4:(I0*)(I4*)L*.R=/#R.L=/#L.*R=/#L.id=/#I5:(I0id)(I4id)Lid.=/#I6:(I2=)SL=.R#R.L#L.*R#L.id#I7:(I4R)L*R.=/#,I8:(I4L)RL.=/#I9:(I6R)SL=R.#I10:(I6L)(I11L)RL.#I11:(I6*)(I11*)L*.R#R.L#L.*R#L.id#I12:(I6id)(I11id)Lid.#I13:(I11R)L*R.#,GS:(0)SS(1)SL=R(2)SR,(3)L*R(4)Lid(5)RL,35,action,goto,状态,=*id#SLR0s4s51231acc2s6r53r24s4s5875r4r46s11s121097r3r38r5r59r110r511s11s12101312r413r3,36,例：构造文法SCCCcC|d的LR(1)和LALR分析表。,37,S.S,#S.CC,#C.cC,c/dC.d,c/dI0,SC.C,#C.cC,#C.d,#I2,SS.,#I1,SCC.,#I5,S,C,C,Cc.C,#C.cC,#C.d,#I6,CcC.,#I9,C,c,Cd.,#I7,d,c,Cc.C,c/dC.cC,c/dC.d,c/dI3,CcC.,c/dI8,C,c,Cd.,c/dI4,d,c,图：对于文法的转移函数图,38,文法的LR(1)分析表,39,S.SS.CCC.cCC.dI0,SC.CC.cCC.dI2,SS.I1,SCC.I5,S,C,C,Cc.CC.cCC.dI3,CcC.I6,C,c,Cd.I4,d,c,c,d,40,文法的LR(1)分析表,文法的LALR(1)分析表,41,7.1.4LALR分析表的构造,LR(k)方法分析能力很强，但是也耗费大量存储空间。在实际应用中，还须简化。观察图4.27可知:1、从自动机状态等价的角度来看，图中彩色相同的状态是等价的。这些等价状态的特点是，它们的LR(0)有效项目集相同。由于判断是否等价只须比较状态的输出弧，因而不难看出，LR(0)有效项目集相同的状态必定等价。2、对于初始状态I0，其中的有效项目均可从项目S.S,#推导出来；对于非初始状态I2,I3,I6，则其中“点在最左端”的项目均可由“点不在最左端”的项目推导出来。观察图也可以得到相同结果。因此在实际存储状态时，可以只存储“点不在最左端”的项目。,42,为了叙述方便，引入“同心项”和项目集的“核”的概念：定义(同心项)：如果两个LR(1)项目集去掉搜索符之后是相同的，则称这两个项目集具有相同的心。定义(核)：对于初始状态I0，有效项目S.S,#称为I0的核；而对于非初始状态，则其中“点不在最左端”的有效项目称为它的核。LALR分析法的基本思想：在LR(1)项目集规范族中，合并同心项以减少状态的数目；在存储LR(1)有效项目集时，仅存储其中的核。注意，由于同心项的合并，使项目的搜索符与活前缀的对应关系不唯一，降低了分析器的识别能力，参见以下两例。,43,Cc.C,c/d/#C.cC,c/d/#C.d,c/d/#I36,I0,Cc+|c+,CcC.,c/d/#I89,C,活前缀Cc+与搜索符#对应，而活前缀c+与搜索符c和d对应。当合并后的自动机识别出活前缀CcC时，若当前的输入符号是c或d，LR(1)分析器马上就能发现出错，而LALR分析器此时则不行，必须先归约，得到活前缀CC后才能发现出错。,例：在图中，I3和I6，I8和I9合并后得到如下部分状态图,44,问题:LALR分析器识别活前缀的能力是否比LR(1)的差？,答：一样。既然都是识别文法活前缀的自动机，它们就是等价的。,45,例：考虑文法GSSSaAd|bBd|aBe|bAeAcBc构造G的LR(1)项目集规范族如下,I0:S.S#S.aAd#S.bBd#S.aBe#S.bAe#I1:(I0S)SS.#,I2:(I0a)Sa.Ad#Sa.Be#A.cdB.ceI3:(I0b)Sb.Bd#Sb.Ae#A.ceB.cd,I4:(I2A)SaA.d#I5:(I2B)SaB.e#I6:(I2c)Ac.dBc.eI7:(I3B)SbB.d#I8:(I3A)SbA.e#,I9:(I3c)Ac.eBc.dI10:(I4d)SaAd.#I11:(I4e)SaBe.#I12:(I7d)SbBd.#I13:(I8e)SbAe.#,46,若将同心项I6和I9合并，则得到项目集I69:Ac.d/eBc.d/e该项目集含“归约-归约”冲突。,因此，文法G是LR(1)文法，但不是LALR文法。,47,一、LALR(1)分析表的原理性构造方法,构造LR(1)项目集族,如果它不存在冲突,就把同心集合并在一起。若合并后不存在归约-归约冲突，则按这个集族构造文法LALR(1)分析表。,48,算法：LALR分析表的构造输入：拓广文法G输出：对于G的LALR(1)分析表方法：1.构造文法的LR(1)项目集族C=I0,I1,In2.合并C中的同心集，得到C=J0,J1,Jm3.从C出发构造action表:(a)若A.a,bJi且go(Ji,a)=Jj置actioni,a=shiftj(b)若A.,aJi,置actioni,a