东北大学秦皇岛分校编译原理课件第二章第七章.ppt

第7章 LR分析法,7.1 LR类分析法,LR分析法根据当前分析栈和输入串来确定句柄。LR分析过程是一种规范归约过程。LR分析法适用于大多数无二义性的上下文无关文法。常用的LR分析法有：（1）LR（0）分析法（2）SLR（1）分析法（3）LALR（1）分析法（4）LR（1）分析法,LR（K）的含义：L表示由左向右处理输入；R表示生成了最右推导；数字K表示使用了先行的K个符号。LR分析法同样要用到先行集合（FIRST集合）和后跟集合（FOLLOE集合）。SLR（1）是“简单LR（1）”的简写，是对LR（1）分析的改进。LALR（1）即先行LR（1），是比SLR（1）分析稍微强大但却比一般LR（1）分析简单的方法。,S E E T|E+T T int|(E),Reduce:如能找到一产生式 A w 且栈中的内容是 qw(q 可能为空),则可以将其归约为 qA。即倒过来用这个产生式。如上例,若栈中内容是(int，我们使用产生式 T int并把栈中内容归约为(T Shift:如不能执行一个归约且在输入串中还有 token，就把它从输入串移到栈中。如上例,假定栈中内容是(,输入中还有 int+int)#.不能对(执行一个归约，因为它不和任何产生式的右端匹配，所以把输入的第一个符号移到栈中,于是栈中内容是(int，而余留的输入是+int)#。,Reduce的一个特殊情况：栈中的全部内容w归约为开始符号S（即施用 S w），且没有余留输入了，意味着已成功分析了整个输入串.移进归约分析中还会出现一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试分析 int+)时就会发生错误。,STACK REMAINING INPUT PARSER 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不能和任何产生式的右端匹配（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 经把句柄替换为相应产生式的左部而得到的,LR分析表中动作表的四种动作,（1）移进：把Sj=GOTOSi，a移入到状态栈，把a移入到文法符号栈。（i，j表示状态号）（2）归约：在确定当前句柄时进行的替换操作。（3）接受acc：当归约到文法符号栈中只剩文法的开始符号时，并且输入符号串已结束即当前输入符号是“#”，则分析成功。（4）报错：当遇到状态栈顶为某一状态下不该遇到的文法符号时，说明输入串不是该文法的一个句子，则报错。,LR分析器,一个LR分析器由3个部分组成：（1）总控程序：也称驱动程序。对所有的LR分析器总控程序都是相同的。（2）分析表（或分析函数）：不同的文法其分析表不同，同一文法采用的LR分析器不同时，分析表也将不同。分析表由动作表（ACTION）和状态转换表（GOTO）组成，在计算机里常用二维数组表示。（3）分析栈：包括文法符号栈和相应的状态栈。都为先进后出栈。分析器的动作由栈顶状态和当前输入符号决定。LR分析器的关键部分是LR分析表的构造。,分析器模型,SP：栈指针Si：状态栈Xi：文法符号栈,SP,文法要求,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 归约还是移进？,LR（0）分析表的结构,LR（0）分析法采用规范归约。LR（0）分析表的构造思想和方法是构造其它LR分析表的基础。LR（0）分析表分为两个部分：（1）ACTION（动作表）部分：列标志为文法的终结符号以及输入结束符#。表中的元素为某个状态或某条规则，或接受标志acc。（2）GOTO（转换表）部分：列标志为非终结符号。表中的元素为要装入的状态。,LR分析算法,置Sp指向输入串w的第一个符号令S为栈顶状态 a是Sp指向的符号重复 beginif ACTIONS,a=Sj then begin PUSH j,a(进栈)Sp 前进(指向下一输入符号)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 rest of input action 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）#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#归约(AAb)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个产生式的左部非终结符入栈。,分析程序,LR 文法对于一个cfg 文法,如果能够构造一张 LR 分析表,使得它的每一个入口均是唯一的（Sj,rj,acc,空白），则称该 cfg 是LR 文法。,LR(0)分析,LR(0)文法 能力最弱，理论上最重要存在FA 识别活前缀识别活前缀的DFA如何构造（LR(0)项目集规范族的构造）LR(0)分析表的构造,分析,活前缀G=(Vn,Vt,P,S),若有S A,是的前缀,则称是文法G的活前缀.其中S是对原文法扩充(SS)增加的非终结符.?为使S不出现在任何产生式的右部.如G=(S,a,SSa,Sa,S),R,可归前缀和活前缀,规范归约的特点：规范归约使得每次归约时，归约前和归约后的已归约部分和剩余部分合起来只是构成文法的规范句型，而用哪个产生式归约仅取决于当前句型的前部分。可归前缀：规范句型中能决定采用哪条规则进行归约的这样的前部分称为可归前缀。活前缀：形成可归前缀之前包括可归前缀在内的所有规范句型的前缀称为活前缀。也就是说，活前缀是一个或若干个规范句型的前缀。可归前缀与活前缀的区别：可归前缀是相对某个规范句型而言的，活前缀是相对文法（或相对多个句型）而言的。前缀是句柄的一部分：LR分析实质上是把句型的前缀放在符号栈中，一旦出现可归前缀，则句柄便已形成，则可用相应的规则进行归约。,识别活前缀的DFA,LR分析法并不去直接分析文法符号栈中的符号是否形成句柄。启示：LR分析使用的信息之一是句柄左部 的内容。将终结符和非终结符都看成是一个有限自动机的输入符号，每当把一个符号进栈时都看成已识别过了该符号，其状态进行转换，当识别到可归前缀时，说明已经确定出句柄，则认为到达了识别句柄的终态。,构造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.,项目及项目分类,拓广文法：新增一开始符号S：SS。引入“项目”的目的：为了由文法的产生式直接构造识别活前缀和可归前缀的有穷自动机，引入“项目”的概念，使得构造识别文法所有活前缀的有穷自动机NFA的每个状态由一个“项目”构成。LR（0）项目：在文法G中每个产生式的右部适当位置添加一个圆点构成。项目的分类：根据圆点所在位置和圆点后是终结符还是非终结符把项目分为如下四种类型：（1）移进项目：形如 A a，其中，V*，aVT（2）待约项目：形如 A B，其中，V*，BVN（3）归约项目：形如 A，其中，V*（4）接受项目：形如 S，其中，V+,活前缀与句柄的关系：,GS:若S=A=r是的前缀，则称r是G的一个活前缀1.活前缀已含有句柄的全部符号，表明产生式A的 右部已出现在栈顶2.活前缀只含句柄的一部分符号表明A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号3.活前缀不含有句柄的任何符号，此时期望A的右部所推出的符号串,R,活前缀,与句柄,与 LR(0)项目,为刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。A刻划产生式A的 右部已出现在栈顶 A12 刻划A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号 A 刻划没有句柄的任何符号在栈顶，此时期望A的右部所推出的符号串对于A的LR(0)项目只有A,构造识别活前缀的DFA,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 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)：,I0：SE E aA E bB,I1：SE,I2：E aA A.cA A d,I3：E bB B cB B d,I4：A c.A A cA A.d,I5：B cB B cB B d,I6：E aA,I7：EbB,I8：AcA,I9：BcB,I10：Ad,I11：BcB,LR(0)项目,根据圆点所在的位置和圆点后是终结符还是非终结符或为空把项目分为以下几种：移进项目，形如 A a a是终结符,V*以下同待约项目，形如 A B归约项目，形如 A 接受项目，形如 S S A的LR(0)项目只有A 是归约项目,利用项目构造识别前缀的DFA,先根据项目按一定的规则画出其相应的NFA，然后再将该NFA确定化简为DFA：（1）如果状态i和状态j出自同一条规则：UX1X2Xn，并且状态j中的圆点只落后于状态i的圆点一个位置，即：如果状态i为：UX1X2Xi-1 XiXn，状态j为：UX1X2Xi-1Xi Xi+1 Xn，则从状态i出发，画一条标记为Xi的弧到状态j。（2）如果状态i的圆点之后的符号Xi为非终结符，则从状态i出发，画标记为的弧到所有形如Xi 的项目。（3）将所得到的NFA进行确定化并化简，得到DFA。注意：对于规则U，其项目为 U,项目集规范族,项目集规范族：构成识别一个文法活前缀的DFA项目集（状态）的全体称为该文法的LR(0)项目集规范族。用C=I0，I1，In表示。构造一个利用闭包函数求DFA一个状态的项目集：若文法G已拓广为G,而S为文法G的开始符号，拓广后增加产生式S S。如果I是文法G的一个项目集，定义和构造I的闭包CLOSURE（I）如下：（1）I的项目均在CLOSURE（I）中，（2）若A B属于CLOSURE（I），则每一形如 B 的项目也属于CLOSURE（I），（3）重复步骤（2）直到不出现新的项目为止。利用闭包函数和转向函数构造文法G的LR(0)项目集规范族：（1）置项目S S为初态集的核，然后对核求闭包，CLOSURE(S S)得到初态的项目集。（2）对初态集或其它所构造的项目集应用转换函数GO(I,X)=CLOSURE(J)求初新状态J的项目集。（3）重复步骤（2）直到不出现新的项目集为止。,构造识别可归前缀的有穷自动机,构造识别文法活前缀的有穷自动机（DFA）的三种方法：（1）一般方法：根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造出相应的NFA，再确定化简为DFA。（2）利用项目直接构造：先求出文法的所有项目，按照一定规则构造识别活前缀的NFA，再将NFA确定化简为DFA。（3）通过求初态集的闭包来构造：把拓广文法的第一个项目S S作为初态集的核，通过求该核的闭包和转换函数，求出LR（0）项目集规范族，再由转换函数建立状态之间的连接关系得到识别前缀的DFA。,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”;若项目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）文法,LR类分析法适用于大多数无二义性的上下文无关性文法。LR（0）分析方法对文法仍有一定限制：能够用LR（0）分析法进行分析的文法不能含有冲突项目。冲突项目的概念：如果一个项目集（状态）中既含有移进项目又含有归约项目，或者一个项目集中含有两（多）个不同的归约项目，则称为冲突项目。LR（0）文法的概念：如果由一个文法构造的识别可归前缀的DFA的每个项目集（状态）均不含有冲突项目，则称这样的文法为LR（0）文法。注：实际上，大多数适用的高级程序设计语言的文法都不能满足LR（0）文法的条件。,例：（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 Sr D,I1:SS,I5:DDi,I3:Sr D DDi,I4:Di,I6:DDi,其中I3中含有移进/归约冲突,文法不是LR(0)的，如何解决？,I2:SrD DD i Di,其它LR类分析法,SLR（1）分析法SLR（1）分析法在一定程度上解决了LR（0）不能解决的含有冲突项目的问题。LR（1）分析法及分析表的构造SLR（1）分析法虽然在一定程度上解决了冲突项目的问题，但还存在下面两个问题：（1）SLR（1）分析法并没有彻底解决冲突问题；（2）SLR（1）分析法要求在出现冲突项目时，向前搜索符号集b1，b2，bn和FOLLOW（V1），FOLLOW（V2），FOLLOW（Vn）两两不相交，但并不是所有的上下文无关文法都满足这一要求。,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,，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,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,例：文法G:（0）SS(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)AeLR(0)项目集规范族（识别G的活前缀的DFA)：I0:SS I1:SS I2:SaAd SaAd Saec SbAc Ae Saec Sbed,I3:SbAc I4:I5:Sbed SaAd Saec Ae Ae I6:I7:I8:SbAc Sbed SaAd Ae I9:Saec I10:SbAc I11:Sbed,构造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)不再增大。,