第六章 算符优先分析(大学编译原理)(精品).ppt

《第六章 算符优先分析(大学编译原理)(精品).ppt》由会员分享，可在线阅读，更多相关《第六章 算符优先分析(大学编译原理)(精品).ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章 自低向上优先分析即即移进移进-规约分析。思想：规约分析。思想：对符号串自左向右扫描，将输入符号移入一个对符号串自左向右扫描，将输入符号移入一个后进先出栈中，边移入边分析，一旦栈顶符号后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可规约串时（该句柄串形成某个句型的句柄或可规约串时（该句柄或可规约串对应某个产生式右部），就用该产或可规约串对应某个产生式右部），就用该产生式的左部非终结符代替相应右部的文法符号生式的左部非终结符代替相应右部的文法符号串，即规约。重复这一过程，直到栈中只剩下串，即规约。重复这一过程，直到栈中只剩下文法的开始符号时则认为分析成功，即输入的文法的开始

2、符号时则认为分析成功，即输入的符号串是文法的句子。符号串是文法的句子。16.1 自底向上优先分析概述有两种优先分析法：有两种优先分析法：1。简单优先分析法：简单优先分析法：求出文法所有符号（终结符，非终结符）求出文法所有符号（终结符，非终结符）之间优先关系，按这种关系确定规约过之间优先关系，按这种关系确定规约过程中的句柄。程中的句柄。2。算符优先分析法：考虑算符之间优先关。算符优先分析法：考虑算符之间优先关系的规约（非规范规约）系的规约（非规范规约）26.36.3算符算符优先分析法优先分析法算符优先文法的定义算符优先文法的定义算符优先关系表的构造算符优先关系表的构造算符优先分析算法算符优先分析

3、算法算符优先分析法的局限性算符优先分析法的局限性36.3.1算符优先分析算符优先分析自下而上分析算法模型自下而上分析算法模型-移进归约移进归约算符优先分析不是算符优先分析不是规范归约规范归约算符优先分析的算符优先分析的可归约可归约串串是是句型的句型的最左素短语最左素短语定义定义:cfgcfg（上下文无关文法）上下文无关文法）G G 的句型的的句型的素短素短语语是一个短语，它是一个短语，它至少包含一个终结符至少包含一个终结符，且除，且除自身外自身外不再包含其他素短语不再包含其他素短语。处于句型最左边。处于句型最左边的素短语为的素短语为最左素短语最左素短语.文法文法GS的短语：的短语：S A且且A

4、 ，则称则称是句型是句型相对于非相对于非终结符终结符A的的短语短语4文法文法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的素短语为的素短语为：T+T,i素短语为素短语为：T*F，iETTi5分析程序模型分析程序模型 总控程序算符优先关系表产生式输入串#输出6例 GE:EET|T TT*F|F FPFP P(E)|i算符优先关表算符优先关表7

5、 6.3.2 算符优先文法的定义算符优先文法的定义算符文法定义算符文法定义：如果不含空产生式的上下文无关文：如果不含空产生式的上下文无关文法法 G G 中，没有形如中，没有形如 A ABCBC的产生式，其中的产生式，其中B B，CVCVN N 则称则称G G 为算符文法（为算符文法（OGOG）。）。例例1 GE：EE+E|E-|E*E|E/E|E E|(E)|i例例2 GE:EET|TTT*F|FFPFPP(E)|i性质性质1 1：在算符文法中任何句型都不包含两个相邻的非终结符：在算符文法中任何句型都不包含两个相邻的非终结符.性质性质2 2：如：如 A Ab b 或或 b bA A 出现在算符

6、文法的出现在算符文法的 句型句型 中，其中中，其中 AVAVN N，b bV VT T，则则 中任何中任何 含含 b b 的短语必含有的短语必含有A A。8算符优先关系算符优先关系在在OG中定义中定义算符优先关系：算符优先关系：a=bG中有形如中有形如：Aab 或或AaBb.的产生式。的产生式。abG中有形中有形如如:ABb的产生的产生 式式,而而Ba或或 BaC 规定规定若若Sa或或SCa则则#（认为存在认为存在#S#）9算符优先文法OPG定义 在在OG文法文法G中，若中，若任意两个终结符间至多任意两个终结符间至多有一种有一种算符优先关系存在，则称算符优先关系存在，则称G为为算符优先算符优先

7、文法文法(OPG)。注意：允许注意：允许bc,cb;不允许不允许bc,bc,b=c中中任两个任两个同时同时存在。存在。b=c不一不一定定 c=b。例例1中：中：“（”=“）”，“）”“（”。结论结论:算符优先文法是无二义的。算符优先文法是无二义的。106.3.3算符优先关系表的构造算符优先关系表的构造首先定义如下两个集合：首先定义如下两个集合：FIRSTVT(B)=bBb或或BCbLASTVT(B)=aBa或或BaC按如下算法计算出给定文法中任何两个终结符按如下算法计算出给定文法中任何两个终结符对对(a,b)之间的之间的优先关系：优先关系：1)=关系关系直接看产生式的右部，若出现了直接看产生式

8、的右部，若出现了A ab或或 A aBb,则则a=b 2)关系关系求出每个非终结符求出每个非终结符B的的FIRSTVT(B)若若AaB,则则 bFIRSTVT(B),则则a关系关系求出每个非终结符求出每个非终结符B的的LASTVT(B)若若ABb,则则 aLASTVT(B),则则ab11计算算符优先关系计算算符优先关系例文法例文法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)=(,iLAST

9、VT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=),i12(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FP F|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:则则 F

10、IRSTVT(F)(E:则则(FIRSTVT(E)1)=关系关系由产生式由产生式(0)和和(6),得得#=#，(=)13例例GE的的算符优先关表算符优先关表(注意加入注意加入#)146.3.4算符优先分析算法算符优先分析算法 算符优先文法句型的性质：算符优先文法句型的性质：算符文法的任何一个句型应为如下形式：算符文法的任何一个句型应为如下形式：N1a1N2a2.NnanNn+1其中其中Nk(1kn+1)为非终结符或空，为非终结符或空，ak(1kn)为为终结符。终结符。算符优先文法句型的最左素短语算符优先文法句型的最左素短语NiaiNi+1ai+1.NjajNj+1满足：满足：ai-1aiai=

11、ai+1=aj-1=ajajaj+1即：即：a ai-1i-1 a aj+1j+115算符优先分析算法算符优先分析算法 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=“#”16算符优先分析法算符优先分析法简单，直观，有利于表达式分析，易于简单，直观，有利于表达式分析，易于手工实现手工实现比规范归约快比规范归约快可能导致把错误的句子得到正确的归约。可能导致把错误的句子得到正确的归约。该方法仅适用于表达式的语法分析该方法仅适用于表达式的语法分析17利用算符优先分析算法分析输入串举例 p115:分析输入串i+i#GE:EET|T TT*F|F FPFP P(E)|i 18