-自顶向下语法分析方法.pptx

第五章第五章第五章第五章 自顶向下语法分析方法自顶向下语法分析方法自顶向下语法分析方法自顶向下语法分析方法学习目标学习目标:掌掌握握：LL(1)LL(1)文文法法的的判判别别，预预测测分分析析法，递归子程序的构造方法法，递归子程序的构造方法理解：理解：LLLL（1 1）文法文法了解：不确定的自顶向下分析了解：不确定的自顶向下分析语语法法分分析析的的作作用用是是识识别别由由词词法法分分析析给给出出的的单单词词序序列是否是给定文法的正确句子列是否是给定文法的正确句子分类分类:语法分析语法分析自顶向下分析自顶向下分析自底向上分析自底向上分析确定的确定的不确定的不确定的算法优先分析（第六章）算法优先分析（第六章）LR分析（第七章）分析（第七章）自顶向下的基本思想自顶向下的基本思想:从从文文法法的的开开始始符符出出发发企企图图推推导导出出与与输输入入的的单单词词串串完全相匹配的句子完全相匹配的句子.5.1确定的自顶向下分析思想确定的自顶向下分析思想5.2LL(1)文法的判别文法的判别5.3某些非某些非LL(1)文法到文法到LL(1)文法的等价变换文法的等价变换5.4不确定的自顶向下分析思想不确定的自顶向下分析思想5.5确定的自顶向下分析方法确定的自顶向下分析方法5.1 5.1 确定的自顶向下分析思想确定的自顶向下分析思想确定的自顶向下分析思想确定的自顶向下分析思想1 确定分析的条件确定分析的条件2 开始符号集开始符号集FIRST()的定义的定义3 后跟符号集后跟符号集FOLLOW(A)的定义的定义4 选择集合选择集合SELECT(A)的定义的定义5 LL(1)文法的定义文法的定义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=abd S=abAS=abS文法的特点是文法的特点是:包含空产生式包含空产生式对于空产生式左部的非终结符对于空产生式左部的非终结符，关键是判断关键是判断该该非终结符的后跟符号（集非终结符的后跟符号（集），分析过程可），分析过程可能是确定的。能是确定的。=aA要进行确定的自顶向下的分析，文法要满足一要进行确定的自顶向下的分析，文法要满足一定的限制定的限制即文法是即文法是LL(1)文法。文法。先研究三个定义先研究三个定义开始符号集开始符号集FIRSTFIRST后跟符号集后跟符号集FOLLOWFOLLOW选择集合选择集合SELECTSELECT2 2 开始符号集开始符号集开始符号集开始符号集FIRST()FIRST()的定义的定义的定义的定义定义定义:设设G=(VN,VT,P,S)是上下文无关文法，是上下文无关文法，(VN VT)*FIRST()=a VT|*a.若若*则规定则规定 FIRST()直观上说文法符号串直观上说文法符号串 的开始符号集是由的开始符号集是由 推导出的开头的终结符（包括推导出的开头的终结符（包括）组成。组成。例文法例文法G2S:SApSBqAaAcABbBdBFIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=a FIRST(cA)=cFIRST(b)=bFIRST(dB)=d由于由于同一非终结符同一非终结符的两个的两个产生式的右部产生式的右部推导出来的推导出来的开始符号集开始符号集不相交，因此可根据当前输入符属于哪不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析行推导，可以进行确定的自顶向下分析3 3 后跟符号集后跟符号集后跟符号集后跟符号集FOLLOW(A)FOLLOW(A)的定义的定义的定义的定义定义定义 设设G=(VT,VN,P,S)是上下文无关文法，是上下文无关文法，A VN，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 =abbASd FOLLOW(S)=#,a,d由由S=*aA 得得#FOLLOW(A)由由S=*abAS=*abAaA 得得 a FOLLOW(A)=*abAd 得得 d FOLLOW(A)FOLLOW(A)=#,a,d说明：说明：对于非终结符对于非终结符A的两个产生式的两个产生式AbAS 和和 A，当输入符号当输入符号FIRST(bAS)=b时，选时，选AbAS推导，推导，当输入符号当输入符号FOLLOW(A)=#,a,d 时，选时，选A推导。推导。由于由于FIRST(bAS)FOLLOW(A)=，所以可进行确定所以可进行确定的自顶向下分析。的自顶向下分析。4 4 选择集合选择集合选择集合选择集合SELECT(A)SELECT(A)的定义的定义的定义的定义定义定义对给定的上下文无关文法的产生式对给定的上下文无关文法的产生式A，A VN，V*，若若*,则则SELECT(A)=FIRST()若若=*,则则SELECT(A)=(FIRST()-)FOLLOW(A)解释解释当当A面面对应输入符对应输入符a，在自顶向下的分析中应选择这在自顶向下的分析中应选择这样的产生式样的产生式A 进行推导：进行推导：First()中包含中包含a；此外若此外若 可能导出空串，可能导出空串，A自动获得匹配，输入符自动获得匹配，输入符a有可能与有可能与A后后的一个符号匹配，所以当的一个符号匹配，所以当a应属于应属于Follow(A)时，选择产生式时，选择产生式A 也是可以的也是可以的。直观上说某产生式直观上说某产生式A的选择集合是指遇到哪些输的选择集合是指遇到哪些输入符号（包括入符号（包括#）时选用该产生式向下推导。）时选用该产生式向下推导。例例 G3S:SaA Sd AbAS ASELECT(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)说明：说明：同一非终结符的不同产生式同一非终结符的不同产生式A与与A，若若SELECT(A)SELECT(A)=，则一定则一定可以进行确定的自顶向下分析可以进行确定的自顶向下分析5 5 LL(1)LL(1)文法的定义文法的定义文法的定义文法的定义定义定义:一一个个上上下下文文无无关关文文法法是是LL(1)文文法法的的充充分分必必要要条条件件是是，对对每每个个非非终终结结符符A的的两两个个不不同同产产生生式式A与与A，满足满足SELECT(A)SELECT(A)=。LL(1)文法的含义是：文法的含义是：第一个第一个L表示从左到右扫描输入串表示从左到右扫描输入串第二个第二个L表示分析过程用最左推导表示分析过程用最左推导1表明只需向前看一个符号便可以决定选哪个产生式表明只需向前看一个符号便可以决定选哪个产生式进行推导，类似地进行推导，类似地LL(k)文法需要向前看文法需要向前看K个符号才个符号才可以确定选用哪个产生式。可以确定选用哪个产生式。例例 有文法有文法GS为：为：SaAS SbAbAASELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=Follow(A)=a,b由于由于SELECT(AbA)SELECT(A)=b，所以文法所以文法GS不是不是LL(1)文法，当文法，当A遇输入符遇输入符b时，不时，不能确定选能确定选AbA还是还是A去推导。去推导。5.2 5.2 LLLL(1 1)文法的判别文法的判别文法的判别文法的判别要判别一个上下文无关文法是否是要判别一个上下文无关文法是否是LL(1)文法文法分为五步：分为五步：1.求能推出求能推出的非终结符集的非终结符集 2.计算每个产生式右部计算每个产生式右部的的FIRST()集集 3.计算每个非终结符计算每个非终结符A的的FOLLOW(A)集集 4.计算每个产生式计算每个产生式A的的SELECT(A)集集 5.按按LL(1)文法的定义判别文法的定义判别1.1.求出能推出求出能推出求出能推出求出能推出 的非终结符集的非终结符集的非终结符集的非终结符集算法算法:用用S表示能推出表示能推出的非终结符集的非终结符集第一步令第一步令S=Aj|Aj 产生式集产生式集对对 每每 个个 产产 生生 式式 p:ApX1.Xn，若若X1.Xn S，则则S:=S Ap重重复复第第二二步步的的循循环环，直直至至S收收敛敛（不不再再变化）为止。变化）为止。例例GS：SAB|bCAb|BaD|CAD|b DaS|cA,B,A,B,S S 第一次第一次 A,BA,B初值初值A,B,SA,B,S收敛收敛第二次第二次非终结符集非终结符集S S能推出能推出的非终结符集为的非终结符集为A,B,S2.2.计算每个产生式右部计算每个产生式右部计算每个产生式右部计算每个产生式右部 的的的的FIRSTFIRST()集集集集首首先先对对每每一一文文法法符符号号X(X VT VN)，求求FIRST(X)的算法的算法:1.对每个对每个a VT：First(a)=a2.对每个对每个A VN：若若A*则则First(A):=否则否则First(A):=3.对每个产生式对每个产生式AX1XjXn做：做：First(A)=First(A)SectionFirst(X1XjXn)其中其中 SectionFirst(XSectionFirst(X1 1X Xj jX Xn n)=(First(X=(First(X1 1)-)-)(First(X(First(X2 2)-)-)(First(First(X(Xj j)-)-)First(XFirst(Xj+1j+1)X Xj+1j+1是产生式右部中第一个不能推出是产生式右部中第一个不能推出的符号的符号若若X X1 1 *则则SectionFirst(XSectionFirst(X1 1X Xj jX Xn n)=First(X)=First(X1 1)若若X X1 1X Xn n全可推出全可推出则则SectionFirst(XSectionFirst(X1 1X Xn n)=FIRST(X)=FIRST(X1 1)FIRST(XFIRST(Xn n)4.4.重复重复3 3直到每个符号的直到每个符号的FIRSTFIRST集合都不再增大为止。集合都不再增大为止。例例GS：SAB|bC Ab|BaD|CAD|b DaS|cb ba aa ca cb a cb a c a b b aFirstFirst集集(3)(3)b ba aa ca cb b a b bFirstFirst集集(2)(2)b ba a FirstFirst集集(1)(1)A AB BC CD Da ab bS Sa ab bFirstFirst集集(0)(0)已求出能推出已求出能推出的非终结符集的非终结符集为为A,B,Sbbab ba ca caa ca c利用求出利用求出每个文法符号每个文法符号的的FIRST集集求求符号串符号串的的FIRST集集设设=X1X2Xn1.当当X1不能不能=*，则，则FIRST()=FIRST(X1)2.若对任何若对任何j(1jn）都有都有 FIRST(Xj),则则FIRST()=(FIRST(X1)-)(FIRST(Xj)-)FIRST(Xj+1)3.若对所有若对所有i(1in)，都有都有 FIRST(Xi)，则则 FIRST()=FIRST(X1)FIRST(Xn)例例GS SAB|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 产生式右部产生式右部符号串符号串的开始符集合为的开始符集合为:SABFIRST(AB)=FIRST(A)FIRST(B)=a,b,SbCFIRST(bC)=bAFIRST()=AbFIRST(b)=bCADFIRST(AD)=(FIRST(A)-)FIRST(D)=b,a,cDaSFIRST(aS)=a3 3计算每个非终结符计算每个非终结符计算每个非终结符计算每个非终结符AA的的的的FOLLOWFOLLOW(AA)集集集集1.对对所所有有A VN令令Follow(A)=;对对开开始始符符S，令令Follow(S)=#因为因为S=*S，显然，显然#FOLLOW(S)2.对每条产生式对每条产生式AxBy，考察产生式右部的每一非终考察产生式右部的每一非终结符结符B，x,y V*，如果如果y不能推出不能推出Follow(B)=Follow(B)First(y)否则否则Follow(B)=Follow(B)(First(y)-)Follow(A)3.重复重复2，直至对所有，直至对所有A VN，Follow(A)收敛为止。收敛为止。若若a FOLLOW(A),则表明则表明S=*Aa，由于由于AxBy，且且y=*,则有则有 S=*Aa=xBya=xBa，即即S=*xBa,所以所以a FOLLOW(B)例例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#cSFollow集集(2)Follow集集(1)Follow集集(0)c4 4计算每个产生式计算每个产生式计算每个产生式计算每个产生式AA的的的的SELECTSELECT(A)A)集集集集按定义计算按定义计算SELECT(A)：若若*，则则SELECT(A)=FIRST()若若=*，则则SELECT(A)=(FIRST()-)FOLLOW(A)例例GS：SAB|bC Ab|BaD|CAD|b DaS|c是否是否=*FirstFirst集集 FollowFollow集集S S是是a,b,#A A是是 b,a,c,#B B是是 a,#C C否否a,b,ca,b,c#D D否否a,ca,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,c5.5.按按按按LL(1)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)=b SELECT(CAD)SELECT(Cb)=b所以文法所以文法GS不是不是LL(1)文法文法5.3 5.3 某些非某些非某些非某些非LL(1)LL(1)文法到文法到文法到文法到LL(1)LL(1)文法的等价变换文法的等价变换文法的等价变换文法的等价变换非非LL(1)文法文法含有含有左公共因子左公共因子的文法的文法若文法中含有形如：若文法中含有形如：A|r 的产生式，称文法的产生式，称文法含有左公共因子。含有左公共因子。显然显然,SELECT(A)SELECT(A r),文法文法不是不是LL(1)文法文法含有含有左递归左递归的文法的文法文文法法中中只只要要含含有有下下列列形形式式的的产产生生式式（含含有有a a或或含含有有b b或二者皆有）则称文法含有左递归：或二者皆有）则称文法含有左递归：a)a)A AA Ab)b)ABABBABA在在a)a)中含有左递归的产生式，称为中含有左递归的产生式，称为直接左递归直接左递归；在在b)b)中虽然没有含左递归的产生式，中虽然没有含左递归的产生式，但但A A=B B=AA 即即A 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 1 提取左公共因子提取左公共因子提取左公共因子提取左公共因子将产生式将产生式A|r 等价变换为等价变换为:A(|r)，将将括括号号内内用用一一新新引引入入的的非非终终结结符符A表表示示,得得 AA，A|r一般形式：若一般形式：若A1|2|n,提取左公共因子后变为提取左公共因子后变为AA，A 1|2|n若在若在i中仍含有左公共因子中仍含有左公共因子,可再次提取可再次提取.例例 文法文法G1：SaSb|aS|提左因子得提左因子得:SaS(b|)|引进新的非终结符得引进新的非终结符得:SaSS|S b|2.2.消除左递归消除左递归消除左递归消除左递归1)消除直接左递归消除直接左递归文法文法G:SSa|b可改写成可改写成 SbSS aS|一般情形一般情形:含直接左递归的文法含直接左递归的文法G：AA1|A2|Am|1|2|n消除左递归后改写成：消除左递归后改写成：A1A|2A|nA A1 A|2 A|m A|2)消除间接左递归消除间接左递归将间接左递归变成直接左递归，再消除将间接左递归变成直接左递归，再消除算法步骤：算法步骤：1.把文法的所有非终结符按任一顺序排列，把文法的所有非终结符按任一顺序排列，如：如：A1，A2，An2.从从A1开始，按以下顺序处理开始，按以下顺序处理Ai。首先，消除左部为首先，消除左部为Ai的产生式的直接左递归的产生式的直接左递归然然后后，若若左左部部为为Ai的的产产生生式式的的右右部部为为非非终终结结符符Aj(j*，且，且Follow(A)First(bAS)=b，从而引起回溯，从而引起回溯例例3文法文法G：SSaSb输入串输入串w=baa，推导树为推导树为:SSabSbSSa回溯回溯回溯回溯SSaSaSSaSab由于文法含有左递归而引起回溯由于文法含有左递归而引起回溯5.5 5.5 确定的自顶向下分析方法确定的自顶向下分析方法确定的自顶向下分析方法确定的自顶向下分析方法确定的自顶向下分析方法有：确定的自顶向下分析方法有：递归子程序法递归子程序法(recursive-descent parser)预测分析法预测分析法(predictive parser)两种方法都要求文法是两种方法都要求文法是LL(1)文法。文法。5.5.1 5.5.1 递归子程序法递归子程序法递归子程序法递归子程序法q实现思想：实现思想：对对文文法法中中的的每每个个非非终终结结符符编编写写一一个个递递归归过过程程，识识别别由由该该非非终终结结符符推推出出的的串串。当当非非终终结结符符有有多多条条产产生生式式时时，按按当当前前输输入入符符属属于于哪哪条条产产生生式式的的SELECT集集可可唯唯一一确确定定选选择择哪哪个个产产生生式式进进行行匹匹配。配。当识别到终结符时，与当前输入符号匹配，当识别到终结符时，与当前输入符号匹配，并读取下一输入符；并读取下一输入符；当识别到非终结符时，则调用该非终结符相当识别到非终结符时，则调用该非终结符相应的过程。应的过程。例例 算术表达式文法算术表达式文法GEE+TTTT*FFF(E)i1）消除左递归得消除左递归得 G:ETE E+TE TFT T*FTF(E)i2 2）求出求出G 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 判断是否可以应用递归子程序法判断是否可以应用递归子程序法n表达式的正规式表达式的正规式 E=T(+T)E=T(+T)*n转换成正则文法转换成正则文法ETBETB，B(+T)B(+T)*，即即B(+T)B(+T)*B(+T)BB(+T)B，B B，即即B(+T)BB(+T)B n与与EE+TT 消除左递归所得消除左递归所得ETE E+TE 一致一致表表达达式式项项原产生式变换后产生式规则1AxyAxB By规则2Ax*yAxA Ay规则3Ax|yAx Ay2 构造文法构造文法G的递归下降分析器的递归下降分析器定义：定义：当一个文法满足当一个文法满足LL(1)LL(1)条件时，就为它构造一条件时，就为它构造一个不带回溯的自顶向下的分析程序，这个分析个不带回溯的自顶向下的分析程序，这个分析程序由一组程序由一组递归过程递归过程组成，每个过程对应文法组成，每个过程对应文法的一个非终结符。这样的一个分析程序称为的一个非终结符。这样的一个分析程序称为递递归下降分析器归下降分析器。组成：组成：递归下降分析器由一个主程序递归下降分析器由一个主程序MAINMAIN和每个非终结符和每个非终结符对应的一个递归过程组成。对应的一个递归过程组成。用到的一些子过程：用到的一些子过程：过程过程GETNEXTGETNEXT负责读入下一个负责读入下一个TOKENTOKEN字字过程过程ERRORERROR负责报告语法错误负责报告语法错误约定：约定：变量变量TOKENTOKEN存放已读入的存放已读入的TOKENTOKEN字字过程进入时变量过程进入时变量TOKENTOKEN存放了一个待匹配的存放了一个待匹配的TOKENTOKEN字字退出过程时，变量退出过程时，变量TOKENTOKEN中仍存放着一个待匹配中仍存放着一个待匹配的的TOKENTOKEN字。字。非终结符相应的分析子程序的构造方法非终结符相应的分析子程序的构造方法1)对于每个非终结符对于每个非终结符U，编写一个相应的子程序编写一个相应的子程序P(U);2)对于产生式对于产生式Ux1|x2|xn，x1,.xn都都 关于关于U的子的子程序程序P(U)按如下方法构造：按如下方法构造：if TOKEN in first(x1)then p(x1)else if TOKEN in first(x2)then p(x2)else .if TOKEN in first(xn)then p(xn)else ERROR3)如果如果U还有空产生式还有空产生式U,则算法中的语句：则算法中的语句：if TOKEN in first(xn)then p(xn)else ERROR改写为改写为if TOKEN in first(xn)then p(xn)else if TOKEN not in follow(U)then ERROR4)对于符号串对于符号串x=y1y2yn；p(x)的含义为：的含义为：begin p(y1);p(y2);p(yn)end如果如果yi VN，则则P(yi)就代表调用就代表调用yi的子程序；的子程序；yi VT T，则则P(yi)为形如下述语句的一段程序为形如下述语句的一段程序if TOKEN=yi then GETNEXT(TOKEN)else ERROR(1)programMAIN;/*主程序主程序,匹配匹配EE#*/beginGETNEXT(TOKEN);E(TOKEN);/*转匹配转匹配ETE*/ifTOKEN#thenERRORend.构造文法构造文法G：ETE E+TE TFT T*FT F(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#thenERROR/*构造方法构造方法3，求，求follow(E)=follow(E)=),#*/end;(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;/*follow(T)=follow(T)=first(E)+follow(E)=+,),#*/(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字字*/elseERRORendelse/*选择产生式选择产生式Fi*/ifTOKEN=ithenGETNEXT(TOKEN)elseERRORend;特点：特点：优点：简单直观、易于构造优点：简单直观、易于构造缺点：缺点：对文法要求高，必须满足对文法要求高，必须满足LL(1)文法；文法；递归调用多，速度慢，占用空间多递归调用多，速度慢，占用空间多实实用用性性：许许多多高高级级语语言言，如如Pascal、c等等编编译译系统常常采用此方法。系统常常采用此方法。5.5.2 5.5.2 预测分析方法预测分析方法预测分析方法预测分析方法一个预测分析器由三个部分组成：一个预测分析器由三个部分组成：预测分析程序：控制分析过程的进行。预测分析程序：控制分析过程的进行。分析栈：存放从文法开始符号出发的自顶向下推分析栈：存放从文法开始符号出发的自顶向下推导过程中导过程中等待匹配等待匹配的文法符号。开始时放入的文法符号。开始时放入#和文法开始符，结束时栈应是空的。和文法开始符，结束时栈应是空的。预测分析表：是一张二维表，元素预测分析表：是一张二维表，元素MA,a的内容的内容是当非终结符是当非终结符A面临输入符号面临输入符号a（终结符或句子括终结符或句子括号）时应选取的号）时应选取的产生式产生式，当无产生式时，元素，当无产生式时，元素内容为转向出错处理。内容为转向出错处理。1.1.构造预测分析表构造预测分析表步骤：步骤：(1)(1)把文法转变为把文法转变为LL(1)LL(1)文法文法(2)(2)求出每条产生式的求出每条产生式的SELECTSELECT集集(3)(3)依照依照SELECTSELECT集把产生式填入分析表集把产生式填入分析表对每个终结符或对每个终结符或用用a a表示表示若若a a SELECT(A SELECT(A)，则把则把AA 放入放入MA,aMA,a中，中，把所有无定义的把所有无定义的MA,aMA,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)(E)F i iFT T T*FTFTT TTFtFtT FTFTTE E E+TEEE#）（*+iETEETE（3 3）依照选择集合把产生式填入分析表）依照选择集合把产生式填入分析表注：表中空白处为出错注：表中空白处为出错2 2 预测分析程序预测分析程序预测分析程序预测分析程序上托栈顶符放入上托栈顶符放入XNYYNNNNYYY把把#和和文文法法开开始始符符压压入入分分析析栈栈；当前输入符送当前输入符送a把把产产生生式式右右部部反序反序进栈进栈XVT?X=#?X=a?X=a?读读下下一一输输入入符到符到aMX,a有有产产生生式式？出错出错结束结束出错出错预测分析程序工作过程预测分析程序工作过程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所用产生式所用产生式剩余输入串剩余输入串分析栈分析栈步骤步骤TFTi*i#ET8Fii#ETF13i匹配匹配i#ETi14T#ET15E#E16接受接受#17*匹配匹配*i#ETF*12T*FT*FT*i#ET11i匹配匹配i*i#ETi10Fii*i#ETF9i+*（）#EETEETEEE+TEE E TT FTFTT FTFTTT T*FTFTT T FF i iF(E)(E)本章小结本章小结q两种自顶向下分析方法：两种自顶向下分析方法：递归子程序法递归子程序法预测分析法预测分析法q一种文法：一种文法：LL(1)文法文法判别方法判别方法非非LL(1)到到LL(1)的转换的转换作业：作业：1.文法GS:S-a|(T)T-T,S|S(1)给出对(a,(a,a)的最左推导(2)改写文法，去除左递归(3)判断新文法是否LL1文法，如是，给出其预测分析表(4)给出输入串（a,a）#的分析过程，判断其是否文法G的句子。