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

第四章 自顶向下语法分析方法,学习目标:掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法理解：LL（1）文法了解：不确定的自顶向下分析,语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子,自顶向下基本思想:从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子.,分类:,回顾自上而下的分析方法,定义:从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。自上而下分析的主要问题 选定产生式,例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,S,=cabd,S,=cAd,回顾自上而下的分析方法,S,成功,不成功,=cad,S,=cAd,4.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)的定义5 LL(1)文法的定义,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,对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。,要进行确定的自顶向下的分析，文法要满足一定的限制即文法是LL(1)文法先研究三个定义开始符号集FIRST后跟符号集FOLLOW选择集合SELECT,2.开始符号集FIRST()的定义,定义:设G=(VN,VT,P,S)是上下文无关文法，(VN,(VNVT)*)FIRST()=a|a VT 且*a.（若*则规定 FIRST()）直观上说文法符号串 的开始符号集是由推导出的所有的终结符开头和可能的组成。,例文法G2S:,SApSBqAaAcABbBdB,FIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=a FIRST(cA)=cFIRST(b)=bFIRST(dB)=d,结论一 针对无空产生式的文法G，同一非终结符的任两个产生式的右部串的First集无交集，即可进行确定的自顶向下分析。,3.后跟符号集FOLLOW(A)的定义,定义 设G=(VT,VN,P,S)是上下文无关文法，BxAy(A,B VN x,y(VNVT)*)FOLLOW(A)=a|S=*Aa，a VT，若有S=*A，则规定#FOLLOW(A)（注：#输入串#，#做为输入串的结束符）直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。,例 文法G3S:SaA|d AbAS|,由 S=*S 得#FOLLOW(S)由S=aA=abAS=abbASS=abbASaA 得 a FOLLOW(S)=abbASd 得 d FOLLOW(S)FOLLOW(S)=#,a,d,由S=*aA 得#FOLLOW(A)由S=*abAS=*abAaA 得 a FOLLOW(A)=*abAd 得 d FOLLOW(A)FOLLOW(A)=#,a,d,FOLLOW(A),FOLLOW(S),解释当A面对应输入符a，在自顶向下的分析中应选择这样的产生式Ai(i可导出空串)进行推导：若a First(i),则 Ai 可选因 i 可能导出空串，A自动获得匹配，输入符a有可能与A 后的一个符号匹配，故当 a Follow(A)时，产生式A i 亦可选,结论一 针对无空产生式的文法G，同一非终结符的任两个产生式的右部串的First集无交集，即可进行确定的自顶向下分析。,结论二,例 文法G3S:SaA|d AbAS|,SaA=,Sd=,AbAS=,A=,First(aA)=a,First(d)=d,First(bAS)=b,First()+Follow(A)=+#,a,d=,#,a,d,=#,a,d,回顾开始符号集FIRST()的定义,定义:设G=(VN,VT,P,S)是上下文无关文法，A(AVN,(VNVT)*)FIRST()=a|a VT 且*a.（若*,则规定FIRST()）直观上说文法符号串 的开始符号集是由推导出的所有的终结符开头和可能的组成。,回顾后跟符号集FOLLOW(A)的定义,定义 设G=(VT,VN,P,S)是上下文无关文法，BxAy(A,B VN x,y(VNVT)*)FOLLOW(A)=a|S=*Aa，a VT，若有S=*A，则规定#FOLLOW(A)（注：#输入串#，#做为输入串的结束符）直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。,4.选择集合SELECT(A)的定义,定义对给定的上下文无关文法的产生式 A(AVN，V*)若*,则SELECT(A)=FIRST()若=*,则SELECT(A)=(FIRST()-)FOLLOW(A),解释 A的产生式A1|2|3|(A面对应输入符a)在自顶向下的分析中：对于A i且 i*,若a First(i),则Ai可选对于A j且 j=*,若a(First(j)-)Follow(A),则A j可选,例 G3S:SaA Sd AbAS A,SELECT(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)=LL(1)文法的含义是：第一个L从左到右扫描输入串第二个L分析过程用最左推导(1)表明只需向前看 1 个输入符号便可以决定选哪个产生式进行推导（类似地，LL(k)文法则需要向前看 k 个输入符号才可以确定选用哪个产生式）,例 有文法GS为：SaAS SbAbAA,SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b,由于SELECT(AbA)SELECT(A)=b，所以文法GS不是LL(1)文法，当A遇输入符b时，不能确定选AbA还是A去推导。,4.2 LL(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.AnT，则 T=T Ap 重复，直至T 收敛（不再变化）为止,例GS：SAB|bCAb|BaD|CAD|b DaS|c,非终结符集T,能推出的非终结符集T为A,B,S,2.计算每个产生式右部的FIRST()集,对每个a VT：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):,对每个产生式 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|bC Ab|BaD|CAD|b DaS|c,First集(3),First集(2),First集(1),A,B,C,D,a,b,S,First集(0),已求出能推出的非终结符集T为A,B,S,b,b,a,b,a c,a,a c,（敛）,（敛）,（敛）,（敛）,（敛）,（敛）,（敛）,c,（敛）,c,c,c,c,结论：文法符号的First集合如下:First(S)=a,b,First(A)=b,First(B)=a,First(C)=a,b,c First(D)=a,c First(a)=a First(b)=b First(c)=c,利用求出每个文法符号的FIRST集求符号串的FIRST集,设右部串=X1X2Xn当X1*，则FIRST()=FIRST(X1)若对任何j(1jn）都有FIRST(Xj)，Xj+1为X1X2Xn中第一个推不出的符号，则 FIRST()=(FIRST(X1)-)(FIRST(Xj)-)FIRST(Xj+1)若对所有i(1in)，都有FIRST(Xi)，则 FIRST()=FIRST(X1)FIRST(Xn),FIRST(AB)=FIRST(A)FIRST(B)=a,b,FIRST(bC)=FIRST(b)=b FIRST()=FIRST(b)=b FIRST(AD)=(FIRST(A)-)FIRST(D)=b,a,c FIRST(aS)=FIRST(a)=a,例GSSAB|bC Ab|BaD|CAD|b DaS|c,已求出非终结符的First集合如下:First(S)=a,b,First(A)=b,First(B)=a,First(C)=a,b,cFirst(D)=a,c,产生式右部符号串的开始符集合为:SABSbCAAbCADDaS,要判别一个上下文无关文法是否是LL(1)文法分为五步：1.求能推出的非终结符集T 2.计算每个产生式右部的FIRST()集 3.计算每个非终结符A的FOLLOW(A)集 4.计算每个产生式A的SELECT(A)集 5.按LL(1)文法的定义判别,要判别一个上下文无关文法是否是LL(1)文法分为五步：1.求能推出的非终结符集T 2.计算每个产生式右部的FIRST()集 3.计算每个非终结符A的FOLLOW(A)集 4.计算每个产生式A的SELECT(A)集 5.按LL(1)文法的定义判别,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),例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,敛,敛,敛,敛,敛,结论：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|bC Ab|BaD|CAD|b DaS|c,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)=c,FIRST(AB)=a,b,FIRST(bC)=bFIRST()=FIRST(b)=bFIRST(aD)=aFIRST(AD)=b,a,cFIRST(aS)=a,5.按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)=a SELECT(Dc)=c,由于SELECT(SAB)SELECT(SbC)=b SELECT(CAD)SELECT(Cb)=b所以文法GS不是LL(1)文法,对每个非终结符A的任两个产生式A与A，满足SELECT(A)SELECT(A)=,要判别一个上下文无关文法是否是LL(1)文法分为五步：1.求能推出的非终结符集T 2.计算每个产生式右部的FIRST()集 3.计算每个非终结符A的FOLLOW(A)集 4.计算每个产生式A的SELECT(A)集 5.按LL(1)文法的定义判别,go,由每个产生式的select集构造LL(1)分析表,例GS：SAB|bC Ab|BaD|CAD|b DaS|c 试判断该文法是否为LL(1)文法?,back,非终结符集T,能推出的非终结符集T为A,B,S,1.求能推出的非终结符集T,back,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)=a,back,3.计算每个非终结符A的FOLLOW(A)集,back,4.计算每个产生式A 的SELECT(A)集,back,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)=(FIRST(A)-)FIRST(A)=b,a,cSELECT(Cb)=FIRST(b)=bSELECT(DaS)=FIRST(aS)=aSELECT(Dc)=FIRST(c)=c,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)=a SELECT(Dc)=c,由每个产生式的select集构造LL(1)分析表,SAB,SAB,SAB,SbC,A,A,A,Ab,BaD,B,CAD,CAD,Cb,CAD,DaS,Dc,5.按LL(1)文法的定义判别,back,根据LL(1)文法的定义判别,由于SELECT(SAB)SELECT(SbC)=b SELECT(CAD)SELECT(Cb)=b所以文法GS不是LL(1)文法,习题判别文法GS是否为LL(1)文法SaSb|P PbP PPc|Qc QaQ QaQ|,First(2),First(1),P,P,Q,Q,S,First(0),aFirst(P)(敛),b(敛),bFirst(Q)(敛),a(敛),a(敛),(1),(2),a b(敛),b(敛),a b(敛),a(敛),a(敛),a b(敛),a b(敛),习题判别文法GS是否为LL(1)文法SaSb|P PbP PPc|Qc QaQ QaQ|,(2),FIRST(aSb)=FIRST(a)=a FIRST(P)=bFIRST(bP)=FIRST(b)=bFIRST(Pc)=FIRST(P)=bFIRST(Qc)=FIRST(Q)=aFIRST(aQ)=FIRST(a)=aFIRST(aQ)=FIRST(a)=aFIRST()=,Follow(2),Follow(1),P,P,Q,Q,S,Follow(0),#b(收敛),#b c,#b c,c(收敛),c,(收敛),(收敛),(收敛),习题判别文法GS是否为LL(1)文法SaSb|P PbP PPc|Qc QaQ QaQ|,(3),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)=a FIRST(P)=bFIRST(bP)=FIRST(b)=bFIRST(Pc)=FIRST(P)=bFIRST(Qc)=FIRST(Q)=aFIRST(aQ)=FIRST(a)=aFIRST(aQ)=FIRST(a)=aFIRST()=,(4),(5),LL(1)分析表,4.3 非LL(1)文法到LL(1)文法的等价变换,非LL(1)文法含有左公共因子的文法若文法中含有形如：A|r 的产生式，称文法含有左公共因子。显然,SELECT(A)SELECT(A r),文法不是LL(1)文法,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,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,含有左递归的文法文法中只要含有下列形式的产生式,则称文法含有左递归：AAAB 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表示,即得 A A A|r一般形式：若A1|2|n|提取左公共因子,即得 A A|A 1|2|n若在i中仍含有左公共因子,可再次提取.,例文法G1：SaSb|aS|提取左因子得:SaS(b|)|引进新非终结符S,得:SaSS|S b|,2.消除左递归,消除直接左递归文法G:SSa|b可改写成 S bSS aS|一般情形:含直接左递归的文法G：AA1|A2|Am|1|2|n消除左递归后改写成：A1A|2A|nA A1 A|2 A|m A|,消除间接左递归 将间接左递归变成直接左递归，再消除算法步骤：把文法的所有非终结符按任一顺序排列，如：A1，A2，Ai，Ak，An从A1开始，按以下顺序处理Ak消除左部为Ak的产生式的直接左递归若左部为Ak的产生式的右部为非终结符Ai(ik)开头(Ak Ai)，则用左部为Ai的所有产生式的右部分别代替Ak Ai 中的Ai，转至(直至A1An的消除工作全部完成,退出2)去掉无用产生式。,例 文法G：(1)SQc|c(2)QRb|b(3)RSa|a,将非终结符排序：R，Q，S对R：产生式(3)不含直接左递归，所以保持不变对Q：把(3)代入(2)得(2)QSab|ab|b，无直接左递归对S：把(2)代入(1)得(1)SSabc|abc|bc|c，有直接左递归，消除直接左递归得SabcS|bcS|cS S abcS|处理结果为：RSa|a QSab|ab|bSabcS|bcS|cS S abcS|由于Q，R是不可到达的非终结符，其产生式应删除。最终得文法G：SabcS|bcS|cS SabcS|,示例说明：当非终结符顺序为R，Q，S，消除左递归的最终结果为：SabcS|bcS|cS S abcS|若非终结符顺序为S，Q，R，则消除左递归的最终结果为：SQc|c QRb|b RbcaR|caR|aR R bcaR|结论：当非终结符的排序不同时，结果的产生式形式不同，但它们是等价的。,LL(1)文法任两个产生式A|都满足下列条件：FIRST()FIRST()=若*，那么FIRST()FOLLOW(A)=,LL(1)文法有一些明显的性质没有公共左因子不是二义的不含左递归,4.4 不确定的自顶向下分析思想,不确定的自顶向下分析也称带回溯的自顶向下分析定义：不确定是指某个非终结符有多条产生式，而面临当前输入符无法唯一确定选用哪条产生式进行推导，只好逐个试探。当分析不成功时，则推翻分析退回到适当位置重新试探其余候选可能的推导，直到把所有可能的推导序列都试完仍不成功，才能确认输入串不是该文法的句子。,不确定的下推自动机理论(PDA),d e a b c,WXm-1,q,输入串,栈,自动机,读指针,X,Z,pi,不确定的下推自动机理论,d e a b c,Stack,q,d e a b c,Stack,hi,移动,构 形(q,w,h),(q,a,Z)=(pi,hi),PDA的形式定义PDA与上下文无关语言的重要理论PDA与CFG的对应关系从CFG到PDA的构造举例,PDA的形式定义PDA与上下文无关语言的重要理论PDA与CFG的对应关系从CFG到PDA的构造举例,例文法GS：S0S1|c(1)构造其PDA规则(2)写出输入串00c11被接收的移动序列,例1设有文法 SxAy Aab|a，对输入串w=xay，推导树为,由于A的两条产生式：Aab 和Aa 右部First集交集不为空，从而引起回溯,例2文法G：SaASSbAbASA 输入串w=ab，推导树为:,由于A的产生式A 右部能=*，且Follow(A)First(bAS)=b，从而引起回溯,例3文法G：SSaSb输入串w=baa，推导树为:,由于文法含有左递归而引起回溯,4.5 确定的自顶向下分析方法,确定的自顶向下分析方法有：LL(1)预测分析器(predictive parser)LL(1)递归子程序分析器(recursive-descent parser)两种方法都要求文法是LL(1)文法,4.5 确定的自顶向下分析方法,确定的自顶向下分析方法有：LL(1)预测分析器(predictive parser)LL(1)递归子程序分析器(recursive-descent parser)两种方法都要求文法是LL(1)文法,4.5.1 LL(1)预测分析器,一个预测分析器由三个部分组成：预测分析程序：控制分析过程的进行。分析栈：存放从文法开始符号出发的自顶向下推导过程中等待匹配的文法符号。开始时放入#和文法开始符，结束时栈应是空的。预测分析表：是一个二维表，元素MA,a的内容是当非终结符A面临输入符号a（终结符或）时应选取的产生式；当无产生式时，元素MA,a为出错处理(error)。,构造预测分析表步骤：(1)把文法转变为LL(1)文法(2)求出每条产生式的SELECT集(3)依照SELECT集把产生式填入分析表横坐标终结符与纵坐标非终结符交点MA,a(A)放入MA,a若a SELECT(A)无产生式的MA,a标记出错,例 算术表达式文法GEE+TTTT*FFF(E)i,（1）消除G的左递归得到文法 GETE E+TE TFT T*FTF(E)i,（2）求出每个产生式的select集,G是LL(1)文法 SELECT(ETE)=(,i SELECT(E+TE)=+SELECT(E)=),#SELECT(TFT)=(,i SELECT(T*FT)=*SELECT(T)=+,),#SELECT(F(E)=(SELECT(F i)=i,F(E),F i,F,T,T,T*FT,T,T,TFT,T FT,T,E,E,E+TE,E,E,#,）,（,*,+,i,ETE,ETE,（3）依照选择集合把产生式填入分析表,注：表中空白处为出错,预测分析程序,上托栈顶符放入X,N,Y,Y,N,N,N,N,Y,Y,Y,把#和文法开始符S压入分析栈；当前输入符送a,把产生式右部反序进栈,XVT?,X=#?,X=a?,X=a?,读下一输入符到a,MX,a有产生式？,出错,结束,出错,预测分析程序工作过程,输入串i+i*i#的分析过程,7,6,5,4,3,2,1,所用产生式,剩余输入串,分析栈,步骤,8,13,14,15,16,17,12,11,10,9,4.5.2 递归子程序法(第三次实验),1 实现思想 对文法中的每个非终结符编写一个递归过程，识别由该非终结符推出的串。当非终结符有多个产生式时，按当前输入符属于哪个产生式的SELECT集可唯一确定选择哪个产生式进行匹配。当识别到终结符时，与当前输入符号匹配，并读取下一输入符；当识别到非终结符时，则调用该非终结符相应的过程。,定义当一个文法满足LL(1)条件时，就为它构造一个不带回溯的自顶向下的分析程序这个分析程序由一组递归过程组成每个过程对应文法的一个非终结符 这样的一个分析程序称为递归下降分析器,2 构造文法G的递归下降分析器,组成：递归下降分析器由一个主程序main和每个非终结符对应的一个递归过程组成。用到的一些子过程：过程getnext负责读入下一个TOKEN字过程error()负责报告语法错误约定：变量TOKEN存放已读入的TOKEN字过程进入时变量TOKEN存放了一个待匹配的TOKEN字退出过程时，变量TOKEN中仍存放着一个待匹配的TOKEN字。,非终结符相应的分析子程序的构造方法 对于每个非终结符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();,如果U还有空产生式U,则算法中的语句：if(TOKEN first(xn)p(xn)else ERROR();改写为if(TOKEN first(xn)p(xn);else if(TOKEN follow(U)ERROR();对于符号串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();,例 算术表达式文法GEE+TTTT*FFF(E)i,1）消除左递归得 G:ETE E+TE TFT T*FTF(E)i,2）求出G的选择集合SELECT(ETE)=(,i SELECT(E+TE)=+SELECT(E)=),#SELECT(TFT)=(,i SELECT(T*FT)=*SELECT(T)=+,),#SELECT(F(E)=(SELECT(F i)=i,G是LL(1)文法,1 判断是否可以应用递归子程序法,(1)ch TOKEN;main()/*主程序*/getnext(TOKEN);E(TOKEN);/*转匹配ETE*/if(TOKEN!=#)ERROR();,构造文法G：ETE E+TE TFT T*FTF(E)i的递归下降分析器,(2)E(TOKEN)/*匹配ETE*/T(TOKEN);/*转匹配TFT*/E(TOKEN);/*转匹配E+TE*/,(3)E(TOKEN)/*匹配E+TE*/if(TOKEN=+)/*选择产生式E+TE*/getnext(TOKEN);/*匹配+,读入下一个Token字*/T(TOKEN);/*转匹配TFT*/E(TOKEN);/*转匹配E+TE*/else/*E对应的语句*/if(TOKEN!=),构造文法G：ETE E+TE TFT T*FTF(E)i的递归下降分析器,(4)T(TOKEN)/*匹配TFT*/F(TOKEN);/*转匹配F(E)i*/T(TOKEN);/*转匹配T*FT*/,构造文法G：ETE E+TE TFT T*FTF(E)i的递归下降分析器,(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!=+),构造文法G：ETE E+TE TFT T*FTF(E)i的递归下降分析器,(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：ETE E+TE TFT T*FTF(E)i的递归下降分析器,特点：优点：简单直观、易于构造缺点：对文法要求高，必须满足LL(1)文法；递归调用多，速度慢，占用空间多实用性：许多高级语言，如Pascal、c等编译系统常常采用此方法。,实验三 语法分析,实验目的 设计编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，加深对构造自顶向下的语法分析器的原理和技术理解与应用。,实验三 语法分析,实验要求 利用C语言编制递归下降分析程序，并对C语言的简单子集进行分析。设计语言文法，运用递归下降分析技术，设计和实现语法分析器。具有出错处理功能。待分析的C语言子集的语法，以扩充的BNF方法描述如下：,(1)main()(2)(3);|(4)|(5)ID=(6)if()|if()else(7)while(8)|（）|i i|i(9)+|*|()|i(10)|=|=|!=,本章小结,两种自顶向下分析方法：递归子程序法预测分析法一种文法：LL(1)文法判别方法非LL(1)到LL(1)的转换,