编译原理总结4_语法1

*,1,S.P,O.P,语义分析、生成中间代码,生成目标程序,代码优化,语法分析程序,词法分析程序,错,误,处,理,符,号,表,管,理,语法分析,2,任务：,根据文法规则，从源程序单词符号串中识别出,语法成分，并进行语法检查。,两大类分析方法：,自顶向下分析,自底向上分析,4.1,语法分析的任务,3,存在主要问题,:,回溯问题,左递归问题,主要方法：,递归下降分析法、,LL,分析法,自顶向下分析算法的基本思想为：,自底向上分析算法的基本思想为：,+,若,S,x,则,xL(GS),否则,xL(GS),GS,存在主要问题,:“,可归约串”的识别问题,主要方法：,算符优先分析法、,LR,分析法,4.1,语法分析的任务,+,若,x,S,则,xL(GS),否则,xL(GS),GS,4,自顶向下分析的一般过程,从,S,出发采用最左推导，试图逐步推出输入串,L(GS)?,S,作为语法树的根，试图自上而下地为,构造一棵语法树：,若叶结点从左向右排列恰好,，则表示,是文法的句子，,而这棵语法树就是句子,的语法结构；,若构造不出语法树，则,不是文法的句子。,4.2,自顶向下分析法概述,5,自上而下分析中的关键问题：,左递归,：当文法中出现左递归时，会使分析过程陷入无限循环。,回溯,：假定要被代换的非终结符号是,V,，且有,n,条规则：,VA,1,|A,2,|,|A,n,，那么如何确定,用哪个右部,A,i,去替代,V,呢？会造成回溯。,4.2,自顶向下分析法概述,回溯问题,左递归问题,6,1.,回溯问题,什么是回溯（,backtracking,）,?,分析工作要部分地或全部地退回去重做叫,回溯,造成回溯的条件：,文法中，对于某个非终结符号的,规则其右部有多个选择,，,并根据所面临的输入符号不能准确的确定所要选择时，就可,能出现回溯。,回溯带来的问题：,严重的,低效率,，只有在理论上的意义而无实际意义。,4.2,自顶向下分析法概述,7,消除回溯的途径：,改写文法,对具有多个右部的规则,反复,提取,左因子,例：对下述两个产生式，提取公共左因子改造文法。,if E then S,1,else S,2,if E then S,1,改造为：,if E then,S,1,U,Uelse,S,2,|,4.2,自顶向下分析法概述,8,A,1,|,2,|,n,如果,1,n,中还有几个首符号相同，可反复提取引入了许多非终结符和,产生式。,A,A,A,1,|,2,|,n,提取公共左因子,4.2,自顶向下分析法概述,9,某些文法不能在有限步骤内提取左公共因子。,【,例,】,文法,G:,S,Ap|Bq,A,aAp|d,B,aBq|e,S,aApp,|,aBqq,Sdp|eq,A,aAp|d,B,aBq|e,S,a(App|Bqq),S,aS,S,App|Bqq,S,dp|eq,A,aAp|d,B,aBq|e,S,aS,S,dp|eq,S,aA,ppp|aBqqq,S,dpp|eqq,A,aAp|d,B,aBq|e,可以看出产生式,A,、,B,继续替换，只能使文法的产生式愈来愈多无限增加下去，变成循环递归，不能得到提取左公共因子的预期结果。,不一定每个文法的公共左因子都能在有限的步骤,内替换成无公共左因子的文法。,一个文法提取了左公共因子后，只解决了相同左,部产生式右部的,FIRST,集不相交问题，当改写后的文,法不含空产生式，且无左递归时，则改写后的文法是,LL(1),文法。否则还需用,LL(1),文法的定义进行判断,才能确定是否为,LL(1),文法。,4.2,自顶向下分析法概述,10,2.,左递归问题,例：文法,GE,：,EE+T|T,TT*F|F,F(E)|i,给出,i*i+i,自顶向下的分析过程。,左递归文法会使自顶向下分析法陷入死循环,如果文法具有间接左递归，则也将发生上述问题，,只不过循环的圈子兜的更大。,要实行自顶向下分析，必须要消除文法的左递归,从左向右扫描源程序，同时实施最左推导。,4.2,自顶向下分析法概述,11,（,1,）消除直接左递归,方法一：使用,EBNF,表示来改写文法,例：文法,GE,：,EE+T|T,TT*F|F,F(E)|i,ET+T,TF*F,F(E)|i,A,|A,规则一,A,4.2,自顶向下分析法概述,12,例：文法,GE,：,EE+T|E-T|T,TT*F|T/F|F,F(E)|i,ET(+|)T,TF(*|/)F,F(E)|i,A,A,|A,规则二,A,A(,|,),4.2,自顶向下分析法概述,13,方法二：将左递归规则改为右递归规则,A,A,|,课堂练习,文法,GE,：,EE+T|E-T|T,TT*F|T/F|F,F(E)|i,E,TE,E,+TE,|,T,FT,T,*FT,|,F,(E)|i,消除左递归,A,A,A,A|,4.2,自顶向下分析法概述,14,间接左递归,直接左递归右递归,【,例,】,文法,G:A,aB,A,Bb,B,Ac,B,d,A,aB,A,Bb,B,aBc,B,Bbc,B,d,B,aBc,|,d,B,Bbc,B,(,aBc,|,d)B,B,bcB|,A,aB,A,Bb,B,(,aBc|d)B,B,bc B,|,4.2,自顶向下分析法概述,(2),消除间接左递归,15,对文法中一切左递归的消除要求文法中不含回,路，即无,A,A,的推导。,满足该文法的充分条件是：文法中不包含形如,A,A,的有害规则和,A,的产生式。,+,算法步骤如下：,4.2,自顶向下分析法概述,(2),消除间接左递归,16,（,2,）从,A,1,开始消除左部为,A,1,的产生式的直接左递归，然后把左部,为,A,1,的所有规则的右部逐个替换左部为,A,2,右部以,A,1,开始的产,生式中的,A,1,，并消除左部为,A,2,的产生式中的直接左递归。继,而以同样方式把,A,1,、,A,2,的右部代入左部为,A,3,右部以,A,1,或,A,2,开始的产生式中，消除左部为,A,3,的产生式之直接左递归，直,到把左部为,A,1,，,A,2,，,，,A,n-1,的右部代入左部为,A,n,的产生式中,，从,A,n,中消除直接左递归。,（,1,）把文法的所有非终结符按某一顺序排序,如,:A,1,|A,2,|,|A,n,（,3,）去掉无用产生式。,消除递归的算法,4.2,自顶向下分析法概述,17,1,）把,G,的非终结符整理成某种顺序,A,1,，,A,2,，,A,n,2,）,for i:=1 to n do,for j:=1 to i-1 do,把每个形如,A,i,=A,j,r,的规则替换成,A,i,=(,1,|,2,|,k,)r,其中,A,j,=,1,|,2,|,k,是当前,全部,A,j,的规则,消除,Ai,规则中的直接左递归,3,）去掉无用的产生式,4.2,自顶向下分析法概述,