精品课程《编译原理》PPT课件第6章自底向上语法分析

6.1自底向上语法分析,一、自底向上方法概述自底向上方法：从给定终极符串进行归约，并归约成文法的初始符。,移进-归约方法的四个动作:移进:输入流头符读到分析栈中归约:分析栈句柄归约非终极符接受:分析成功报错:处理错误,例子：对输入串abbcde进行分析，检查该串是否是GS的句子。GS：SaAcBeAbAAbBd对输入串abbcde的最右推导是：SaAcBeaAcdeaAbcdeabbcdeSaAcBeaAcdeaAbcdeabbcde,所以移进-归约方法的分析过程如下：,例：考虑文法G(E):ET|E+TTF|T*FFi|(E)并假定已给定终极符串(i+i)*i。下面是对该串的移入归约过程:,(,(i+i)*i)1=移=(,i+i)*i)2=移=(i,+i)*i)3=归=(F,+i)*i)4,=归=(T,+i)*i)5=归=(E,+i)*i)6=移=(E+,i)*i)7=移=(E+i,)*i)8=归=(E+F,)*i)9=归=(E+T,)*i)10=归=(E,)*i)11=移=(E),*i)12=归=(F,*i)13,=归=(T,*i)14=移=(T*,i)15=移=(T*i,)16=归=(T*F,)17=归=(T,)18=归=(E,)19,6.2简单优先方法,优先关系可用矩阵来表示，称这种矩阵为优先关系矩阵。,具体定义如下图：,Msi,sj,STEP2：对每个符号对Si，Sj填写优先关系矩阵。,构造优先关系矩阵步骤：,STEP1：对每个非终极符号W求下面两种集合,例子：假设有文法GZ:ZbMbMa|(LLMa),所以对GZ:ZbMbMa|(LLMa)有：FRIST(M)=(,aLAST(M)=),L,a有下表：,定义3.13满足下面两个条件的文法称为简单优先文法。1.任意两个符号至多成立一种关系2.任意两个产生式具有不同右部,例子：GZ:EE+T|TTT*F|FF(E)|i,下面文法均不为简单优先文法,G1:BaDa(有两个相同的右部),定理3.10设S1S2Sn是简单优先文法的规范句型,其子串SiSi+1Sj满足条件:,+,试用简单优先方法分析符号串b(aa)b是否为该文法的句子。,例：设有GZ:ZbMbMa|(LLMa),分析句子b(aa)b的过程：,移进项目的处理,移进项目的处理,算符优先文法的定义算符优先关系表的构造算符优先分析算法算符优先分析法的局限性,6.3算符优先方法,分析程序模型,总控程序,算符优先关系表,产生式,输入串#,#,输出,6.3.1直观算符优先分析法,自下而上分析算法模型-移进归约算符优先分析不是规范归约,如何确定算符优先关系？,人为确定：（1）i的优先级最高（1）优先级次于i，右结合（2）*和/优先级次之，左结合（3）+和-优先级最低，左结合（4）括号(,)的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号（5）#的优先性低于与其相邻的算符,文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i,算符优先关系表,6.3.2算符优先文法的定义,定义：如果不含空产生式的上下文无关文法G中没有形如ABC的产生式，其中B，CVN则称G为算符文法（OG）。例6.1GE：EE+E|E-|E*E|E/E|EE|(E)|i例6.2GE:EET|TTT*F|FFPFPP(E)|i性质1：在算符文法中任何句型都不包含两个相邻的非终结符.性质2：如Ab或bA出现在算符文法的句型中，其中AVN，bVT，则中任何含b的短语必含有A。,算符优先关系,在OG中定义（算符优先关系）a=bG中有形如：Aab或AaBb.的产生式。abG中有形如:ABb的产生式,而Ba或BaC规定若Sa或SCa则#,在OG文法G中，若任意两个终结符间至多有一种算符优先关系存在，则称G为算符优先文法(OPG)。注意：允许bc,cb;不允许bc,b“（”。结论:算符优先文法是无二义的。,6.3.3算符优先关系表的构造,首先定义如下两个集合：FIRSTVT(B)=bBb或BCbLASTVT(B)=aBa或BaC按如下算法计算出给定文法中任何两个终结符对(a,b)之间的优先关系：1)=关系直接看产生式的右部，若出现了Aab或AaBb,则a=b2)关系求出每个非终结符B的LASTVT(B)若ABb,则aLASTVT(B),则ab,计算算符优先关系,例6.3文法GE：(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF|P(6)P(E)(7)Pi,FIRSTVT(E)=#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=),i,(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF|P(6)P(E)(7)Pi,3)关系找形如：ABb的产生式E#:则LASTVT(E)#E+:则LASTVT(E)+T*:则LASTVT(T)*P:则LASTVT(P)E):则LASTVT(E),2）关系找形如AaB的产生式#E：则#FIRSTVT(E)+T:则+FIRSTVT(T)*F:则*FIRSTVT(F)F:则FIRSTVT(F)(E:则(FIRSTVT(E),1)=关系由产生式(0)和(6),得#=#，(=),表达式文法GE的算符优先关表,6.3.4算符优先分析算法,算符优先文法句型的性质算符文法的任何一个句型应为如下形式：N1a1N2a2.NnanNn+1其中Nk(1kn+1)为非终结符或空，ak(1kn)为终结符算符优先文法句型的最左素短语NiaiNi+1ai+1.NjajNj+1满足：ai-1aiai=ai+1=aj-1=ajajaj+1即：ai-1aj+1,算符优先分析的可归约串是句型的最左素短语定义cfg（上下文无关文法）G的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语文法GS短语的定义SA且A则称是句型相对于非终结符A的短语,例：有文法GE：(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF|P(6)P(E)(7)Pi,1.画出句型T+T*F+i的语法树并写出改句型的所有短语。2.写出句型T+T*F+i的简单短语和句柄。3.写出句型T+T*F+i的素短语和最左素短语。,文法GE：(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF|P(6)P(E)(7)Pi,句型T+T*F+i其短语有：T+T*F+iT+T*FTT*Fi,E,E,T,+,+,E,T,*,F,T,T,i,最左素短语为：T*F,F,素短语为：T*F，i,简单短语为：T，T*F，i,句柄为：T,句型T+T*F+i的语法树,E,E,T,+,+,E,T,*,F,T,T,i,句型T+T*F+i进行算符优先分析时语法树的框架,F,N,N,N,+,+,N,N,*,N,N,i,省略了ET,ET,ET的规约,F,句型T+T+F的素短语为：T+T最左素短语是T+T,E,+,+,T,E,句型T+T+i的素短语为：T+T,I最左素短语为T+T(注：T+T不是简单短语，但是素短语）,E,T,T,例