编译原理-LR分析法.ppt

7 自底向上分析(Bottom-up Parsing),LR分析器,7.1 LR分析器 自底向上分析(Bottom-up Parsing),“L”:left-to-right scanning 自左向右扫描“R”:rightmost derivation in reverse 最右推导的逆,5.3.4.1 LR分析方法概述5.3.4.2 LR(0)分析器5.3.4.3 SLR(1)分析器5.3.4.4 LR(1)分析器5.3.4.5 LALR(1)分析器,7.1.1 LR(0)分析器,例：考虑文法GS S aA A cA|d 识别accd是否该文法的句子。,Ac.AA.cAA.d s2,Sa.AA.cAA.d s1,S.aA s0,start,AcA.s4,SaA.s5,Ad.s3,A,d,d,A,c,a,c,Ac.AA.cAA.d s2,Sa.AA.cAA.d s1,S.aA s0,start,AcA.s4,SaA.s5,Ad.s3,A,d,d,A,c,a,c,s0 accd#shifts0as1 ccd#shifts0as1cs2 cd#shifts0as1cs2cs2 d#shifts0as1cs2cs2ds3#reduce Ad s0as1cs2cs2As4#reduce AcA s0as1cs2As4#reduce AcA s0as1As5#reduce SaA s0S#accept,GS:1:S aA 2:A cA3:A daccdL(GS)?,根据上述例子，可以总结如下：一、概念 产生式右部符号被识别的多少,在产生式右部加上.指示位置。项目：在文法产生式右部某个位置标有.的产生式，称为文法的一个LR(0)项目。为了叙述方便，形如 A.的项目称为归约项目；形如 A.B 的项目称为待约项目(基本项目)；形如 A.a 的项目称为移进项目。,定义(有效项目)：项目A1.2对活前缀=1 是有效的，如果存在规范推导 S*Aw 12w。若项目 A1.B2 对活前缀=1 是有效的，且 B 是产生式，则项目 B.对活前缀=1 也是有效的。,据假设，存在一个规范推导S*Aw 1 B 2w设2w*xw,则对任何B 有规范推导 rm S*Aw 1 B 2w 1 B xw 1 xw所以 B.对活前缀 1 也是有效的。,：伽马：艾塔,定义(有效项目集，项目集规范族)：文法G的某个活前缀的所有有效项目组成的集合，称为活前缀的LR(0)有效项目集。文法G的所有有效项目集组成的集合，称为G的LR(0)项目集规范族。,定义(项目闭包)：设I是文法G的一个LR(0)项目集合，I的项目闭包closure(I)定义如下：1、I closure(I)。2、若项目A.B closure(I)，且 B 是G的产生式，则项目B.closure(I)。3、closure(I)仅包含上述两条规则确定的LR(0)项目。,定义(转移函数)：若I是文法G的一个LR(0)项目集，X是G中的文法符号。定义 go(I,X)=closure(J)其中 J=A X.|A.X I 称函数go(I,X)为转移函数。项目A X.称为项目A.X后继。,二、识别句柄和活前缀的自动机,若文法G=(VT,VN,S,P)，则识别G的句柄的自动机为DFA M=(=VTVN，Q=G的LR(0)项目集规范族,q0=closure(S.S)，F=所有含归约项目的有效项目集组成的集合，=go(I,X)。若将所有状态均视为终态，则识别活前缀的自动机DFA M=(=VTVN,Q=G的LR(0)项目集规范族,q0=closure(S.S)，F=Q，=go(I,X)。,定理：对于拓广文法G的每一个活前缀，它的有效项目集恰好是从识别 G 活前缀的自动机的初态出发，经过 路径所到达的那个状态所代表的项目集合。,例：设拓广文法GS的产生式为：S S S aA|bB A cA|d B cB|d,Ac.AA.cAA.d I4,Sa.AA.cAA.d I2,Sb.BB.cBB.d I3,Bc.BB.cBB.d I5,S.SS.aAS.bB I0,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,LR(0)分析表,三、LR分析器的结构和工作过程,LR分析器的结构如图，它的工作过程由算法1描述。,输入,a1.ai.an#,LR驱动程序,分析表,输出,栈,smXmsm-1Xm-1.s0,图4.19 一个LR分析器的模型,action goto,算法1:LR分析算法,输入：一个输入串w和文法G的一张LR分析表M。输出：若w L(G),输出w的一个自底向上的分析；否则，输出一个出错表示。方法：分别置放s0到栈中和w#到输入缓冲器中;置ip指向w#的第一个符号；repeat forever begin 令s是栈顶状态且a是ip所指向的符号 if actions,a=shift s then begin 将a和s先后压入栈内；使ip指向输入串中的下一个符号；end,算法1:LR分析算法,else if actions,a=reduce A then begin 从栈顶弹出2*|个符号；令s是当前栈顶状态；把A和gotos,A先后入栈；输出产生式A end else if actions,a=accept then return else error()end,7.1.2 SLR(1)分析,若有效项目集中存在冲突动作:I=X.b,A.,B.,设当前输入符号为a,1.若a=b,则移进;2.若aFollow(A),则用A 进行归约;3.若aFollow(B),则用B 进行归约;4.其余情况报错.,SLR分析算法,算法2(构造SLR分析表)输入：一个拓广文法G输出：对于G的分析表的action 子表和goto子表方法：1.构造G的LR(0)项目集规范族。2.对于状态Ii的分析动作如下：(a)若A.aB Ii且 go(Ii,a)=Ij actioni,a=shift j(b)若A.Ii,对于所有a Follow(A)actioni,a=reduce A,A S(c)若SS.Ii,actioni,#=accept3.若go(Ii,A)=Ij,AVN,则 gotoi,A=j4.分析表其余位置为error,SLR(SLR(1)算法：如果文法G按上述算法构造出的分析表不存在冲突动作，则称G为SLR文法。类似地，不难定义LR(0)文法。,若将上述算法的2(b)步中的aFollow(A)改为aVT#，则由此修改后的算法所定义的文法，称为LR(0)文法。,问题.如何定义LR(0)文法？,例：设文法GE的产生式为,EE+T|T TT*F|F F(E)|id 并用SLR(1)方法分析id*id+idL(GE)?G的拓广文法GE：(0)E E(4)TF(1)EE+T(5)F(E)(2)ET(6)F id(3)TT*F,I0:E.E E.E+T E.T T.T*F T.F F.(E)F.idI1(I0 E):EE.EE.+TI2(I0 T)(I4 T):ET.TT.*F,I3(I0 F)(I4 F)(I6 F):TF.I4(I0()(I4()(I6()(I7():F(.E)E.E+T E.T T.T*F T.F F.(E)F.id,I5(I0 id)(I4 id)(I6 id)(I7 id):Fid.I6(I1+)(I8+)EE+.T T.T*F T.F F.(E)F.id,I7(I2*)(I9*):TT*.F F.(E)F.idI8(I4 E):F(E.)EE.+TI9(I6 T):EE+T.TT.*FI10(I7 F):TT*F.I11(I8):F(E).,G：(0)E E(4)TF(1)EE+T(5)F(E)(2)ET(6)F id(3)TT*F,E E,E E+T,E T,T T*F,T F,F(E),F id,E,EE E E+T,T,E T T T*F,(,F(E)E E+TE TT T*FT F F(E)F id,I0,I1,I2,I6,F,T F,I3,F id,id,I5,T,I2,F,I3,id,I5,(,E E+TT T*FT F F(E)F id,+,*,T T*F F(E)F id,I7,F(E)E E+T,E,I8,T,E E+T T T*F,I9,F,I3,id,I5,(,F,T T*F,I10,id,I4,(,I4,*,I7,),F(E),+,I6,I11,E E,E E+T,E T,T T*F,T F,F(E),F id,E,EE E E+T,T,E T T T*F,(,F(E)E E+TE TT T*FT F F(E)F id,I0,I1,I2,I6,F,T F,I3,F id,id,I5,T,I2,F,I3,id,I5,(,E E+TT T*FT F F(E)F id,+,*,T T*F F(E)F id,I7,F(E)E E+T,E,I8,T,E E+T T T*F,I9,F,I3,id,I5,(,F,T T*F,I10,id,I4,(,I4,*,I7,),F(E),+,I6,I11,I0,I1,I6,I9,E,+,T,*,to I7,F,to I3,(,to I4,id,to I5,I2,I7,I10,T,*,F,(,to I4,id,to I5,I3,F,I4,I8,I11,(,E,),+,to I6,T,to I4,F,to I5,I5,id,id,(,图4.24 识别文法(4.22)的活前缀的 DFA,I1:EE I2:E T I9:E E+T E E+T T T*F T T*FI=X b,A,B 若bFOLLOW(A)FOLLOW(B)=则，面对当前读入符号a，状态I的解决方法：1.若a=b,则移进。2.若ab,且a FOLLOW(A),则用A 进行归约。3.若ab,且a FOLLOW(B),则用B进行归约。4.此外，报错。这种解决方法是比较简单的，因此称作SLR分析，由此构造的分析表，称作SLR分析表。,对于表达式文法的例子，FOLLOW集如下：,I1:EE EE+TI2:ET T T*FI9:E E+T T T*F,G：(0)E E(4)TF(1)EE+T(5)F(E)(2)ET(6)F id(3)TT*F,I1:FOLLOW(E)+=I2:FOLLOW(E)*=I9:FOLLOW(E)*=可用SLR(1)方法实现,表4.11 文法(4.22)的SLR分析表,Follow(E)=#,+,),表：关于id*id+id的LR分析过程,LR(1)分析,例：设文法G的产生式为(1)S L=R(2)S R,拓广文法G的LR(0)项目集规范族为:I0=S.S,S.L=R,S.R,L.*R,L.id,R.L I1=SS.I2=SL.=R,RL.I3=SR.I4=L*.R,R.L,L.*R,L.id I5=Lid.I6=SL=.R,R.L,L.*R,L.id I7=L*R.I8=RL.I9=SL=R.,(3)L*R(4)L id(5)R L,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)S L=R(2)S R,(3)L*R(4)L id(5)R L,LR(1)分析表的构造,问题分析：当识别出句柄时，活前缀中与句柄相关的非终结符号A的后继符号集合，一般是非终结符号A的Follow集合的真子集。例如在前例中，若活前缀L是句柄，则它的后继符号集合为#，而Follow(L)=,#。所以，只有在输入符号为#时,用RL进行归约,而输入符号为=时,移进。可见用Follow集合来消除分析表的多重入口还是略嫌粗糙。,LR(1)项目:由LR(0)项目和一个lookahead符号组成 A.,a,LR(1)分析法的思想：用活前缀中与句柄相关的非终结符号A的后继符号(亦称为搜索符)集合，而不是Follow(A)，来避免分析表的多重入口。重新定义项目，使每个项目附带一个向前搜索符,定义(LR(1)有效项目)：LR(1)项目A.,a(aVT#)对活前缀是有效的，如果存在规范推导 S*Aww 且aFirst(w#)。定理：若LR(1)项目A.B,a对活前缀是有效的，且 B 是一个产生式，则对任何bFirst(a)，项目B.,b也是活前缀的有效项目。,例.构造文法GS的LR(1)分析表。LR(1)项目集规范族,I0:S.S#S.L=R#S.R#L.*R=/#L.id=/#R.L#I1:(I0 S)SS.#I2:(I0 L)SL.=R#RL.#I3:(I0 R)SR.#,I4:(I0*)(I4*)L*.R=/#R.L=/#L.*R=/#L.id=/#I5:(I0 id)(I4 id)Lid.=/#I6:(I2=)SL=.R#R.L#L.*R#L.id#I7:(I4 R)L*R.=/#,I8:(I4 L)RL.=/#I9:(I6 R)SL=R.#I10:(I6 L)(I11 L)RL.#I11:(I6*)(I11*)L*.R#R.L#L.*R#L.id#I12:(I6 id)(I11 id)Lid.#I13:(I11 R)L*R.#,GS:(0)SS(1)S L=R(2)S R,(3)L*R(4)L id(5)R L,action,goto,状态,=*id#S L R0 s4 s5 1 2 31 acc 2 s6 r53 r2 4 s4 s5 8 75 r4 r46 s11 s12 10 9 7 r3 r3 8 r5 r59 r110 r5 11 s11 s12 10 13 12 r413 r3,例：构造文法 S C C C c C|d的LR(1)和LALR分析表。,S.S,#S.CC,#C.cC,c/dC.d,c/d I0,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/d I3,CcC.,c/d I8,C,c,Cd.,c/d I4,d,c,图：对于文法的转移函数图,文法的LR(1)分析表,S.SS.CCC.cCC.d I0,SC.CC.cCC.d I2,SS.I1,SCC.I5,S,C,C,Cc.CC.cCC.d I3,CcC.I6,C,c,Cd.I4,d,c,c,d,文法的LR(1)分析表,文法的LALR(1)分析表,LALR分析表的构造,LR(k)方法分析能力很强，但是也耗费大量存储空间。在实际应用中，还须简化。观察图4.27可知:1、从自动机状态等价的角度来看，图中彩色相同的状态是等价的。这些等价状态的特点是，它们的LR(0)有效项目集相同。由于判断是否等价只须比较状态的输出弧，因而不难看出，LR(0)有效项目集相同的状态必定等价。2、对于初始状态I0，其中的有效项目均可从项目S.S,#推导出来；对于非初始状态I2,I3,I6，则其中“点在最左端”的项目均可由“点不在最左端”的项目推导出来。观察图也可以得到相同结果。因此在实际存储状态时，可以只存储“点不在最左端”的项目。,为了叙述方便，引入“同心项”和项目集的“核”的概念：定义(同心项)：如果两个LR(1)项目集去掉搜索符之后是相同的，则称这两个项目集具有相同的心。定义(核)：对于初始状态I0，有效项目S.S,#称为I0的核；而对于非初始状态，则其中“点不在最左端”的有效项目称为它的核。LALR分析法的基本思想：在LR(1)项目集规范族中，合并同心项以减少状态的数目；在存储LR(1)有效项目集时，仅存储其中的核。注意，由于同心项的合并，使项目的搜索符与活前缀的对应关系不唯一，降低了分析器的识别能力，参见以下两例。,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合并后得到如下部分状态图,问题:LALR分析器识别活前缀的能力是否比LR(1)的差？,答：一样。既然都是识别文法活前缀的自动机，它们就是等价的。,例：考虑文法G SS SaAd|bBd|aBe|bAe Ac Bc构造G的LR(1)项目集规范族如下,I0:S.S#S.aAd#S.bBd#S.aBe#S.bAe#I1:(I0 S)SS.#,I2:(I0 a)Sa.Ad#Sa.Be#A.c d B.c eI3:(I0 b)Sb.Bd#Sb.Ae#A.c e B.c d,I4:(I2 A)SaA.d#I5:(I2 B)SaB.e#I6:(I2 c)Ac.d Bc.eI7:(I3 B)SbB.d#I8:(I3 A)SbA.e#,I9:(I3 c)Ac.e Bc.dI10:(I4 d)SaAd.#I11:(I4 e)SaBe.#I12:(I7 d)SbBd.#I13:(I8 e)SbAe.#,若将同心项I6和I9合并，则得到项目集 I69:Ac.d/e Bc.d/e该项目集含“归约-归约”冲突。,因此，文法G是LR(1)文法，但不是LALR文法。,一、LALR(1)分析表的原理性构造方法,构造LR(1)项目集族,如果它不存在冲突,就把同心集合并在一起。若合并后不存在归约-归约冲突，则按这个集族构造文法LALR(1)分析表。,算法：LALR分析表的构造输入：拓广文法G输出：对于G的LALR(1)分析表 方法：1.构造文法的LR(1)项目集族C=I0,I1,In 2.合并C中的同心集，得到C=J0,J1,Jm 3.从C出发构造action表:(a)若A.a,b Ji且 go(Ji,a)=Jj 置actioni,a=shift j(b)若A.,a Ji,置actioni,a=r A,A S(c)若SS.,#Ji,置actioni,#=accept 4.若go(Ik,A)=Jj,AVN,则 gotok,A=j 5.分析表其余位置为error,二、LALR分析表的有效构造方法,前算法在构造LALR分析表时，耗费的存储空间与LR(1)算法完全相同，代价还是太大。可以从两个方面改进：1、存储有效项目集时，只存储它们的核，每当需要完整的有效项目集时，再根据核来计算。2、直接生成LALR项目集规范族的核，这是有效构造方法的关键。注意，LALR项目的搜索符一般是与该项目相关的非终结符号的Follow集的子集，这正是LALR分析法比SLR分析法强的原因。,直接生成LALR项目集规范族的核的方法如下：(1)构造LR(0)项目集规范族的核及其自动机。(2)为LR(0)项目集规范簇中的每个核项目配上适当的搜索符。核项目的搜索符无非有两种产生途径：若搜索符从其父核传递下来，则称这样的搜索符为“传播的”；否则，称搜索符为“自生的”。下面算法确定核项目的搜索符是自生的或者是传播的：for 有效项目集I的核K中的每一项目B.do begin J=closure(B.,#);for J中的每一个项目A.X,a do 如果a#，则有效项目集go(I,X)中的核项目AX.,a中的搜索符是自生的，否则就是传播的。,练习：已知文法：请构造LALR分析表。,构造文法的LALR(1)项目集的核。LR(0)项目集的核：,I0:S.S I1:SS.I2:SL.=R I3:SR.I4:L*.R I5:Lid.I6:SL=.R I7:L*R.I8:RL.I9:SL=R.,计算closure(S.S,#)S.S#S.L=R#S.R#L.*R#/=L.id#/=R.L#,GS:(0)SS(1)S L=R(2)S R,(3)L*R(4)L id(5)R L,表4.15 搜索符的传播,表4.16 搜索符的计算,Thanks.,