编译原理自下而上语法分析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理 长春工业大学计算机科学与工程学院,自下而上语法分析,掌握自底相上分析的基本思想，基本概念,掌握算符优先关系的判定，求FIRSTVT集,LASTVT集,构造算符优先关系表，能运用算符优先分析方法进行表达式分析,掌握最左素短语、句柄的定义与判定,理解规范规约与算符优先归约的区别,LR(0)和SLR文法的理解,自下而上的语法分析,实现思想,从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功，称为,“移进-归约”方法,。,从语法树的角度看：从语法树的,树叶,开始，逐步向上归约,构造分析树,，直到形成根结。是推导的逆过程,。,核心,寻找可归约串(这是关键)进行规约。,用不同的方法寻找,可归约串,，就可获得不同的分析方法。,最左推导(Left-most Derive),每次推导都替换当前句型的最左边的非终结符。,与最右归约对应,最右推导(Right-most Derive),每次推导都替换当前句型的最右边的非终结符。,与最左归约(规范归约)对应，得规范句型,例：设有文法GS：(1)S,aAcBe (2)A b (3)A Ab (4)B d 使用最右推导：,因为S=aAcBe=aAcde=aAbcde=abbcde，,所以 abbcde是文法G的句子。,步骤,动作,(1)S,aAcBe(2)A b(3)A Ab(4)B d,最左归约过程是最右推导的逆过程，对输入串,abbcde,的归约过程如下：,该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。,a,b,a,A,a,b,A,a,A,a,c,A,a,d,c,A,a,B,c,A,a,e,B,c,A,a,S,1,移进a,2,移进,b,3,归约,2,4,移进b,5,归约3,6,移进,c,7,移进d,8,归约4,9,移进e,10,归约1,语法分析树的生成演示,a b b c d e,A,A,B,S,Ab,AAb,Bd,SaAcBe,(1)S,aAcBe(2)A b(3)A Ab(4)B d,这种分析过程具有如下特点：,从输入串的开始依次读入单词(移进栈中)。,一旦发现,可归约串,(某个产生式的右端)就立即归约。,归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。,若最终能归约成文法的开始符号，则分析成功。,关键是如何判断可归约串？,问题的提出：,在构造语法树的过程中，何时归约？,当可归约串出现在栈顶时就进行归约。,如何知道在栈顶符号串中已经形成可归约串？,如何进行归约？,通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。,规范归约：使用句柄来定义可归约串。,算符优先：使用最左素短语来定义可归约串,规范归约概念,有文法G，开始符号为S,如果有S=xy,则xy是文法G的,句型,，x,y是任意的符号串,如果有S=xAy,且有A=,则是句型xy相对于非终结符A的,短语,如果有S=xAy,且有A-,则是句型xy相对于A-的,直接短语,位于,一个,句型最左边的直接短语称为,句柄,。,*,*,+,*,注:每次归约的部分必须是称之为,句柄,的字符串,(,最右推导,)。,关键的问题是,如何识别句柄,例子,下面的例子说明作为短语的两个条件缺一不可。,例考虑表达式文法：,E,T|E+T,T,F|T*F,F,i|(E),对于句型i*i+i 推导,E,E+T,E+,F,E+,i,T+i,T*F+T,T*i+i,F*i+i,i*i+i,尽管有E,+,i+i 但是,i+i 并不是该句型的一个短语，因为不存在从E(文法开始符）到i*E的推导。,句型的短语和句柄举例,文法：S(T)|TS|T,S|a,短语：,句型(a),S)S,=,*,(T,S)T,=,+,(a),句型(T,S),S)S,=,*,(T),S)T,=,+,T,S,句型(a,(T),(T,S)直接短语以及句柄：,S,=,*,(T,(T),(T,S)T,=,a,S,=,*,(a,S,(T,S)S,=,(T),S,=,*,(a,(T),(T)T,=,T,S,短语与语法树的关系,短语：语法树子树的叶子结点组成的符号串。,直接短语：语法树简单子树（只有父子两代）的叶子结点组成的符号串。,句柄：语法树最左边简单子树的叶子结点组成的符号串。,短语与语法树关系的例子,句型(a,(T),(T,S)的语法树：,S,(,),T,T,S,T,S,(,T,),a,(,T,),T,S,用句柄对句子,abbcde,进行归约,用句柄对句子进行归约的过程与用移进-归约过程是一致的，使用归约的产生式及其顺序是一致的。,句型,归约规则,abbcde,(1)S,aAcBe(2)A b(3)A Ab(4)B d,(2)A,b,(3)A Ab,aAbcde,aAcde,(4)B d,(1)S,aAcBe,aAcBe,S,规范归约的定义,假定,是文法G的一个句子，如果序列：,n,n-1,0,(=,S,),满足如下条件，则序列,n,n-1,0,是一个规范归约:,(1),n,=,是给定的句子,(2),0,=,S,是文法的开始符号,(3)对任何,i,0E+T|T,T-T*F|F,F-(E)|i,对输入串,i1+i2*i3,的规范归约过程：,动作 栈 输入缓冲区,1)准备#i,1,+i,2,*i,3,#,2)移进#i,1,+i,2,*i,3,#,3)归约 Fi#F +i,2,*i,3,#,4)归约 TF#T +i,2,*i,3,#,5)归约 ET#E +i,2,*i,3,#,6)移进#E+i,2,*i,3,#,7)移进#E+i,2,*i,3,#,8)归约 Fi#E+F *i,3,#,9)归约 TF#E+T *i,3,#,10)移进#E+T*i,3,#,11)移进#E+T*i,3,#,12)归约 Fi#E+T*F#,13)归约 TT*F#E+T#,14)归约 EE+T#E#,15)接受,所得的结果是：用产生式序列表示语法分析树,E-E+T|T,T-T*F|F,F-(E)|i,i,1,+i,2,*i,3,F,T,E,F,T,F,T,E,算符优先分析,算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归约串。,将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定,可归约串,。,显然，在一个符号串中，任意两个相邻终结符号a和b之间，只可能存在以下四种优先关系：,(1)a,b优先性相同，记作a b。(2)a优先性高于b，记作a,b。(3)a优先性低于b，记作a,b。(4)a与b不可能相邻，即此符号串不是句型(出错)。,如果以上四种关系中的任意两种都不会同时成立，则可以根据终结符号之间的归约关系进行语法分析。,算符文法,:,一个上下无关文法G,如果没有P-,且没有P-.QR.(P,Q,R属于非终结符),则G是一个算符文法。,算符优先关系,的定义：,a b,G,中有,P-.ab.,或,P-.aQb.(,在同一产生式中,),a b,G,中有,P-.aR.,的产生式,且,R=b.,或,R=Qb.,a b,G,中有,P-.Rb.,的产生式,且,R=.a,或,R=.aQ,算符优先文法（,OPG,）的定义,+,+,+,+,例：,EE+E|E*E|(E)|i,证明不是OPG文法。,因为：,EE+E，E,E*E,则有+*,又因为：,EE*E,E,E+E,则有+,*,所以不是算符优先文法。,算符优先文法,算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有 ,中的一种成立,则G为一算符优先文法。,算符优先关系表的构造,FIRSTVT集,定义：对每个非终结符P,FIRSTVT(P)=a|P=a.或P=Qa.,a为终结符,P，Q为非终结符,+,+,由优先性低于的定义和,FIRSTVT,集合的定义可以得出：,若存在某个产生式：aP，对所有：,b,FIRSTVT,(P)，都有：a b。,按照下面两条规则来构造FIRSTVT集：,若有产生式P-a.或P-Qa.,则aFIRSTVT(P),若有产生式P-R.,则FIRSTVT(R)包含在FIRSTVT(P)中,LASTVT集,定义：对每个非终结符P,LASTVT(P)=a|P=.a或P=.aQ,a为终结符,P，Q为非终结符,+,+,由优先性高于的定义和,LASTVT,集合的定义可以得出：,若存在某个产生式：Pb，对所有：,a,LASTVT,(P)，都有：a b。,按照下面两条规则来构造LASTVT集：,若有产生式P-.a或P-.aQ,则aLASTVT(P),若有产生式P-.R,则LASTVT(R)包含在LASTVT(P)中,构造优先关系表,如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。,若产生式右部有.aP.的形式,则对于每个bFIRSTVT(P)都有a b,若产生式右部有.Pb的形式,则对于每个aLASTVT(P)集,都有a b,若产生是形如：Aab 或 AaBb形式，则有a b,构造优先关系表的算法如下：,For 每条形如P,X,1,X,2,X,n,的,产生式 do,for i=1 to n-1 do,if X,i,和X,i+1,都是终结符 then,X,i,=X,i+1,if i=n-2 且 x,i,和X,i+2,都是终结符,X,i+1,为非终结符 then X,i,=X,i+2,if X,i,为终结符,X,i+1,为非终结符 then for firstVT中的每个元素a do,X,i,X,i+1,算符优先分析算法,通过比较终结符间的优先关系来实现,根据优先分析的原理，语法分析程序的任务是：不断移进输入符号，识别可归约串并进行归约。,分析的方法：根据优先性“高于”来识别可归约串的头，根据优先性“低于”来识别可归约串的尾。各种优先关系已经存于优先关系表中。,不能识别只由一个非终结符组成的句柄。不能保证每次对句柄进行归约,在算符优先分析过程中,每次归约的符号串,是当前句型的最左素短语。,素短语：,至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。,最左素短语(leftmost prime phrase)：,是指位于句型最左边的那个素短语。,例：下述文法的一个句型：,T*F+i,其短语、素短语、最左素短语分别是？,E,T|E+T,TF|T*F,F,i|(E),E,E +T,F,i,T,T *F,短语有：i,T*F,T*F+i,素短语有：i,T*F,最左素短语是：T*F,例:文法G,E-E+T|T T-T*F|F F-(E)|i,句型T+T*F+i,的语法树如图：,E,E,T,+,E,+,T,F,T,T,*,F,P,i,根据语法树可知：,句型#T+T*F+i#的短语有：,T 相对非终结符E的短语,T*F 相对非终结符T的短语,T+T*F 相对非终结符E的短语,i 相对非终结符P、F、T的短语,T+T*F+i 相对非终结符E的短语,根据素短语的定义可知：,i和T*F为素短语。,其中：T+T*F (含T*F素短语)、T+T*F+i(含T*F素短语)和 T(不含终结符)也不是素短语,T*F为最左素短语。,一个算符文法G的某个句型的最左素短语可描述：,设句型的一般形式为(N,i,V,N,a,i,V,T,#N,1,a,1,N,2,a,2,N,n,a,n,N,n+1,#,它的,最左素短语,是满足下列条件的最左子串：,N,i,a,i,N,i+1,a,i+1,N,j,a,j,N,j+1,其中：a,i-1,a,i,a,i,a,i+1,.,a,j-1,a,j,，,a,j,a,j+1,该定理说明了最左素短语与周围符号之间的关系,算符优先分析过程：,(根据最左素短语的定义),句型的一般形式:#N,1,a,1,N,2,a,2,.N,n,a,n,N,n+