编译原理自顶向下语法分析方法.pptx
学习目标:掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法理解：LL（1）文法了解：不确定的自顶向下分析第1页/共101页语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子语法分析自顶向下分析自底向上分析确定的不确定的算法优先分析（第六章）LR分析（第五章）自顶向下基本思想:从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子.分类:第2页/共101页回顾自上而下的分析方法q定义:从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。q语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。q自上而下分析的主要问题选定产生式第3页/共101页例文法G：S cAdA abA a识别输入串w=cabd是否为该文法的句子ScAdab=cabdS=cAd回顾自上而下的分析方法ScA da成功不成功=cadS=cAd第4页/共101页4.1确定的自顶向下分析思想4.2LL(1)文法的判别4.3某些非LL(1)文法到LL(1)文法的等价变换4.4不确定的自顶向下分析思想4.5确定的自顶向下分析方法本章内容第5页/共101页4.1确定的自顶向下分析思想1确定分析的条件2开始符号集FIRST()的定义3后跟符号集FOLLOW(A)的定义4选择集合SELECT(A)的定义5LL(1)文法的定义第6页/共101页1.确定分析的条件从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。第7页/共101页例1设有文法G1S:SpA|qBAcAd|aBdB|b若输入串W=pccadd。自顶向下的推导过程为:SSApcAdcAda=pA=pcAd=pccAdd=pccaddG1S有如下特点：(1)每个产生式的右部由终结符开头;(2)同一非终结符的不同产生式的右部由不同的终结符开头。对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。第8页/共101页例2：设有文法G2S为:SAp|BqAa|cABb|dBpAScAcAa=ccapS=cAp=ccAp=Ap该例说明，当(1)产生式右部以终结符或非终结符开头（无空产生式）；(2)同一非终结符的不同产生式的右部由不同的符号开头。若输入串W=ccap,自顶向下的推导过程为：对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集），分析过程可能是确定的第9页/共101页例3：设有文法G3SSaA|dAbAS|若输入串W=abd，自顶向下的推导过程为：AaSbSA d=abdS=abAS=abS文法的特点包含空产生式=aA对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。第10页/共101页要进行确定的自顶向下的分析，文法要满足一定的限制即文法是LL(1)文法先研究三个定义开始符号集FIRST后跟符号集FOLLOW选择集合SELECT第11页/共101页2.开始符号集FIRST()的定义定义:设G=(VN,VT,P,S)是上下文无关文法，(VN,(VNVT)*)FIRST()=a|aVT且*a.（若*则规定FIRST()）直观上说文法符号串的开始符号集是由推导出的所有的终结符开头和可能的组成。第12页/共101页例文法G2S:SApSBqAaAcABbBdBFIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=aFIRST(cA)=cFIRST(b)=bFIRST(dB)=d结论一 针对无空产生式的文法G，同一非终结符的任两个产生式的右部串的First集无交集，即可进行确定的自顶向下分析。第13页/共101页3.后跟符号集FOLLOW(A)的定义定义设G=(VT,VN,P,S)是上下文无关文法，BxAy (A,BVNx,y(VNVT)*)FOLLOW(A)=a|S=*Aa，aVT，若有S=*A，则规定#FOLLOW(A)（注：#输入串#，#做为输入串的结束符）直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。第14页/共101页例文法G3S:SaA|dAbAS|由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)第15页/共101页解释当A面对应输入符a，在自顶向下的分析中应选择这样的产生式Ai(i可导出空串)进行推导：若aFirst(i),则Ai可选因i可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，故当aFollow(A)时，产生式Ai亦可选结论一 针对无空产生式的文法G，同一非终结符的任两个产生式的右部串的First集无交集，即可进行确定的自顶向下分析。结论二第16页/共101页例文法G3S:SaA|dAbAS|SaA=Sd=AbAS=A=First(aA)=aFirst(d)=dFirst(bAS)=bFirst()+Follow(A)=+#,a,d=,#,a,d=#,a,d第17页/共101页回顾开始符号集FIRST()的定义定义:设G=(VN,VT,P,S)是上下文无关文法，A(AVN,(VNVT)*)FIRST()=a|aVT且*a.（若*,则规定FIRST()）直观上说文法符号串的开始符号集是由推导出的所有的终结符开头和可能的组成。第18页/共101页回顾后跟符号集FOLLOW(A)的定义定义设G=(VT,VN,P,S)是上下文无关文法，BxAy (A,BVNx,y(VNVT)*)FOLLOW(A)=a|S=*Aa，aVT，若有S=*A，则规定#FOLLOW(A)（注：#输入串#，#做为输入串的结束符）直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。第19页/共101页4.选择集合SELECT(A)的定义定义对给定的上下文无关文法的产生式A(AVN，V*)若*,则SELECT(A)=FIRST()若=*,则SELECT(A)=(FIRST()-)FOLLOW(A)第20页/共101页解释A的产生式A1|2|3|(A面对应输入符a)在自顶向下的分析中：对于Ai且i*,若aFirst(i),则Ai可选对于Aj且j=*,若a(First(j)-)Follow(A),则Aj可选第21页/共101页例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)第22页/共101页结论三同一非终结符的不同产生式A与A，若SELECT(A)SELECT(A)=，则一定可以进行确定的自顶向下分析第23页/共101页5.LL(1)文法的定义定义:上下文无关文法为LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A与A，满足SELECT(A)SELECT(A)=LL(1)文法的含义是：第一个L从左到右扫描输入串第二个L分析过程用最左推导(1)表明只需向前看1个输入符号便可以决定选哪个产生式进行推导（类似地，LL(k)文法则需要向前看k个输入符号才可以确定选用哪个产生式）第24页/共101页例有文法GS为：SaASSbAbAASELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b由于SELECT(AbA)SELECT(A)=b，所以文法GS不是LL(1)文法，当A遇输入符b时，不能确定选AbA还是A去推导。第25页/共101页4.2LL(1)文法的判别要判别一个上下文无关文法是否是LL(1)文法分为五步：1.求能推出的非终结符集2.计算每个产生式右部的FIRST()集3.计算每个非终结符A的FOLLOW(A)集4.计算每个产生式A的SELECT(A)集5.按LL(1)文法的定义判别第26页/共101页1.求出能推出的非终结符集算法描述:用T表示能推出的非终结符集令T=Aj|(Aj)产生式集对于产生式ApA1.An若A1.AnT，则T=TAp重复，直至T收敛（不再变化）为止第27页/共101页例GS：SAB|bCAb|BaD|CAD|bDaS|cA,B,S第一次A,B初值A,B,S收敛第二次非终结符集T能推出的非终结符集T为A,B,S第28页/共101页2.计算每个产生式右部的FIRST()集对每个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是产生式右部中第一个不能推出的符号首先对文法符号X(XVT VN)，求FIRST(X):第29页/共101页对每个产生式 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集合都不再增大为止第30页/共101页例GS:SAB|bCAb|BaD|CAD|bDaS|cbaa cb a c a b b aFirst集(3)baa cb a b bFirst集(2)ba First集(1)ABCDabSabFirst集(0)已求出能推出的非终结符集T为A,B,Sbbaba caa c（敛）（敛）（敛）（敛）（敛）（敛）（敛）c（敛）cccc第31页/共101页baa cb a c a b b aFirst集(3)baa cb a b bFirst集(2)ba First集(1)ABCDabSabFirst集(0)bbaba caa c（敛）（敛）（敛）（敛）（敛）（敛）（敛）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第32页/共101页利用求出每个文法符号的FIRST集求符号串的FIRST集设右部串=X1X2Xn1.当X1*，则FIRST()=FIRST(X1)2.若对任何j(1jn）都有FIRST(Xj)，Xj+1为X1X2Xn中第一个推不出的符号，则FIRST()=(FIRST(X1)-)(FIRST(Xj)-)FIRST(Xj+1)3.若对所有i(1in)，都有FIRST(Xi)，则FIRST()=FIRST(X1)FIRST(Xn)第33页/共101页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第34页/共101页要判别一个上下文无关文法是否是LL(1)文法分为五步：1.求能推出的非终结符集T2.计算每个产生式右部的FIRST()集3.计算每个非终结符A的FOLLOW(A)集4.计算每个产生式A的SELECT(A)集5.按LL(1)文法的定义判别第35页/共101页要判别一个上下文无关文法是否是LL(1)文法分为五步：1.求能推出的非终结符集T2.计算每个产生式右部的FIRST()集3.计算每个非终结符A的FOLLOW(A)集4.计算每个产生式A的SELECT(A)集5.按LL(1)文法的定义判别第36页/共101页3计算每个非终结符A的FOLLOW(A)集1.对所有AVN，令Follow(A)=(对开始符S，令Follow(S)=#)因为S=*S，显然#FOLLOW(S)2.对每条产生式BxAy，考察产生式右部的每一非终结符A，x,y V*，若y *,则Follow(A)=Follow(A)First(y)否则 Follow(A)=Follow(A)(First(y)-)Follow(B)3.重复2，直至对所有AVN，Follow(A)收敛为止若aFOLLOW(B),则表明S=*Ba，由于BxAy，且y=*,则有S=*Ba=xAya=xAa，即S=*xAa,所以aFOLLOW(A)第37页/共101页例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)=#第38页/共101页4计算每个产生式A的SELECT(A)集按定义计算SELECT(A)：若右部串*，则SELECT(A)=FIRST()若右部串=*，则SELECT(A)=(FIRST()-)FOLLOW(A)第39页/共101页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)=a第40页/共101页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)文法对每个非终结符A的任两个产生式A与A，满足SELECT(A)SELECT(A)=第41页/共101页要判别一个上下文无关文法是否是LL(1)文法分为五步：1.求能推出的非终结符集T2.计算每个产生式右部的FIRST()集3.计算每个非终结符A的FOLLOW(A)集4.计算每个产生式A的SELECT(A)集5.按LL(1)文法的定义判别go由每个产生式的select集构造LL(1)分析表第42页/共101页例GS：SAB|bCAb|BaD|CAD|bDaS|c试判断该文法是否为LL(1)文法?back第43页/共101页A,B,S第一次A,B初值A,B,S收敛第二次非终结符集T能推出的非终结符集T为A,B,S1.求能推出的非终结符集Tback第44页/共101页2.计算每个产生式右部的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)=abackbaa cb a c a b b aFirst集(3)baa cb a b bFirst集(2)ba First集(1)ABCDabSabFirst集(0)bbaba caa c（敛）（敛）（敛）（敛）（敛）（敛）（敛）c（敛）cccc第45页/共101页3.计算每个非终结符A的FOLLOW(A)集back#D#C#Ba#A#a#c#SFollow集(2)Follow集(1)Follow集(0)c敛敛敛敛敛第46页/共101页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)=c第47页/共101页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集构造LL(1)分析表abc#SABCDSABSABSABSbCAAAAbBaDBCADCADCbCADDaSDc第48页/共101页5.按LL(1)文法的定义判别back根据LL(1)文法的定义判别,由于 SELECT(SAB)SELECT(SbC)=bSELECT(CAD)SELECT(Cb)=b所以文法GS不是LL(1)文法第49页/共101页习题判别文法GS是否为LL(1)文法SaSb|PPbPPPc|QcQaQQaQ|First(2)First(1)PPQQSFirst(0)aFirst(P)(敛)b(敛)bFirst(Q)(敛)a(敛)a(敛)(1)(2)a b(敛)b (敛)a b(敛)a (敛)a(敛)a b(敛)a b(敛)First集集Sa b PbP a b QaQ a第50页/共101页习题判别文法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集集Sa b PbP a b QaQ a第51页/共101页Follow(2)Follow(1)PPQQS#Follow(0)#b (收敛)#b c#b cc (收敛)c(收敛)(收敛)(收敛)习题判别文法GS是否为LL(1)文法SaSb|PPbPPPc|QcQaQQaQ|(3)Follow集集S#b P#b cP#b cQcQ cFirst集集Sa b PbP a b QaQ a第52页/共101页 SELECT(SaSb)=a SELECT(SP)=b SELECT(PbP)=b SELECT(PPc)=b SELECT(PQc)=a SELECT(QaQ)=a SELECT(QaQ)=a SELECT(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#b P#b cP#b cQcQc(4)(5)abc#SSaSbSPPPbP PPQcPPcQQaQQQaQQLL(1)分析表第53页/共101页4.3非LL(1)文法到LL(1)文法的等价变换非LL(1)文法含有左公共因子的文法若文法中含有形如：A|r的产生式，称文法含有左公共因子。显然,SELECT(A)SELECT(Ar),文法不是LL(1)文法第54页/共101页stmt if expr then stmt|if expr then stmt else stmt|other 句型 if e1 then if e2 then s1 else s2推导一stmt if e1 then stmt if e1 then if e2 then s1 else s2悬空 else 问题推导二stmt if e1 then stmt else s2 if e1 then if e2 then s1 else s2第55页/共101页stmt if expr then stmt|if expr then stmt else stmt|other stmt matched _stmt|unmatched_stmtmatched_stmt if expr then matched_stmt else matched_stmt|otherunmatched_stmt if expr then stmt|if expr then matched_stmt else unmatched_stmt第56页/共101页含有左递归的文法文法中只要含有下列形式的产生式,则称文法含有左递归：a)AAb)AB BA在a)中含有左递归的产生式，称为直接左递归在b)中虽然没有含左递归的产生式，但A=B=A 即A=+A,称为间接左递归第57页/共101页以直接左递归为例，若有如下产生式AA|A其中和为任意语法符号串。不难证明有下面关系式：Select(AA)First(A)First()Select(A)First()故AA和A的Select集相交，不是LL(1)文法第58页/共101页对非LL(1)文法进行等价变换提取左公共因子消除左递归注意：变换后的文法不一定是LL(1)文法，文法不含左递归和左公共因子只是LL(1)文法的必要条件第59页/共101页1提取左公共因子将产生式A|r等价变换为:A(|r)，(|r)引入一新非终结符A表示,即得AAA|r一般形式：若A1|2|n|提取左公共因子,即得AA|A1|2|n若在i中仍含有左公共因子,可再次提取.第60页/共101页例文法G1：SaSb|aS|提取左因子得:SaS(b|)|引进新非终结符S,得:SaSS|Sb|第61页/共101页2.消除左递归1)消除直接左递归文法G:SSa|b可改写成SbSSaS|一般情形:含直接左递归的文法G：AA1|A2|Am|1|2|n消除左递归后改写成：A1A|2A|nAA1A|2A|mA|第62页/共101页2)消除间接左递归将间接左递归变成直接左递归，再消除算法步骤：1.把文法的所有非终结符按任一顺序排列，如：A1，A2，Ai，Ak，An2.从A1开始，按以下顺序处理Ak消除左部为Ak的产生式的直接左递归若左部为Ak的产生式的右部为非终结符Ai(i*，且Follow(A)First(bAS)=b，从而引起回溯第74页/共101页例3文法G：SSaSb输入串w=baa，推导树为:SSabSbSSa回溯回溯SSaSaSSaSab由于文法含有左递归而引起回溯第75页/共101页4.5确定的自顶向下分析方法确定的自顶向下分析方法有：LL(1)预测分析器(predictiveparser)LL(1)递归子程序分析器(recursive-descentparser)两种方法都要求文法是LL(1)文法第76页/共101页4.5确定的自顶向下分析方法确定的自顶向下分析方法有：LL(1)预测分析器(predictiveparser)LL(1)递归子程序分析器(recursive-descentparser)两种方法都要求文法是LL(1)文法第77页/共101页预测分析器一个预测分析器由三个部分组成：预测分析程序：控制分析过程的进行。分析栈：存放从文法开始符号出发的自顶向下推导过程中等待匹配的文法符号。开始时放入#和文法开始符，结束时栈应是空的。预测分析表：是一个二维表，元素MA,a的内容是当非终结符A面临输入符号a（终结符或）时应选取的产生式；当无产生式时，元素MA,a为出错处理(error)。第78页/共101页1.构造预测分析表步骤：(1)把文法转变为LL(1)文法(2)求出每条产生式的SELECT集(3)依照SELECT集把产生式填入分析表横坐标终结符与纵坐标非终结符交点MA,a(A)放入MA,a若aSELECT(A)无产生式的MA,a标记出错第79页/共101页例算术表达式文法GEE+TTTT*FFF(E)i（1）消除G的左递归得到文法GETEE+TETFTT*FTF(E)i第80页/共101页（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)F iFT T T*FTT TTFTT FTTE E E+TEEE#）（*+iETEETE（3）依照选择集合把产生式填入分析表注：表中空白处为出错第81页/共101页2.预测分析程序上托栈顶符放入XNYYNNNN YY Y把#和文法开始符S压入分析栈；当前输入符送a把产生式右部反序进栈XVT?X=#?X=a?X=a?读下一输入符到aMX,a有产生式？出错结束出错预测分析程序工作过程第82页/共101页3.输入串i+i*i#的分析过程i+*（）#EETEETEEE+TEE E TT FTFTT FTFTTT T*FTFTT T FF i 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所用产生式剩余输入串分析栈步骤第83页/共101页TFTi*i#ET8Fii#ETF13i匹配i#ETi14T#ET15E#E16接受#17*匹配*i#ETF*12T*FT*i#ET11i匹配i*i#ETi10Fii*i#ETF9i+*（）#EETEETEEE+TEE E TT FTFTT FTFTTT T*FTFTT T FF i iF(E)(E)第84页/共101页递归子程序法(第三次实验)1实现思想对文法中的每个非终结符编写一个递归过程，识别由该非终结符推出的串。当非终结符有多个产生式时，按当前输入符属于哪个产生式的SELECT集可唯一确定选择哪个产生式进行匹配。当识别到终结符时，与当前输入符号匹配，并读取下一输入符；当识别到非终结符时，则调用该非终结符相应的过程。第85页/共101页定义当一个文法满足LL(1)条件时，就为它构造一个不带回溯的自顶向下的分析程序u这个分析程序由一组递归过程组成u每个过程对应文法的一个非终结符这样的一个分析程序称为递归下降分析器2 构造文法G的递归下降分析器第86页/共101页组成：递归下降分析器由一个主程序main和每个非终结符对应的一个递归过程组成。用到的一些子过程：过程getnext负责读入下一个TOKEN字过程error()负责报告语法错误约定：变量TOKEN存放已读入的TOKEN字过程进入时变量TOKEN存放了一个待匹配的TOKEN字退出过程时，变量TOKEN中仍存放着一个待匹配的TOKEN字。第87页/共101页非终结符相应的分析子程序的构造方法 对于每个非终结符U，编写一个相应的子程序P(U)对于产生式Ux1|x2|xn(x1,.,xn)关于U的子程序P(U)按如下方法构造：if(TOKEN first(x1)p(x1);else if(TOKEN first(x2)p(x2);else if(TOKEN first(xn)p(xn);else ERROR();第88页/共101页3)如果U还有空产生式U,则算法中的语句：if(TOKEN first(xn)p(xn)else ERROR();改写为if(TOKEN first(xn)p(xn);else if(TOKEN follow(U)ERROR();4)对于符号串x=y1y2yn p(x)的含义为：main()p(y1);p(y2);p(yn);如yiVN，则P(yi)就代表调用yi的子程序；如yiVT，则P(yi)为如下述代码if(TOKEN=yi)getnext(TOKEN);else ERROR();第89页/共101页例算术表达式文法GEE+TTTT*FFF(E)i1）消除左递归得 G:ETE E+TE TFT T*FTF(E)i2）求出G的选择集合SELECT(ETE)=(,iSELECT(E+TE)=+SELECT(E)=),#SELECT(TFT)=(,iSELECT(T*FT)=*SELECT(T)=+,),#SELECT(F(E)=(SELECT(Fi)=iG是LL(1)文法1 判断是否可以应用递归子程序法第90页/共101页(1)chTOKEN;main()/*主程序*/getnext(TOKEN);E(TOKEN);/*转匹配ETE*/if(TOKEN!=#)ERROR();构造文法G：ETEE+TETFTT*FT F(E)i的递归下降分析器(2)E(TOKEN)/*匹配ETE*/T(TOKEN);/*转匹配TFT*/E(TOKEN);/*转匹配E+TE*/第91页/共101页(3)E(TOKEN)/*匹配E+TE*/if (TOKEN=+)/*选择产生式E+TE*/getnext(TOKEN);/*匹配+,读入下一个Token字*/T(TOKEN);/*转匹配TFT*/E(TOKEN);/*转 匹 配E+TE*/else/*E对应的语句*/if(TOKEN!=)&(TOKEN!=#)ERROR();构造文法G：ETEE+TETFTT*FT F(E)i的递归下降分析器第92页/共101页(4)T(TOKEN)/*匹配TFT*/F(TOKEN);/*转匹配F(E)i*/T(TOKEN);/*转匹配T*FT*/构造文法G：ETEE+TETFTT*FT F(E)i的递归下降分析器第93页/共101页(5)T(TOKEN)/*匹配T*FT*/if(TOKEN=*)/*选择产生式T*FT*/getnext(TOKEN);/*匹配*，读下一TOKEN字*/F(TOKEN);/*转匹配F(E)i*/T(TOKEN);/*转匹配T*FT*/else/*T对应的语句*/if(TOKEN!=+)&(TOKEN!=)&(TOKEN!=#)ERROR();构造文法G：ETEE+TETFTT*FT F(E)i的递归下降分析器第94页/共101页(6)F(TOKEN)/*匹配F(E)i*/if (TOKEN=()/*选择产生式F(E)*/getnext(TOKEN);/*匹配(，读下一TOKEN字*/E(TOKEN);/*转匹配ETE*/if(TOKEN=)getnext(TOKEN);/*匹配),读下一TOKEN字*/else ERROR();else /*选择产生式Fi */if (TOKEN=i)getnext(TOKEN);else ERROR();构造文法G：ETEE+TETFTT*FT F(E)i的递归下降分析器第95页/共101页特点：优点：简单直观、易于构造缺点：对文法要求高，必须满足LL(1)文法；递归调用多，速度慢，占用空间多实用性：许多高级语言，如Pascal、c等编译系统常常采用此方法。第96页/共101页实验三语法分析实验目的设计编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，加深对构造自顶向下的语法分析器的原理和技术理解与应用。第97页/共101页实验三语法分析实验要求利用C语言编制递归下降分析程序，并对C语言的简单子集进行分析。设计语言文法，运用递归下降分析技术，设计和实现语法分析器。具有出错处理功能。待分析的C语言子集的语法，以扩充的BNF方法描述如下：第98页/共101页(1)main()(2)(3);|(4)|(5)ID=(6)if()|if()else(7)while(8)|（）|ii|i(9)+|*|()|i(10)|=|=|!=第99页/共101页本章小结q两种自顶向下分析方法：递归子程序法预测分析法q一种文法：LL(1)文法判别方法非LL(1)到LL(1)的转换第100页/共101页感谢您的观看。第101页/共101页
