第五章自下向上分析语法分析方法(LR).

1一、算符优先分析法存在的问题强调算符之间的优先关系的唯一性，这使得它的适应面比较窄；算法在发现最左素短语的尾时，需要返回来寻找对应的最左素短语头。二、LR(k)分析法L：从左到右扫描输入符号，R：最右推导对应的最左归约,k：超前读入k个符号，用以确定归约所用的规则§5.3LR分析概述2*LR分析优点：对文法的限制很少、分析速度快、能准确即时地指出出错位置*LR分析主要缺点：对于一个实用语言文法的分析器的构造工作量相当大，k愈大构造愈复杂，实现比较困难一个LR分析器的组成：（1）总控程序（驱动程序）：（2）分析表（分析函数）：动作表和状态转换表（3）分析栈：文法符号栈和状态栈3三、LR分析器工作示意图4四、LR分析表LR分析表包括action[s,a]、goto[s,X]表两部分，LR(0)、SLR(1)、LR(1)、LALR(1)将以不同的原则构造这张分析表。构造表时约定：用sn表示将符号a、状态n压入栈；用rn表示用第n个产生式进行归约。555规范句型：通过规范规约得到的句型.规范句型前缀：将输入串的剩余部分与其连结起来就构成了规范句型.如：x1x2.....xmai...an为规范句型x1x2.....xm为规范句型前缀ai...an为输入串的剩余部分§5.4LR（0）分析活前缀和可归前缀:若S’=*αAγ=αβγ是G的拓广文法G’的一个规范推导,则称αβ为可归前缀;若有串W是αβ的前缀，则称W是G的一个活前缀（S‘为文法拓广后的开始符，它只出现在规则左部）。可归前缀是包含句柄的活前缀。6规范句型的活前缀:对于句型αβt，β表示句柄,如果αβ=u1u2…ur那么符号串u1u2…ui(1≤i≤r)即是句型αβt的活前缀例：有文法E→T|E+T|E-TT→i|(E)拓广文法G’：S→E#E→T|E+T|E-TT→i|(E)已知句型E-(i)#，求活前缀?E,E-,E-(,E-(i是句型E-(i)#的活前缀。6SE#ET-()ETi7识别活前缀的有穷自动机例:G[S]:S→aAcBe[1]A→Ab[2]A→b[3]B→d[4](S'→S[0])对句子abbcde,其可归前缀为：ab[3],aAb[2],aAcd[4],aAcBe[1],S[0]对它们分别构造有穷自动机，然后，通过加入一开始状态X和一些ε弧，将各可归前缀的有穷自动机合并成一个有穷自动机NFA。其中由S[0]得到的终态称为句子识别状态，用*标记。89上图是通过一个句子(abbcde)的归约过程直观的看出其活前缀和可归前缀，然后构造其NFA。进一步将其确定化为DFA如下：10一、LR(0)分析表的构造构造LR分析表的方法是:(1)根据文法构造识别规范句型活前缀的有穷自动机DFA(2)由DFA构造LR（0）分析表11项目:文法G的每个产生式(规则)的右部某个位置添加一个圆点‘.’就构成一个项目。1、LR(0)项目例:产生式:A→XYZ项目:A→.XYZA→X.YZA→XY.ZA→XYZ.产生式:A→ε项目:A→.12形如A.的项目称为归约项目；形如A.B的项目称为待约项目(基本项目)；形如A.a的项目称为移进项目。形如S’.的项目称为接受项目,S’为拓广文法2、项目的分类3、项目集规范族项目的集合称项目集。识别活前缀的DFA项目集(状态)的全体称项目集规范族。134.项目集的闭包（Closure）求法：设I是文法G的一个LR(0)项目集，I的项目闭包closure(I)定义如下：1、Iclosure(I)。2、若项目A.Bclosure(I)，且B是G的产生式，则项目B.closure(I)。3、重复2直到不出现新的项目为止。145.转移函数：若I是文法G的一个LR(0)项目集，X是G中的文法符号.定义go(I,X)=closure(J)其中J={AX.|A.XI}称函数go(I,X)为转移函数。项目AX.称为项目A.X后继。15用CLOSURE和GO（I，X）构造文法G`的LR（0）项目集规范族，步骤如下：①置项目S`·S为初始集的核，然后对核求闭包，CLOSURE（｛S`·S｝）得到初始的项目集②对初态集或其他所构造的项目集应用GO（I，X）＝CLOSURE（J）求出新状态J的项目集③重复②直到不出现新的项目为止。对一个文法的LR（0）项目集规范族不存在移进－归约，或归约－归约冲突时，称这个文法为LR（0）文法6.LR（0）项目集规范族的构造161616LR(0)项目集规范族的构造算法:G'→LR(0)ProcedureITEMSETS(G');beginLR(0):={closure({E'→.E})};repeatforLR(0)中的每个项目集I和G'的每个符号XdoifGOTO(I,X)非空,且不属于LR(0)then把GOTO(I,X)放入LR(0)中untilLR(0)不再增大end171717Ⅰ.将文法扩充构造LR（0）项目集规范族的方法(三步)目的：使构造出来的分析表只有一个接受状态,这是为了实现的方便。方法：修改文法，使识别符号的规则只有一条G[E]E→···E→······拓广G'[E']E'→EE→···E→······L(G(E))=L(G'[E])181818Ⅱ.根据文法列出所有的项目Ⅲ.将有关项目组合成集合，即DFA中的状态；所有状态再组合成一个集合，即LR（0）项目集规范族我们通过一个具体例子来说明LR(0)的构造以及DFA的构造方法19例：设拓广文法G[S]的产生式为：SSSaA|bBAcA|dBcB|dLR(0)项目集规范族I0:S.SS.aAS.bBI1:(I0,S)SS.I2:(I0,a)Sa.AA.cAA.dI3:(I0,b)Sb.BB.cBB.dI4:(I2,c)(I4,c)Ac.AA.cAA.dI5:(I3,c)(I5,c)Bc.BB.cBB.dI6:(I2,A)SaA.I7:(I3,B)SbB.I8:(I4,A)AcA.I9:(I5,B)BcB.I10:(I4,d)Ad.I11:(I3,d)Bd.20Ac.AA.cAA.dI4Sa.AA.cAA.dI2Sb.BB.cBB.dI3Bc.BB.cBB.dI5S.SS.aAS.bBI0startSS.I1AcA.I8SaA.I6Ad.I10AddAcabSSbB.I7BcB.I6Bd.I11BddBccc识别文法活前缀的DFA21令包含S‘→•S的项目集Ik的下标k为分析器的初态LR(0)分析表的ACTION和GOTO表的构造步骤如下：a)若项目A→•a属于Ik，且转换函数GOTO(Ik,a)=Ij，当a为终结符时，则置ACTION[k,a]为Sjb)若项目A→•属于Ik，则对a为任何终结符或‘#’，置ACTION[k,a]=rj，j为产生式在文法G‘中的编号c)若GO(Ik,A)=Ij，则置GOTO[k,A]=j，其中A为非终结符，j为某一状态号d)若项目S‘→S•属于Ik，则置ACTION[k,#]=acce)其它填上“报错标志”由DFA构造LR分析表22LR(0)分析表actiongoto状态abcd#SAB01234567891011s2s3accs4s10s5s11s4s10s5s11r1r1r1r1r1r2r2r2r2r2r3r3r3r3r3r5r5r5r5r5r4r4r4r4r4r6r6r6r6r616789分析bccd#23（5）LR（0）分析器的工作过程①若ACTION[S,a]＝Sj，a为终结符，则把a移入符号栈，j移入状态栈②若ACTION[S,a]＝rj，a为终结符或＃,则用第j个产生式归约,并将两个栈的指针减去k，其中k为第j个产生式右部的符号串长度,这时当前面面临符号为第j个产生式左部的非终结符,不防设为A，归约后栈顶状态设为n，则再进行GOTO[n,A]③若ACTION[S,a]＝acc，a为#，则为接受，表示分析成功24④若GOTO[S,A]＝j，A为非终结符，表明前一动作是用关于A的产生式归约的，当前面临非终结符A应移入符号栈，j移入状态栈。对于终结符的GOTO[S,a]已和ACTION[S,a]重合⑤若ACTION[S,a]＝空白，则转向出错处理现用上表的LR（0）分析表对输入串bccd#用LR（0）分析器进行分析，其状态栈和符号栈及输入串的变化过程如表所示：25步骤状态栈符号输入串Actiongoto1＃0＃bccd#S32＃03＃bccd#S53＃035＃bccd#S54＃0355＃bccd#S115＃0355(11）＃bccd#r696＃03559＃bccB#r597＃0359＃bcB#r578＃037＃bB#r219＃01＃E#acc分析bccd#26若有效项目集中存在冲突动作:I={X.b,A.,B.}将b移进栈将归约为A将归约为B设当前输入符号为a,1.若a=b,则移进;2.若aFollow(A),则用A进行归约;3.若aFollow(B),则用B进行归约;4.其余情况报错.§５.５SLR（1）分析27构造SLR(1)分析表的方法是:1根据文法构造识别规范句型活前缀的有穷自动机DFA(同LR(0))2由DFA构造SLR（1）分析表28令包含S‘→•S的项目集Ik的下标k为分析器的初态LR(0)分析表的ACTION和GOTO表的构造步骤如下：a)若项目A→•a属于Ik，且转换函数GOTO(Ik,a)=Ij，当a为终结符时，则置ACTION[k,a]为Sjb)若项目A→•属于Ik，则对a为任何终结符或‘#’，且满足aFOLLOW(A)时置ACTION[k,a]=rj，j为产生式在文法G‘中的编号c)若GO(Ik,A)=Ij，则置GOTO[k,A]=j，其中A为非终结符，j为某一状态号d)若项目S‘→S•属于Ik，则置ACTION[k,#]=acce)其它填上“报错标志”2由DFA构造SLR(1)分析表29例：设文法G[E]的产生式为EE+T|TTT*F|FF(E)|id并用SLR(1)方法分析id*id+id∈L(G[E])?G的拓广文法G[E]：(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fid(3)TT*F30I0:E.EE.E+TE.TT.T*FT.FF.(E)F.idI1(I0E):EE.EE.+TI2(I0T)(I4T):ET.TT.*FI3(I0F)(I4F)(I6F):TF.I4(I0()(I4()(I6()(I7():F(.E)E.E+TE.TT.T*FT.FF.(E)F.idI5(I0id)(I4id)(I6id)(I7id):Fid.I6(I1+)(I8+)EE+.TT.T*FT.FF.(E)F.idI7(I2*)(I9*):TT*.FF.(E)F.idI8(I4E):F(E.)EE.+TI9(I6T):EE+T.TT.*FI10(I7F):TT*F.I11(I8)):F(E).G：(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fid(3)TT*F31E’EEE+TETTT*FTFF(E)FidEE’EEE+TTETTT*F(F(E)EE+TETTT*FTFF(E)FidI0I1I2I6FTFI3FididI5TI2FI3idI5(EE+TTT*FTFF(E)Fid+*TT*FF(E)FidI7F(E)EE+TEI8TEE+TTT*FI9FI3idI5(FTT*FI10idI4(I4*I7)F(E)+I6I1132I0I1I6I9E+T*toI7FtoI3(toI4idtoI5I2