编译原理第五章自底向上优先分析法.doc

第五章 自底向上优先分析法自底向上优先分析法，其基本思想是采用自左向右扫描，向下而上分析。该类分析方法是从输入符号串开始，查找句柄，并使用规则把它归约成相应的非终结符号。任何自底向上分析的关键，就是要找出这种句柄。本章首先介绍自底向上分析一般过程，然后介绍算符优先分析法。本章重点：句柄、算符优先分析法第一节 自底向上分析一般过程。先举例说明 例1 有一文法GS SaAcBeAbAAbBd 对输入串abbcde#进行分析，检查该符号串是否是GS的句子。它的最右推导是：SaAcBeaAcdeaAbcdeabbcde 由此我们可以构造它的逆过程即归约过程。先设一个先进后出符号栈，并且把句子左括号“#”号放入栈底，其分析过程如下所示步骤符号栈输入符号中（1）#abbcde # （2）# a bbcde #（3）# ab bcde # Ab 归约（4）# aA bcde #（5）# aAb cde # AAb 归约（6）# aA cde #（7）# aAc de #（8）# aAcd e # Bd 归约（9）# aAcB e #（10）# aAcBe # SaAcBe 归约（11）# S # 接受上述归约过程，是从输入符号串开始，自底向上地通过归约当前句型的句柄来建立语法树的。我们不难画出上述分析过程的语法树，下图。在图中，我们仅画出与生成语法树有关的几步。从所建立的语法树，可以清楚看出，上述每一步确实都是归约当前句型的句柄。且句柄出现在符号栈栈顶，不会在栈中间，其实上述分析过程并未真正解决句柄的识别问题。例如，对于上面的例子，分析进行到第（5）步，当时栈内符号串为aAb。根据该符号串，我们有规则AAb。和规则Ab。那么，符号串Ab和b都是某条规则的右部，故都有可能被判别是句型的句柄。假如我们选择b作为句柄，并把b归约为A，那么，最终就达不到归约到S的目的。因而，我们也就无从得知输入串abbcde是一个句子了。AASA B ABAA A a b b c d a b b c d ea b a b b在自底向上分析中，如何寻找确定一个句型的句柄是构造一个自左向右扫描，自底向上分析方法必须要解决的一个问题。第二节 算符优先分析法众所周知，作算术式的四则运算时，为了保证计算过程和结果的唯一性，必须要规定一个统一四则运算法则。这种法则的主要方面，就是规定运算之间的优先顺序。现在人们所遵循的统一法则是：乘除运算优先于加减运算，故在算术中要先作乘除运算后作加减运算；同优先级的运算符是先左后右（即左结合），先作左边的运算符的运算，后作右边运算符的运算。根据这个法则，如果每一步只做一个运算，那么，任何算术式的计算过程和结果便是唯一的。例如： 9+86/23+和同级，先作+ =176/23优先级低于/，先作/， =1733优先级低于，先作 =179 只有唯一的。 =8对于含有括号一目运算减的算术式，我们只需对上述的法则加以补充。如规定要先作括号里的运算，后作括号外的；一目运算减的优先级高于加减低于乘幂。那么，包含有括号和一目运算的算术式的计算过程也是唯一的。以上关于算术式的四则运算法则，连小学生也是熟知的。所谓算符优先分析法就是仿照上述算术式的四则运算过程而设计的一种语法分析方法。实际上，该方法在一开始就是为了分析和翻译程序语言中的表达式而设计的。这种方法首先是要规定运算符之间（更一般说是终结符号之间）的优先关系和结合性质，然后就利用这种关系，用比较相邻运算符的优先顺序来确定句型的“句柄”和进行归约。应该指出，这种归约未必是严格的最左归约，即每一步未必是归约当前句型的句柄，所以，我们在句柄上打上了引号。下面，举一个简单的例子，来说明应用该方法分析符号串的过程。例2 有文法：GE：EE=E|EE|E*E|E/E|E（E）|i这是一个二义性的文法，它的句子往往有不同的规范推导，因而就有不同的规范归约（句型的句柄未必是唯一的）。例如，对句子i+ii*(i+i)，就有两种不同的规范推导和规范归约。所以，归约过程中句型的句柄不唯一。但是，如果采用上述关于运算符优先顺序和结合原则的规定，并按这种规定进行归约，那么，该句子的归约过程就是唯一的。例如，我们按正常的四则运算法则，即规定乘除运算符的优先级高于加减运算符；同级运算符是左边的运算符的优先级高于右边的；有括号时，先括号内后括号外；另外，因i是一个基本的运算对象（属终结符号），因此，我们要先算一算它，然后进行别的运算，故规定i的优先级高于其他运算符。按此条件来归约分析上述句子，那么，可得该句子的归约过程为：（1）i+ii *（i+i）（2）E+ii *（i+i）（3）E+Ei *（i+i）（4）Ei *（i+i）（5）EE *（i+i）（6）EE *（E+i）（7）EE *（E+E）（8）EE *（E）（9）EE *E（10）EE （11）E 由前所述，可知这个归约过程是唯一的。当从第（3）归约到第（4）时，相继的两个运算符+和虽属同一优先级，但因采用左结合原则，故+优先于（记为+）。因此先把E+E归约为E。当第（5）归约到第（6）时，因的优先级低于*（记为 *），所以，不能立即把EE归约为E，而必须首先归约乘法运算。但因*的右运算对象是带括号的，故必须先对括号里的式子进行归约。当从第（8）至第（9）时，同样不能先归约减法而必须先归约乘法，但由于乘法的右运算对象含有括号，因此，首先又必须把括号去掉。这次归约同时去掉两个终结符（和），这两个终结符的优先级是认为相同的记为（）在上述的整个归约过程中，起决定作用的是相邻两个终结符的优先关系，所以应用算符优先分析法自底向上地分析句子，解决了前面提到的两个问题，即：（1）可以只根据相邻运算符的优先关系，就能方便地并且唯一地确定归约的“句柄”；（2）可以用来分析二义性文法所产生的语言。上述文法虽是二义性的（存在不同的规范归约），但用算符优先法分析其句子时，其归约过程是唯一的。我们所规定的运算符之间的优先顺序和左结合的原则，就是避免二义性的充分条件。第三节 直观算符优先分析法 直观算符优先分析法是按照文法符号（终结符和非终结符）的优先关系确定句柄的，因此我们首先介绍任意两个文法符号之间的优先关系是怎样确定的，及如何构造优先关系表。 一、 优先关系首先定义优先关系的表示：XY 表示X和Y的优先关系相等。XY 表示X的优先性比Y的优先性大。XY 表示X的优先性比Y的优先性小。这样我们就可以对已知文法对它的任意两个文法符号X,Y按其在句型中可能会出现的相邻关系来确定它们的优先关系。（注意、和数学中的= 、不同）。（1）XY 当且仅当G中存在产生式规则AX Y（2）XY 当且仅当G中存在产生式规则AXB，且BY（3）XY 当且仅当G中存在产生式规则ABD，且BX和DY例3 若有文法GS：SbAb A(B|a BAa）根据上面、关系的定义，由文法的产生式可求得文法符号之间的优先关系如下：（1）求关系：由SbAb,A(B,BAa)可得：bA,Ab,( B,Aa,a)（2）求关系：由SbAb,且A (B，Aa)可得：b(，ba由A（B且B（B，Ba;BA，可得：（,（a ,（A （3）求关系：由SbAb且A),AB,Aa可得：)b,ab,Bb由BAa）且A），Aa，AB可得：)a,aa,Ba上述关系也可以用语法树的结构表示如图5-3-1由语法树层次可看出当（B为某句型的句柄时，它们将同时归约，同样bAb,Aa）也是如此。也可看出当b(,ba出现在某一句型中时，则（和a在句柄中时b不在句柄中，因此必须（和a先归约，所以b的优先级比(a小，同样可以看出当（、（a，或（A出现在某句型中时，右边的（，aA出现在句柄中，而左边的（不被包含在句柄中，所以左边（的优先级小于右边相邻的（、a或A。对于大于关系也可由树中看出，当ab或aa出现在某一句型中时，左边的a在句柄中，右边的a和b不可能在句柄中，所以有ab,aa的关系存在，同样)b或)a出现在某一句型中时，）在句柄中而a,b不在句柄中，因此）先归约，则有)a,)b的关系。当然对含有Bb和Ba的句型，B先归约，则有Bb,Ba的关系。S S S Sb A b b A b b A b b A b( B a ( B ( BA a ) A a )( B aA a )(a) (b) (c) (d)图5-3-1 语法树结构为了表示简洁明了我们也可以把文法符号之间的关系用矩阵表示，称作优先关系矩阵。例3文法的简单优先关系矩阵可用表5.1 表示。表5.1 例3文法的简单优先关系矩阵SbA(Ba)#SbA(Ba)# 在表5.1 简单优先关系矩阵中可以看出：若矩阵中元素要么只有一种关系，要么为空，元素为空时表示该文法的任何句型中不会出现该符号对的相邻关系，在分析过程中若遇到这种相邻关系出现，则为出错，也就可以肯定输入符号串不是该文法的句子。#号用来表示语句括号，#号的优先级所有符号，所有符号的优先级 #号，当然这里仅对与#号有相邻关系的文法符号而言。 二、直观算符优先分析法通常在算术表达式求值过程中，运算次序是先乘除后加减，这说明了乘除运算的优先级高于加减运算的优级，乘除为同一优先级但运算符在前边的先做，这称为左结合，同样加减运算也是如此，这也说明了运算的次序只与运算符有关，而与运算对象无关，因而直观算符优先分析法的关键是对一个给定文法G，人为地规定其算符的优先顺序，即给出优先级别和同一级别中的结合性质，算符间的优先关系表示与前面介绍的优先关系的表示类似，其规定如下：ab 表示a的优先性低于b。ab 表示a的优先性等于b，即与b相同。ab 表示a的优先性高于b。但必须注意，这三个关系和数学中的是不同的，它们是有序的，也就是若有ab，不一定有ba，ab成立不一定有ba，例如：通常表达式中运算符的优先关系有+-，但没有-+成立，（）成立但没有）（成立。下面给出一个表达式的文法为GE:EE+E|E-E|E*E|E/E|EE|（E）|i我们可以对此表达式的文法按公认的计算顺序规定优先级和结合性如下：（1）优先级最高，遵循右结合。相当。例如：232=29=512。也就是同类运算符在归约时为从右向左归约。即i1i2i3为i2i3先归约。（2）*，/优先级其次，服从左结合。相当*、*/、/、/*。（3）+，-优先级最低，服从左结合。相当+、+-、-+、-。（4）对（，）规定括号的优先性大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号。对于句子括号#号规定与它相邻的任何运算的优先性都比它大。此外，对运算对象的终结符i其优先级最高。综上所述，我们可对表达式运算符的优先关系构造如表5.2表5.2 算符优先关系表+-*/（）i#+-*/()I# 很显然所给表达式文法显然是二义性文法，但我们认为直观地给出运算符之间的优先关系且这种优先关系是唯一的下面，我们使用已经建立起来的文法GE的优先关系矩阵，构造一个分析该文法句子的算法，即直观算符优先分析法。为了便于比较相邻运算符的优先级，它使用两个工作栈（也可以使用一个栈），一个称为运算符栈，以OPTR表示，用来存放运算符，另一个称为运算对象栈，以OPND表示，用来存放运算对象（包括最基本的运算对象和运算结果）。仍用符号#代表待分析句子的左右分界符。分析开始时，OPTR栈中压入左界符#，OPND栈为空。同时，令代表OPTR当前栈顶符号，a存放新输入的那个符号。那么分析算法的基本步骤是：（1）把下一个输入符号读至a中；（2）若a为i，则把它推进OPND栈；转第一步；（3）若 a，则应根据规则E=E2E1进行归约，E2和E1 代表OPND栈的次高元和最高元中的运算对象。先将E1 和E2从OPND栈中弹出，然后把代表该子表达式运算结果的E压入OPND中，同时，把从OPTR栈顶弹出，然后重新进入第3步（此时已代表OPTR栈的新栈顶项了）；（4）若a，则按表5.2这只有一种可能：即=“（”，而a =“）”。在这种情况下，弹出OPTR栈顶高元的“（”，放弃a中的右括号，然后转第1步；（5）若 a，把a移进OPTR栈，转至第一步；（6）若 = a =“#”，分析过程宣告结束；（7）若与a不存在优先关系，即矩阵元素为空白，这意味着输入串含有错误，调出错处理程序进行处理。分析成功的标志是（只是必要条件）：OPTR栈底的“#”与输入串后的“#”相遇（即过程进行到第4步），而OPND栈中仅含一项，这一项代表整个表达式的分析结果。如果不是这种情况，则意味着分析失败，也就是说：表达式有语法错误。在第3和第4步，当要形成子式E E和（E）时，若OPND栈中没有足够的项数（前者要两项，后者要一项），那也表示输入串有错。上面的算法仅对文法GE所定义的算术表达式的分析有效。然而，所有算符优先分析法大体上也都是这样工作。现在，我们用上述算法来分析表达式i+i*i。步骤对象栈算符栈关系读入符号符号串（0）#i+i*i #（1）#i+i*i #（2）i# + i*i #（3）i# +i *i #（4）i i# + * i #（5）i i# + *i#（6）i i i# + * #（7）i t# #（8）e#分析结果表明i+i*i是文法GE的句子。上述算法由于使用了两个栈，当读进的符号一旦判断出是运算对象时，就立即推进运算对象栈，而不与运算栈的栈顶符号比较优先级。因此，没有用到作为终结符的运算对象与其他算符之间的优先关系。三 、 优先函数在实际上，实现算符优先分析法时，一般不用文法的优先关系矩阵，而是用两个优先函数f和g。前面用算符优先分析法时，对算符之间的优先关系，我们用优先矩阵表示，这样需占用大量的内存空间，当文法有n个非终结符时，就需要有(n+1)2个内存单元（终结符和#号），因而，在实际应用中往往用优先函数来代替优先矩阵表示优先关系。它对具有n个终结符的文法，只需2(n+1)个单元存放优先函数，这样可节省大量的存储空间。缺点是原先不存在优先关系的，由于与自然数相对应，变成可比较。我们可以定义两个函数f,g满足如下条件：当ab，则令f(a)=g(b)当ab，则令f(a) g(b)对f,g我们称它为优先函数。它的值可用整数表示，下面给出其构造方法：（1）由定义直接构造优先函数若已知文法G终结符之间的优先关系，可按如下步骤构造其优先函数f,g。a）对每个终结符aVT（包括#号在内）令f(a)=g(a)=1，（也可是其它整数）。b）如果ab，而f(a)g(b) 则令f(a)=g(b)+1c）如果ab而f(a)g(b) 则令 g(b)=f(a)+1d）如果ab，而f(a)g(b)则令minf(a), g(b)=maxf(a), g(b)e）重复b）d）直到过程收敛。如果重复过程中有一个值大于2n，则表明该算符优先文法不存在算符优先函数。例如：若已知表达式文法的算符优先矩阵如表5.2，我们可按上述规则构造它的优先函数。其优先函数的构造过程为：首先：把所有f(a)，g(a)的值置为1如表5.3中的初值（0次迭代）。然后对算符优先关系矩阵逐行扫描，按前述算法规则的b)e)修改函数f(a), g(a)的值，这是个迭代过程，一直进行到优先函数的值再无变化为止。在表5.3中给出每次迭代对优先关系矩阵逐行扫描后函数值f(a), g(a)的变化结果。表5.3 表达式文法优先函数计算过程迭代次数+*i（）#0（初值）f1111111g11111111f2446161g23555112f3557171g24666113f同第2次迭代结果g例中优先函数的计算迭代三次收敛。不难看出对优先函数每个元素的值都增加同一个常数，优先关系不变。因而，对同一个文法的优先关系矩阵对应的优先函数不唯一。然而也有一些优先关系矩阵中的优先关系是唯一的，却不存在优先函数，例如下面优先关系矩阵：不存在优先函数f,g的对应关系。abab由于若存在优先函数f,g，则必定满足下列条件，由矩阵的第一行应有f(a)=g(a), f(a) g(b)由矩阵的第二行应有f(b)=g(a), f(b)=g(b)这样导致有 f(a)=g(a)=f(b)=g(b)与f(a) g(b)矛盾，因而优先函数不存在。第四节 算符优先文法我们首先给出算符文法和算符优先文法的定义定义1 设有一文法G，如果G中没有形如ABC的产生式，其中B和C为非终结符，则称G为算符文法（Operater Grammar）也称OG文法。例如：表达式文法EE+E|E*E|（E）|i其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法是算符文法。算符文法有如下两个性质。性质1 在算符文法中任何句型都不包含两个相邻的非终结符。证：用归纳法设是句型，SS=01n -1n=推导长度为n，归纳起点n=1时，S=01 即S=必存在产生式S，而由算符文法的定义，文法的产生式中无相邻的非终结符，显然满足性质1。假设n 1, n -1满足性质1。若n -1=A，A为非终结符。由假设的尾符号和的首符号都不可能是非终结符，否则与假设矛盾。又若A是文法的产生式，则有n -1n=而A是文法的原产生式不含两个相邻的非终结符，所以也不含两个相邻的非终结符。满足性质1证毕。性质2 如果Ab或（bA）出现在算符文法的句型中，其中AVN，bVT,则中任何含b的短语必含有A。证明：用反证法。因为由算符文法的性质1可知有：S=bA若存在Bb，这时b和A不同时归约，则必有SBA，这样的句型BA中，存在相邻的非终结符B和A，所以与性质1矛盾，证毕。注意：含b的短语必含A，含A的短语不一定含b。定义2 设G是一个算符文法，a和b是任意两个终结符，A、B、C是非终结符，算符优先关系、定义如下：（1）ab 当且仅当G中含有形如Aab或AaBb的产生式（2）ab 当且仅当G中含有形如AaB的产生式，且Bb或BCb（3）ab 当且仅当G中含有形如ABb的产生式，且Ba或BaC以上三种关系也可由下列语法树来说明：（1）ab则存在语法树如图5-4-1（a）其中为或为B，这样a,b在同一句柄中同时归约所以优先级相同。（2）ab则存在语法子树如图5-4-1（b）其中为或为C。a, b不在同一句柄中，b先归约，所以a的优先级低于b。（3）ab则存在语法子树如图5-4-1（c）。AAA a b a B B b p p b a (a)ab (b)ab (c)ab图5-4-1由语法树结构决定优先性其中为或为C，a、b不在同一句柄中，a先归约，所以a的优先性大于b。下面我们给出算符优先文法的定义。定义3 设有一不含产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有、和三种关系的一种成立，则称G一个算符优先文法。（Operator Precedence Grammar）即OPG文法。由定义2和定义3很容易证明前面我们给的表达式文法。EE+E|E*E|(E)|i不是算符优先文法。因为对算符+、*来说，由EE+E和EE*E可有+*，由语法树图5-4-2(a)也可看出。又可由EE*E和EE+E得+*，由语法子树表示为图5-4-2(b)E EE + E E * EE * E E + E(a)+* (b)+*图5-4-2 二义性文法的语法树这样+、*的优先关系不唯一，所以该表达式的文法仅是算符文法而不是算符优先文法。这里必须再次强调，两个终结符之间的优先关系是有序的，允许有ab,ba同时存在，而不允许有ab,ab,ab三种情况之两种同时存在。第五节 算符优先关系表的构造一、由定义直接构造由定义2我们可按如下算法计算出给定文法中任何两个终结符对（a，b）之间的优先关系，首先我们定义如下两个集合：FIRSTVT（B）=b|Bb或BCb LASTVT（B）=a|Ba或BaC 三种优先关系的计算为：a) 关系：可直接查看产生式的右部，对形如产生式Aab AaBb则有ab成立。b) 关系：求出每个非终结符B的FIRSTVT（B），对形如产生式：AaB中对每一 bFIRSTVT（B）则有ab成立 c）关系：计算每个非终结符B的LASTVT（B），对形如产生式ABb中对每一aLASTVT（B）则有ab成立。现在我们可用上述算法计算下列表达式文法的算符优先关系。若表达式文法为：（0）E#E#（1）EE+T（2）ET（3）TT*F（4）TF（5）FPF|P（6）P（E）（7）Pi计算优先关系为：a）关系由产生式（0）E#E#和（6）P（E）可得# #，（）成立，为了求，关系，首先计算每个非终结符的FIRSTVT集合和LASTVT集合。FIRSTVT（E）=#FIRSTVT（E）=+，*，(,iFIRSTVT（T）=*,（，iFIRSTVT（F）=,（，iFIRSTVT（P）=（，iLASTVT（E）=#LASTVT（E）=+，*，),i LASTVT（T）=*，),i LASTVT（F）=，),i LASTVT（P）=),i 然后逐条扫描产生式寻找终结符在前非终结符在后的相邻符号对，及非终结符在前终结符在后的相邻符号对，即产生式右部有形如：AaB 和ABb的产生式b）关系：对所给表达式文法中终结符在前非终结符在后的相邻符号对有：#E 则有：#FIRSTVT（E）+T 则有：+FIRSTVT（T）*F 则有：*FIRSTVT（F）F 则有：FIRSTVT（F）(E 则有：(FIRSTVT（E）c）关系：对表达式文法中非终结符在前终结符在后的相邻符号对有：E#则有：LASTVT（E）#E+则有：LASTVT（E）+T* 则有：LASTVT（T）*P 则有：LASTVT（P）E) 则有：LASTVT（E）)从而可以构造优先关系矩阵为表5-5-1。表5-5-1 表达式文法算符优先关系表+*i（）#+*i（）#第六节 算符优先分析算法设计前面，我们仿照算术式的四则运算法则，以文法为例，直观地介绍了算符优先分析法的基本思想和基本算法。同时指出这种算法在一般情况下并不是严格的最左归约法。也就是说，每次归约未必是归约当前句型的“句柄”。因此，我们将句柄打上了引号。下面，准备从理论上来讨论打上引号的句柄是什么。并在此基础上，再来研究算符优先分析法的实现问题。算符优先分析法仍然是一种自底向上的分析算法，但不是严格从左到右的。在每一步分析中，它将识别和归约那些所谓的最左素短语。1、定义 文法的句型的素短语是这样一个短语，它至少包含有一个终结符号，并且，除它自身外，不再包含其他素短语。考虑文法GE（1）EE+T|T（2）TT*F|F（3）F（E）|i的句型（两端已加上分界符#）#T+T*F+i#，它的短语是T+T*F+i，T+T*F，i，最左边的那个T，以及T*F。只要画出该句型的语法树，就能很方便地找出这些短语，见图5-6-1 EE +