第六章 自底向上优先分析

1、1,第六章自底向上的优先分析法,6.1自底向上优先分析概述6.2简单优先分析法6.3算符优先分析法6.4典型例题,2,基本思想：对输入符号串自左向右扫描，并将输入符移入一先进后出栈中，边移入边分析，一但栈顶符号串形成某个句型的句柄，就用该句柄对应产生式的左部非终结符代替栈顶相应符号串(即进行了一步归约)。重复该过程直到归约到栈中只剩文法的开始符号，则分析成功。,6.1自底向上优先分析概述自底向上分析法，也称移进-归约分析法。,3,6.1自底向上优先分析概述,例6.1已知文法GS为：(1)SaAcBe(2)Ab(3)AAb(4)Bd对输入串abbcde#进行分析。由于自底向上分析的移进-归约是自

2、顶向下最右推导的逆过程，而最右推导为规范推导，所以自左向右的归约过程称为规范归约。又因输入串abbcde的最右推导是：S=aAcBe=aAcde=aAbcde=abbcde所以，上述句子的规约过程为,4,6.1自底向上优先分析概述,5,自底向上构造语法树的过程,6,问题：在上述移进-归约过程中，如何确定何时移进何时规约？,故自底向上分析的关键是在分析过程中如何确定句柄。具体方法有：优先分析法（简单优先、算符优先）和LR类分析方法。,GS：(1)SaAcBe(2)Ab(3)AAb(4)Bd,7,简单优先分析法对一个文法按一定规则求出该文法所有符号之间的优先关系，再按照这种关系确定规约过程的句柄，

3、该规约过程实际上是一种规范规约。算符优先分析法只规定算符(广义为终结符)之间的优先关系，不考虑非终结符之间的优先关系，在规约过程中只要找到可规约串就规约，不考虑规约到那个非终结符，所以不是规范规约。,6.1自底向上优先分析概述,8,6.2简单优先分析法,简单优先分析法是按照文法符号(VTandVN)的优先关系确定句柄的。6.2.1优先关系优先关系的表示:XY表示X的优先性等于Y。XY表示X的优先性低于YXY表示X的优先性高于Y。优先关系是有序的，XY不一定YX；XY不一定YX；XY不一定YX；,9,(1)XY当且仅当G中存在产生式AXY(2)XY当且仅当G中存在产生式AXB,且B=+Y(3)X

4、Y当且仅当G中存在产生式ABD,且B=+X和D=*Y,优先关系的定义:,6.2简单优先分析法,10,根据优先关系的定义可求得各文法符号之间的优先关系如下：,6.2简单优先分析法,11,6.2简单优先分析法,例6.2文法中的优先关系也可用语法树的结构表示为：,12,为表示简洁，通常用优先关系矩阵表示,6.2简单优先分析法,13,6.2.2简单优先文法的定义若一文法是简单优先文法，必须满足：在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。在文法中任意两个产生式没有相同的右部。,6.2简单优先分析法,14,6.2简单优先分析法,6.2.3简单优先分析法的操作步骤首先根据已知文法构造优先关

5、系矩阵，保存产生式，并设置符号栈S，然后按下步骤进行分析：将输入符号串a1a2an#依次入栈，直到遇到栈顶符号ai的优先性下一个待输入符号aj为止。栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头，ak（其中ak-1ak）。由句柄akai在文法产生式中找右部与之相等的产生式，若找到则用相应左部代替该句柄，否则出错。重复上述操作，直到栈中只剩文法的开始符为止。,15,6.3.0算符优先问题的提出,6.3算符优先分析法,已知文法G:EE+E；EE*E；Ei输入串i+i*i的归约过程可表示为表6.3。,16,6.3.1直观算符优先分析法普通算术表达式求值中，运算次序只与运算符有关而与运算对象无关，

6、因而算符优先分析法的关键是规定文法G中算符的优先顺序和结合性。算符间的优先关系是有序的，表示如下：,6.3算符优先分析法,17,如何确定算符优先关系？,人为确定(直观算符优先分析法中)1.i的优先级最高2.优先级次于i，右结合3.*和/优先级次之，左结合4.+和-优先级最低，左结合5.括号(,)的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号6.#的优先性低于与其相邻的算符,表6.4算符优先关系表,18,例如:文法G：(1)EE+E(2)EE*E(3)Ei规定了算符优先性后，输入串i+i*i的归约过程不再有歧义,19,6.3.2算符优先文法的定义,算符文法定义：设一文法

7、G，若没有形如ABC的产生式,其中B,CVN则称G为算符文法(operatorgrammar:OG)。例6.1GE：EE+E|E*E|i是OG文法性质1：在算符文法中任何句型都不包含两个相邻的非终结符。性质2：如Ab或bA出现在算符文法的句型中,其中AVN,bVT,则中任何含b的短语必含有A(但含A的短语不一定含b)。,6.3算符优先分析法,20,证明：（归纳法）设是句型,则有S=*,不妨记为S=0=1=.=n-1=n=，此时推导长度为n，归纳起点n=1时，S=0=1=，即S=，必存在产生式S，而由算符文法的定义，文法的产生式中无相邻的非终结符，显然满足性质1。,性质1:在算符文法中任何句型都

8、不包含两个相邻的非终结符。,假设n1,n-1满足性质1。若n-1=A，A为非终结符。由假设的尾符号和的首符号都不可能是非终结符，否则与假设矛盾。又若A是文法的产生式，则有n-1=n=而A是文法的原产生式，不含两个相邻的非终结符，所以也不含两个相邻的非终结符。满足性质1。证毕。,21,证明：(反证法)由算符文法的性质1可知，此类文法句型均为如下形式：S=*=bA假设存在B=*b，这时b和A不同时归约，则必有S=*BA,这样在句型BA中存在相邻的非终结符B和A，所以与性质1矛盾，证毕。注意：含A的短语不一定含b。,性质2:如Ab或bA出现在算符文法的句型中,其中AVN,bVT,则中任何含b的短语必

9、含有A(但含A的短语不一定含b)。,22,算符优先关系的形式化定义：,定义6.2:设G为不含产生式的OG，a,b是终结符,A,B,C为非终结符，则算符优先关系的定义如下：a=bG中有形如：Aab或AaBb.的产生式。a+b或B=+CbabG中有形如:ABb的产生式,而B=+a或B=+aC规定：若S=+a或S=+Ca则#+a或S=+aC则a#,23,以上三种优先关系也可由以下语法树来说明：,算符优先关系定义的语法树描述：,注意：两个终结符之间的优先关系是有序的，允许ab,ba同时存在，而不允许ab,ab,a=b三种情况中的任意两种同时存在。,24,定义6.3:在不含产生式的OG文法G中，若任意两

10、个终结符间至多有一种算符优先关系存在，则称G为算符优先文法(operatorprecedencegrammar:OPG)。,算符优先文法的定义,根据定义6.2和6.3判断文法GE：EE+E|E*E|i是否是算符优先文法？,25,图6.4二义性算术表达式文法的语法树,结论：因+,*的优先关系不唯一，所以该文法只是OG文法而不是OPG。需要特别定义后才能转化为OPG。,GE：EE+E|E*E|i,26,6.3.3算符优先关系表的构造,首先定义如下两个集合：FIRSTVT(B)=bB=+b或B=+CbLASTVT(B)=aB=+a或B=+aC,这样任何两个终结符对(a,b)间的优先关系可表示为：1)

11、=关系直接看产生式的右部，若出现了Aab或AaBb,则a=b2)关系求出每个非终结符B的LASTVT(B)若ABb,则aLASTVT(B),则ab即LASTVT(B)b,27,计算文法的算符优先关系,例文法GE：(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF|P(6)P(E)(7)Pi,FIRSTVT(E)=#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=

12、),i,28,(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF|P(6)P(E)(7)Pi,3)关系找形如：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),得#=#，(=),29,表达式文法GE的算符优先关表,30,优先关系表的自动构造方法,FIRSTVT集的求

13、法LASTVT集的求法优先关系表的自动构造方法,6.3.3算符优先关系表的构造,31,FIRSTVT集的构造方法:1.布尔数组法算符所用两条基本规则若有产生式Aa或ABa则aFIRSTVT(A)若aFIRSTVT(B)且有产生式AB则aFIRSTVT(A),程序实现所需数据结构及含义定义一个布尔数组Fm,n(m为非终结符个数，n为终结符个数）和堆栈Stack,并将所有非终结符和终结符分别排序，iA表示非终结符A的序号，ja表示终结符a的序号。算法最终使数组元素取值满足：FiA,ja=1，当且仅当aFIRSTVT(A),32,具体程序实现的描述：,FIRSTVT集构造方法一（布尔数组法）,33,

14、FIRSTVT集构造方法一（布尔数组法）,34,例题:求表达式文法GE每个非终结符的FIRSTVT(B),FIRSTVT集构造方法一（布尔数组法）,GE：(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF|P(6)P(E)(7)Pi,1.第1次扫描产生式后，Stack的值为:,2.使用规则2:若aFIRSTVT(B)且有产生式AB则aFIRSTVT(A);对栈中元素进行替换。,35,FIRSTVT集构造方法一（布尔数组法）,扫描文法看到再无右部以E开始的产生式所以(E,i)弹出后无进栈项，这时Stack变为,同样，由产生式：,以下逐次弹出栈顶元素后，都再无进栈项，直至栈

15、空。,36,最终可得表6.6所示布尔数组,FIRSTVT集构造方法一（布尔数组法）,37,2.关系图法,FIRSTVT集构造方法二（关系图法）,38,FIRSTVT集构造方法二（关系图法）,39,LASTVT集求法:基本规则若有产生式Aa或AaB则aLASTVT(A)若aLASTVT(B)且有产生式AB则aLASTVT(A)具体实现方法与FISTVT求法类似,40,算符优先文法中优先关系表的构造,41,6.3.4算符优先分析算法,1)算符优先文法(OPG)句型的性质因：算符文法的任何句型均可表示为如下形式N1a1N2a2.NnanNn+1其中Nk(1kn+1)为非终结符或空，ak(1kn)为终

16、结符。故：若ai.Njaj是句型.Niai.NjajNj+1.中句柄的一部分，则Ni，Nj+1也必定在该句柄中。在OPG中该句柄所包含的各终结符之间满足以下关系：ai-1aj+1,42,性质2原因分析（ai-1aj+1）由算符优先文法的定义可知：如果aNb(或ab)出现在句型r中，则a和b之间有且只有一种优先关系,即若ab则在r中必含有a而不含b的短语存在。若a=b则在r中含有a的短语必含有b，反之亦然。,算符优先分析过程归约时,只能把之间的符号串作为可归约串进行归约。,6.3.4算符优先分析算法,43,例：表达式文法：(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF

17、|P(6)P(E)(7)Pi对i+i#的规范规约和算符优先规约的比较。,注意:在算符优先分析过程中，因去掉了单非终结符之间的归约，非终结符的名字没有任何意义。所以在归约过程中所有的非终结符都用同一个名字。,6.3.4算符优先分析算法,44,6.3.4算符优先分析算法,45,6.3.4算符优先分析算法,46,2)最左素短语算符优先分析的可归约串是句型的最左素短语定义：G的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其它素短语。素短语必须满足下列两个条件:1、至少包含一个终结符号。2、该短语不再包含满足第一个条件的更小的短语。,处于句型最左边的素短语为最左素短语,6.3.4算符

18、优先分析算法,47,例：求文法GE的最左素短语。(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF|P(6)P(E)(7)Pi,句型T+T*F+i其短语有：T+T*F+iT+T*FTT*Fi,E,E,T,+,+,E,T,*,F,T,T,i,句型T+T*F+i的最左素短语为：T*F,F,句型T+T*F+i的素短语为：T*F，i,P,48,算法优先分析法的关键是寻找当前句型的最左素短语。而最左素短语Niai.NjajNj+1应满足如下性质：ai-1aj+1在寻找规约所用产生式时：产生式右部的终结符必须与素短语中对应一致，而非终结符不要求名称一样。,3)算符优先分析算法,49,3)算符优先

19、分析归约过程,S:寄存归约或待形成最左素短语的符号串；a:存放当前读入的终结符号。,50,6.3.5优先函数利用优先矩阵表示算符之间的优先关系时，需要占用大量的内存空间，实用中可以用优先函数来表示优先关系。,51,6.3.5优先函数的构造方法一,若重复过程中有一个值大于2n，则文法不存在算符优先函数。,52,6.3.5优先函数的构造方法一,例：,53,迭代计算三次后收敛，结果如下,6.3.5优先函数的构造方法一,54,并不是所有合法的优先关系矩阵都存在对应的优先函数。,6.3.5优先函数的构造方法一,例：,55,(2)关系图法构造优先函数a)对所有终结符a（包括#）用有下标的fa，ga为结点名画出2n个结点。,6.3.5优先函数的构造方法二,c)给每个结点赋一个数，此数等于从该结点出发所能到达的结点（包括该结点自身在内）的个