编译原理 第7章(清华大学).ppt

1、第7章算符优先分析,算符优先文法的定义算符优先关系表的构造算符优先分析算法算符优先分析法的局限性,算符优先分析,自下而上分析算法模型-移进归约算符优先分析不是规范归约算符优先分析的可归约串是句型的最左素短语定义cfg（上下文无关文法）G的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语文法GSSA且A则称是句型相对于非终结符A的短语,文法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,*,F

2、,T,T,i,最左素短语为：T*F,句型T+T+F的素短语为：T+T,E,+,+,T,F,E,句型T+T+i的素短语为：i,素短语为：T*F，i,E,T,T,i,分析程序模型,总控程序,算符优先关系表,产生式,输入串#,#,输出,如何确定算符优先关系？,人为确定：（1）i的优先级最高（1）优先级次于i，右结合（2）*和/优先级次之，左结合（3）+和-优先级最低，左结合（4）括号(,)的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号（5）#的优先性低于与其相邻的算符,文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i,算符优先关系表,算符优先文法的定义,定义：如

3、果不含空产生式的上下文无关文法G中没有形如ABC的产生式，其中B，CVN则称G为算符文法（OG）。例7.1GE：EE+E|E-|E*E|E/E|EE|(E)|i例7.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为算符优

4、先文法(OPG)。注意：允许bc,cb;不允许bc,b“（”。结论:算符优先文法是无二义的。,算符优先关系表的构造,首先定义如下两个集合：FIRSTVT(B)=bBb或BCbLASTVT(B)=aBa或BaC按如下算法计算出给定文法中任何两个终结符对(a,b)之间的优先关系：1)=关系直接看产生式的右部，若出现了Aab或AaBb,则a=b2)关系求出每个非终结符B的LASTVT(B)若ABb,则aLASTVT(B),则ab,计算算符优先关系,例文法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

5、(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:则(ado5repeat6Q:=Sj;7ifSj-1Vtthenj:=j-18elsej:=j-29untilSjQ;10将Sj+1Sj+2Sk归约到某个N;/11k:=j+1;12Sk:=N;1314if(SjaorSj=a)15thenk: