编译原理自顶向下语法分析方法.ppt

第四章第四章 自顶向下语法分析方法自顶向下语法分析方法学习目标学习目标:掌掌握握：LL(1)LL(1)文文法法的的判判别别，预预测测分分析析法法，递归子程序的构造方法递归子程序的构造方法理解：理解：LLLL（1 1）文法文法了解：不确定的自顶向下分析了解：不确定的自顶向下分析语语法法分分析析的的作作用用是是识识别别由由词词法法分分析析给给出出的的单单词词序序列列是否是给定文法的正确句子是否是给定文法的正确句子语法分析语法分析自顶向下分析自顶向下分析自底向上分析自底向上分析确定的确定的不确定的不确定的算法优先分析（第算法优先分析（第六六章）章）LR分析（第五章）分析（第五章）自顶向下基本思想自顶向下基本思想:从从文文法法的的开开始始符符出出发发企企图图推推导导出出与与输输入入的的单单词词串完全相匹配的句子串完全相匹配的句子.分类分类:回顾回顾自上而下的分析方法自上而下的分析方法q定义定义:从文法的开始符号出发，反复使用文法的从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。产生式，寻找与输入符号串匹配的推导。q语法树的构造：语法树的构造：将文法的开始符号作为语法树的根，向下将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。号串正好是输入符号串。q自上而下分析的主要问题自上而下分析的主要问题选定产生式选定产生式例例文法文法G：S cAdA abA a识别输入串识别输入串w=cabd是否为该文法的句子是否为该文法的句子ScAdab=cabdS=cAd回顾回顾自上而下的分析方法自上而下的分析方法ScA da成功成功不成功不成功=cadS=cAd4.1确定的自顶向下分析思想确定的自顶向下分析思想4.2LL(1)文法的判别文法的判别4.3某些非某些非LL(1)文法到文法到LL(1)文法的等价变换文法的等价变换4.4不确定的自顶向下分析思想不确定的自顶向下分析思想4.5确定的自顶向下分析方法确定的自顶向下分析方法本章内容本章内容4.1确定的自顶向下分析思想确定的自顶向下分析思想1确定分析的条件确定分析的条件2开始符号集开始符号集FIRST()的定义的定义3后跟符号集后跟符号集FOLLOW(A)的定义的定义4选择集合选择集合SELECT(A)的定义的定义5LL(1)文法的定义文法的定义1.确定分析的条件确定分析的条件从从文文法法的的开开始始符符出出发发，如如能能根根据据当当前前的的输输入入符符号号（单单词词符符号号）唯唯一一地地确确定定选选用用哪个产生式进行推导，则分析是确定的。哪个产生式进行推导，则分析是确定的。例例1设有文法设有文法G1S:SpA|qBAcAd|aBdB|b若输入串若输入串W=pccadd。自顶向下的推导过程为自顶向下的推导过程为:SSApcAdcAda=pA=pcAd=pccAdd=pccaddG1S有如下特点：有如下特点：(1)每个产生式的右部由终结符开头每个产生式的右部由终结符开头;(2)同一非终结符的不同产生式的右部由不同一非终结符的不同产生式的右部由不同的终结符开头。同的终结符开头。对对于于这这种种文文法法，在在推推导导过过程程可可以以根根据据当当前前的的输输入入符符号号唯唯一一确确定定选选哪哪个个产产生生式式往往下下推推导导，即分析过程是确定的。即分析过程是确定的。例例2：设有文法设有文法G2S为为:SAp|BqAa|cABb|dBpAScAcAa=ccapS=cAp=ccAp=Ap该例说明，当该例说明，当(1)产产生生式式右右部部以以终终结结符符或或非非终终结结符符开开头头（无无空空产生式）；产生式）；(2)同一非终结符的不同产生式的右部由不同的同一非终结符的不同产生式的右部由不同的符号开头。符号开头。若输入串若输入串W=ccap,自顶向下的推导过程为：自顶向下的推导过程为：对对于于这这种种文文法法，在在推推导导过过程程选选用用哪哪个个产产生生式式不不直直观观，关关键键是是判判断断产产生生式式右右部部推推出出的的开开始始符符号号（集集），分析过程可能是确定的，分析过程可能是确定的例例3：设有文法设有文法G3SSaA|dAbAS|若输入串若输入串W=abd，自顶向下的推导过程为：自顶向下的推导过程为：AaSbSA d=abdS=abAS=abS文法的特点文法的特点包含空产生式包含空产生式=aA对于空产生式左部的非终结符对于空产生式左部的非终结符，关键是判断关键是判断该该非终结符的后跟符号（集）非终结符的后跟符号（集），分析过程可，分析过程可能是确定的。能是确定的。要进行确定的自顶向下的分析，文法要满要进行确定的自顶向下的分析，文法要满足一定的限制足一定的限制即文法是即文法是LL(1)文法文法先研究三个定义先研究三个定义开始符号集开始符号集FIRST后跟符号集后跟符号集FOLLOW选择集合选择集合SELECT2.开始符号集开始符号集FIRST()的定义的定义n定义定义:设设G=(VN,VT,P,S)是上下文无关文法，是上下文无关文法，(VN,(VN VT)*)FIRST()=a|a VT且且*a.（若若*则规定则规定FIRST()）直观上说文法符号串直观上说文法符号串 的开始符号集是由的开始符号集是由 推推导出的所有的终结符开头和可能的导出的所有的终结符开头和可能的组成。组成。例文法例文法G2S:SApSBqAaAcABbBdBFIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=aFIRST(cA)=cFIRST(b)=bFIRST(dB)=d结论一结论一针对无空产生式的文法针对无空产生式的文法G，同一非终结符的任两，同一非终结符的任两个产生式的右部串的个产生式的右部串的First集无交集，即可进行确定的集无交集，即可进行确定的自顶向下分析。自顶向下分析。3.后跟符号集后跟符号集FOLLOW(A)的定义的定义定义定义设设G=(VT,VN,P,S)是上下文无关文法，是上下文无关文法，Bx xAy y (A,BVNx,yx,y (VN VT)*)FOLLOW(A)=a|S=*Aa，aVT，若有若有S=*A，则规定则规定#FOLLOW(A)（注：（注：#输入串输入串#，#做为输入串的结束符）做为输入串的结束符）直观上说直观上说,非终结符非终结符A的后跟符号集是由句型中紧跟的后跟符号集是由句型中紧跟A后的那后的那些终结符（包括些终结符（包括#）组成。）组成。例 文法G3S:SaA|d AbAS|由由S=*S得得#FOLLOW(S)由由S=aA=abAS=abbASS=abbASaA得得aFOLLOW(S)=abbASd得得dFOLLOW(S)FOLLOW(S)=#,a,d由由S=*aA得得#FOLLOW(A)由由S=*abAS=*abAaA得得aFOLLOW(A)=*abAd得得dFOLLOW(A)FOLLOW(A)=#,a,dFOLLOW(A)FOLLOW(S)n解释解释当当A面对应输入符面对应输入符a，在自顶向下的分析中应选择这在自顶向下的分析中应选择这样的产生式样的产生式A i(i可导出空串可导出空串)进行推导：进行推导：若若aFirst(i),则则A i可可选选因因 i可能导出空串，可能导出空串，A自动获得匹配，输入符自动获得匹配，输入符a有可能与有可能与A后的一个符号匹配，故当后的一个符号匹配，故当aFollow(A)时，产生式时，产生式A i亦可亦可选选结论一结论一针对无空产生式的文法针对无空产生式的文法G，同一非终结符的任两个，同一非终结符的任两个产生式的右部串的产生式的右部串的First集无交集，即可进行确定的集无交集，即可进行确定的自顶向下分析。自顶向下分析。结论二结论二例 文法G3S:SaA|d AbAS|SaA=Sd=AbAS=A=First(aA)=aFirst(d)=dFirst(bAS)=bFirst()+Follow(A)=+#,a,d=,#,a,d=#,a,d回顾回顾开始符号集开始符号集FIRST()的定义的定义n定义定义:设设G=(VN,VT,P,S)是上下文无关文法，是上下文无关文法，A(AVN,(VN VT)*)FIRST()=a|a VT且且*a.（若若*,则规定则规定FIRST()）直观上说文法符号串直观上说文法符号串 的开始符号集是由的开始符号集是由 推推导出的所有的终结符开头和可能的导出的所有的终结符开头和可能的组成。组成。回顾回顾后跟符号集后跟符号集FOLLOW(A)的定义的定义定义定义设设G=(VT,VN,P,S)是上下文无关文法，是上下文无关文法，Bx xAy y (A,BVNx,yx,y (VN VT)*)FOLLOW(A)=a|S=*Aa，aVT，若有若有S=*A，则规定则规定#FOLLOW(A)（注：（注：#输入串输入串#，#做为输入串的结束符）做为输入串的结束符）直观上说直观上说,非终结符非终结符A的后跟符号集是由句型中紧跟的后跟符号集是由句型中紧跟A后的那后的那些终结符（包括些终结符（包括#）组成。）组成。4.选择集合选择集合SELECT(A)的定义的定义n定义定义对给定的上下文无关文法的产生式对给定的上下文无关文法的产生式A(AVN，V*)若若*,则则SELECT(A)=FIRST()若若=*,则则SELECT(A)=(FIRST()-)FOLLOW(A)解释解释A的产生式的产生式A 1|2|3|(A面对应输入符面对应输入符a)在自顶向下的分析中：在自顶向下的分析中：对于对于A i且且 i*,若若aFirst(i),则则A i可可选选对于对于A j且且 j=*,若若a(First(j)-)Follow(A),则则A j可可选选例例G3S:SaASdAbASASELECT(SaA)=FIRST(aA)=aSELECT(Sd)=FIRST(d)=dSELECT(AbAS)=FIRST(bAS)=bSELECT(A)=(FIRST()-)+FOLLOW(A)=#,a,d若若*,则则SELECT(A)=FIRST()若若=*,则则SELECT(A)=(FIRST()-)FOLLOW(A)结论三结论三同一非终结符的不同产生式同一非终结符的不同产生式A与与A，若若SELECT(A)SELECT(A)=，则一定可则一定可以进行确定的自顶向下分析以进行确定的自顶向下分析5.LL(1)文法的定义文法的定义定义定义:上上下下文文无无关关文文法法为为LL(1)文文法法的的充充分分必必要要条条件件是是，对对每每个个非非终终结结符符A的的两两个个不不同同产产生生式式A与与A，满满足足SELECT(A)SELECT(A)=nLL(1)文法的含义是：文法的含义是：第一个第一个L从左到右扫描输入串从左到右扫描输入串第二个第二个L分析过程用最左推导分析过程用最左推导(1)表明只需向前看表明只需向前看1个输入符号便可以决定选个输入符号便可以决定选哪个产生式进行推导（类似地，哪个产生式进行推导（类似地，LL(k)文法则需要文法则需要向前看向前看k个输入符号才可以确定选用哪个产生式）个输入符号才可以确定选用哪个产生式）例例有文法有文法GS为：为：SaASSbAbAASELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b由于由于SELECT(AbA)SELECT(A)=b，所以所以文法文法GS不是不是LL(1)文法，当文法，当A遇输入符遇输入符b时，不能确时，不能确定选定选AbA还是还是A去推导。去推导。4.2LL(1)文法的判别文法的判别要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为五步：分为五步：1.求能推出求能推出的非终结符集的非终结符集2.计算每个产生式右部计算每个产生式右部的的FIRST()集集3.计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集4.计算每个产生式计算每个产生式A的的SELECT(A)集集5.按按LL(1)文法的定义判别文法的定义判别1.求出能推出求出能推出的非终结符集的非终结符集算法描述算法描述:用用T表示能推出表示能推出的非终结符集的非终结符集令令T=Aj|(Aj)产生式集产生式集对于产生式对于产生式ApA1.An若若A1.An T，则则T=T Ap重复重复，直至，直至T收敛（不再变化）为止收敛（不再变化）为止例例GS：SAB|bCAb|BaD|CAD|bDaS|cA,B,A,B,S S 第一次第一次 A,BA,B初值初值A,B,SA,B,S收敛收敛第二次第二次非终结符集非终结符集T T能推出能推出的非终结符集的非终结符集T为为A,B,S2.计算每个产生式右部计算每个产生式右部的的FIRST()集集对每个对每个a VT：First(a)=a对每个对每个A VN：若若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是产生式右部中第一个不能推出是产生式右部中第一个不能推出的符号的符号首先对首先对文法符号文法符号X(X VT VN)，求求FIRST(X):对每个产生式对每个产生式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|cbaacbacabbaFirst集集(3)baacbabbFirst集集(2)baFirst集集(1)ABCDabSabFirst集集(0)已求出能推出已求出能推出的非终结符集的非终结符集T为为A,B,Sbbabacaac（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）c（敛）（敛）ccccbaacbacabbaFirst集集(3)baacbabbFirst集集(2)baFirst集集(1)ABCDabSabFirst集集(0)bbabacaac（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）c（敛）（敛）cccc结论：文法符号的结论：文法符号的First集合如下集合如下:First(S)=a,b,First(A)=b,First(B)=a,First(C)=a,b,cFirst(D)=a,cFirst(a)=aFirst(b)=bFirst(c)=c利用求出利用求出每个文法符号每个文法符号的的FIRST集求集求符号串符号串的的FIRST集集设右部串设右部串=X1X2Xn1.当当X1*，则，则FIRST()=FIRST(X1)2.若对任何若对任何j(1jn）都有都有 FIRST(Xj)，Xj+1为为X1X2Xn中第一个推不出中第一个推不出的符号的符号，则，则3.FIRST()=(FIRST(X1)-)(FIRST(Xj)-)FIRST(Xj+1)3.若对所有若对所有i(1in)，都有都有 FIRST(Xi)，则则FIRST()=FIRST(X1)FIRST(Xn)FIRST(AB)=FIRST(A)FIRST(B)=a,b,FIRST(bC)=FIRST(b)=bFIRST()=FIRST(b)=bFIRST(AD)=(FIRST(A)-)FIRST(D)=b,a,cFIRST(aS)=FIRST(a)=a例例GS SAB|bCAb|BaD|CAD|bDaS|c已求出非终结符的已求出非终结符的First集合如下集合如下:First(S)=a,b,First(A)=b,First(B)=a,First(C)=a,b,cFirst(D)=a,c产生式右部产生式右部符号串符号串的开始符集合为的开始符集合为:SABSbCAAbCADDaS要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为五步：分为五步：1.求能推出求能推出的非终结符集的非终结符集T2.计算每个产生式右部计算每个产生式右部的的FIRST()集集3.计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集4.计算每个产生式计算每个产生式A的的SELECT(A)集集5.按按LL(1)文法的定义判别文法的定义判别要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为五步：分为五步：1.求能推出求能推出的非终结符集的非终结符集T2.计算每个产生式右部计算每个产生式右部的的FIRST()集集3.计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集4.计算每个产生式计算每个产生式A的的SELECT(A)集集5.按按LL(1)文法的定义判别文法的定义判别3计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集1.对所有对所有A VN，令令Follow(A)=(对开始符对开始符S，令令Follow(S)=#)因为因为S=*S，显然，显然#FOLLOW(S)2.对每条产生式对每条产生式BxAy，考察产生式右部的每一非终考察产生式右部的每一非终结符结符A，x,yV*，若若y*,则则Follow(A)=Follow(A)First(y)否则否则Follow(A)=Follow(A)(First(y)-)Follow(B)3.重复重复2，直至对所有，直至对所有A VN，Follow(A)收敛为止收敛为止若若a FOLLOW(B),则表明则表明S=*Ba，由于由于BxAy，且且y=*,则有则有S=*Ba=xAya=xAa，即即S=*xAa,所以所以a FOLLOW(A)例例GS：1SAB2SbC3Ab4A5BaD6B7CAD8Cb9DaS10Dc已求出已求出非终结符的非终结符的First集合如下集合如下:First(S)=a,b,First(A)=b,First(B)=a,First(C)=a,b,cFirst(D)=a,c#D#C#Ba#A#a#c#SFollow集集(2)Follow集集(1)Follow集集(0)c敛敛敛敛敛敛敛敛敛敛结论：结论：Follow(S)=#Follow(A)=a,c,#Follow(B)=#Follow(C)=#Follow(D)=#4计算每个产生式计算每个产生式A的的SELECT(A)集集按定义计算按定义计算SELECT(A)：若右部串若右部串*，则则SELECT(A)=FIRST()若右部串若右部串=*，则则SELECT(A)=(FIRST()-)FOLLOW(A)SELECT(SAB)SELECT(SbC)SELECT(A)SELECT(Ab)SELECT(BaD)SELECT(B)SELECT(CAD)SELECT(Cb)SELECT(DaS)SELECT(Dc)例例GS：SAB|bCAb|BaD|CAD|bDaS|c=*否？否？Follow集集S是是#A是是a,c,#B是是#C否否#D否否#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(B)=(FIRST()-）FOLLOW(B)=#SELECT(CAD)=FIRST(AD)=b,a,cSELECT(Cb)=FIRST(b)=bSELECT(DaS)=FIRST(aS)=aSELECT(Dc)=FIRST(c)=cFIRST(AB)=a,b,FIRST(bC)=bFIRST()=FIRST(b)=bFIRST(aD)=aFIRST(AD)=b,a,cFIRST(aS)=a5.按按LL(1)文法的定义判别文法的定义判别产生式的产生式的select集如下集如下:SELECT(SAB)=b,a,#SELECT(SbC)=bSELECT(A)=a,c,#SELECT(Ab)=bSELECT(B)=#SELECT(BaD)=aSELECT(CAD)=b,a,c SELECT(Cb)=bSELECT(DaS)=aSELECT(Dc)=c由于由于SELECT(SAB)SELECT(SbC)=bSELECT(CAD)SELECT(Cb)=b所以文法所以文法GS不是不是LL(1)文法文法对对每每个个非非终终结结符符A的的任任两两个个产产生生式式A与与A，满满足足SELECT(A)SELECT(A)=要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为五步：分为五步：1.求能推出求能推出的非终结符集的非终结符集T2.计算每个产生式右部计算每个产生式右部的的FIRST()集集3.计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集4.计算每个产生式计算每个产生式A的的SELECT(A)集集5.按按LL(1)文法的定义判别文法的定义判别go由每个产生式的由每个产生式的select集构造集构造LL(1)分析表分析表例例GS：SAB|bCAb|BaD|CAD|bDaS|c试判断该文法是否为试判断该文法是否为LL(1)文法文法?backA,B,A,B,S S 第一次第一次 A,BA,B初值初值A,B,SA,B,S收敛收敛第二次第二次非终结符集非终结符集T T能推出能推出的非终结符集的非终结符集T为为A,B,S1.求能推出求能推出的非终结符集的非终结符集Tback2.计算每个产生式右部计算每个产生式右部的的FIRST()集集FIRST(AB)=FIRST(A)FIRST(B)=a,b,FIRST(bC)=bFIRST()=FIRST(b)=bFIRST(AD)=(FIRST(A)-)FIRST(D)=b,a,cFIRST(aS)=aFIRST(aD)=abackbaacbacabbaFirst集集(3)baacbabbFirst集集(2)baFirst集集(1)ABCDabSabFirst集集(0)bbabacaac（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）（敛）c（敛）（敛）cccc3.计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集back#D#C#Ba#A#a#c#SFollow集集(2)Follow集集(1)Follow集集(0)c敛敛敛敛敛敛敛敛敛敛4.计算每个产生式计算每个产生式A的的SELECT(A)集集backSELECT(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(B)=(FIRST()-）FOLLOW(B)=#SELECT(CAD)=FIRST(AD)=(FIRST(A)-)FIRST(A)=b,a,cSELECT(Cb)=FIRST(b)=bSELECT(DaS)=FIRST(aS)=aSELECT(Dc)=FIRST(c)=cSELECT(SAB)=b,a,#SELECT(SbC)=bSELECT(A)=a,c,#SELECT(Ab)=bSELECT(B)=#SELECT(BaD)=aSELECT(CAD)=b,a,c SELECT(Cb)=bSELECT(DaS)=aSELECT(Dc)=c由每个产生式的由每个产生式的select集构造集构造LL(1)分析表分析表abc#SABCDSAB SABSABSbCAAAAbBaDBCADCADCbCADDaSDc5.按按LL(1)文法的定义判别文法的定义判别back根据根据LL(1)文法的定义判别文法的定义判别,由于由于 SELECT(SAB)SELECT(SbC)=bSELECT(CAD)SELECT(Cb)=b所以文法所以文法GS不是不是LL(1)文法文法习题习题判别文法判别文法GS是否为是否为LL(1)文法文法SaSb|PPbPPPc|QcQaQQaQ|First(2)First(1)PPQQSFirst(0)aFirst(P)(敛敛)b(敛敛)bFirst(Q)(敛敛)a(敛敛)a(敛敛)(1)(2)ab(敛敛)b(敛敛)ab(敛敛)a(敛敛)a(敛敛)ab(敛敛)ab(敛敛)First集集SabPbP abQaQ a习题习题判别文法判别文法GS是否为是否为LL(1)文法文法SaSb|PPbPPPc|QcQaQQaQ|(2)FIRST(aSb)=FIRST(a)=aFIRST(P)=bFIRST(bP)=FIRST(b)=bFIRST(Pc)=FIRST(P)=bFIRST(Qc)=FIRST(Q)=aFIRST(aQ)=FIRST(a)=aFIRST(aQ)=FIRST(a)=aFIRST()=First集集SabPbP abQaQ aFollow(2)Follow(1)PPQQS#Follow(0)#b(收敛收敛)#bc#bcc(收敛收敛)c(收敛收敛)(收敛收敛)(收敛收敛)习题习题判别文法判别文法GS是否为是否为LL(1)文法文法SaSb|PPbPPPc|QcQaQQaQ|(3)Follow集集S#bP#bcP#bcQcQ cFirst集集SabPbP abQaQ aSELECT(SaSb)=aSELECT(SP)=bSELECT(PbP)=bSELECT(PPc)=bSELECT(PQc)=aSELECT(QaQ)=aSELECT(QaQ)=aSELECT(Q)=c构造构造LL(1)分析表分析表根据根据LL(1)定义判断定义判断,文法文法GS是是LL(1)文法文法FIRST(aSb)=FIRST(a)=aFIRST(P)=bFIRST(bP)=FIRST(b)=bFIRST(Pc)=FIRST(P)=bFIRST(Qc)=FIRST(Q)=aFIRST(aQ)=FIRST(a)=aFIRST(aQ)=FIRST(a)=aFIRST()=Follow集集S#bP#bcP#bcQcQc(4)(5)abc#SSaSbSPPPbPPPQcPPcQQaQQQaQQLL(1)分分析析表表4.3非非LL(1)文法到文法到LL(1)文法的等价变换文法的等价变换n非非LL(1)文法文法含有含有左公共因子左公共因子的文法的文法若文法中含有形如：若文法中含有形如：A|r的产生式，称文法含的产生式，称文法含有左公共因子。有左公共因子。显然显然,SELECT(A)SELECT(Ar),文法文法不是不是LL(1)文法文法stmt if expr then stmt|if expr then stmt else stmt|other 句型句型ife1thenife2thens1elses2推导一推导一stmtife1thenstmt ife1thenife2thens1elses2悬空悬空else问题问题推导二推导二stmtife1thenstmt elses2 ife1thenife2thens1elses2stmt if expr then stmt|if expr then stmt else stmt|other stmtmatched_stmt|unmatched_stmtmatched_stmtifexprthenmatched_stmtelsematched_stmt|otherunmatched_stmtif exprthenstmt|ifexprthenmatched_stmtelseunmatched_stmt含有含有左递归左递归的文法的文法文文法法中中只只要要含含有有下下列列形形式式的的产产生生式式,则则称称文文法法含含有有左递归：左递归：a)AAb)AB BA在在a)中含有左递归的产生式，称为中含有左递归的产生式，称为直接左递归直接左递归在在b)中虽然没有含左递归的产生式，中虽然没有含左递归的产生式，但但A=B=A即即A=+A,称为称为间接左递归间接左递归以直接左递归为例，若有如下产生式以直接左递归为例，若有如下产生式AA|A 其中其中 和和 为任意语法符号串。为任意语法符号串。不难证明有下面关系式：不难证明有下面关系式：Select(AA)First(A)First()Select(A)First()故故AA 和和A 的的Select集集相交相交，不是不是LL(1)文法文法对非对非LL(1)文法进行等价变换文法进行等价变换提取左公共因子提取左公共因子消除左递归消除左递归注意：变换后的文法不一定是注意：变换后的文法不一定是LL(1)文法，文文法，文法不含左递归和左公共因子只是法不含左递归和左公共因子只是LL(1)文法的文法的必要条件必要条件1提取左公共因子提取左公共因子将产生式将产生式A|r等价变换为等价变换为:A(|r)，(|r)引入一新非终结符引入一新非终结符A表示表示,即得即得AAA|r一般形式：若一般形式：若A1|2|n|提取左公共因子提取左公共因子,即得即得AA|A1|2|n若在若在i中仍含有左公共因子中仍含有左公共因子,可再次提取可再次提取.例例文法文法G1：SaSb|aS|提取左因子得提取左因子得:SaS(b|)|引进新非终结符引进新非终结符S,得得:SaSS|Sb|2.消除左递归消除左递归1)消除直接左递归消除直接左递归文法文法G:SSa|b可改写成可改写成SbSSaS|一般情形一般情形:含直接左递归的文法含直接左递归的文法G：AA1|A2|Am|1|2|n消除左递归后改写成：消除左递归后改写成：A1A|2A|nAA1A|2A|mA|2)消除间接左递归消除间接左递归将间接左递归变成直接左递归，再消除将间接左递归变成直接左递归，再消除算法步骤：算法步骤：1.把文法的所有非终结符按任一顺序排列，把文法的所有非终结符按任一顺序排列，如：如：A1，A2，Ai，Ak，An2.从从A1开始，按以下顺序处理开始，按以下顺序处理Ak消除左部为消除左部为Ak的产生式的直接左递归的产生式的直接左递归若若左左部部为为Ak的的产产生生式式的的右右部部为为非非终终结结符符Ai(i*，且，且Follow(A)First(bAS)=b，从而引起回溯，从而引起回溯例例3文法文法G：SSaSb输入串输入串w=baa，推导树为推导树为:SSabSbSSa回溯回溯回溯回溯SSaSaSSaSab由于文法含有左递归而引起回溯由于文法含有左递归而引起回溯4.5确定的自顶向下分析方法确定的自顶向下分析方法确定的自顶向下分析方法有：确定的自顶向下分析方法有：LL(1)预测分析器预测分析器(predictiveparser)LL(1)递递 归归 子子 程程 序序 分分 析析 器器(recursive-descentparser)两种方法都要求文法是两种方法都要求文法是LL(1)文法文法4.5确定的自顶向下分析方法确定的自顶向下分析方法确定的自顶向下分析方法有：确定的自顶向下分析方法有：LL(1)预测分析器预测分析器(predictiveparser)LL(1)递递 归归 子子 程程 序序 分分 析析 器器(recursive-descentparser)两种方法都要求文法是两种方法都要求文法是LL(1)文法文法4.5.1LL(1)预测分析器预测分析器一个预测分析器由三个部分组成：一个预测分析器由三个部分组成：n预测分析程序：预测分析程序：控制分析过程的进行。控制分析过程的进行。n分析栈：分析栈：存放从文法开始符号出发的自顶向下推存放从文法开始符号出发的自顶向下推导过程中导过程中等待匹配等待匹配的文法符号。开始时放入的文法符号。开始时放入#和文法开始符，结束时栈应是空的。和文法开始符，结束时栈应是空的。n预测分析表：预测分析表：是一个二维表，元素是一个二维表，元素MA,a的内容的内容是当非终结符是当非终结符A面临输入符号面临输入符号a（终结符或）时终结符或）时应选取的应选取的产生式产生式；当无产生式时，元素；当无产生式时，元素MA,a为为出错处理出错处理(error)。1.构造预测分析表构造预测分析表步骤：步骤：(1)把文法转变为把文法转变为LL(1)文法文法(2)求出每条产生式的求出每条产生式的SELECT集集(3)依照依照SELECT集把产生式填入分析表集把产生式填入分析表l横坐标横坐标终结符与终结符与l纵坐标纵坐标非终结符非终结符l交点交点MA,an(A)放入放入MA,a若若a SELECT(A)n无产生式的无产生式的MA,a标记出错标记出错例例算术表达式文法算术表达式文法GEE+TTTT*FFF(E)i（1）消除）消除G的左递归得到文法的左递归得到文法GETEE+TETFTT*FTF(E)i（2）求出每个产生式的求出每个产生式的select集集,G是是LL(1)文法文法SELECT(ETE)=(,iSELECT(E+TE)=+SELECT(E)=),#SELECT(TFT)=(,iSELECT(T*FT)=*SELECT(T)=+,),#SELECT(F(E)=(SELECT(Fi)=iF(E)(E)Fi iFTTT*FTFTTTTFTFTTFTFTTEEE+TEEE#）（*+iETEETE（3 3）依照选择集合把产生式填入分析表）依照选择集合把产生式填入分析表注：表中空白处为出错注：表中空白处为出错2.预测分析程序预测分析程序上托栈顶符放入上托栈顶符放入XNYYNNNNYYY把把#和和文文法法开开始始符符S压压入入分分析析栈栈；当前输入符送当前输入符送a把把产产生生式式右右部部反序反序进栈进栈XVT?X=#?X=a?X=a?读读下下一一输输入入符到符到aMX,a有产生式？有产生式？出错出错结束结束出错出错预测分析程序工作过程预测分析程序工作过程3.输入串输入串i+i*i#的分析过程的分析过程i+*（）#EETEETEEE+TEEETTFTFTTFTFTTTT*FTFTTTFFi iF(E)(E)+匹配匹配+i*i#ET+7E+TE+i*i#E6T+i*i#ET5i匹配匹配i+i*i#ETi4Fii+i*i#ETF3TFTi+i*i#ET2ETEi+i*i#E1所用产生式所用产生式剩余输入串剩余输入串分析栈分析栈步骤步骤TFTi*i#ET8Fii#ETF13i匹配匹配i#ETi14T#ET15E#E16接受接受#17*匹配匹配*i#ETF*12T*FT*FT*i#ET11i匹配匹配i*i#ETi10Fii*i#ETF9i+*（）#EETEETEEE+TEEETTFTFTTFTFTTTT*FTFTTTFFi iF(E)(E)4.5.2递归子程序法递归子程序法(第三次实验第三次实验)1实现思想实现思想对对文文法法中中的的每每个个非非终终结结符符编编写写一一个个递递归归过过程程，识识别别由由该该非非终终结结符符推推出出的的串串。当当非非终终结结符符有有多多个个产产生生式式时时，按按当当前前输输入入符符属属于于哪哪个个产产生生式式的的SELECT集可唯一确定选择哪个产生式进行匹配。集可唯一确定选择哪个产生式进行匹配。当识别到终结符时，与当前输入符号匹配，并读取下一当识别到终结符时，与当前输入符号匹配，并读取下一输入符；输入符；当识别到非终结符时，则调用该非终结符相应的过程。当识别到非终结符时，则调用该非终结符相应的过程。定义定义当一个文法满足当一个文法满足LL(1)条件时，就为它构造条件时，就为它构造一个不带回溯的自顶向下