《【教学课件】第6章LR分析程序及其自动构造.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第6章LR分析程序及其自动构造.ppt（58页珍藏版）》请在三一办公上搜索。
1、第6章分析程序及其自动构造,6.1自下而上分析及其LR分析概述6.2LR(0)分析6.3SLR(1)分析6.4LR（1）分析6.5LALR分析6.6使用二义文法,自下而上分析算法 能力强 构造复杂 最常用和最有效的模型-移进归约(动作）,将输入分成两部分：未消化和半消化的,总控程序,output,Input#未消化,半消化的,分析表,产生式表,S E E T|E+T T int|(E),Reduce:如能找到一产生式 A w 且栈中的内容是 qw(q 可能为空),则可以将其归约为 qA.即倒过来用这个产生式.如上例,若栈中内容是(int，我们使用产生式 T int柄把栈中内容归约为(T Shi
2、ft:如不能执行一个归约且在未消化的输入中还有 token，就把它从输入移到栈中.如上例,假定栈中内容是(,输入中还有 int+int)#.不能对(执行一个归约，因为它不和任何产生式的右端匹配.所以把输入的第一个符号移到栈中,于是栈中内容是(int，而余留的输入是+int)#.,Reduce的一个特殊情况：栈中的全部内容w归约为开始符号S（即施用 S w），且没有余留输入了，意味着已成功分析了整个输入串.移进归约分析中还会出现一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试分析 int+)时就会发生错误.,STACK REMAINING INPUT PA
3、RSER ACTION 1(int+int)#Shift2(int+int)#Shift3(int+int)#Reduce:T int 4(T+int)#Reduce:E T5(E+int)#Shift6(E+int)#Shift7(E+int)#Reduce:T int8(E+T)#Reduce:E E+T9(E)#Shift10(E)#Reduce:T(E)11 T#Reduce:E T12 E#Reduce:S E13 S#,(E+T)#Reduce:E E+T why?不用 E T(E)#若使用了E T，在栈中形成的(E+E不是规范句型的活前缀（viable prefixes）（E+E
4、不能和任何产生式的右端匹配（E+E）不是规范句型 活前缀 是规范句型（右句型）的前缀，但不超过句柄移进归约分析的栈中出现的内容加上余留输入构成规范句型,规范推导 规范句型 规范归约,最右推导：在推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型GS：SE EE+T|T T(E)|intSE T(E)(E+T)(E+int)(T+int)(int+int)规范归约假定是G的一个句子，称序列n,n-1,0是 的一个规范归约如果该序列满足：（1）n=（2）0为文法的开始符号（3）对任何j,0j=n,j-1是从j经把句柄替换为相应产生式
5、的左部而得到的,文法要求,shift-reduce or reduce-reduce 冲突（conflicts）分析程序不能决定是shift 还是 reduce或者分析程序归约时有多个产生式可选例子（dangling else）：S if E then S|if E then S else S如输入if E then if E then S else S分析某一时刻，栈的内容:if E then if E then S而 else 是下一 token 归约还是移进？,特定的一种shift-reduce实现技术分析,L R 最右推导分析器模型和分析算法分析特征讨论,分析器模型,LR分析算法,置i
6、p指向输入串w的第一个符号令S为栈顶状态 a是ip指向的符号重复 beginif ACTIONS,a=Sj then begin PUSH j,a(进栈)ip 前进(指向下一输入符号)endelse if ACTIONS,a=rj(第j条产生式为A),分析程序,then beginpop|项令当前栈顶状态为Spush GOTOS,A和A(进栈)endelse if ACTIONs,a=accthen return(成功）else errorend.重复,分析程序,例:GS:S a A c B e 1 A b2 A Ab3 B d4w=abbcde#,Step states.Syms.The r
7、est of inputaction goto1 0#abbcde#s22 02#a bbcde#s43 024#ab bcde#r2 goto(2,A)4 023#aA s65 0236#aAb cde#r36 023#aA s57 0235#aAc de#s88 02358#aAcd e#r4 9 02357#aAcB s910 023579#aAcBe#r111 01#S acc,文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1）#abbcde#移进,2）#a bbcde#移进,4）#aA bcde#移进,6
8、）#aA cde#移进,7）#aAc de#移进,9）#aAcB e#移进,11）#S#接受,符号串abbcde是否是GS的子,对输入串abbcde#的移进-规约分析过程,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,6）#aA cde#移进 023 S5,7）#aAc de#移进 0235 S8,9）#aAcB e#移进 02357 S9,11）#S#接受 01 acc,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(A
9、Ab)0236 r3 3,8）#aAcd e#归约(Bd)02358 r4 7,10）#aAcBe#归约(SaAcBe)023579 r1 1,状态栈,ACTION,GOTO,文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d,Si:移进，将状态i和输入符进栈ri:归约，用第i个产生式归约，同时状态栈与符号栈退出相应个符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。,分析程序,推导过程S aAcBe1 aAcd4e1 aAb3cd4e1ab2b3cd4e1规约时在栈里的句型的前缀规约前可在栈里的规范句型(不含句柄)的前缀ab2aaAb3a,aAaAcd4a,aA
10、,aAcaAcBe1a,aA,aAc,aAcB,R,分析程序,LR 文法对于一个cfg 文法,如果能够构造一张 LR 分析表,使得它的每一个入口均是唯一的（Sj,rj,acc,空白），则称该 cfg 是LR 文法,分析,特征:规范的符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)分析决策依据栈顶状态和现行输入符号？识别活前缀的 DFA.四种技术LR(0)SLR(1)LR(1)LALR(1),LR(0)分析,LR(0)文法 能力最弱，理论上最重要存在FA 识别活前缀识别活前缀的DFA如何构造（LR(0)项目集规范族的构造）LR(0)分析表的构造,分析,活前缀G=(Vn,Vt,P
11、,S),若有S A,是的前缀,则称是文法G的活前缀.其中S是对原文法扩充(SS)增加的非终结符.?为使S不出现在任何产生式的右部.如G=(S,a,SSa,Sa,S),R,识别活前缀的DFA,启示:LR分析使用的信息之一是句柄左部 的内容.定义(非终结符的左文)LC(A)=|SA,V*,Vt*,对拓广文法的开始符号S:LC(S)=若BA 则:LC(A)LC(B).,GS:(0)SS(1)S a A c B e(2)A b(3)A Ab(4)B d,每个非终结符的左文方程组LC(S)=LC(S)=LC(S).LC(A)=LC(S).a LC(A)LC(B)=LC(S).aAc化简为：S=S=SA=
12、Sa+A B=SaAc,用代入法求解得：S=S=A=a+A B=aAc令=S，S，A，B，a，A,c则方程两边都是上的正规式而A=a+A 即为 A=a|A 由正规式所表示的正规集得：A=a,GS:(0)SS(1)S a A c B e(2)A b(3)A Ab(4)B d,定义(产生式的LR(0)左文)LR(0)LC(A)=|=且SA,Vt*有推论：LR(0)LC(A)=LC(A).则有:LR(0)LC(SS)=SLR(0)(LC(SaAcBe)=aAcBeLR(0)LC(Ab)=abLR(0)LC(AAb)=aAbLR(0)LC(Bd)=aAcd(=VnVt)上的正规式,R,x,5,9,2,
13、14,3,0,6,7,10,11,12,16,15,17,18,S,a,a,a,a,A,A,A,b,c,c,b,d,e,B,DFA,x,2,3,5,7,A,b,a,S,b,c,B,e,d,构造LR(0)项目集规范族,LR(0)项目集规范族(构成识别一个文法的活前缀的DFA的状态的全体)。LR（0）项目或配置（item or configuration）.-在右端某一位置有圆点的G的产生式 A xyz A.xyz Ax.yz Axy.z Axyz.如：SaAd S.aAd Sa.Ad SaA.d SaAd.,活前缀与句柄的关系：,GS:若S=A=r是的前缀，则称r是G的一个活前缀1.活前缀已含有
14、句柄的全部符号，表明产生式A的 右部已出现在栈顶2.活前缀只含句柄的一部分符号表明A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号3.活前缀不含有句柄的任何符号，此时期望A的右部所推出的符号串,R,活前缀,与句柄,与 LR(0)项目,为刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。A刻划产生式A的 右部已出现在栈顶 A12 刻划A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号 A 刻划没有句柄的任何符号在栈顶，此时期望A的右部所推出的符号串对于A的LR(0)项目只有A,构造识别活前缀的D
15、FA,LR（0）项目集的闭包LOSURE,GO 函数，function CLOSURE(I);/*I 是项目集*/J:=I;repeat for J 中的每个项目A.B 和产生式 B，若B.不在J中 do 将 B.加到J中 until 再没有项目加到J中return J;GO(I,x)=CLOSURE(J);其中，I:项目集，x:文法符号，J=任何形如A x.的项目|A.x I,LR（0）项目集的闭包LOSURE,若当前处于A XYZ刻划的情况，期望移进 First(Y)中的某些符号，假如有产生式 Y u|w.那么Y u和Y w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况.A
16、 XYZY uY w 这三个项目对应移进归约分析的同一个状态,这三个项目构成一个配置集,对应每个配置集，分析表将有一个状态.,LR(0)项目集规范族,计算LR（0）项目集规范族 C=I0，I1,.In Procedure itemsets(G);Begin C:=CLOSURE(S.S)Repeat For C 中每一项目集I和每一文法符号x Do if GO(I,x)非空且不属于C Then 把 GO(I,x)放入C中 Until C 不再增大End;,例：文法G:（0）SE(1)EaA(2)EbB(3)AcA(4)Ad(5)BcB(7)Bd LR(0)项目集规范族（识别G的活前缀的DFA)
17、：I0:SE I1:SE I2:EaA EaA A.cA EbB Ad,I3:EbB I4:Ac.A I5:BcB AcA BcB Bd A.d BcB Bd I6:I7:I8:EaA EbB AcA I9:BcB I10:Ad I11:BcB,LR(0)分析表的构造,假定C=I0,I1,，In，令每个项目集Ik的下标k 为分析器的一个状态，因此，G 的LR(0)分析表含有状态0，1，n。令那个含有项目SS的Ik的下标k为初态。ACTION和GOTO可按如下方法构造：若项目Aa属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTIONk,a为“把状态j和符号a移进栈”，简记为“sj”;若项
18、目A属于Ik,那么，对任何终结符a,置ACTIONk,a为“用产生式A进行规约”，简记为“rj”;其中，假定A为文法G的第j个产生式；若项目SS属于Ik,则置ACTIONk,#为“接受”，简记为“acc”;若GO(Ik,A)=Ij,A为非终结符，则置GOTO(k,A)=j;分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。,按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)表。具有LR(0)表的文法G称为一个LR（0）文法。LR(0)文法是无二义的。,LR(0)项目,根据圆点所在的位置和圆点后是终结符还是非终结符或为空
19、把项目分为以下几种：移进项目，形如 A a a是终结符,V*以下同待约项目，形如 A B归约项目，形如 A 接受项目，形如 S S A的LR(0)项目只有A 是归约项目作用？,例：（0）SS(1)SrD(2)DD,i(3)DiLR（0）项目1.SS 2.SS 3.SrD 4.SrD 5.SrD 6.DD,i 7.DD,i 8.DD,i 9.DD,i 10.Di 11.Di,NFA,1,3,10,7,8,i,S,r,r,D,4,6,D,例：（0）SS(1)SrD(2)DD,i(3)DiLR（0）项目集规范族I0:SS I3:Sr D Sr D DDiI1:SS I4:Di I2:SrD I5:D
20、Di DD i I6:DDi Di其中I3中含有移进/归约冲突 文法不是LR(0)的，如何解决？,SLR(1)技术,若 LR(0)项目集规范族中有项目集IK含 移进/归约 归约/归约 冲突：IK:.A.b,P.,Q.,若FOLLOWQA)FOLLOW(P)=FOLLOWP(P)b=FOLLOW(Q)b=则解决冲突的SLR(1)技术：action k,b=移进对a FOLLOW(P)则 action k,a=用 P 归约 对a FOLLOW(Q)则 action k,a=用 Q 归约能用SLR(1)技术解决冲突的文法称为SLR(1)文法。SLR(1)文法是无二义的。,SLR表,假定C=I0,I1
21、,，In，令每个项目集Ik的下标k 为分析器的一个状态，因此，G 的SLR分析表含有状态0，1，n。令那个含有项目SS的Ik的下标k为初态。函数ACTION和GOTO可按如下方法构造：若项目Aa属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTIONk,a为“把状态j和符号a移进栈”，简记为“sj”;若项目A属于Ik,那么，对任何输入符号a,aFOLLOW(A),置ACTIONk,a为“用产生式A进行规约”，简记为“rj”;其中，假定A为文法G的第j个产生式；若项目SS属于Ik,则置ACTIONk,#为“接受”，简记为“acc”;若GO(Ik,A)=Ij,A为非终结符，则置GOTO(k,
22、A)=j;分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张SLR表。具有SLR表的文法G称为一个SLR（1）文法。数字1的意思是，在分析过程中顶多只要向前看一个符号。,实数说明文法的SLR（1）分析表 状态 ACTION GOTO r,i#S D 0 S2 1 1 acc 2 S4 3 3 r1 S5 r1 r1 4 r3 r3 r3 r3 5 S6 6 r2 r2 r2 r2,?SLR,例：文法G:（0）SS(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)AeL
23、R(0)项目集规范族（识别G的活前缀的DFA)：I0:SS I1:SS I2:SaAd SaAd Saec SbAc Ae Saec Sbed,?SLR,I3:SbAc I4:I5:Sbed SaAd Saec Ae Ae I6:I7:I8:SbAc Sbed SaAd Ae I9:Saec I10:SbAc I11:Sbed,?,I5:S aec A e S=S=aAd=aed S=S=aec I7:S bed A e S=S=bAc=bec S=S=bed？信息 哪些输入符号能跟在句柄之后,R,R,R,R,R,R,R,R,R,R,Another example,GS:(0)SS(1)SL=
24、R(2)SR(3)L*R(4)Li(5)RLLR(0)项目集规范族和G0函数I1 S S.I6 I0 SS I2 SL=R S L=.R L.*R SL=R R L.R.L L.i SR L*R I3 Li SR RL I4 L*R I7I5 RL L*R Li L*R L.i I8 RL,(1)不是LR(0)文法 I2 SL=R R L.中存在移进/归约冲突（2）SLR能否解决I2中的冲突 FOLLOW（R）=#,=与=交不为空 不是SLR（1）文法 SL.=R RL.若用 RL 归约 则形成 R=而 R=不是活前缀?早知此信息 向前搜索符 LR（1）方法若 A.B I则 B.（B 是一产生
25、式）I把FIRST（B）中的符号作为用B 归约的搜索符,LR（1）项目 A.，a LR（K）项目 A.，a1 a2 aK,构造LR(1)项目集规范族和G0函数,closure(I)按如下方式构造(1)I的任何项目属closure(I)；(2)若A1B2，aclosure(I)，B是一产生式，那么对于FIRST(2a)中的每个终结符b，如果B,b不在closure(I)中，则把它加进去；(3)重复（1）（2），直至closure(I)不再增大。,GO函数：若I是一个项目集，X是一个文法符号GO(I,X)=closure(J)其中 J=任何形如AX,a的项目A.X,aILR(I)项目规范族C的构造
26、算法类同LR(0)的，只是初始时：C=closure(SS,#);,LR(1)项目集规范族,I0:SS,#I5:S aec,#S aAd,#A e,d S bAc,#I6:S bAc,#S aec,#I7:S bed,#S bed,#A e,c I1:S S,#I8:S aAd,#I2:S aAd,#I9:S aec,#S aec,#I10:S bAc,#A e,d I11:S bed,#I3:S bAc,#S bed,#Ae,c I4:S aAd,#,LR(1)项目集规范族,I1:SS,#I9:S L=R.,#I2:I6:SL=R,#I0:SS,#SL=R,#RL,#SL=R,#RL,#L*
27、R,#SR,#I3:Li,#L*R,=/#SR,#Li,=/#I4:I11:RL,#L*R,=/#L*R,#L*R,=/#RL,#I5:Li,=/#Li,=/#L*R,#RL,=/#Li,#I7 L*R,=/#I8 RL,#/=I10 I13I12:Li.RL,#L*R,#,LR(1)分析表的构造,若项目AA属于Ik,那么 置 ACTIONk,a为“用产生式A进行规约”，简记为“rj”;其中，假定A为文法G的第j个产生式；,At the heart of the table construction is the notion of an LR(0)configuration or item.A configuration is a production of the grammar with a dot at someposition on its right side.For example,A XYZ gives four items:A XYZA XYZA XYZA XYZ,
