编译原理第4章1

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,四,章 语法分析,本,章讨论程序语言的语法分析方法，以及,语法分析程序的设计原理和实现技术,。,第,四,章 语法分析,语法分析程序的功能和语法分析方法,自顶向下语法分析法,自底向上算符优先分析法,LR,分析法,4.1,语法分析程序的功能,语法分析程序的功能,语法分析器,词法分析后的单词串,语法成分构成的语法树,或错误表,4.1,语法分析程序的功能,语法分析的方法,自顶向下语法分析法,(,自上而下语法分析法,),自底向上语法分析法,(,自下而上语法分析法,),4.1,语法分析程序的功能,1.,自上而下的分析法,从文法的,开始符号,出发，根据文法规则正向推导出给定句子的一种方法；或者说，从树根开始，往下构造语法树，直到建立每个叶的分析方法。,4.1,语法分析程序的功能,2.,自下而上的分析法,从给定的,输入串,开始，根据文法规则,逐步进行归约,，直至归约到文法开始符号的一种方法；或者说，从语法树的未端开始，步步向上归约，直至根结点的分析方法。,4.2,自上而下,语法,分析,法,非确定的自上而下分析法的基本思想是：,对任何输入串,W,试图,用一切可能的办法，从文法的开始符号出发，自上而下地为它建立一棵语法树。或者说，为输入串寻找一个最左推导。如果试探成功，则,W,为相应文法的一个句子，否则,W,就不是文法句子。,4.2.1,非确定的自上而下分析法的思想,也就是说，这种分析过程,本质上是一种,穷举试探过程,，是反复使用不同规则，谋求匹配输入串的过程。,试探发生回溯,。,4.2.1,非确定的自上而下分析法的思想,例 设有文法,GS,：,S,aAb,A de | d,输入串,W=,adb,S,a A b,d e,匹配失败、这时应回溯,选择,A,的其它可能的规则重新匹配。,4.2.1,非确定的自上而下分析法的思想,d,匹配成功,S,aAb,A de | d,S,a A b,输入串,W=,adb,4.2.1,非确定的自上而下分析法的思想,上述自上而下为输入串,W,建立语法树的过程，实际也是设法为输入串建立一个最左推导序列：,S,aAb,a,db,。,由于对输入串从左向右进行扫描，使用,最左推导,，才能保证按从,左到右扫描顺序匹配输入串,。,4.2.1,非确定的自上而下分析法的思想,根据以上分析，不难看出，非确定的自上而下分析法即是带回溯的自上而下分析法,实际上是一种穷举的试探方法，其分析效率极低，代价很高，在实用的编译程序中是不常用的。我们通常使用,确定的自上而下分析法进行语法分析,。,4.2.1,非确定的自上而下分析法的思想,但确定的自上而下分析法对语言的文法有一定的限制条件，那就是,要求描述语言的文法是无左递归的和无回溯的,。,4.2.2,文法,的左递归性和回,溯的消除,文法左递归的消除,当一个文法是左递归文法时，采用自上而下分析法会,使分析过程进入无穷循环之中,。,文法左递归是指文法中的某个非终结符,A,存在推导,A,A,+,4.2.2,文法,的左递归性和回,溯的消除,用非终结符,A,去匹配输入串时,使,当前句型的最左非终结符仍然为,A,。,也就是说，在,没有读进任何输入符号,的情况下，又,重新要求,A,去进行新的匹配,。,于是，造成无穷循环。,4.2.2,文法,的左递归性和回,溯的消除,对含直接左递归的规则进行等价变换，消除左递归,引进一个新的非终结符，把含左递归,的规则改写成右递归。,设关于非终结符,A,的直接左递归的规则为,4.2.2,文法,的左递归性和回,溯的消除,对,A,的规则可改写成如下右递归形式：,A,A, |,A,A,A, A,|,其中,、,是任意的符号串,不等于,不以,A,开头,4.2.2,文法,的左递归性和回,溯的消除,改写以后的形式和原来形式是等价的。也就是说，从,A,推出的符号串的集合是相同的。,4.2.2,文法,的左递归性和回,溯的消除,一般情况下，设文法中关于,A,的规则为,A, A,1,| A,2,|,| A,m,|,1,|,2,|,|,n,其中每个,都不等于,，,而每个,都不以,A,开头，消除直接左递归后改写为,:,A,1,A,|,2,A,|,|,m,A,|,A,1,A,|,2,A,|,|,n,A,4.2.2,文法,的左递归性和回,溯的消除,例,1,设有文法,GE,：,E, E+T | ET | T,T T,*,F | T/F | F,F (E) | id,消去非终结符,E, T,的直接左递归后，文法,GE,改写为：,F,(E) | id,E,TE,E, +TE,| TE,|,T FT,T,*,FT,| /FT,|,4.2.2,文法,的左递归性和回,溯的消除,例,2,设有文法,GA:,A, Ac |,Aad,|,bd,| e,消去直接左接左递归后文法,GA,改写为,A, ,cA, |,adA, |,A,bdA,|,eA,4.2.2,文法,的左递归性和回,溯的消除,(2),采用,扩充,BNF,表示法改写含直接左,递归的规则：,在扩充的,BNF,表示中,使用花括号,表示符号串,的,出现可,0,次或多次，即表示,*,4.2.2,文法,的左递归性和回,溯的消除,例如 定义标识符的文法,(b),使用方括号,表示,的出现可有可,无，它用来表示可供选择的符号串。,l,l,d,使用扩充,BNF,表示可改写成, l l | d ,4.2.2,文法,的左递归性和回,溯的消除,例如，定义,C,语言中条件语句的文法是,if ,if ; else ,用扩充,BNF,表示可改写成如下形式,if ;else,4.2.2,文法,的左递归性和回,溯的消除,(c),使用圆括号可在规则中提因子。,例如,A, x,1,| x,2,|,| x,m,可写为,A x (,1,|,2,|,|,m,),4.2.2,文法,的左递归性和回,溯的消除,例,3,对下列文法用扩充,BNF,表示法对其进,行改写。,E, E+T,|,ET,|,T,T T,*,F,|,T/F,|,F,F (E),|,id,分析 规则,EE+T | E,T | T,表示了,E,所生成的符号串是,T,开头的后面跟,0,个或多个,+T,或,T,组成,对,T,规则类似。,4.2.2,文法,的左递归性和回,溯的消除,文法,GE,可以改写为：,E,T +T | T ,TF,*,F | / F ,F(E) | id,4.2.2,文法,的左递归性和回,溯的消除,例,4,对下列文法用扩充,BNF,表示法对其,进行改写。,A, Ac |,Aad,|,bd,| e,分析,规则 表示了,A,所生成的符号串是,bd,或,e,开头的后面跟,0,个或多个,c,或,ad,组成,。,A, Ac |,Aad,|,bd,| e,4.2.2,文法,的左递归性和回,溯的消除,所以原文法可以改写成如下形式,A, (,bd,| e) c | ad ,4.2.2,文法,的左递归性和回,溯的消除,2.,回溯的消除,在自上而下分析过程中，由于回溯，需要推翻前面的分析，包括已做的一大堆语义工作，重新去进行试探，这样大大降低了语法分析器的工作效率，因此，需要消除回溯。,4.2.2,文法,的左递归性和回,溯的消除,我们分析发现引起回溯的原因是,:,在文法中,当某个非终结符,A,有多个候选式时,:,遇到用,A,去匹配当前输入符号,a,时，无法确定选用唯一的一个候选式，而只能逐一进行试探，从而引起回溯,。具体表现在下面两种情况。,A ,1,|,2,|,3,|,|,n,4.2.2,文法,的左递归性和回,溯的消除,第一种情况,:,文法中相同左部的规则，其,右部左端,第一个符号相同而引起回溯。,S,aAb,A de | d,例 设有文法,GS,：,4.2.2,文法,的左递归性和回,溯的消除,第二种情况,:,文法中相同左部的规则，其中,某一右部能推出,串,，例如,文法,G,：,A,Bx,B x |,其非终结符,B,有两个右部，第二个右部能推导出,串且两个右部左端第一个符号不相同，但在分析符号串,W,x,时出现回溯。,4.2.2,文法,的左递归性和回,溯的消除,试探分析过程如下图所示：,A,B x,x,A,B x,A,Bx,B x |,Wx,匹配失败,匹配成功,4.2.2,文法,的左递归性和回,溯的消除,综上所述，在自上而下分析过程中，为了避免回溯， 对描述语言的文法有一定的要求,:,对文法的某个非终结符,A,当它有多个侯选式时,:,若用,A,匹配输入串时,能根据当前读到的输入符号,a,唯一地选择一条规则去匹备输入串,。或者说，能唯一地选择一条规则进行推导。,4.2.2,文法,的左递归性和回,溯的消除,A ,1,|,2,|,3,|,|,n,这也就是说，在自上而下分析过程中，为了避免回溯，,要求描述语言的文法是,LL(1),文法,。,4.2.2,文法,的左递归性和回,溯的消除,LL(1),文法的判断条件,为了建立,LL(1),文法的判断条件，需引进三个相关的集合：,FIRST,集,FOLLOW,集,SELECT,集,LL(1),文法的判断条件,设,是文法,G,的任一符号串，定义文,法符号串,的首符号集合。,FIRST(,) = a |,a,且,aV,T,*,则规定,FIRST(,),若,*,LL(1),文法的判断条件,例 设有文法,GS:,S ,Ap,|,Bq,A ,cA,| a,B dB | b,FIRST(Ap,) =, c, a ,AP,cAp,AP,ap,FIRST(Bq,) =,Bq,bq, b, d ,Bq,dBq,LL(1),文法的判断条件,(2),设文法,G,的开始符号为,S,，,对于,G,的任,何非终结符,A,，,定义非终结符,A,的后,继符号的集合,FOLLOW(A) = a | S,Aa,且,a,V,T,*,若有,S,A ,*,则规定,$,FOLLOW(A),。,LL(1),文法的判断条件,换句话说,FOLLOW(A),是,G,的所有句型中紧接在,A,之后出现的终结符或,$,。,这里我们用,$,作为输入串的结束符，例如，,$,输入串,$,。,也可以用,#,作为输入串的结束符，例如，,#,输入串,#,。,LL(1),文法的判断条件,例 设有文法,GA:,FOLLOW(B) =,A,aB,A,aB,abBA,abBd,A,aB,abBA,abBaB, $, d, a ,AaB,| d,BbBA,|,*,/,若,LL(1),文法的判断条件,(3),定义规则的选择集合,SELECT,，,设,A,是文法,G,的任一条规则，其中,AV,N,(V,N,V,T,),*,，,定义,SELECT(A,) =,FIRST(,),FIRST(,),FOLLOW (A),*,若,LL(1),文法的判断条件,例 设有文法,GA:,AaB,| d,BbBA,|,SELECT(AaB,) =,FIRST(aB,) =, a ,SELECT(Ad ) =,FIRST(d) =, d ,LL(1),文法的判断条件, b ,SELECT(BbBA,) =,FIRST(bBA,) =,=,$, d, a ,FOLLOW(B),SELECT(B,) =,FIRST(,),FOLLOW(B) =, $, d, a ,AaB,| d,BbBA,|,LL(1),文法的判断条件,LL(1),文法定义,一个上下文无关文法,G,是,LL(1),文法,当且仅当对,G,中,每个非终结符,A,的任何两个不同的规则,A,| ,，,满足,SELECT(A,)SELECT(A,) =,其中,、,中至多只有一个能推出,串。,LL(1),文法的判断条件,LL(1),中的第一个,L,表明自上而下的分析是从,左到右扫描输入串,，第二个,L,表明分析过程中,使用最左推导,，,1,表示分析时每一步只需,向前看一个符号,即可决定所选用的规则，而且这种选择是准确无误的。,LL(1),文法的判断条件,例,1,设有文法,GS:,S ,aAb,A de | d,SELECT(Ade)= FIRST(de)=d,SELECT(Ad)= FIRST(d)=d,SELECT(Ade),SELECT(Ad),由,LL(1),文法定义可知，该文法不是,LL(1),文法,，因此对输入串不能进行确,定的自上而下分析。,LL(1),文法的判断条件,例,2,设有文法,GA,A,aB,| d,B,bBA,|,则,SELECT(A,aB,)=,FIRST(aB,)=a,SELECT(A,d)=FIRST(d)=d,SELECT(B,bBA,)=,FIRST(bBA,)=b,SELECT(B,)=,FIRST(,) ,FOLLOW(B),=a, d, $,LL(1),文法的判断条件,所以,SELECT(A,aB,),SELECT(Ad)=,SELECT(BbBA,),SELECT(B,)=,由定义可知，,GA,是,LL(1),文法,，对任何输入串,W,可进行确定的分析。,LL(1),文法的判断条件,例,3,设有文法,GS:,S,aAB,A,bB,|,dA,|,B a | e,SELECT(A,bB,)=,FIRST(bB,)= b,SELECT(A,dA,)=,FIRST(dA,)= d,SELECT(A,)=,FIRST()FOLLOW(A,),= a, e,试判断该文法是否,LL(1),文法。,LL(1),文法的判断条件,SELECT(B,a)=FIRST(a)= a,SELECT(B,e)=FIRST(e)= e,SELECT(A,bB)SELECT(AdA,)=,SELECT(AbB)SELECT(A,)=,SELECT(AdA)SELECT(A,)=,SELECT(Ba)SELECT(B,e,)=,S,aAB,A,bB,|,dA,|,B a | e,该文法为,LL(1),文法,LL(1),文法的判断条件,例,4,设有文法,GS:,S, AB |,bC,A b |,B,aD,|,C AD |,D ,aS,| c,试判断该文法是否,LL(1),文法,分析 对文法某个非终结符,当有多个候选式时,求规则的,SELECT,集合,LL(1),文法的判断条件,SELECT(S,AB),=FIRST(AB)FOLLOW(S),= a, b, $ ,SELECT(S,bC,)=,FIRST(bC,)=,b,SELECT(S,AB),SELECT(S ,bC,),S, AB |,bC,A b |,B,aD,|,C AD |,D ,aS,| c,S,AB,*,FIRST(AB)=FIRST(A)FIRST(B)=a, b,FOLLOW(S)=$,该文法不为,LL(1),文法,LL(1),文法,的判断条件,由定义可知,文法,GS,是,LL(1),文法,，对任何的输入串可进行确定的自上而下分析。,LL(1),文法的判断条件,综合上面的讨论，我们可知对,LL(1),文法，若当前非终结符,A,面临输入符号,a,时，可根据,a,属于哪一个,SELECT,集，唯一地选择一条相应规则去准确地匹配输入符号,a,。,也就是说，,当描述语言的文法是,LL(1),文法时，可对其进行确定的自上而下的分析,。,4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,某些非,LL(1),文法到,LL(1),文法的改写,前面已经指出，构造确定的自上而下分析程序要求对给定语言的文法必须是,LL(1),文法，但是，并不是每个语言都有,LL(1),文法。,由,LL(1),文法定义可知,若文法中含有左递归或含有公共左因子，则该文法不是,LL(1),文法，因此，对某些非,LL(1),文法而言,可通过,消除左递归和反复提取公共左因子对文法进行等价变换，,可能将其改造为,LL(1),文法。,消除文法左递归的方法见,4.2.2,。,4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,提取公共左因子,当文法中含有形如,A,1,|,2,|,|,n,的规则,不满足,LL(1),文法条件。,则其右部的,FIRST,集交不空，即,SELECT(A,i,),SELECT(A,j,),4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,提取公共左因子将文法改写成,:,A,A,若在,1,2,3,中仍含有公共左因子，这时可再次提取,这样反复进行提取，直到引进新非终结符的有关规则再无公共左因子为止。,A,1,|,2,|,|,n,的规则,A,1,|,2,|,|,n,4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,例,1,设有文法,GS:,该文法是非,LL(1),文法，该文法有公共左因子，利用提取公共左因子的方法对其进行改写，我们得到,S,aAb,A de | d,4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,不难验证改写后的文法为,LL(1),文法。,因为,SELECT(A,e),SELECT(A,),=e, b= ,S,aAb,A ,dA,A e |,4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,例,2,设有文法,GS:,S, ad |,Ae,A,aS,|,bA,将,A,的两条规则代入非终结符,S,的规则中,A,aS,|,bA,S, ad |,aSe,|,bAe,4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,对,S,提取公共左因子得,S,bAe,|,aS,改写后的文法是,LL(1),文法。,S, d | Se,A,aS,|,bA,A,aS,|,bA,S, ad |,aSe,|,bAe,4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,应当指出的是并非一切非,LL(1),文法都能改写为,LL(1),文法。,例如，对于文法,S,Ae,|,Bd,A ,aAe,| b,B,aBd,| b,该文法不为,LL(1),文法,SELECT(S,Ae,),SELECT(SBd,),= a, b a, b ,4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,对,S,提取公共左因子后，得,对于,S,的两条规则,可先将非终结符,A,、,B,用相应规则右部进行替换，我们得到,S,aAee,| be |,aBdd,|,bd,A ,aAe,| b,B,aBd,| b,4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,显然，它仍不是一个,LL(1),文法，且不难看出无论将上述步骤重复多少次,都无法将它改写为,LL(1),文法。,S,aS, |,bS,S,Aee,|,Bdd,A,aAe,| b,S, e,| d,B,aBd,| b,4.2.3,某些非,LL(1),文法到,LL(1),文法的改写方法,