第4章(3)白底黑字

4.3自下而上分析法的一般原理自下而上分析法的一般原理:编译中存在着多种自下而上的分析法，但不管哪种自下而上的分析法都是按照移进—归约法的原理建立起来的一种语法分析方法。4.3自下而上分析法的一般原理$t1t3ti-1t2tn…tj…titi+1$S基本思想:符号栈可规约串……$$A4.3自下而上分析法的一般原理例1设有文法G[S]:(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d对输入串abbcde进行自下而上语法分析,检查该符号串是否该文法的正确句子。4.3自下而上分析法的一般原理首先设一个符号栈并将输入符号串的左界符‘$’移入栈，分析时将输入符号串按从左到右扫描顺序移入栈中，其整个分析过程如下表所示。符号栈输入串(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d输入串abbcde$abbcde$$abbcde$$abbcde$$aAbcde$$aAbcde$$aAcde$$aAcde$$aAcde$$aAcBe$$aAcBe$$S$4.3自下而上分析法的一般原理实现自下而上分析法的关键问题是如何精确定义可归约串这个直观概念，以及怎样识别“可归约串”？4.3自下而上分析法的一般原理对“可归约串”的不同定义形成不同的自下而上的分析方法,在规范归约分析法中，是用句柄来刻画可归约串,而在算符优先分析法中,是用最左素短语来刻画可归约串。(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d输入串abbcde$abbcde$$abbcde$$abbcde$$aAbcde$$aAbcde$$aAcde$$aAcde$$aAcde$$aAcBe$$aAcBe$$S$符号栈输入串SaAcBeAbdb4.3自下而上分析法的一般原理识别可归约串的不同方法，也同样形成不同的自下而上的分析方法,简单优先分析法和LR分析法都是规范归约分析法，即都是用句柄刻画可归约串。4.3自下而上分析法的一般原理但它们识别句柄的方法不同,LR分析法是根据历史、现实、展望三者信息来确定栈顶符号串是否形成句柄，而简单优先分析法是根据文法符号之间的优先关系来确定栈顶符号串是否形成句柄。4.3自下而上分析法的一般原理下面，我们将介绍两种常用的自下而上的分析方法即算符优先分析法和LR分析法。在这两种分析法中，重点讨论怎样识别栈顶符号串是可归约串以及如何进行归约。4.4算符优先分析法方法概述1.算符优先分析法所谓算符优先分析法就是仿照算术表达式的四则运算过程而设计的一种语法分析方法。这种分析方法首先要规定运算符之间(确切地说终结符之间)的优先关系和结合性质，然后借助这种关系，比较相邻运算符的优先级来确定句型的可归约串并进行归约。4.4.1方法概述例如：文法G[E]为：E→E+E|E*E|(E)|id这个文法是一个二义性文法，因而对句子id+id*id有两种不同的规范归约，也就是在归约过程中句型的句柄不唯一。4.4.1方法概述句子id+id*id的两种不同的规范归约过程如下：第一个规范归约过程(1)id+id*id(2)E+id*id(3)E+E*id(4)E+E*E(5)E+E(6)E第二个规范归约过程(1)id+id*id(2)E+id*id(3)E+E*id(4)E*id(5)E*E(6)E4.4.1方法概述分析上述归约过程，句型E+E*id在第一个规范归约中id是它的句柄;而在第二个规范归约中E+E是它的句柄。此现象是由于没有定义运算符+和*的优先关系而引起的。在第一个规范归约中是假定*优先于+,所以不能立即把E+E归约为E;而在第二个规范归约中是假定+优先于*,因此必须先把E+E归约为E。4.4.1方法概述上述归约过程中起决定作用的是相邻两个终结符号之间的优先关系。算符优先分析法的关键:用合适的方法去定义任何两个可能相邻出现的终结符号a和b之间的优先关系。4.4.1方法概述2.任何两个相邻终结符号a和b之间的优先关系有三种：ab.a的优先级低于bab=.a的优先级等于bab.a的优先级高于b4.4.1方法概述通常表达式中运算符的优先关系有ba.+（.withbutwithab.(+.+（。.4.4.1方法概述ab……ab……优先关系表算符优先分析法借助优先关系表寻找句型的可归约串。...4.4.1方法概述优先关系表算符优先分析算法符号栈文法规则词法分析后的单词串输出4.4.2算符优先文法的定义算符优先文法的定义1.算符文法的定义设有文法G,若G中没有形如U→…VW…的规则，其中V和W为非终结符，则称G为算符文法，也称OG文法。4.4.2算符优先文法的定义在算符文法中，任何一个规则右部都不存在两个非终结符相邻的情况。2.定义任意两个终结符号之间的优先关系4.4.2算符优先文法的定义设G是一个算符文法，a和b是任意两个终结符，P、Q、R是非终结符，算符优先关系、、定义如下：.=..=.ab当且仅当G中含有形如(1)P→…ab…或P→…aQb…的规则。4.4.2算符优先文法的定义当且仅当G中含有形如(2)P→…aR…的规则,ab.R+b…且或R+Qb…当且仅当G中含有形如(3)的规则,R+…a且或R+…aQab.P→…Rb…4.4.2算符优先文法的定义3.算符优先文法的定义设有一个不含ε规则的算符文法G，如果任意两个终结符号对(a，b)在、和三种关系中只有一种关系成立，则称G是算符优先文法，也称OPG文法。..=.4.4.2算符优先文法的定义对前述算术表达式的文法:由算符文法和算符优先文法的定义，我们不难证明该文法是一个算符文法，但不是算符优先文法。E→E+E|E*E|(E)|id4.4.2算符优先文法的定义因为该文法的任一规则右部都不包含两个相邻的非终结符，所以该文法是算符文法。但是,由于E→E+E和有+*.又由于E→E*E和E+E*E有+*.E+E+E4.4.2算符优先文法的定义即运算符+和*之间存在两种不同的优先关系，所以该表达式的文法仅是算符文法而不是算符优先文法。4.4.2算符优先文法的定义若算术表达式的文法为：E→E+T|TT→T*F|FF→(E)|id显然,该算术表达式的文法是算符优先文法。4.4.3算符优先关系表的构造算符优先关系表的构造对算符优先文法,根据优先关系的定义,可按如下方法直接构造优先关系表。4.4.3算符优先关系表的构造首先对文法每个非终结符Ａ定义两个集合：FIRSTVT(A)={b|Ab…或ABb…,b∈VT,B∈VN}++LASTVT(A)={a|A…a或A…aB,a∈VT,B∈VN}++4.4.3算符优先关系表的构造使用这两个集合，构造文法Ｇ的优先关系表的算法如下：输入：算符优先文法Ｇ输出：关于文法Ｇ的优先关系表4.4.3算符优先关系表的构造方法：1.为每个非终结符Ａ计算FIRSTVT(A)和LASTVT(A)2.执行程序for(每个产生式A→x1x2…xn)for(i=1;i=n-1;i++){if(xi和xi+1均VT)置xixi+1=.if(i=n-2且xi和xi+2都VT,而xi+1VN)置xixi+2=.if(xi∈VT,xi+1∈VN)for(FIRSTVT(xi+1)中的每个b)置xib;.if(xi∈VN,xi+1∈VT)for(LASTVT(xi)中的每个a)置axi+1;.}4.4.3算符优先关系表的构造3.对FIRSTVT(S)中的所有b，置$b;对LASTVT(S)中的所有a，置a$；.置$$。=.（S为文法开始符号）.4.4.3算符优先关系表的构造例设有表达式的文法G[E]：E→E+T|TT→T*F|FF→(E)|id构造该文法的算符优先关系表。4.4.3算符优先关系表的构造首先计算每个非终结符的FIRSTVT和LASTVT：FIRSTVT(A)={b|Ab…或ABb…,b∈VT,B∈VN}++LASTVT(A)={a|A…a或A…aB,a∈VT,B∈VN}++4.4.3算符优先关系表的构造FIRSTVTLASTVTETFE→E+T|TT→T*F|FF→(E)|id{*,+,(,id}{*,+,),id}{*,(,id}{*,),id}{(,id}{),id}4.4.3算符优先关系表的构造+*id()$+*id()$执行算法，逐条扫描文法规则，因有F→(E)的规则，则有()=.=.4.4.3算符优先关系表的构造+T寻找终结符在左边，非终结符在右边的符号对有则+FIRSTVT(T).*F.则*FIRSTVT(F).则(FIRSTVT(E)(E{*,(,id}{(,id}{*,+,(,id}4.4.3算符优先关系表的构造+*id()$+*id()$.........=.4.4.3算符优先关系表的构造寻找非终结符在左边，终结在右边的符号对有E+则LASTVT(E)+..则LASTVT(T)*T*.则LASTVT(E))E)有$$;=.$FIRSTVT(E);LASTVT(E)$..{*,),id}{*,+,),id}+*id()$+*id()$........................=.....=.4.4.3算符优先关系表的构造构造出文法G[E]的算符优系表如下：+*id()$+*id()$........................=.....=.E→E+T|TT→T*F|FF→(E)|id