new第四章语法分析1(最后版本).ppt

编译原理CompilerPrinciples,蒋凌云jianglingyun南京邮电大学.计算机学院,第四章语法分析,教材：编译技术原理及其实现方法王汝传编著,第四章语法分析,4.1引言一、语法分析任务二、语法分析方法4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法二、递归子程序分析法（递归下降分析法）三、LL（1）分析法4.3自底向上语法分析一、简单优先文法分析法二、算符优先分析法三、优先函数及其构造四、LR分析法五、二义性文法的应用4.4语法分析程序的自动生成一、分析器的生成器YACC二、用YACC处理二义性文法,2,本章内容,第四章语法分析,4.1引言一、语法分析任务二、语法分析方法4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法二、递归子程序分析法（递归下降分析法）三、LL（1）分析法4.3自底向上语法分析一、简单优先文法分析法二、算符优先分析法三、优先函数及其构造四、LR分析法五、二义性文法的应用4.4语法分析程序的自动生成一、分析器的生成器YACC二、用YACC处理二义性文法,3,本章内容,4.1引言,本节内容,一、语法分析任务1.语法检查2.根据语法符号进行一定处理加工二、语法分析方法1.自顶向下语法分析方法2.自底向上语法分析方法,词法分析阶段，主要介绍了单词符号的结构、识别（用状态转换图），描述（通过正规式）以及有限自动机DFA和NFA。在一个编译程序对某个源程序完成了词法工作以后，就进入了语法分析阶段。由词法分析程序所产生的单词符号流，作为语法分析程序的输入串，按文法规则分析检查是否构成了合法的句子。首先来了解一下语法分析的任务。,5,4.1引言,一、语法分析任务,一、语法分析任务1.语法检查2.根据语法符号进行一定处理加工二、语法分析方法1.自顶向下语法分析方法2.自底向上语法分析方法,6,4.1引言,一、语法分析任务,7,1.语法检查根据语法规则对各种语法成分进行分析，确定它们的语法关系以检查语法上的正确和错误，并指出错误的性质和出错位置。如：ifBthenS1elseS2若写成ifBthenelseS2就错了（then后少一个S1）,4.1引言,一、语法分析任务,一、语法分析任务1.语法检查2.根据语法符号进行一定处理加工二、语法分析方法1.自顶向下语法分析方法2.自底向上语法分析方法,8,4.1引言,一、语法分析任务,9,2.根据语法符号进行一定语义处理加工如语法分析过程得到一个合法的句子时，往往同时进行必要的语义分析等如：当遇到处理表达式a+b*c时，若该表达式语法关系正确，就可以进行语义处理加工，可将该表达式变成中间语言，以便以后生成目标程序,4.1引言,一、语法分析任务,一、语法分析任务1.语法检查2.根据语法符号进行一定处理加工二、语法分析方法1.自顶向下语法分析方法2.自底向上语法分析方法,10,4.1引言,二、语法分析方法,语法分析方法很多，但能够产生计算机程序并能得到广泛应用的主要有两大类，按照生成语法树的顺序，分别称为自顶向下和自底向上分析方法。,11,4.1引言,二、语法分析方法,一、语法分析任务1.语法检查2.根据语法符号进行一定处理加工二、语法分析方法1.自顶向下语法分析方法2.自底向上语法分析方法,12,4.1引言,二、语法分析方法,13,1.自顶向下语法分析方法（1）带回溯分析方法（2）不带回溯分析方法（3）递归子程序法（4）LL（1）分析法,4.1引言,二、语法分析方法,一、语法分析任务1.语法检查2.根据语法符号进行一定处理加工二、语法分析方法1.自顶向下语法分析方法2.自底向上语法分析方法,14,4.1引言,二、语法分析方法,15,2.自底向上语法分析方法,（1）简单优先分析法（2）算符优先分析法（3）LR分析法（4）SLR分析法（5）LALR分析法,4.1引言,二、语法分析方法,第四章语法分析,4.1引言一、语法分析任务二、语法分析方法4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法二、递归子程序分析法（递归下降分析法）三、LL（1）分析法4.3自底向上语法分析一、简单优先文法分析法二、算符优先分析法三、优先函数及其构造四、LR分析法五、二义性文法的应用4.4语法分析程序的自动生成一、分析器的生成器YACC二、用YACC处理二义性文法,16,本章内容,第四章语法分析,4.1引言一、语法分析任务二、语法分析方法4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法二、递归子程序分析法（递归下降分析法）三、LL（1）分析法4.3自底向上语法分析一、简单优先文法分析法二、算符优先分析法三、优先函数及其构造四、LR分析法五、二义性文法的应用4.4语法分析程序的自动生成一、分析器的生成器YACC二、用YACC处理二义性文法,17,本章内容,一、自顶向下分析方法的问题及其解决办法1.消除回溯2.消除左递归二、递归子程序分析法（递归下降分析法）1.递归子程序定义2.递归调用子程序的处理3.分析实例4.递归子程序特点三、LL（1）分析法1.定义2.LL（1）分析方法3.构造分析表4.LL（1）文法,18,4.2自顶向下语法分析,本节内容,一、自顶向下分析方法的问题及其解决办法1.消除回溯2.消除左递归二、递归子程序分析法（递归下降分析法）1.递归子程序定义2.递归调用子程序的处理3.分析实例4.递归子程序特点三、LL（1）分析法1.定义2.LL（1）分析方法3.构造分析表4.LL（1）文法,19,4.2自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,一、自顶向下分析方法的问题及其解决办法1.消除回溯2.消除左递归二、递归子程序分析法（递归下降分析法）1.递归子程序定义2.递归调用子程序的处理3.分析实例4.递归子程序特点三、LL（1）分析法1.定义2.LL（1）分析方法3.构造分析表4.LL（1）文法,20,4.2自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,1.消除回溯对于自顶向下语法分析来说，对于某些文法，可能会遇到“回溯”和“左递归”的问题，为了能有效地运用这种语法分析方法，应使文法不含左递归及避免回溯。（1）回溯分析方法定义在进行自顶向下语法分析时，对于文法规则中具有同一左部而右部有不同规则时，在分析时按顺序一个个试探，若能分析下去则成，否则再退回到出错点换另一规则重新试探。这种方法称回溯分析方法。其实质就是使用不同规则反复试探。如：ScAdAab|a要判断“cad”是否为该文法的句子，可以分别用Aab和Aa代入第一个产生式中试探。,21,4.2自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,（2）回溯问题的解决1）路标法定义：设有规则Ua1V1|a2V2|anVn若ai为互不相同的终结符时，将ai作为路标，当被分析符号串为ai时，便可按规则UaiVi往下分析，这样可以消除回溯。如：:|ifthen当分析语句：ifA1）才能确定应选规则时，这种语法分析方法就称LL（K）分析法。,94,4.2自顶向下语法分析,三、LL(1)分析法,一、自顶向下分析方法的问题及其解决办法1.消除回溯2.消除左递归二、递归子程序分析法（递归下降分析法）1.递归子程序定义2.递归调用子程序的处理3.分析实例4.递归子程序特点三、LL（1）分析法1.定义2.LL（1）分析方法3.构造分析表4.LL（1）文法,95,4.2自顶向下语法分析,三、LL(1)分析法,96,2.LL（1）分析方法（1）基本思想借助于一张分析表及一个语法分析栈，在一个总控程序控制下实现。我们通常把按LL（1）方法执行语法分析任务的程序称为LL（1）分析程序或LL（1）分析器，它由一个总控程序、一张分析表和一个分析栈组成，如下图所示。,a1a2aian#,输入串,总控程序,分析表m,X.#,分析栈,4.2自顶向下语法分析,三、LL(1)分析法,（2）LL（1）方法分析过程考虑文法:FT*（）i1）建立文法LL（1）的分析表相应的分析表如下表所示（其构造方法，在后面叙述)。,97,4.2自顶向下语法分析,三、LL(1)分析法,98,4.2自顶向下语法分析,三、LL(1)分析法,99,由上述分析过程可以看出，在分析的每一时刻，当前已读过的符号与栈中的符号一起总是构成了当前的左句型，（）分析器确实构造了输入串的一个最左推导。,2）分析过程现在以输入符号串ii*i为例，列出利用上述算法对此符号串的分析过程如下:,步骤分析栈余留输入串所用产生式#Ei+i*i#ETE#ETi+i*i#TFT#ETFi+i*i#Fi#ETii+i*i#ET+i*i#T#E+i*i#E+TE#ET+i*i#ETi*i#TFT#ETFi*i#Fi#ETii*i#ET*i#T*FT#ETF*i#ETFi#Fi#ETii#ET#T#E#E#成功,（3）一般分析步骤其中“输入”就是待分析的符号串，它以右界符#作为结尾。分析表可用一个矩阵（或二维数组）来表示。它概括了相应文法的全部信息。分析表的每一行与文法的一个非终结符相关联，而每一列则与文法的一个终结符号或#相关联。分析表元素，a（aU#）或者指示了当前推导所应使用的产生式，或者指出了输入串中含有语法错误。分析器对每个输入串的分析在总控程序控制下进行。,100,4.2自顶向下语法分析,三、LL(1)分析法,其步骤如下：1）分析开始时，首先将符号#及文法的开始符号依次置于分析栈的底部，并把各指示器调整至起始位置,即分别指向分析栈的栈顶元素和输入串的首字符。然后反复执行第（2）步2）设在分析的某一步，分析栈及余留的输入符号串处于如下格局#X1X2Xm-1Xmaiai+1#其中，m为分析过程中所得的文法符号，此时，可视栈顶符号m的不同情况，分别做如下的动作:,101,4.2自顶向下语法分析,三、LL(1)分析法,若m，则以m及ai组成符号对（m，ai）查分析表，设m,ai为一产生式，譬如说Xm，此时将m从分析栈中退出，并将按反序推入栈中（即用该产生式推导一步），从而得到新的格局:#X1X2Xm-1WVUaiai+1#但若m，ai“”，则调用出错处理程序进行处理;若mai#，则表明栈顶符号已与当前正扫视的输入符号得到匹配，此时应将m（即ai）从栈中退出，并将输入符号指示器向前推进一个位置；若mai#，则表明输入串已完全得到匹配，此时即可宣告分析成功而结束分析工作。,102,4.2自顶向下语法分析,三、LL(1)分析法,(4)几点说明1)分析表M根据具体文法构造，文法不同M就不同2)LL（1）分析法的总控程序对于不同文法总是一样的。3)分析表MA，a或指出应选规则或指出错误（空白时）4)LL（1）语法分析程序的机器模型是一个下推自动机,103,构造一个LL（1）分析器问题，主要归结为构造LL（1）分析表的问题。,4.2自顶向下语法分析,三、LL(1)分析法,一、自顶向下分析方法的问题及其解决办法1.消除回溯2.消除左递归二、递归子程序分析法（递归下降分析法）1.递归子程序定义2.递归调用子程序的处理3.分析实例4.递归子程序特点三、LL（1）分析法1.定义2.LL（1）分析方法3.构造分析表4.LL（1）文法,104,4.2自顶向下语法分析,三、LL(1)分析法,105,3.构造分析表（1）头终结符号集合和后继终结符号集合1）头终结符号集合定义为了构造分析表，我们引进与文法有关的集合FIRST集和FOLLOW集。假定是文法G的任一符号串，或者说(VTV)*，我们定义FIRST（）b*b，b特别是，若*，则规定FIRST（）即FIRST（）是的所有可能推导的开头终结符或可能的,4.2自顶向下语法分析,三、LL(1)分析法,106,例如：设文法GTABAPQ|BCPpP|QqQ|BbB|eCcC|f求FIRST（PQ）,由定义有PQpPqQ=pPQQQqQqPQQQ所以FIRST（PQ）=p,q,同理FIRST（BC)=b,e,对于一个简单的文法我们用手工可以求得其FISRT集，对于复杂的文法我们通常使用下述算法求解,4.2自顶向下语法分析,三、LL(1)分析法,构造头终结符号集合FIRST的算法对于文法中的每一个文法符()，构造（）时，只要连续使用下列规则，直至每个集不再扩大为止。a.若X，则（）。b.若，且有形如b规则（b），或的规则，把b或（和）加入（）中。c.设文法中有形如Y的规则，若，则将FIRST（）中一切非符号加进（）中，对于一切2ik，若*，则把2中首符号集（除外）也加进FIRST（）中，如此继续下去，直到k-1*，则把YK中首符号集(除外)也入FIRST(X)中。d.若每个非终结符号都可能推导出空符号串，即*，则把也加进（）中。,107,4.2自顶向下语法分析,三、LL(1)分析法,现在，可以对文法G的任何符号串n，可按如下步骤构造FIRST（）。首先置FIRST()=,然后将FIRST(X1)中一切非的符号加进FIRST（）若FIRST（），再将FIRST（）的一切非加进FIRST（）中，如此等等。最后，若对于in，（i），则再将加进（）中。,108,考虑文法:FT*（）i,由算法步骤a.得FIRST（+）=+FIRST（*）=*FIRST（）=（FIRST（）=）FIRST（i）=i,由算法步骤b.得FIRST（E）=+，FIRST（T）=*，FIRST（F）=（，i,4.2自顶向下语法分析,三、LL(1)分析法,109,文法:,FT*,（）i对于算法步骤c.和d.因为FT所以FIRST（T）=FIRST（F）=又因为F不能推出，所以FIRST（T）不能被加入FIRST（T）,4.2自顶向下语法分析,三、LL(1)分析法,110,利用该算法还能方便地得到如下的符号串头终结符号集：FIRST（TE）=FIRST（T）=FIRST（F）=（，iFIRST（+TE）=FIRST（+）FIRST（FT）=FIRST（F）=（，iFIRST（*FT）=FIRST（*）=*FIRST（E）=FIRST（）=（FIRST（）=,4.2自顶向下语法分析,三、LL(1)分析法,2)后继终结符号集合定义假定S是文法G的开始符号，对于G的任何非终结符A，我们定义FOLLOW（A）=c|S*Ac,c特别是，若S*A，则规定#FOLLOW（A）即：FOLLOW（A）是所有句型中出现在紧接A之后的终结符或#,111,4.2自顶向下语法分析,三、LL(1)分析法,构造后继符号集合FOLLOW的算法对文法中每个非终结符B，为了构造（B），可反复应用如下规则，直到每个集不再扩大为止。a.对于文法的开始符号，令#（）。(因为S*S由定义#FOLLOW（S）b.若文法中有形如的规则，且，则将FIRST（）中一切非符号加进（）中。c.若文法中有形如B或B的规则，且*，则（）中全部终结符均属于（），其中可以为。,112,4.2自顶向下语法分析,三、LL(1)分析法,113,考虑文法:FT*（）i1.求FOLLOW（E）,）由算法步骤a.得：#FOLLOW（E）(E是文法开始符号）由算法步骤b.规则得：）FOLLOW（E）所以FOLLOW（E）,）2.求FOLLOW（E）,）由算法步骤c.规则得：FOLLOW（E）FOLLOW（E）所以FOLLOW（E）,）,4.2自顶向下语法分析,三、LL(1)分析法,114,考虑文法:FT*（）i3.求FOLLOW（T）+,）1)由算法步骤b.规则、得：+FOLLOW（T）(因为FIRST(E)-=+)2)由算法步骤c.规则得：FOLLOW（E）FOLLOW（T）即），#FOLLOW(T)(由规则得：*,所以由算法c.规则得：FOLLOW（E）FOLLOW（T）即），#FOLLOW(T)所以FOLLOW（T）+,）,4.2自顶向下语法分析,三、LL(1)分析法,115,考虑文法:FT*（）i4.求FOLLOW（T)+,）由算法步骤c.规则得：FOLLOW（T）FOLLOW（T）即+，#,）FOLLOW(T)所以FOLLOW（T)+，#,）,4.2自顶向下语法分析,三、LL(1)分析法,116,考虑文法:FT*（）i5.求FOLLOW（F)+,*，,）1)由算法步骤b.规则、得：*FOLLOW（F）(因为FIRST(T)-=*)2)由算法步骤c.规则得：FOLLOW（T）FOLLOW（F）即+,），#FOLLOW(F)(由规则得：*,所以由算法c.规则得：FOLLOW（T）FOLLOW（F）即+,），#FOLLOW(F)所以FOLLOW（T）+,*,）,4.2自顶向下语法分析,三、LL(1)分析法,117,(2)构造分析表M1)构造分析表M过程（以文法为例）下面列出文法符号串头终结符号集合和非终结符后继终结符号集合，文法:FT*（）i,4.2自顶向下语法分析,三、LL(1)分析法,对下述文法求出符号串头终结符号集合和非终结符后继终结符号集合整理得：文法:FT*（）iFIRST（TE）=（，iFIRST（+TE）=+FIRST（FT）=（，iFIRST（*FT）=*FIRST（E）=（FIRST（）=,118,FOLLOW（E）=FOLLOW（E）=），#FOLLOW（E）,）FOLLOW（T）=FOLLOW（T）=），#，+FOLLOW（T)+,）FOLLOW（F）=），#，+，*,4.2自顶向下语法分析,三、LL(1)分析法,119,2)构造分析表M算法求出集和集后，根据前面构造文法的（）分析表的过程，我们就可以得出构造分析表M算法，对于中每一个规则，可按如下算法确定表中各元素：对（）中每一终结符a，置A,a“”若（），则对属于（）中的每一符号b(b为终结符或)，置，b“”；把中所有不能按规则、定义的元素均置为出错。,4.2自顶向下语法分析,三、LL(1)分析法,FT*（）i1.对于规则由于FIRST（TE）=(，i，于是置ME,（=ME，i=,120,4.2自顶向下语法分析,三、LL(1)分析法,FT*（）i2.对于规则由于FIRST（+TE）=+，于是置M,+=由于，则FIRST（）=，而FOLLOW（E）=)，#于是置M，）=M，#=,121,4.2自顶向下语法分析,三、LL(1)分析法,122,4.2自顶向下语法分析,三、LL(1)分析法,FT*（）i3.对于规则FT由于FIRST（FT）=(，i，于是置MT，（=FTMT，i=FT,123,4.2自顶向下语法分析,三、LL(1)分析法,FT*（）i4.对于规则*由于FIRST(*FT)=*，于是置M，*=“*”由于T，则FIRST（）=，而FOLLOW（T）=），#，+，于是置MT，）=“T”MT，#=“T”MT，+=“T”,124,4.2自顶向下语法分析,三、LL(1)分析法,125,4.2自顶向下语法分析,三、LL(1)分析法,FT*（）i5.对于规则（）i由于FIRST（E）=（，于是置MF，(=“（）”由于FIRST（i）=i，于是置MF，i=“i”,126,4.2自顶向下语法分析,三、LL(1)分析法,127,该表和书上p86表4.1完全相同,4.2自顶向下语法分析,三、LL(1)分析