编译原理及其习题解答(武汉大学出版社)课件chap6.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,编译原理,Compiler Principles,中南民族大学计算机科学学院,编译原理,Compiler Principles,第六章 自底向上优先分析法,编译原理,Compiler Principles,第六章 自底向上优先分析法,自底向上的分析方法，也称移进,-,归约分析法。它的,实现思想,是：,对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，,(,该句柄对应某产生式的右部,),，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。,确定的自底向上的分析方法分为两大类：,优先分析法,和,LR,分析方法,。本章将在介绍自底向上分析思想基础上，着重介绍算符优先分析法。,编译原理,Compiler Principles,6.1,短语、直接短语、句柄,1,、短语：,令文法,G,，,开始符号为,S,，,xAy,是,G,的句型,（即,S,xAy,），,如果,S,xAy,且,A ,，,则称,是句型,xy,相对于非终结符,A,的短语。,2,、直接短语（简单短语）,如短语中有,A=,，,则称,是句型相对于规则,A,的直接短语。,3,、句柄（,Handle,）,一个句型的最左直接短语称为该句型的句柄。（可规约串）,编译原理,Compiler Principles,例,6.1,例：文法,G,数,:,|,0|1|2|3|4|5|6|7|8|9,=1,所以，,1,是一个句型。下面结论是否正确？,1.1,是句型,1,相对于,的短语。,2.1,是句型,1,相对于,的短语。,3.,是句型,1,相对于,的短语。,编译原理,Compiler Principles,语法树与短语的关系,1.,每个句型（句子）都对应有一棵语法树；,2.,每棵语法树的叶子结点从左到右、从上到下构成一个句型（句子）；,3.,每棵子树的叶子结点从左到右、从上到下构成一个短语；,每棵子树的直接叶子结点从左到右、从上到下构成一个直接短语；,最左简单子树的直接叶子结点从左到右、从上到下构成一个句柄。,编译原理,Compiler Principles,例,6.1,1,编译原理,Compiler Principles,解题方法 例,2,例：文法,GE:E T|E+T,T F|T*F,F(E)|i,证明,i+i*i,是,G,的一个句型，并指出这个句型的所有短语、直接短语、句柄。,证明：,E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i,编译原理,Compiler Principles,接上例,语法树：,E,E,+,T,T,T,*,F,F,F,i,3,i,1,i,2,第,1,层,i,1,+i,2,*i,3,相对于,E,第,2,层,i,1,相对于,E;i,2,*i,3,相对于,T,第,3,层,i,1,i,2,相对于,T;i,3,相对于,F,第,4,层,i,1,i,2,相对于,F(F i,直接短语,),第,5,层,i+i*i,是,G,的一个句型，其中,i,1,i,2,i,3,i,2,*i,3,i,1,+i,2,*i,3,都是句型,i,1,+i,2,*i,3,的短语，且,i,1,i,2,i,3,为直接短语，,i,1,为句柄,编译原理,Compiler Principles,分析说明,(2),作为“短语”的两个条件是不可缺少的，仅仅有,A,，,未必意味着,就是句型,的一个短语，因为还需要有,S,这个条件。,例如：上例中有,E i,1,+i,2,，但,i,1,+i,2,并不是该句型的一个短语，因为不存在从,E,（,开始符号）到,E*i,3,的推导。,(1),短语、直接短语、句柄是针对某一句型（,S,）,而言的,;,编译原理,Compiler Principles,解题方法,先证明前提（如,证明,i+i*i,是,G,的一个句型）,给出语法树（注意文法是否是二义性的）,如题,文法,GE:E E+E|E*E|(E)|i,所以：证明,i+i*i,是,G,的一个句型，并指出这个句型的所有短语、直接短语、句柄。,根据每颗语法树得出短语、直接短语、句柄,例课本,P143,例,6.3,编译原理,Compiler Principles,练习,1,题目,文法,GT:T F|T*F,F F P|P,P(T)|i,证明,T*P(T*F),是文法,G,的一个句型，并指出这个句型的所有短语、直接短语、句柄。,编译原理,Compiler Principles,练习解答,证明：,T T*F T*F,P T*F,(T)T*F,(T*F),T*P,(T*F),语法树：,T,T,*,F,F,P,P,T,(,),T,*,F,第,1,层,T*P,(T*F),相对于,T,第,2,层,P,(T*F),相对于,F;,第,3,层,P,相对于,F;(T*F),相对于,P,第,4,层,T*F,相对于,T,第,5,层,T*P,(T*F),是,G,的一个句型，其中,T*F,P,(T*F),P,(T*F),T*P,(T*F),都是该句型的短语，且,T*F,P,为直接短语，,P,为句柄,编译原理,Compiler Principles,练习,2,题目,设有文法,GS:,S V,1,V,1,V,2,|V,1,iV,2,V,2,V,3,|V,2,+V,3,V,3,)V,1,*|(,(1),给出,(+(i(,的最右推导，并画出相应的语法树；,(2),证明,V,2,+V,3,i(,是文法的一个句型，并指出这个句型的短语、直接短语、句柄。,编译原理,Compiler Principles,练习解答（）,(1),解：,S V,1,V,1,iV,2,V,1,iV,3,V,1,i(V,2,i(V,2,+V,3,i(V,2,+(i(,V,3,+(i(+(i(,语法树：,V,1,V,1,i,V,2,(,S,V,2,V,2,+,V,3,V,3,V,3,(,(,编译原理,Compiler Principles,练习解答（）,(2),证明：,S V,1,V,1,iV,2,V,1,iV,3,V,1,i(V,2,i(V,2,+V,3,i(,V,2,+V,3,i(,是文法的一个句型,短语：,V,2,+V,3,(,V,2,+V,3,i(,直接短语：,V,2,+V,3,(,句柄：,V,2,+V,3,编译原理,Compiler Principles,算法应考虑的问题,算法是否能够终止？,算法是否快速？,算法是否能够处理所有的情况？,在每一步中如何选择子串进行归约？,编译原理,Compiler Principles,文法,GS,：,(1)S,aAcBe,(2)A b(3)A,Ab,(4)B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1,）,#,abbcde,#,移进,2,）,#a,bbcde,#,移进,A,3,）,#,ab,bcde,#,归约,(Ab),4,）,#,aA,bcde,#,移进,A,5,）,#,aAb,cde,#,归约,(,AAb,),6,）,#,aA,cde,#,移进,7,）,#,aAc,de#,移进,B,8,）,#,aAcd,e#,归约,(Bd),9,）,#,aAcB,e#,移进,11,）,#S#,接受,S,10,）,#,aAcBe,#,归约,(,SaAcBe,),分析符号串,abbcde,是否,GS,的句子,对输入串,abbcde,#,的移进,-,规约分析过程,S,aAcBe,aAcde,aAbcde,abbcde,编译原理,Compiler Principles,自下而上分析法存在的问题,可归约串的问题,；（,该分析的每一步就是从当前串中找一个子串（称“可归约串”），将它归约到某个非终结符号）,自下而上分析法的,关键,就是找哪个子串是“可归约串”，哪个不是“可归约串”。例如上例中的,(3),a b b c d e,A,A,(3),用产生式,(2),而非,(3),，否则不能归约到,S,因此必须精确定义“可归约串”，事实上存在着种种不同的方法刻画“可归约串”，对这个概念的不同定义，形成了不同的自下而上的分析法。在“规范归约”的分析中，用“句柄”来刻画“可归约串”。,编译原理,Compiler Principles,课本例,6.4,例,6.4,设文法,GZ:,Z-AB,A-,aAb,A-,ab,B-,bB,B-c,对输入符号串,aabbbc,进行移进,-,归约分析。,分析过程在,p146.,编译原理,Compiler Principles,非确定的自下而上的分析器,非确定的自下而上的分析器，是一般移进,-,归约方法的抽象模型，可识别任何上下文无关语言。给定一个上下文无关文法，可构造一个自下而上的分析器。,非确定的自下而上的分析器与非确定的自上而下的分析器的不同之处：,课本,P147,编译原理,Compiler Principles,非确定的自下而上的分析器形式定义,非确定的自下而上的分析器，是一个七元组。,课本,P147-148,编译原理,Compiler Principles,6.2,自底,向上优先分析方法概述,优先分析方法可分为简单优先分析法和算符优先分析法。,1,、简单优先分析法的基本思想,对一个文法按一定原则求出该文法所有符号（终结符和非终结符）之间的优先关系，并按照这种关系来确定归约过程中的句柄。它的归约过程是一种规范归约。,2,、算符优先分析法的基本思想,只规定算符之间的优先关系（即只考虑终结符之间的优先关系），在规约过程中，只要找到句柄就规约，不考虑归约到哪个非终结符，不是规范归约。,编译原理,Compiler Principles,两种优先分析方法的比较,3,、简单优先分析法和算符优先分析法比较,简单优先分析法准确、规范，但分析效率低，不实用；算符优先分析法不规范，但速度快，特别适用于表达式的分析。,编译原理,Compiler Principles,6.3,简单优先分析方法,按照文法符号之间的优先关系来确定句柄。,1,、优先关系的表示,（,1,）,X=Y,表示,X,和,Y,的优先关系相等,（,2,）,XY,表示,X,的优先性比,Y,的优先性大,编译原理,Compiler Principles,6.3,简单优先分析方法,按照文法符号之间的优先关系来确定句柄。,2,、优先关系的确定,（,1,）,X=Y,文法,G,中存在产生式,A,.XY.,（,2,）,XY,文法,G,中存在产生式,A,.BD.,，,且,B .X,和,D Y.,编译原理,Compiler Principles,简单优先关系的确定 例子,文法,GS,：,(1)S,bAb,(2)A (B|a (3)B,Aa,),确定优先关系：,（,1,）求,=,关系,因为：,S,bAb,和,A (B|a,和,Aa,),所以：,b=A,A=b,(=B,A=a,a=),（,2,）,求,关系,因为：,S,bAb,且,A (B,，,A a,所以：,b (,b a,因为：,A (B,且,B (B,，,B a,B A,所以,:(,(,(a,(,关系,因为：,S,bAb,且,A ),，,A B,，,A a,所以,:),b,B b,a b,因为：,B,Aa,),且,A ),，,A B,，,A a,所以,:),a,B a,a a,编译原理,Compiler Principles,3.,简单优先关系矩阵 及,例子,优先关系矩阵：把文法符号之间的优先关系用矩阵来表示。,注意,：,1.,矩阵中的元素要么只有一种优先关系，要么为空；,2.#,用来表示语句括号，,#,优先级,#,。相当于存在,：,#S#,文法,GS,：,(1)S,bAb,(2)A (B|a(3)B,Aa,),编译原理,Compiler Principles,4.,简单优先文法的定义,若一个文法是简单优先文法，必须满足以下条件：,（,1,）在文法符号集,V,中，任意两个符号序偶最多只有一种优先关系存在；,（,2,）在文法 中，任意两个产生式没有相同的右部。（若不满足会出现归约不唯一）,句柄：,在句型,a,1,a,2,a,n,中，,a,i-1,a,j+1,则,a,i,a,i+1,a,j,是,句柄。,编译原理,Compiler Principles,5.,简单优先分析法,首先,构造优先关系矩阵；,其次,将文法的产生式保存，设置符号栈等；,然后,，按照以下算法进行归约：,（,1,）将输入符号串,a,1,a,2,a,n,#,依次逐个移入符号栈中，直到遇到栈顶符号,a,i,的优先性,下一个待输入符号,a,j,为止；,（,2,）当前栈顶符号,a,i,为,句柄尾，由此向左在栈中找句柄的头符号,a,k,，,即找到,a,k-1,a,k,为止；,（,3,）由句柄,a,k,a,i,在,文法的产生式中查找对应的产生式，若找到则进行归约，,a,k,a,i,全部出栈，将产生式右部的非终结符进栈；否则出错；,（,4,）重复以上步骤，直到归约完输入符号串，栈中只剩下文法的开始符号。,编译原理,Compiler Principles,文法,GS,：,(1)S,bAb,(2)A (B|a(3)B,Aa,),步骤,符号栈,输入符号串,动作,1,）,#,b(aa)b,#b,移进,2,）,#b (,aa)b,#b(,移进,3,）,#b(,aa)b,#(a,归约,Aa,5,）,#b(A a)b#A=a,移进,6,）,#,b(Aa,)b#a=),移进,7,）,#,b(Aa,)b#)b,归约,BAa,),8,）,#b(B b#Bb,归约,A(B,9,）,#,bA,b#A=b,移进,10,）,#,bAb,#b#,归约,SbAb,11,）,#S#,接受,对输入串,b(aa,)#,的简单优先分析过程,简单优先关系矩阵,编译原理,Compiler Principles,简单优先分析方法的算法流程图及例子,1.,流程图：,P166,图,6.6,2.,例题：,P167,例,6.13,3.,优先关系矩阵的表示,P168,4.,文法存放的数据结构,P168,编译原理,Compiler Principles,6.,有关文法的一些关系 课本,P151,1.,一个,n,元关系,R,可定义为一个有序的,n,元组集合。,2.,基本性质：自反、对称、可传递,3.,与文法相关的一些关系：关系和、关系积、传递闭包和自反传递闭包。,4.,布尔矩阵和关系,5.,Warshall,算法,一个求关系的传递闭包的算法。,P154,6.,设,R,是集合,A,上的关系，若,#A=n,，则,R,+,=R,1,+R,2,+,R,n,2,元关系,R,的传递闭包,R,+,的关系矩阵为：,M(R,+,)=M(R,1,)+M(R,2,)+,M(R,k,),=M(R),1,+M(R),2,+M(R),k,其中，,k B,其中，,AV,N,，,B(V,N,V,T,),，,(V,N,V,T,),*,(2).A LAST B,，,当且仅当文法有如下产生式：,A-B,其中，,AV,N,，,B(V,N,V,T,),，,(V,N,V,T,),*,2.FIRST,关系的传递闭包,FIRST+,定义为：,A FIRST,+,B,，,当且仅当文法有如下产生式序列：,A-B,1,B,1,-B,2,B,n,-B,3.FIRST,关系的自反传递闭包,FIRST*,定义为：,A FIRST,*,B,，,当且仅当,A FIRST,0,B,或,A FIRST,+,B,4.,同理可定义,LAST,的传递闭包和自反传递闭包。,编译原理,Compiler Principles,关系,FIRST,与,LAST,的 例子课本,P156,例,6.9,设文法,G,44,S,：,S-(A)|a|b A-B B-S|,ScB,S,A,B,a,b,c,(,),S,0,0,0,1,1,0,1,0,A,0,0,1,0,0,0,0,0,B,1,0,0,0,0,0,0,0,a,0,0,0,0,0,0,0,0,b,0,0,0,0,0,0,0,0,c,0,0,0,0,0,0,0,0,(,0,0,0,0,0,0,0,0,),0,0,0,0,0,0,0,0,FIRST=,编译原理,Compiler Principles,关系,FIRST,与,LAST,例子 续,1,例,6.9,：,S-(A)|a|b A-B B-S|,ScB,S,A,B,a,b,c,(,),S,0,0,0,1,1,0,0,1,A,0,0,1,0,0,0,0,0,B,1,0,1,0,0,0,0,0,a,0,0,0,0,0,0,0,0,b,0,0,0,0,0,0,0,0,c,0,0,0,0,0,0,0,0,(,0,0,0,0,0,0,0,0,),0,0,0,0,0,0,0,0,LAST=,编译原理,Compiler Principles,关系,FIRST,与,LAST,例子 续,2,FIRST,+,=FIRST,1,+FIRST,2,+FIRST,8,=FIRST,1,+FIRST,2,+FIRST,4,LAST,+,=LAST,1,+LAST,2,+LAST,8,=LAST,1,+LAST,2,+LAST,4,两个重要结论：,1.A=+B,，,当且仅当,A FIRST,+,B,，,其中,AV,N,，,B(V,N,V,T,),，,(V,N,V,T,),*,2.A=+B,，,当且仅当,A LAST,+,B,，,其中,AV,N,，,B(V,N,V,T,),，,(V,N,V,T,),*,编译原理,Compiler Principles,8.,简单优先关系的形式化构造方法,P160,可以利用布尔矩阵及其运算，计算出文法中的,关系。,1.,两个公式：,(1).,(=)(,FIRST,+,),公式,(6.1),(2).,(LA,ST,+,),T,(=)(,FIRST,*,),公式,(6.2),2.,根据公式,(6.1),，构造关系的,的算法。,4.,将简单优先关系,=,、,的关系矩阵中为,1,的元素置换成相应的,=,、,并合并，即可得到文法的简单优先关系矩阵。,编译原理,Compiler Principles,9.,简单优先分析方法的局限性,课本,P169,编译原理,Compiler Principles,10.,简单优先分析方法 练习,1,练习题：设文法,G,E,为：,E-E+E E-E*E E-i,求简单优先关系矩阵。（考虑对输入串,i1+i2*i3,的归约过程。）,E,+,*,i,#,E,=,=,+,=,*,=,#,=,+,=,*,=,#,E+E,E-E*E,E-i,编译原理,Compiler Principles,10.,简单优先分析方法 练习,2,考虑文法,GE,：,E,E+T|T T T*F|F F(E)|i,求简单优先关系矩阵,.,E,T,F,+,*,(,),i,#,E,=,=,T,=,F,+,=,*,=,(,=,),i,#,T,=,F,+,=,*,=,(,=,),i,#,编译原理,Compiler Principles,10.,简单优先分析方法 练习,3,求简单优先关系矩阵,.,文法,GE,为：,E,TE E+TE|T FT T*FT|F(E)|I,复杂。所以，根据文法的特点，考虑其它的分析方法。,编译原理,Compiler Principles,6.4,算符优先分析方法,1.,求优先关系矩阵,.,文法,GE,为：,E,E+E|E-E|E*E|E,/E|,EE|(E)|i,算术表达式求值中，运算的次序与运算符有关，而与运算对象无关。若能人为地给出算符的优先顺序，则可以解决简单优先文法中的冲突问题。,约定：,编译原理,Compiler Principles,算符优先分析方法,1.,求优先关系矩阵,.,文法,GE,为：,E,E+E|E-E|E*E|E,/E|,EE|(E)|i,(1),的优先级最高，右结合，有,*,*/,/,/*;,+,-,优先级最低，左结合，有,+,+-,-,-+;,对,(,和,),规定括号的优先性,括号外的运算符，,外括号。,i,的优先级最高。,编译原理,Compiler Principles,1.,算符优先分析法,表达式文法优先矩阵,优先关系矩阵为：,+,-,*,/,(,),i,#,+,-,*,/,(,=,i,#,=,编译原理,Compiler Principles,文法,GE,：,EE+E|E-E|E*E|E/E|E,E|(E)|i,步骤,符号栈,输入符号串,动作,1,）,#i+i*i#i,移进,2,）,#i +i*i#+,规约,3,）,#E +i*i#+,移进,4,）,#E+i*i#+i,移进,5,）,#E+i *i#+*,规约,6,）,#E+E *i#+*,移进,7,）,#E+E*i#*i,移进,8,）,#E+E*i#*#,规约,9,）,#E+E*E#+#,规约,10,）,#E+E#,规约,11,）,#E#,接受,对输入串,i+i*i,的算符优先分析过程,算符优先关系表,An Introduction to Database System,2.,算符文法,(OG),定义和性质,算符文法的定义,如果不含空产生式的上下文无关文法,G,中没有形如,U,VW,的产生式，其中,V,WVN,则称,G,为算符文法（,Operater,Grammar,OG,）。,即任,一个产生式的右部，都不包含两个相邻的非终结符。,两个重要性质,性质,1,：在算符文法中任何句型都不包含两个相邻的非终结符,.(,数学归纳法,),性质,2,：如,Ax,或,xA,出现在算符文法的 句型,中，其中,AVN,xVT,则,中任何 含,x,的短语必含有,A.,（,反证法）,编译原理,Compiler Principles,2.,算符文法,(OG),优先关系的定义,(3),算符优先关系的定义,在,OG,中 定义,（算符优先关系）,x,=,y G,中有形如,U,xy,或,U,xVy,.,的产生式。,x,y G,中有形如,U,Wy,的产生式,而,W x,或,W ,xV,规定,若,S x,或,S,Vx,则,#,编译原理,Compiler Principles,3.,算符优先文法,(OPG),定义,(1),算符优先文法的定义,在,OG,文法,G,中，若任意两个终结符间,至多有一种,算符优先关系存在，则称,G,为算符优先文法,(,Operater,Precedence Grammar,OPG,),。,注意：允许,bc,cb;,不允许,bc,bc,b=c,结论：算符优先文法是无二义的。,编译原理,Compiler Principles,3.,算符优先文法,(OPG),优先关系的构造,(2),算符优先文法的构造,由定义直接构造,由关系图法构造算符优先关系表,以下介绍由定义直接构造优先关系的方法。,编译原理,Compiler Principles,首先引入两个概念,FIRSTVT(B)=b|B b,或,B,Cb,.,对于非终结符,B,，,其往下推导所可能出现的首个算符,(,终结符,),LASTVT(B)=a|B a,或,B .,aC,对于非终结符,B,，,其往下推导所可能出现的最后一个算符,(,终结符,),1),由定义构造,OPG,的优先关系,编译原理,Compiler Principles,如何计算算符优先关系,1)=,关系,直接看产生式的右部，若出现了,A,ab,或,A,aBb,则,a=b,2),关系,求出每个非终结符,B,的,FIRSTVT(B),若,A,aB,则,b,FIRSTVT(B),a,关系,求出每个非终结符,B,的,LASTVT(B),若,ABb,则,a,LASTVT(B),ab,编译原理,Compiler Principles,文法,GE,：,(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FP,F|P(6)P,(E)(7)Pi,FIRSTVT(E)=,#,FIRSTVT(E)=,+,*,(,i,FIRSTVT(T)=,*,(,i,FIRSTVT(F)=,(,i,FIRSTVT(P)=,(,i,LASTVT(E)=,#,LASTVT(E)=,+,*,),i,LASTVT(T)=,*,),i,LASTVT(F)=,),i,LASTVT(P)=,),i,1)=,关系由产生式,(0),和,(6),得,#=#,，（,=,）,2,）,关系找形如,A,aB,的产生式,#E,：,则,#FIRSTVT(E)+T:,则,+FIRSTVT(T)*F:,则*,FIRSTVT(F),F:,则,FIRSTVT(F)(E:,则,(,关系找形如：,ABb,的产生式,E#,则,LASTVT(E)#E+,则,LASTVT(E)+T*,则,LASTVT(T)*P,则,LASTVT(P),E),则,LASTVT(E),编译原理,Compiler Principles,(3),算符优先分析算法,归约过程中，,只考虑终结符,之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用,算符优先分析法的规约过程与规范归约是不同的,，,P172.,例子在下一页。,为,解决在算符优先分析过程中如何寻找句柄的问题,，,引入,最左素短语,的概念,3.,算符优先文法,(OPG),之,优先分析算法,编译原理,Compiler Principles,算符文法的任一句型有如下形式：,#N,1,a,1,N,2,a,2,.N,n,a,n,N,n+1,#,若,N,i,a,i,.N,j,a,j,N,j+1,为句柄，则有,a,i-1,a,i+1,对于算符优先文法，如果,aNb,(,或,ab,),出现在句型,r,中,若,ab,，,则在,r,中必含有,a,而不含,b,的短语存在,若,a=b,，,则在,r,中含有,a,的短语必含有,b,，反,之亦然,1,）算符优先分析句型的性质,编译原理,Compiler Principles,对输入串,i+i#,的规范归约的过程,步骤,符号栈,输入符号串,句柄,1,）,#i+i#,2,）,#i +i#i,3,）,#,F,+i#F,4,）,#T +i#T,5,）,#E +i#,6,）,#E+i#,7,）,#E+i i#i,8,）,#E+F#F,9,）,#E+T#E+T,10,）,#E#,对输入串,i+i,的,规范归约过程,文法,GE,：,(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FP,F|P(6)P,(E)(7)Pi,编译原理,Compiler Principles,对输入串,i+i*i,的算符优先分析过程,算符优先关系表,对输入串,i+i#,的算符优先归约过程,步骤,符号栈,输入符号串,移进或归约,1,）,#i+i#,移进,2,）,#i +i#,归约,3,）,#F +i#,移进,4,）,#F+i#,移进,5,）,#F+i#,归约,6,）,#F+F#,归约,7,）,#F#,接受,文法,GE,：,EE+E|E-E|E*E|E/E|E,E|(E)|i,编译原理,Compiler Principles,定义,cfg,G,的句型的素短语是一个短语，它,至少包含一个终结符,，且除自身外,不再包含其他素短语,。处于句型最左边的素短语为,最左素短语,2,）最左素短语,编译原理,Compiler Principles,文法,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*Fi,E,E,T,+,+,E,T,F,*,F,T,T,i,最左素短语为：,T*F,句型,#N+N*N+i#,的,归约过程,N,N,+,+,N,N,i,*,N,N,N,又如,P173,的图,6.9,以及表,6.4,编译原理,Compiler Principles,句柄和素短语的区别：,GE:E,E+TT E E+E E*E(E)id,T T*FF,F(E)id,E,E,+,T,*,F,T,F,id,id,T,F,id,E,E,+,E,*,E,E,id,id,id,编译原理,Compiler Principles,算法描述,P174,流程图,P175,例子：,P176,及表,6.5,算符优先分析算法描述,编译原理,Compiler Principles,优先函数,优先函数比优先矩阵节省空间,文法中有,n,个文法符号时，优先矩阵中有,(n+1),2,个元素。如：假设某文法中有,99,个终结符，其算符优先关系矩阵则有,10000,个元素，每个元素至少用,2,个二进制位来表示，也需要,20000,位，即,2500,个字节。,在实际应用中，往往用优先函数来代替优先矩阵来表示优先关系。具有,n,个终结符的算符文法（或具有,n,个文法符号的简单优先文法），只需,2(n+1),个单元存放优先函数。,优先函数的构造,用关系图构造优先函数,用迭代法构造,编译原理,Compiler Principles,优先函数的定义,为了节约存储空间和便于执行比较运算,，,定义两个优先函数,f,和,g,，,它们是从终结符号映射到整数的函数。对于文法符号,R,和,S,，,定义择,f,和,g,使之满足：,1,当,R,S,时,f(R),S,时,f(R),g(S),。,于是，,R,和,S,之间的优先关系，可以由比较,f(R),与,g(S),的大小来决定。,f:,入栈优先函数；,g:,比较优先函数。,损失,:,错误检测能力降低，例如：,id,id,不存在,f(id)g(id),可比较。,编译原理,Compiler Principles,优先函数 例子,简单表达式文法的算符优先关系矩阵：,线性化后，优先函数为：,在进行语法分析时，每当需要查询符号对,(,S,i,S,j,),之间的优先关系，比较,f(S,i,),和,g(S,j,）,的大小即可。,编译原理,Compiler Principles,关于优先函数的,3,个重要事实,(1),不是所有的优先矩阵都能线性化,。,a,b,a,=,.,b,=,=,f(a)=g(a),f(a)g(b),f(b)=g(a)f(b)=g(b),于是有：,f(a)=g(b),编译原理,Compiler Principles,关于优先函数的,3,个重要事实,(2),(2),对于给定的优先矩阵，若优先函数存在，则优先函数不唯一，即存在无穷多个,f,和,g,满足条件。,+,-,*,/,(,),id,$,f,3,3,5,5,5,1,7,7,1,g,2,2,4,4,6,6,1,6,1,等价于,编译原理,Compiler Principles,关于优先函数的,3,个重要事实,(3),(3),优先矩阵线性化后，每一对符号之间，都能够进行比较。对于,原先不存在优先关系的符号对,，因为也能比较，所以，在分析过程中，当输入串,存在语法错误时，可能被掩盖（至少是推迟发现）,。,编译原理,Compiler Principles,优先函数构造的,两种方法,Bell,法,1.,有向图法,(Bell,法,),若优先文法中的所有符号（包括,#),为,n,个，,A,1,A,2,A,n,，,则：,作一个具有,2n,个结点的有向图。通常的，分为上下两排，各,n,个结点，上面一排结点的标记为,f,Ai,，,上排结点标记为,g,Ai,。,若,A,i,.,A,j,则从,f,Ai,到,g,Ai,画,一条箭弧。,若,A,i,b,=,=,编译原理,Compiler Principles,优先函数构造,Bell,法 举例,3,课本例,6.19 p179,图,6.11,当一个优先文法的优先关系矩阵的阶数比较高时，,bell,法线性化过程很难手工实现。可以考虑用布尔矩阵来构造优先函数。下面介绍一个容易在计算机上实现的算法。,编译原理,Compiler Principles,Bell,法 布尔矩阵实现优先函数的构造,算法步骤：,作关系,.,和,=,的布尔矩阵,FE,作关系,.,和,=,的布尔矩阵的转置矩阵,LET,根据上述含有,2n,个结点的有向图的作法可知，所构造的有向图，可用如下的,2n,阶矩阵来表示：,其中，,I,为,n,阶单位矩阵。,求,B,的正闭包,B,+,。,f(S,i,)=B,+,中，第,i,行中值为,1,的元素的个数,g(S,j,)=B,+,中，第,n+j,行中值为,1,的元素的个数,B=,I,FE,LET,I,编译原理,Compiler Principles,用布尔矩阵构造优先函数 举例,(1),假设优先文法的优先矩阵为：,(1)FE,矩阵为：,=,id,+,*,$,id,0,1,1,1,+,0,1,0,1,*,0,1,1,1,$,0,0,0,1,(2)LET,矩阵为：,id,+,*,$,id,0,1,1,1,+,0,0,0,1,*,0,1,0,1,$,0,0,0,1,编译原理,Compiler Principles,用布尔矩阵构造优先函数 举例,(2),(3)B,矩阵为：,1,0,0,0,0,1,1,1,0,1,0,0,0,1,0,1,0,0,1,0,0,1,1,1,0,0,0,1,0,0,0,1,0,1,1,1,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,编译原理,Compiler Principles,用布尔矩阵构造优先函数 举例,(3),(3)B,2,矩阵为：,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,0,0,0,1,0,0,0,1,0,1,1,1,1,1,1,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,0,0,1,0,0,0,1,B,3,=B,2,，,所以，,B,+,=B,1,+B,2,=B,2,编译原理,Compiler Principles,用布尔矩阵构造优先函数 举例,(4),(4),优先函数为：,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,0,0,0,1,0,0,0,1,0,1,1,1,1,1,1,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,0,0,1,0,0,0,1,id,+,*,$,f,6,4,6,2,g,7,3,5,2,(5),对照优先矩阵检验,编译原理,Compiler Principles,优先函数构造的,两种方法,Floyd,法,又称为逐次加,1,法。,假设,x,、,y,为优先文法的符号,(,算符文法为终结符,),，有,:,(1),对于每一个,x,，令,f(x)=g(x)=1,(2),对于,x=g(y),，则令,g(y)=f(x)+1,(3),对于,x.y,，若,f(x)2n,，,则不会收敛，优先函数不存在。,编译原理,Compiler Principles,优先函数构造,Floyd,法 举例,1(1),优先矩阵为：,=,(1),设置初值：,id,+,*,$,f,1,1,1,1,g,1,1,1,1,(2),根据（,2,）,：,id,+,*,$,f,1,1,1,1,g,2,2,2,1,编译原理,Compiler Principles,优先函数构造,Floyd,法 举例,1(2),=,(3),根据（,3,）,：,(4),根据（,2,）,：,id,+,*,$,f,1,1,1,1,g,2,2,2,1,id,+,*,$,f,3,3,3,1,g,2,2,2,1,id,+,*,$,f,3,3,3,1,g,4,2,4,1,编译原理,Compiler Principles,优先函数构造,Floyd,法 举例,1(3),=,(5),根据（,3,）,：,(6),根据（,2,）,：,id,+,*,$,f,5,3,5,1,g,4,2,4,1,id,+,*,$,f,3,3,3,1,g,4,2,4,1,id,+,*,$,f,5,3,5,1,g,6,2,4,1,编译原理,Compiler Principles,优先函数构造,Floyd,法 举例,1(4),(7),过程已经收敛,与根据,Bell,法求出的优先函数比较：,id,+,*,$,f,5,3