编译原理-自顶向下语法分析方法PPT课件

.,1,第四章自顶向下语法分析方法,学习目标:掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法理解：LL（1）文法了解：不确定的自顶向下分析,语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子,自顶向下基本思想:从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子.,分类:,回顾自上而下的分析方法,定义:从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。自上而下分析的主要问题选定产生式,例文法G：ScAdAabAa识别输入串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)的定义5LL(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|aVT且*a.（若*则规定FIRST()）直观上说文法符号串的开始符号集是由推导出的所有的终结符开头和可能的组成。,例文法G2S:,SApSBqAaAcABbBdB,FIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=aFIRST(cA)=cFIRST(b)=bFIRST(dB)=d,结论一针对无空产生式的文法G，同一非终结符的任两个产生式的右部串的First集无交集，即可进行确定的自顶向下分析。,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后的那些终结符（包括#）组成。,例文法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,d,FOLLOW(A),FOLLOW(S),解释当A面对应输入符a，在自顶向下的分析中应选择这样的产生式Ai(i可导出空串)进行推导：若aFirst(i),则Ai可选因i可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，故当aFollow(A)时，产生式Ai亦可选,结论一针对无空产生式的文法G，同一非终结符的任两个产生式的右部串的First集无交集，即可进行确定的自顶向下分析。,结论二,例文法G3S:SaA|dAbAS|,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|aVT且*a.（若*,则规定FIRST()）直观上说文法符号串的开始符号集是由推导出的所有的终结符开头和可能的组成。,回顾后跟符号集FOLLOW(A)的定义,定义设G=(VT,VN,P,S)是上下文无关文法，BxAy(A,BVNx,y(VNVT)*)FOLLOW(A)=a|S=*Aa，aVT，若有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)在自顶向下的分析中：对于Ai且i*,若aFirst(i),则Ai可选对于Aj且j=*,若a(First(j)-)Follow(A),则Aj可选,例G3S:SaASdAbASA,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为：SaASSbAbAA,SELECT(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.AnT，则T=TAp重复，直至T收敛（不再变化）为止,例GS：SAB|bCAb|BaD|CAD|bDaS|c,非终结符集T,能推出的非终结符集T为A,B,S,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(XVTVN)，求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|c,First集(3),First集(2),First集(1),A,B,C,D,a,b,S,First集(0),已求出能推出的非终结符集T为A,B,S,b,b,a,b,ac,a,ac,（敛）,（敛）,（敛）,（敛）,（敛）,（敛）,（敛）,c,（敛）,c,c,c,c,结论：文法符号的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集,设右部串=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)=bFIRST()=FIRST(b)=bFIRST(AD)=(FIRST(A)-)FIRST(D)=b,a,cFIRST(aS)=FIRST(a)=a,例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,产生式右部符号串的开始符集合为: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.对所有AVN，令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，直至对所有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|bCAb|BaD|CAD|bDaS|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,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)=,要判别一个上下文无关文法是否是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)文法?,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,cSELECT(Cb)=bSELECT(DaS)=aSELECT(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)=bSELECT(CAD)SELECT(Cb)=b所以文法GS不是LL(1)文法,习题判别文法GS是否为LL(1)文法SaSb|PPbPPPc|QcQaQQaQ|,First(2),First(1),P,P,Q,Q,S,First(0),aFirst(P)(敛),b(敛),bFirst(Q)(敛),a(敛),a(敛),(1),(2),ab(敛),b(敛),ab(敛),a(敛),a(敛),ab(敛),ab(敛),习题判别文法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()=,Follow(2),Follow(1),P,P,Q,Q,S,Follow(0),#b(收敛),#bc,#bc,c(收敛),c,(收敛),(收敛),(收敛),习题判别文法GS是否为LL(1)文法SaSb|PPbPPPc|QcQaQQaQ|,(3),SELECT(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()=,(4),(5),LL(1)分析表,4.3非LL(1)文法到LL(1)文法的等价变换,非LL(1)文法含有左公共因子的文法若文法中含有形如：A|r的产生式，称文法含有左公共因子。显然,SELECT(A)SELECT(Ar),文法不是LL(1)文法,stmtifexprthenstmt|ifexprthenstmtelsestmt|other,句型ife1thenife2thens1elses2,推导一stmtife1thenstmtife1thenife2thens1elses2,悬空else问题,推导二stmtife1thenstmtelses2ife1thenife2thens1elses2,stmtifexprthenstmt|ifexprthenstmtelsestmt|other,stmtmatched_stmt|unmatched_stmtmatched_stmtifexprthenmatched_stmtelsematched_stmt|otherunmatched_stmtifexprthenstmt|ifexprthenmatched_stmtelseunmatched_stmt,含有左递归的文法文法中只要含有下列形式的产生式,则称文法含有左递归：AAABBA在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.消除左递归,消除直接左递归文法G:SSa|b可改写成SbSSaS|一般情形:含直接左递归的文法G：AA1|A2|Am|1|2|n消除左递归后改写成：A1A|2A|nAA1A|2A|mA|,消除间接左递归将间接左递归变成直接左递归，再消除算法步骤：把文法的所有非终结符按任一顺序排列，如：A1，A2，Ai，Ak，An从A1开始，按以下顺序处理Ak消除左部为Ak的产生式的直接左递归若左部为Ak的产生式的右部为非终结符Ai(i*，且Follow(A)First(bAS)=b，从而引起回溯,例3文法G：SSaSb输入串w=baa，推导树为:,由于文法含有左递归而引起回溯,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)预测分析器,一个预测分析器由三个部分组成：预测分析程序：控制分析过程的进行。分析栈：存放从文法开始符号出发的自顶向下推导过程中等待匹配的文法符号。开始时放入#和文法开始符，结束时栈应是空的。预测分析表：是一个二维表，元素MA,a的内容是当非终结符A面临输入符号a（终结符或）时应选取的产生式；当无产生式时，元素MA,a为出错处理(error)。,构造预测分析表步骤：(1)把文法转变为LL(1)文法(2)求出每条产生式的SELECT集(3)依照SELECT集把产生式填入分析表横坐标终结符与纵坐标非终结符交点MA,a(A)放入MA,a若aSELECT(A)无产生式的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)=i,F(E),Fi,F,T,T,T*FT,T,T,TFT,TFT,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(TOKENfirst(x1)p(x1);elseif(TOKENfirst(x2)p(x2);elseif(TOKENfirst(xn)p(xn);elseERROR();,如果U还有空产生式U,则算法中的语句：if(TOKENfirst(xn)p(xn)elseERROR();改写为if(TOKENfirst(xn)p(xn);elseif(TOKENfollow(U)ERROR();对于符号串x=y1y2ynp(x)的含义为：main()p(y1);p(y2);p(yn);如yiVN，则P(yi)就代表调用yi的子程序；如yiVT，则P(yi)为如下述代码if(TOKEN=yi)getnext(TOKEN);elseERROR();,例算术表达式文法GEE+TTTT*FFF(E)i,1）消除左递归得G:ETEE+TETFTT*FTF(E)i,2）求出G的选择集合SELECT(ETE)=(,iSELECT(E+TE)=+SELECT(E)=),#SELECT(TFT)=(,iSELECT(T*FT)=*SELECT(T)=+,),#SELECT(F(E)=(SELECT(Fi)=i,G是LL(1)文法,1判断是否可以应用递归子程序法,(1)chTOKEN;main()/*主程