自顶向下语法分析方法(完).ppt

第5章自顶向下语法分析方法,2019/12/2,第5章自顶向下语法分析方法,Page2,第五章自顶向下语法分析方法,学习目标:掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法理解：LL(1)文法了解：不确定的自顶向下分析,2019/12/2,Page3,第5章自顶向下语法分析方法,语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子.分类:,自顶向下的基本思想:从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子。,2019/12/2,第5章自顶向下语法分析方法,Page4,5.1确定的自顶向下分析思想5.2LL(1)文法的判别5.3某些非LL(1)文法到LL(1)文法的等价变换5.4不确定的自顶向下分析思想5.5确定的自顶向下分析方法,第五章自顶向下语法分析方法,2019/12/2,第5章自顶向下语法分析方法,Page5,5.1确定的自顶向下分析思想,1确定分析的条件2开始符号集FIRST()的定义3后跟符号集FOLLOW(A)的定义4选择集合SELECT(A)的定义5LL(1)文法的定义,2019/12/2,Page6,第5章自顶向下语法分析方法,1确定分析的条件,从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。,2019/12/2,Page7,第5章自顶向下语法分析方法,例1设有文法G1S:SpA|qBAcAd|aBdB|b若输入串W=pccadd。自顶向下的推导过程为:,S,S,=pA,=pcAd,=pccAdd,=pccadd,G1S有如下特点：(1)每个产生式的右部由终结符开头;(2)同一非终结符的不同产生式的右部由不同的终结符开头。对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。,2019/12/2,Page8,第5章自顶向下语法分析方法,例2：设有文法G2S为:SAp|BqAa|cABb|dB,S,=ccap,S,=cAp,=ccAp,=Ap,该例说明，当(1)产生式右部以终结符或非终结符开头（无空产生式）；(2)同一非终结符的不同产生式的右部由不同的符号开头。对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集）First集，分析过程可能是确定,若输入串W=ccap,自顶向下的推导过程为：,2019/12/2,Page9,第5章自顶向下语法分析方法,例3：设有文法G3SSaA|dAbAS|若输入串W=abd，自顶向下的推导过程为：,S,=abd,S,=abAS,=abS,文法的特点是：包含空产生式对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集）Follow集，分析过程可能是确定的。,=aA,2019/12/2,Page10,第5章自顶向下语法分析方法,1确定分析的条件,要进行确定的自顶向下的分析，文法要满足一定的限制即文法是LL(1)文法。先研究三个定义开始符号集FIRST集后跟符号集FOLLOW集选择集合SELECT集,2019/12/2,Page11,第5章自顶向下语法分析方法,2开始符号集FIRST()的定义,定义:设G=(VN,VT,P,S)是上下文无关文法，(VNVT)*FIRST()=aVT|*a.若*则规定FIRST()直观上说，文法符号串的开始符号集是由推导出的开头的终结符（包括）组成。,2019/12/2,Page12,第5章自顶向下语法分析方法,例文法G2S:,SApSBqAaAcABbBdB,FIRST(Ap)=FIRST(Bq)=FIRST(a)=FIRST(cA)=FIRST(b)=FIRST(dB)=,由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析,a,c,b,d,a,c,b,d,First:开始符号集,2019/12/2,Page13,第5章自顶向下语法分析方法,例2：设有文法G2S为:SAp|BqAa|cABb|dB,S,=ccap,S,=cAp,=ccAp,=Ap,SApFIRST(Ap)=a,cSBqFIRST(Bq)=b,dAaFIRST(a)=aAcAFIRST(cA)=cBbFIRST(b)=bBdBFIRST(dB)=d,若输入串W=ccap,自顶向下的推导过程为：,2019/12/2,Page14,第5章自顶向下语法分析方法,3后跟符号集FOLLOW(A)的定义,定义：设G=(VT,VN,P,S)是上下文无关文法，AVN，FOLLOW(A)=a|S=*Aa，aVT，若有S=*A，则规定#FOLLOW(A)（注：#输入串#，#做为输入串的结束符）直观上说，非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。,2019/12/2,Page15,第5章自顶向下语法分析方法,例文法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,2019/12/2,Page16,第5章自顶向下语法分析方法,3后跟符号集FOLLOW(A)的定义,说明：对于非终结符A的两个产生式AbAS和A：当输入符号FIRST(bAS)=b时，选AbAS推导，当输入符号FOLLOW(A)=#,a,d时，选A推导。由于FIRST(bAS)FOLLOW(A)=，所以可进行确定的自顶向下分析。,2019/12/2,Page17,第5章自顶向下语法分析方法,例3：设有文法G3SSaA|dAbAS|若输入串W=abd，自顶向下的推导过程为：,=abd,S,=abAS,=abS,文法的特点是:包含空产生式对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。,=aA,FIRST(bAS)=bFOLLOW(A)=#,a,d,2019/12/2,Page18,第5章自顶向下语法分析方法,4选择集合SELECT(A)的定义,定义对给定的上下文无关文法的产生式A，AVN，V*，若*,则SELECT(A)=FIRST()若=*,则SELECT(A)=(FIRST()-)FOLLOW(A),2019/12/2,Page19,第5章自顶向下语法分析方法,4选择集合SELECT(A)的定义,解释当A面对应输入符a，若First()中包含a，在自顶向下的分析中应选择产生式A进行推导；此外若可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，所以当a属于Follow(A)时，选择产生式A也是可以的。直观上说某产生式A的SELECT集是指遇到哪些输入符号（包括#）时选用该产生式向下推导。,SELECT(A)=a,b,c,2019/12/2,Page20,第5章自顶向下语法分析方法,4选择集合SELECT(A)的定义,即：若*,则是否选择A这条产生式进行推导，主要是看当时输入字符是否属于FIRST()，若是，则选它。若=*,则是否选择A这条产生式进行推导，除了看当时输入字符是否属于FIRST()，还要看当时输入字符是否属于FOLLOW(A)，若属于其中一个集合，则选它。,若*,则SELECT(A)=FIRST()若=*,则SELECT(A)=(FIRST()-)FOLLOW(A),2019/12/2,Page21,第5章自顶向下语法分析方法,例G3S:SaASdAbASA,SELECT(SaA)=SELECT(Sd)=SELECT(AbAS)=SELECT(A)=,若*,则SELECT(A)=FIRST()若=*,则SELECT(A)=(FIRST()-)FOLLOW(A),FIRST(aA)=,FIRST(d)=,FIRST(bAS)=,FOLLOW(A)=,#,a,b,b,d,a,2019/12/2,Page22,第5章自顶向下语法分析方法,4选择集合SELECT(A)的定义,说明：同一非终结符的不同产生式A与A，若SELECT(A)SELECT(A)=，则一定可以进行确定的自顶向下分析。,SELECT(A)=a,bSELECT(A)=c,d,SELECT(A)=a,bSELECT(A)=a,d,2019/12/2,Page23,第5章自顶向下语法分析方法,5LL(1)文法的定义,定义:一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A与A，满足SELECT(A)SELECT(A)=（无交集）。LL(1)文法的含义是：第一个L表示从左到右扫描输入串第二个L表示分析过程用最左推导1表明只需向前看一个符号便可以决定选哪个产生式进行推导，类似地LL(k)文法需要向前看K个符号才可以确定选用哪个产生式。,2019/12/2,Page24,第5章自顶向下语法分析方法,例有文法GS为：SaASSbAbAA,SELECT(SaAS)=a,由于SELECT(AbA)SELECT(A)=b，所以文法GS不是LL(1)文法，当A遇输入符b时，不能确定选AbA还是A去推导。,SELECT(Sb)=b,SELECT(AbA)=b,SELECT(A)=Follow(A)=a,b,2019/12/2,第5章自顶向下语法分析方法,Page25,5.2LL(1)文法的判别,要判别一个上下文无关文法是否是LL(1)文法分为五步：1.求出能推出的非终结符集2.计算每个产生式右部的FIRST()集3.计算每个非终结符A的FOLLOW(A)集4.计算每个产生式A的SELECT(A)集5.按LL(1)文法的定义判别,2019/12/2,Page26,第5章自顶向下语法分析方法,1.求出能推出的非终结符集,步骤：(1)第1次扫描扫描文法中的产生式对能直接推出的产生式左部的终结符标“是”。删除所有右部含有终结符的产生式。若以某一非终结符为左部的所有产生式都被删除，则该非终结符不能推出，将其标为“否”。,2019/12/2,Page27,第5章自顶向下语法分析方法,1.求出能推出的非终结符集,例GS：SAB|bCAb|BaD|CAD|bDaS|c,SABSbCAbABaDBCADCbDaSDc,是,是,否,2019/12/2,Page28,第5章自顶向下语法分析方法,1.求出能推出的非终结符集,(2)第2次扫描扫描产生式右部的符号对每个产生式p:AX1.Xn，如果X1,Xn都被标为“是”(即X1,Xn都能推出)，则A也能推出，将其标为“是”。如果AY1.Yn中，Y1.Yn中任一个已被标为“否”，则删掉该产生式，若这么做使得A的所有产生式都被删去，则A不能推出，将其标为“否”。,2019/12/2,Page29,第5章自顶向下语法分析方法,1.求出能推出的非终结符集,例GS：SAB|bCAb|BaD|CAD|bDaS|c,SABSbCAbABaDBCADCbDaSDc,是,是,否,是,否,能推出的非终结符集为A,B,S,2019/12/2,Page30,第5章自顶向下语法分析方法,2.计算每个产生式右部的FIRST()集,首先对每一文法符号X(XVTVN)，求FIRST(X)的算法:对每个aVT：FIRST(a)=a对每个AVN：若A*，则FIRST(A)对每个AVN：若Aa,aVT，则aFIRST(A),2019/12/2,Page31,第5章自顶向下语法分析方法,2.计算每个产生式右部的FIRST()集,若X,Y1,Y2,Yn都VN,有产生式XY1Y2Yn.当Y1,Y2,Yn-1都*时，FIRST(Y1)-,FIRST(Y2)-,FIRST(Yn-1)-,FIRST(Yn)都包含在FIRST(X)中。当4中所有Yi*，则FIRST(X)=FIRST(Y1)FIRST(Y2)FIRST(Yn),2019/12/2,Page32,第5章自顶向下语法分析方法,例GS：SABSbCAbABaDBCADCbDaSDc,First集(3),First集(2),First集(1),A,B,C,D,a,b,S,First集(0),已求出能推出的非终结符集为A,B,S,b,a,b,ac,a,ac,b,2019/12/2,Page33,第5章自顶向下语法分析方法,利用求出每个文法符号的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),2019/12/2,Page34,第5章自顶向下语法分析方法,例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)=SbCFIRST(bC)=AFIRST()=AbFIRST(b)=CADFIRST(AD)=DaSFIRST(aS)=,FIRST(A)FIRST(B)=a,b,b,b,(FIRST(A)-)FIRST(D)=b,a,c,a,2019/12/2,Page35,第5章自顶向下语法分析方法,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),否则,若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),2019/12/2,Page36,第5章自顶向下语法分析方法,例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,2019/12/2,Page37,第5章自顶向下语法分析方法,4计算每个产生式A的SELECT(A)集,按定义计算SELECT(A)：若*，则SELECT(A)=FIRST()若=*，则SELECT(A)=(FIRST()-)FOLLOW(A),2019/12/2,Page38,第5章自顶向下语法分析方法,例GS：SAB|bCAb|BaD|CAD|bDaS|c,部分产生式的select集合SELECT(SAB)=SELECT(SbC)=SELECT(A)=SELECT(Ab)=SELECT(BaD)=SELECT(CAD)=,(FIRST(AB)-)FOLLOW(S)=b,a,#,FIRST(bC)=b,FIRST(b)=b,FIRST(aD)=a,FIRST(AD)=b,a,c,(FIRST()-)FOLLOW(A)=a,c,#,2019/12/2,Page39,第5章自顶向下语法分析方法,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)文法,一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A与A，满足SELECT(A)SELECT(A)=,2019/12/2,第5章自顶向下语法分析方法,Page40,非LL(1)文法含有左公共因子的文法若文法中含有形如：A|r的产生式，称文法含有左公共因子。显然,SELECT(A)SELECT(Ar),文法不是LL(1)文法,5.3某些非LL(1)文法到LL(1)文法的等价变换,2019/12/2,第5章自顶向下语法分析方法,Page41,含有左递归的文法文法中只要含有下列形式的产生式（含有或含有或二者皆有），则称文法含有左递归:AAABBA在中含有左递归的产生式，称为直接左递归；在中虽然没有含左递归的产生式，但A=B=A即A=+A,称为间接左递归.,5.3某些非LL(1)文法到LL(1)文法的等价变换,2019/12/2,第5章自顶向下语法分析方法,Page42,以直接左递归为例，若有如下产生式AA|A其中和为任意语法符号串。不难证明有下面关系式：Select(AA)First(A)First()Select(A)First()故AA和A的Select集相交，不是LL(1)文法,5.3某些非LL(1)文法到LL(1)文法的等价变换,AAAA不知何时结束不确定,若*,则SELECT(A)=FIRST()若=*,则SELECT(A)=(FIRST()-)FOLLOW(A),2019/12/2,第5章自顶向下语法分析方法,Page43,对非LL(1)文法进行等价变换提取左公共因子消除左递归注意：变换后的文法不一定是LL(1)文法，文法不含左递归和左公共因子只是LL(1)文法的必要条件。,5.3某些非LL(1)文法到LL(1)文法的等价变换,2019/12/2,Page44,第5章自顶向下语法分析方法,将产生式A|r等价变换为:A(|r)，将括号内用一新引入的非终结符A表示,得AA，A|r一般形式：若A1|2|n,提取左公共因子后变为A(1|2|n)，引进新的非终结符A，得：AA，A1|2|n若在i中仍含有左公共因子,可再次提取.,1、提取左公因子,2019/12/2,Page45,第5章自顶向下语法分析方法,例文法G1：SaSb|aS|提左因子得:SaS(b|)|引进新的非终结符S得:SaSS|Sb|,1、提取左公因子,2019/12/2,Page46,第5章自顶向下语法分析方法,1)消除直接左递归文法G:SSa|b可改写成SbSSaS|一般情形:含直接左递归的文法G：AA1|A2|Am|1|2|n消除左递归后改写成：A1A|2A|nAA1A|2A|mA|,2、消除左递归,不难验证，改写前和改写后的文法都产生语言ban|n0,2019/12/2,Page47,第5章自顶向下语法分析方法,2)消除间接左递归将间接左递归变成直接左递归，再加以消除。算法步骤：把文法的所有非终结符按任一顺序排列，如：A1，A2，An从A1开始，按以下顺序处理Ai。首先，消除左部为Ai的产生式的直接左递归；然后，若左部为Ai的产生式的右部为非终结符Aj(j*，且Follow(A)First(bAS)=b，从而引起回溯,2019/12/2,Page53,第5章自顶向下语法分析方法,例3文法G：SSaSb输入串w=baa，推导树为:,由于文法含有左递归而引起回溯,2019/12/2,第5章自顶向下语法分析方法,Page54,5.5确定的自顶向下分析方法,确定的自顶向下分析方法有：递归子程序法(recursive-descentparser)预测分析法(predictiveparser)两种方法都要求文法是LL(1)文法。,2019/12/2,第5章自顶向下语法分析方法,Page55,实现思想：对应文法中每个非终结符编写一个递归过程，识别由该非终结符推出的串。当非终结符有多条产生式时，按当前输入符属于哪条产生式的SELECT集可唯一确定选择哪个产生式进行匹配。当识别到终结符时，与当前输入符号匹配，并读取下一输入符；当识别到非终结符时，则调用该非终结符相应的过程。,5.5.1递归子程序法,2019/12/2,第5章自顶向下语法分析方法,Page56,5.5.1递归子程序法,由于递归子程序法对每个过程可能存在直接或间接递归调用，所以对某个过程在退出之前可能又被调用，因此有些信息需要保留，通常在入口时需保留某些信息，出口时需恢复先进后出栈。优点：简单直观、易于构造缺点：对文法要求高，必须是LL(1)文法递归调用多，速度慢，占用空间多,2019/12/2,第5章自顶向下语法分析方法,Page57,5.5.2预测分析方法,一个预测分析器由三个部分组成：预测分析程序：控制分析过程的进行。分析栈：存放从文法开始符号出发的自顶向下推导过程中等待匹配的文法符号。开始时放入#和文法开始符，结束时栈应是空的。预测分析表：是一张二维表，元素MA,a的内容是当非终结符A面临输入符号a(终结符或句子括号)时应选取的产生式，当无产生式时，元素内容为转向出错处理。,2019/12/2,Page58,第5章自顶向下语法分析方法,构造预测分析表步骤：(1)把文法转变为LL(1)文法(2)求出每条产生式的SELECT集(3)依照SELECT集把产生式填入分析表对每个终结符或用a表示若aSELECT(A)，则把A放入MA,a中，把所有无定义的MA,a标上出错标记。,2019/12/2,Page59,第5章自顶向下语法分析方法,例算术表达式文法GEE+TTTT*FFF(E)i,（1）消除G的左递归得到文法GETEE+TETFTT*FTF(E)i,2019/12/2,Page60,第5章自顶向下语法分析方法,（2）求出每个产生式的select集,G是LL(1)文法SELECT(ETE)=(,iSELECT(E+TE)=+SELECT(E)=),#SELECT(TFT)=(,iSELECT(T*FT)=*SELECT(T)=+,),#SELECT(F(E)=(SELECT(Fi)=i,F(E),Fi,F,T,T,T*FT,T,T,TFT,TFT,T,E,E,E+TE,E,E,#,）,（,*,+,i,ETE,ETE,（3）依照选择集合把产生式填入分析表,注：表中空白处为出错,2019/12/2,Page61,第5章自顶向下语法分析方法,预测分析程序,2019/12/2,Page62,第5章自顶向下语法分析方法,输入串i+i*i#的分析过程,7,6,5,4,3,2,1,所用产生式,剩余输入串,分析栈,步骤,反序压栈!,2019/12/2,Page63,第5章自顶向下语法分析方法,8,13,14,15,16,17,12,11,10,9,2019/12/2,Page64,第5章自顶向下语法分析方法,P