编译原理 第5章-自底向上优先分析

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