第五章自顶向下语法分析方法PPT课件

.,1,第五章自顶向下语法分析方法,学习目标:掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法理解：LL（1）文法了解：不确定的自顶向下分析,语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子分类:,自顶向下的基本思想:从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子.,.,3,5.1确定的自顶向下分析思想5.2LL(1)文法的判别5.3某些非LL(1)文法到LL(1)文法的等价变换5.4不确定的自顶向下分析思想5.5确定的自顶向下分析方法,.,4,5.1确定的自顶向下分析思想,1确定分析的条件2开始符号集FIRST()的定义3后跟符号集FOLLOW(A)的定义4选择集合SELECT(A)的定义5LL(1)文法的定义,.,5,1确定分析的条件,从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。,例1设有文法G1S:SpA|qBAcAd|aBdB|b若输入串W=pccadd。自顶向下的推导过程为:,S,S,=pA,=pcAd,=pccAdd,=pccadd,G1S有如下特点：(1)每个产生式的右部由终结符开头;(2)同一非终结符的不同产生式的右部由不同的终结符开头。对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。,例2：设有文法G2S为:SAp|BqAa|cABb|dB,S,=ccap,S,=cAp,=ccAp,=Ap,该例说明，当(1)产生式右部以终结符或非终结符开头（无空产生式）；(2)同一非终结符的不同产生式的右部由不同的符号开头。对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集），分析过程可能是确定,若输入串W=ccap,自顶向下的推导过程为：,例3：设有文法G3SSaA|dAbAS|若输入串W=abd，自顶向下的推导过程为：,S,=abd,S,=abAS,=abS,文法的特点是:包含空产生式对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。,=aA,.,9,要进行确定的自顶向下的分析，文法要满足一定的限制即文法是LL(1)文法。先研究三个定义开始符号集FIRST后跟符号集FOLLOW选择集合SELECT,.,10,2开始符号集FIRST()的定义,定义:设G=(VN,VT,P,S)是上下文无关文法，(VNVT)*FIRST()=aVT|*a.若*则规定FIRST()直观上说文法符号串的开始符号集是由推导出的开头的终结符（包括）组成。,例文法G2S:,SApSBqAaAcABbBdB,FIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=aFIRST(cA)=cFIRST(b)=bFIRST(dB)=d,由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析,.,12,3后跟符号集FOLLOW(A)的定义,定义设G=(VT,VN,P,S)是上下文无关文法，AVN，FOLLOW(A)=a|S=*Aa，aVT，若有S=*A，则规定#FOLLOW(A)（注：#输入串#，#做为输入串的结束符）直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。,例文法G3S:SaA|dAbAS|,由S=*S得#FOLLOW(S)由S=aA=abAS=abbASS=abbASaA=abbASdFOLLOW(S)=#,a,d,由S=*aA得#FOLLOW(A)由S=*abAS=*abAaA得aFOLLOW(A)=*abAd得dFOLLOW(A)FOLLOW(A)=#,a,d,说明：对于非终结符A的两个产生式AbAS和A，当输入符号FIRST(bAS)=b时，选AbAS推导，当输入符号FOLLOW(A)=#,a,d时，选A推导。由于FIRST(bAS)FOLLOW(A)=，所以可进行确定的自顶向下分析。,.,15,4选择集合SELECT(A)的定义,定义对给定的上下文无关文法的产生式A，AVN，V*，若*,则SELECT(A)=FIRST()若=*,则SELECT(A)=(FIRST()-)FOLLOW(A),.,16,解释当A面对应输入符a，在自顶向下的分析中应选择这样的产生式A进行推导：First()中包含a；此外若可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，所以当a应属于Follow(A)时，选择产生式A也是可以的。直观上说某产生式A的选择集合是指遇到哪些输入符号（包括#）时选用该产生式向下推导。,例G3S:SaASdAbASA,SELECT(SaA)=FIRST(aA)=aSELECT(Sd)=FIRST(d)=dSELECT(AbAS)=FIRST(bAS)=bSELECT(A)=FOLLOW(A)=#,a,d,若*,则SELECT(A)=FIRST()若=*,则SELECT(A)=(FIRST()-)FOLLOW(A),.,18,说明：同一非终结符的不同产生式A与A，若SELECT(A)SELECT(A)=，则一定可以进行确定的自顶向下分析,.,19,5LL(1)文法的定义,定义:一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A与A，满足SELECT(A)SELECT(A)=。LL(1)文法的含义是：第一个L表示从左到右扫描输入串第二个L表示分析过程用最左推导1表明只需向前看一个符号便可以决定选哪个产生式进行推导，类似地LL(k)文法需要向前看K个符号才可以确定选用哪个产生式。,例有文法GS为：SaASSbAbAA,SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=Follow(A)=a,b,由于SELECT(AbA)SELECT(A)=b，所以文法GS不是LL(1)文法，当A遇输入符b时，不能确定选AbA还是A去推导。,.,21,5.2LL(1)文法的判别,要判别一个上下文无关文法是否是LL(1)文法分为五步：1.求能推出的非终结符集2.计算每个产生式右部的FIRST()集3.计算每个非终结符A的FOLLOW(A)集4.计算每个产生式A的SELECT(A)集5.按LL(1)文法的定义判别,.,22,1.求出能推出的非终结符集,算法:用S表示能推出的非终结符集第一步令S=Aj|Aj产生式集对每个产生式p:ApX1.Xn，若X1.XnS，则S:=SAp重复第二步的循环，直至S收敛（不再变化）为止。,.,23,例GS：SAB|bCAb|BaD|CAD|bDaS|c,非终结符集S,能推出的非终结符集为A,B,S,.,24,2.计算每个产生式右部的FIRST()集,首先对每一文法符号X(XVTVN)，求FIRST(X)的算法:对每个aVT：First(a)=a对每个AVN：若A*则First(A):=否则First(A):=对每个产生式AX1XjXn做：First(A)=First(A)SectionFirst(X1XjXn),其中SectionFirst(X1XjXn)=(First(X1)-)(First(X2)-)(First(Xj)-)First(Xj+1)Xj+1是产生式右部中第一个不能推出的符号若X1*则SectionFirst(X1XjXn)=First(X1)若X1Xn全可推出则SectionFirst(X1Xn)=FIRST(X1)FIRST(Xn)重复3直到每个符号的FIRST集合都不再增大为止。,例GS：SAB|bCAb|BaD|CAD|bDaS|c,First集(3),First集(2),First集(1),A,B,C,D,a,b,S,First集(0),已求出能推出的非终结符集为A,B,S,b,b,a,b,ac,a,ac,利用求出每个文法符号的FIRST集求符号串的FIRST集,设=X1X2Xn当X1不能=*，则FIRST()=FIRST(X1)若对任何j(1jn）都有FIRST(Xj),则FIRST()=(FIRST(X1)-)(FIRST(Xj)-)FIRST(Xj+1)若对所有i(1in)，都有FIRST(Xi)，则FIRST()=FIRST(X1)FIRST(Xn),例GSSAB|bCAb|BaD|CAD|bDaS|c,已求出非终结符的First集合如下:First(S)=a,b,First(A)=b,First(B)=a,First(C)=a,b,cFirst(D)=a,c,产生式右部符号串的开始符集合为:SABFIRST(AB)=FIRST(A)FIRST(B)=a,b,SbCFIRST(bC)=bAFIRST()=AbFIRST(b)=bCADFIRST(AD)=(FIRST(A)-)FIRST(D)=b,a,cDaSFIRST(aS)=a,.,29,3计算每个非终结符A的FOLLOW(A)集,1.对所有AVN令Follow(A)=;对开始符S，令Follow(S)=#,因为S=*S，显然#FOLLOW(S),2.对每条产生式AxBy，考察产生式右部的每一非终结符B，x,yV*，如果y不能推出Follow(B)=Follow(B)First(y)否则Follow(B)=Follow(B)(First(y)-)Follow(A),3.重复2，直至对所有AVN，Follow(A)收敛为止。,若aFOLLOW(A),则表明S=*Aa，由于AxBy，且y=*,则有S=*Aa=xBya=xBa，即S=*xBa,所以aFOLLOW(B),例GS：1SAB2SbC3Ab4A5BaD6B7CAD8Cb9DaS10Dc,已求出非终结符的First集合如下:First(S)=a,b,First(A)=b,First(B)=a,First(C)=a,b,cFirst(D)=a,c,#,D,#,C,#,B,a#,A,S,Follow集(2),Follow集(1),Follow集(0),c,.,31,4计算每个产生式A的SELECT(A)集,按定义计算SELECT(A)：若*，则SELECT(A)=FIRST()若=*，则SELECT(A)=(FIRST()-)FOLLOW(A),例GS：SAB|bCAb|BaD|CAD|bDaS|c,部分产生式的select集合SELECT(SAB)=(FIRST(AB)-)FOLLOW(S)=b,a,#SELECT(SbC)=FIRST(bC)=bSELECT(A)=(FIRST()-）FOLLOW(A)=a,c,#SELECT(Ab)=FIRST(b)=bSELECT(BaD)=FIRST(aD)=aSELECT(CAD)=FIRST(AD)=b,a,c,.,33,5.按LL(1)文法的定义判别,产生式的select集如下:SELECT(SAB)=b,a,#SELECT(SbC)=bSELECT(A)=a,c,#SELECT(Ab)=bSELECT(B)=#SELECT(BaD)=aSELECT(CAD)=b,a,cSELECT(Cb)=bSELECT(DaS)=aSELECT(Dc)=c,由于SELECT(SAB)SELECT(SbC)=bSELECT(CAD)SELECT(Cb)=b所以文法GS不是LL(1)文法,.,34,5.3某些非LL(1)文法到LL(1)文法的等价变换,非LL(1)文法含有左公共因子的文法若文法中含有形如：A|r的产生式，称文法含有左公共因子。显然,SELECT(A)SELECT(Ar),文法不是LL(1)文法,.,35,含有左递归的文法文法中只要含有下列形式的产生式（含有a或含有b或二者皆有）则称文法含有左递归：AAABBA在a)中含有左递归的产生式，称为直接左递归；在b)中虽然没有含左递归的产生式，但A=B=A即A=+A,称为间接左递归,.,36,以直接左递归为例，若有如下产生式AA|A其中和为任意语法符号串。不难证明有下面关系式：Select(AA)First(A)First()Select(A)First()故AA和A的Select集相交，不是LL(1)文法。,.,37,对非LL(1)文法进行等价变换提取左公共因子消除左递归注意：变换后的文法不一定是LL(1)文法，文法不含左递归和左公共因子只是LL(1)文法的必要条件。,.,38,1提取左公共因子,将产生式A|r等价变换为:A(|r)，将括号内用一新引入的非终结符A表示,得AA，A|r一般形式：若A1|2|n,提取左公共因子后变为AA，A1|2|n若在i中仍含有左公共因子,可再次提取.,.,39,例文法G1：SaSb|aS|提左因子得:SaS(b|)|引进新的非终结符得:SaSS|Sb|,.,40,2.消除左递归,消除直接左递归文法G:SSa|b可改写成SbSSaS|一般情形:含直接左递归的文法G：AA1|A2|Am|1|2|n消除左递归后改写成：A1A|2A|nAA1A|2A|mA|,消除间接左递归将间接左递归变成直接左递归，再消除算法步骤：把文法的所有非终结符按任一顺序排列，如：A1，A2，An从A1开始，按以下顺序处理Ai。首先，消除左部为Ai的产生式的直接左递归然后，若左部为Ai的产生式的右部为非终结符Aj(j*，且Follow(A)First(bAS)=b，从而引起回溯,例3文法G：SSaSb输入串w=baa，推导树为:,由于文法含有左递归而引起回溯,.,48,5.5确定的自顶向下分析方法,确定的自顶向下分析方法有：递归子程序法(recursive-descentparser)预测分析法(predictiveparser)两种方法都要求文法是LL(1)文法。,.,49,5.5.1递归子程序法,实现思想：对文法中的每个非终结符编写一个递归过程，识别由该非终结符推出的串。当非终结符有多条产生式时，按当前输入符属于哪条产生式的SELECT集可唯一确定选择哪个产生式进行匹配。当识别到终结符时，与当前输入符号匹配，并读取下一输入符；当识别到非终结符时，则调用该非终结符相应的过程。,例算术表达式文法GEE+TTTT*FFF(E)i,1）消除左递归得G:ETEE+TETFTT*FTF(E)i,2）求出G的选择集合SELECT(ETE)=(,iSELECT(E+TE)=+SELECT(E)=),#SELECT(TFT)=(,iSELECT(T*FT)=*SELECT(T)=+,),#SELECT(F(E)=(SELECT(Fi)=i,G是LL(1)文法,1判断是否可以应用递归子程序法,.,51,2构造文法G的递归下降分析器定义：当一个文法满足LL(1)条件时，就为它构造一个不带回溯的自顶向下的分析程序，这个分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。,组成：递归下降分析器由一个主程序MAIN和每个非终结符对应的一个递归过程组成。用到的一些子过程：过程GETNEXT负责读入下一个TOKEN字过程ERROR负责报告语法错误约定：变量TOKEN存放已读入的TOKEN字过程进入时变量TOKEN存放了一个待匹配的TOKEN字退出过程时，变量TOKEN中仍存放着一个待匹配的TOKEN字。,非终结符相应的分析子程序的构造方法对于每个非终结符U，编写一个相应的子程序P(U);对于产生式Ux1|x2|xn，x1,.xn都关于U的子程序P(U)按如下方法构造：ifTOKENinfirst(x1)thenp(x1)elseifTOKENinfirst(x2)thenp(x2)else.ifTOKENinfirst(xn)thenp(xn)elseERROR,如果U还有空产生式U,则算法中的语句：ifTOKENinfirst(xn)thenp(xn)elseERROR改写为ifTOKENinfirst(xn)thenp(xn)elseifTOKENnotinfollow(U)thenERROR对于符号串x=y1y2yn；p(x)的含义为：beginp(y1);p(y2);p(yn)end如果yiVN，则P(yi)就代表调用yi的子程序；yiVT，则P(yi)为形如下述语句的一段程序ifTOKEN=yithenGETNEXT(TOKEN)elseERROR,(1)programMAIN;/*主程序*/beginGETNEXT(TOKEN);E(TOKEN);/*转匹配ETE*/ifTOKEN#thenERRORend.,构造文法G：ETEE+TETFTT*FTF(E)i的递归下降分析器,(2)procedureE(TOKEN);/*匹配ETE*/beginT(TOKEN);/*转匹配TFT*/E(TOKEN)/*转匹配E+TE*/end;,(3)procedureE(TOKEN);/*匹配E+TE*/beginifTOKEN=+then/*选择产生式E+TE*/beginGETNEXT(TOKEN);/*匹配+,读下一个TOKEN字*/T(TOKEN);/*转匹配TFT*/E(TOKEN)/*转匹配E+TE*/endelse/*E对应的语句*/ifTOKEN)andTOKEN#thenERRORend;,(5)procedureT(TOKEN);/*匹配T*FT*/beginifTOKEN=*then/*选择产生式T*FT*/beginGETNEXT(TOKEN);/*匹配*，读下一TOKEN字*/F(TOKEN);/*转匹配F(E)i*/T(TOKEN)/*转匹配T*FT*/endelse/*T对应的语句*/ifTOKEN+andTOKEN)andTOKEN#thenERRORend;,(4)procedureT(TOKEN);/*匹配TFT*/beginF(TOKEN);/*转匹配F(E)i*/T(TOKEN)/*转匹配T*FT*/end;,(6)procedureF(TOKEN);/*匹配F(E)i*/beginifTOKEN=(then/*选择产生式F(E)*/beginGETNEXT(TOKEN);/*匹配(，读下一TOKEN字*/E(TOKEN);/*转匹配ETE*/ifTOKEN=)thenGETNEXT(TOKEN)/*匹配),读下一TOKEN字*/elseERROR