编译原理第7章算符优先分析.ppt
第7章算符优先分析算符优先文法的定义算符优先文法的定义算符优先关系表的构造算符优先关系表的构造算符优先分析算法算符优先分析算法算符优先分析法的局限性算符优先分析法的局限性算符优先分析u自下而上分析算法自下而上分析算法模型模型-移进归约移进归约u算符优先分析不是算符优先分析不是规范归约规范归约算符优先分析的算符优先分析的可归约可归约串串是是句型的句型的最左素短语最左素短语定义定义 cfgcfg（上下文无关文法）上下文无关文法）G G 的句型的的句型的素短素短语语是一个短语，它是一个短语，它至少包含一个终结符至少包含一个终结符，且除，且除自身外自身外不再包含其他素短语不再包含其他素短语。处于句型最左边。处于句型最左边的素短语为的素短语为最左素短语最左素短语文法文法GS S A且且A 则称则称是句型是句型 相对于非终相对于非终结符结符A的的短语短语文法文法GE：(1)EE+T(2)ET(3)TT*F(4)TF(5)FP F|P(6)P(E)(7)Pi句型句型T+T*F+i其短语有：其短语有：T+T*F+iT+T*FTT*FiEET+ETF*FTTi最左素短语为最左素短语为：T*F句型句型T+T+F的素短语为的素短语为：T+TE+TFE句型句型T+T+i的素短语为的素短语为：i素短语为素短语为：T*F，iETTi分析程序模型 总控程序算符优先关系表产生式输入串#输出如何确定算符优先关系？人为人为确定：确定：（1 1）i i的优先级最高的优先级最高（1 1）优先级次于优先级次于i i，右结合右结合（2 2）*和和/优先级次之，左结合优先级次之，左结合（3 3）+和和-优先级最低，左结合优先级最低，左结合（4 4）括号）括号(,)的优先级大于的优先级大于括号外的运算符，小于括号内的运括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号算符，内括号的优先性大于外括号（5 5）#的优先性低于与其相邻的算符的优先性低于与其相邻的算符文法文法GE：EE+E|E-E|E*E|E/E|E E|(E)|i算符优先关系表算符优先关系表算符优先文法的定义u定义定义：如果不含空产生式的上下文无关文法：如果不含空产生式的上下文无关文法 G G 中没中没有形如有形如 A ABCBC的产生式，其中的产生式，其中B B，CVCVN N 则称则称G G 为算符文法（为算符文法（OGOG）。）。例例7.1 GE：EE+E|E-|E*E|E/E|E E|(E)|i例例7.2 GE:EET|TTT*F|FFPFPP(E)|i性质性质1 1：在算符文法中任何句型都不包含两个相邻的非终结符：在算符文法中任何句型都不包含两个相邻的非终结符.性质性质2 2：如：如 A Ab b 或或 b bA A 出现在算符文法的出现在算符文法的 句型句型 中，其中中，其中 AVAVN N，b bV VT T，则则 中任何中任何 含含 b b 的短语必含有的短语必含有A A。算符优先关系在在OG中中 定义定义（算符优先关系）（算符优先关系）a=bG中有形如中有形如：Aab 或或AaBb.的产生式。的产生式。abG中有形如中有形如:ABb的产生的产生 式式,而而Ba或或 BaC 规定规定若若Sa或或SCa则则#在在OG文法文法G中，若中，若任意两个终结符间至多有任意两个终结符间至多有一种一种算符优先关系存在，则称算符优先关系存在，则称G为为算符优先文算符优先文法法(OPG)。注意：允许注意：允许bc,cb;不允许不允许bc,bc,b=c中中任两个任两个同时同时存在。存在。b=c不一不一定定 c=b。例例7.1中：中：“（”=“）”，“）”“（”。结论结论:算符优先文法是无二义的。算符优先文法是无二义的。算符优先关系表的构造首先定义如下两个集合：首先定义如下两个集合：FIRSTVT(B)=bBb或或BCbLASTVT(B)=aBa或或BaC按如下算法计算出给定文法中任何两个终结符对按如下算法计算出给定文法中任何两个终结符对(a,b)之间的之间的优先关系：优先关系：1)=关系关系直接看产生式的右部，若出现了直接看产生式的右部，若出现了A ab或或 A aBb,则则a=b 2)关系关系求出每个非终结符求出每个非终结符B的的FIRSTVT(B)若若AaB,则则 bFIRSTVT(B),则则a关系关系求出每个非终结符求出每个非终结符B的的LASTVT(B)若若ABb,则则 aLASTVT(B),则则ab计算算符优先关系例文法例文法GE：(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FP F|P(6)P(E)(7)PiFIRSTVT(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)Pi3)关系关系找形如：找形如：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的算符优先关表算符优先分析算法 算符优先文法句型的性质算符文法的任何一个句型应为如下形式：N1a1N2a2.Nnan Nn+1其中N k(1kn+1)为非终结符或空，ak(1kn)为终结符算符优先文法句型的最左素短语NiaiNi+1ai+1.Njaj Nj+1满足：ai-1 aiai=ai+1=aj-1=ajaj aj+1即：即：a ai-1i-1 a aj+1j+1 1 k:=1;S k :=“#”2 repeat read 下一符号到a;3 if S k Vt then j:=k else j:=k-1;4 while S j a do5 repeat 6 Q:=S j;7 if S j-1 Vt then j:=j-18 else j:=j-29 until S j Q;10 将 S j+1 S j+2 S k 归约到某个N;/11 k:=j+1;12 S k:=N;13 14 if(S j a or S j =a)15 then k:=k+1;S k:=a16 else error17 until a=“#”算符优先分析法u简单，直观，有利于表达式分析，易于简单，直观，有利于表达式分析，易于手工实现手工实现u比规范归约快比规范归约快u可能导致把错误的句子得到正确的归约可能导致把错误的句子得到正确的归约
