语法分析自底向上分析.ppt

第五章语法分析自底向上分析,5.1基本问题方法从句子出发，反复利用产生式做归约（用产生式的左部替代右部），逐步构造语法分析树，最后得到文法的开始符号核心寻找句型与句柄的匹配,分析方法,例5-1：SaAcBeAAbbBd分析过程:abbcdeaAbcdeaAcdeaAcBeS,语法分析树的生成,abbcde,A,A,B,S,Ab,AAb,Bd,SaAcBe,句柄：最左直接短语,短语：设文法T，N，若=*且=+，则称是句型相对于非终结符的短语若=*且=，则称是直接短语。,规范归约的定义,设为文法G的句子，称序列n，.，1，0为的规范归约，其中1)n=2)0=（开始符号）3)对每个i(1BaB.=BB.=S.,LR(0)项目,目的用产生式中的符号分割位置(有限）来表示分析位置(无限)定义右部某个位置上标有园点的产生式坐标表示(x,y)表示x号产生式的y号位置的LR(0)项目,文法的改写,文法G的拓广文法G：扩充识别符号SS（G的识别符号)例5-50)SS1)SBB2)BaB3)Bb,LR(0)项目例(0,0)S.S(2,1)Ba.B(3,1)Bb.,用状态近似表示分析位置,分析位置对应多个LR(0)项目，状态应是LR(0)项目集合。状态计算：从一个分割位置出发，考虑向前分析中可能处于同一分析位置的分割位置。,.B,A,.,状态的计算,求核心位置的闭包closure(I)J:=I;repeatJ=JB.A.BJuntilJ不再扩大例：closure（(0,0)）=(0,0),(1,0),(2,0),(3,0),状态转移的计算：,确定在某状态遇到一个文法符号后的状态转移目标,A,状态I,核心J,.X,状态转移函数,当前状态I文法符号X下一状态go(I,X)=closure(J)其中J=AX.A.XI,计算状态集合（P105)即：LR(0)项目集规范族,beginI:=closure(S.S);C:=I;repeatforC中的每一状态I和每一文法符号Xifgo(I,X)非空并且go(I,X)不在C中将状态go(I,X)加入到C中until不出现新的状态end.,例5-6：表达式文法的状态集合,拓广文法0)1)+2)3)*4)5)()6)id,010,41,8690,420,4,62,97100,4,630,4,6,748110,4,6,75,状态计算,状态核心闭包增加0(0,0)(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)go(0,E)1(0,1)(1,1)go(0,T)2(2,1)(3,1)go(0,F)3(4,1)go(0,()4(5,1)(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)go(0,id)5(6,1)go(1,+)6(1,2)(3,0)(4,0)(5,0)(6,0)go(2,*)7(3,2)(5,0)(6,0)go(4,E)8(5,2)(1,1)go(4,T)2(2,1)(3,1),go(4,F)3(4,1)go(4,()4(5,1)go(4,id)5(6,1)go(6,T)9(1,3)(3,1)go(6,F)3(4,1)go(6,()4(5,1)go(6,id)5(6,1)go(7,F)10(3,3)go(7,()4(5,1)go(7,id)5(6,1)go(8,)11(5,3)go(8,+)6(1,2)go(9,*)7(3,2)至此，所有状态转移的可能都被考虑到了，不可能再产生新的状态。,构造识别活前缀的有限自动机,以状态为结点，以状态转移为有向弧。,(,+,活前缀与句柄,活前缀是规范归约中句型的前缀，且其右端不超过句柄的末端。例：id+id*id的分析中句型E+id.*id和E+E*.id,活前缀,活前缀,出现在符号栈中的符号串,SLR（1）分析表的构造,输入：一个拓广文法G作用表(action)：各状态下遇到终结符时的动作状态转移表(goto)：各状态下遇到非终结符时的转移,构造算法：,1.构造G的状态集合I0、I1In2.状态Ii的分析动作action如下：a)ifA.aIiandgo(Ii,a)=Ijthen(处于状态、且识别a转移到状态）将shiftj置入actioni,a（把a和状态推入栈）,b)ifA.Iithen（在识别之后，应做归约）将reduceA置入actioni,aforanyaFOLLOW(A)（将栈中的产生式右侧符号换为左侧符号）c)ifSS.Iithen将accept置入actioni,#（分析成功）,3.ifgo(Ii,A)=IjandANthen将j置入gotoi,A（设置遇非终结符时的状态转移）4.所有空格置error5.以S.S所在的状态为初态,例5-7：表达式文法的SLR分析表,求非终结符的FISRT集和FOLLOW集FIRST(F)=id,(FIRST(T)=id,(FIRST(E)=id,(FOLLOW(E)=),+,#FOLLOW(T)=),+,#,*FOLLOW(F)=),+,#,*,si表示移进到状态i,ri表示归约i号产生式P175,SLR(1)分析的特点,分析位置的表示状态+文法符号的FOLLOW集描述能力强于LL(1)LL(1)仅考虑产生式的首符号SLR(1)文法SLR(1)分析能够处理的文法,5.3.3SLR(1)和LR(0)分析,LR(0)与SLR(1)的区别分析表的构造算法不同第步)项的处理中的区别：LR(0)分析对所有终结符均采用归约动作SLR(1)分析参考FOLLOW集确定归约动作,例5-7：表达式文法的LR(0)分析表,在状态2、9采用归约，出现移进归约冲突,SLR(1)文法的确认,上例的文法是SLR(1)文法，不是LR(0)文法LR(0)分析表出现冲突SLR(1)分析表无冲突在状态2和状态9选用移进还是归约取决于输入符号是*还是#SLR(1)文法的分析能力强于LR(0)方法,SLR(1)分析的局限性,如果SLR(1)分析表仍有多重入口（移进归约冲突或归约归约冲突），则说明该文法不是SLR(1)文法；说明仅使用LR(0)项目集和FOLLOW集还不足以分析这种文法,例5-8：赋值表达式的LR(0)项目集,0)SS1)SL=R2)SR3)L*R4)Lid5)RL,010269030,4,6470,4,650,4,62,8,分析中的冲突,I2=SL.=R,RL.输入符号为=时，出现了移进归约冲突：SL.=RI2andgo(I2,=)=I6=action2,=Shift6RL.I2and=FOLLOW(R)=,#=action2,=ReduceRL说明该文法不是（）文法，分析这种文法需要更多的信息。,5.3.4LR(1)分析引论,SLR(1)和LR(0)分析仅通过LR(0)项目集反映分析过程，信息量有限考虑对于产生式A的归约，不同使用位置的A会有不同的后继符号,后继符的概念,E,E+T,(E),T*F,不同的归约中有不同的后继符。特定位置的后继符是FOLLOW集的子集,LR(1)项目：,定义：右部某个位置上标有园点的产生式(分析位置)和几个终结符(后继符)A.,a表示在本产生式中的分析位置，以及A在上一个产生式中的归约位置用后继符近似表示,状态的计算,闭包计算closure(I)(核心位置状态)同时考虑可能出现的后继符a来自,.B,A,.,a,闭包计算,J:=I;repeatJ=JB.,bA.B,aJ,bFIRST(a)untilJ不再扩大有可能，此时b=a,状态I和文法符号X的转移函数,go(I,X)=closure(J)其中J=AX.,aA.X,aI,A,状态I,核心J,.X,LR(1)分析表的构造,状态集的计算方法和LR(0)基本相同分析表的构造方法和LR(0)基本相同构造方法的不同点：第2步)项处理中归约动作的选择：LR(0)分析考虑所有终结符SLR(1)分析参考FOLLOW集LR(1)分析仅考虑LR(1)项目中的后继符,5.3.5LALR(1)分析的概念,简化LR(1)分析减少资源开销(lookahead-LR)在不带来移进归约冲突的条件下，合并状态，重构分析表可行性（合并条件）LR(1)项目有相同的LR(0)项目，但后继符可能不同(可能带来归约归约冲突),LALR(1)的分析能力,高于SLR(1)分析合并的后继符仍为FOLLOW集的子集局限性合并中不出现归约归约冲突LALR(1)文法定义的依据,自底向上分析小结,基本框架移进归约分析核心：在句型中确认句柄分析器具有基本相同的逻辑结构控制算法：基于算符优先关系表基于LR分析表（动作和状态转移）,LR分析的基本步骤,1、编写拓广文法，求Follow集2、求状态集合3、构造LR分析表4、编制移进归约分析器,