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

《hh自顶向下语法分析方法.pptx》由会员分享，可在线阅读，更多相关《hh自顶向下语法分析方法.pptx（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1hh 自顶向下语法分析方法自顶向下语法分析方法(fngf)第一页，共80页。对于(duy)文法GS:SxAyAab|a考虑输入串为xay,其分析过程如下:1.自上而下自上而下(z shn r xi)分分析的不确定性析的不确定性abyAxSayAxS第1页/共80页第二页，共80页。在上述分析过程中,若有多个候选式可供选择,则需逐一试探每个候选式。当试探失败时,必须回溯到该试探的初始现场,包括注销(zhxio)已生长子树、输入串指针回退到试探前状态。这种带回溯的自上而下分析法是一种穷举法,效率很低。第2页/共80页第三页，共80页。为了实现确定的自上而下分析,要求文法满足下述条件:(1)

2、文法不含左递归。左递归:AA或AA左递归的存在使自上而下分析过程陷入无限循环(xnhun),因此,使用自上而下分析法必须消除左递归。+2.确定的自上而下确定的自上而下(z shn r xi)分析分析第3页/共80页第四页，共80页。(2)分析过程无回溯回溯的存在可能使已做的大量分析工作推倒重来,这会严重(ynzhng)影响效率,因此,使用自上而下分析法必须消除回溯。第4页/共80页第五页，共80页。直接左递归的消除:方法:引入一个新非终结符,把含有左递归的产生式改写(gixi)为右递归形式。考虑产生式:AA|其中,是任意串且不以A开头.A的产生式可改写(gixi)为:(1)左递归的消除左递归的

3、消除(xioch)AAAA|第5页/共80页第六页，共80页。例如,算术(sunsh)表达式文法GE为:GE:EE+T|TTT*F|FF(E)|i消去直接(zhji)左递归后得到文法GE:GE:ETEE+TE|TFTT*FT|F(E)|i第6页/共80页第七页，共80页。一般(ybn)地,设文法中A的产生式为:AA1|A2|Am|1|2|n其中,每个都不等于每个都不以A开头消除A的直接(zhji)左递归,文法可改写为:A1A|2A|nAA1A|2A|mA|第7页/共80页第八页，共80页。例如(lr)消除EE+T|ET|T的左递归解:消除左递归后变为ETEE+TE|TE|第8页/共80页第九页

4、，共80页。间接(jinji)左递归的消除考虑GS:SQc|cQRb|bRSa|a间接左递归的存在是由于非终结符之间形成了循环推导,只要把循环推导中的某个连接切断(qidun),间接左递归就消除了。第9页/共80页第十页，共80页。切断循环推导中某个连接的方法:Step1.对n个产生式中的某一个(y)进行至多n-1次替换,使间接左递归变成直接左递归,再消除之。例如(lr),消除GS中S,Q之间的连接:SQc|cRbc|bc|cSabc|abc|bc|c改写为:SabcS|bcS|cSSabcS|第10页/共80页第十一页，共80页。Step2.对其余(qy)n-1个产生式中的某一个进行至多n-

5、2次替换,再消除其直接左递归。若后两个产生式改为:QRb|bRSa|a|Qa则还需消除Q,R之间的连接(linji):QRb|bSab|ab|Qab|b再消除其直接左递归。考虑(kol)后两个产生式:QRb|bRSa|a第11页/共80页第十二页，共80页。消除左递归算法:(1)文法所有非终结符排序为A1,An;(2)把间接左递归改为直接左递归,并消除之,方法如下:for(i=1;i=n;i+)for(j=1;j=i1;j+)把AiAj|及Aj1|k改写(gixi)为Ai1|k|;消除Ai的直接左递归;(3)化简,删去不可达元的产生式。第12页/共80页第十三页，共80页。例如(lr),GS:

6、SQc|cQRb|bRSa|a(1)将非终结符排序(pix)为R,Q,S;(2)对于R(i=1,P1)内层循环不执行;消除R的直接左递归:RSa|a对于Q(i=2,P2)内层循环改写:QSab|ab|b消除Q的直接左递归:QSab|ab|b第13页/共80页第十四页，共80页。对于S(i=3,P3)内层循环(xnhun)改写:SSabc|abc|bc|c消除S的直接左递归:SabcS|bcS|cSSabcS|第14页/共80页第十五页，共80页。于是(ysh)得文法GS:SabcS|bcS|cSSabcS|QSab|ab|bRSa|a(3)化简,删去关于(guny)Q 和R的产生式:SabcS

7、|bcS|cSSabcS|第15页/共80页第十六页，共80页。对消除左递归算法的两点说明:消除左递归算法有两个限制条件:文法中不含回路和-生成式。该限制不影响消除左递归算法的使用,因为对任一CFGG,存在一个不含-生成式和单一生成式的CFGG,使得L(G)=L(G)-。对非终结符的不同排序会导致文法形式(xngsh)上的不同,但它们等价。第16页/共80页第十七页，共80页。上例中,若排序为S,Q,R,则得到文法GS:SQc|cQRb|bRbcaR|caR|aRRbcaR|下面(ximian)证明:GS与GS等价。第17页/共80页第十八页，共80页。GS与GS等价(dngji)的证明:Sa

8、bc(abc)*|bc(abc)*|c(abc)*L(G)=(abc|bc|c)(abc)i|i0Sbca(bca)*bc|ca(bca)*bc|a(bca)*bc|bc|cL(G)=(abc|bc|c)(abc)i|i0第18页/共80页第十九页，共80页。有兴趣的同学课后以下述文法(wnf)为例熟悉消除左递归的执行过程:GS:SQc|c|RcQRb|b|SbRSa|a|QaGS:SQc|c|Rc|ScQRb|b|Sb|QbRSa|a|Qa|Ra第19页/共80页第二十页，共80页。要消除回溯,首先要清楚回溯存在的原因,根除了这些原因,自然就消除了回溯。假设用产生式A1|2|n去执行匹配任务

9、,而A面临(minlng)的输入串为a1a2am。(2)回溯回溯(hu s)的消的消除除第20页/共80页第二十一页，共80页。回溯的存在是由于分析过程中需对多个(du)候选式进行试探性匹配。若能根据输入符从A的多个(du)候选式中选出一个作为全权代表,使得若该候选式与输入串匹配成功,则A与输入串匹配成功,否则A与输入串匹配不成功,则可消除试探性匹配,从而消除回溯。第21页/共80页第二十二页，共80页。如何从多个候选式中选出一个作为全权代表呢?考虑产生式:AaA|bB|cCa一般地,A1|2|na若A的候选式中只有i推出的终结符串的首字符(zf)包含a,则i可作为A的全权代表。这要求匹配前先

10、求出各个候选式所能推出的所有终结符串的首字符(zf),即终结首符集FIRST(i)。第22页/共80页第二十三页，共80页。终结首符集FIRST()对于文法G的所有(suyu)非终结符的每个候选式,定义FIRST()a|a,aVT若,则FIRST()*即FIRST()是由所能推出的所有(suyu)终结符串的首字符或。第23页/共80页第二十四页，共80页。若A的产生(chnshng)式为A1|2|n则FIRST(A)=FIRST(1)FIRST(2)若A有多个候选式的终结首符集含a,则仍需进行试探。可见,要消除回溯,准确指派一个候选式去执行(zhxng)匹配任务,则各候选式的终结首符集应互不相

11、交,即FIRST(i)FIRST(j)=(ij)第24页/共80页第二十五页，共80页。如何使候选(huxun)式的终结首符集互不相交?方法是提取公共左因子。提取公共左因子考虑产生式:AabA|aB|ab改写文法:AaAAbA|B|b改写第2式:AbA|BAA|第25页/共80页第二十六页，共80页。一般地,假设文法中A的产生式为A1|2|i|i+1|j提取公共左因子后,改写为AA|i+1|jA1|2|i经反复(fnf)提取公共左因子,可使每个非终结符的终结首符集互不相交。第26页/共80页第二十七页，共80页。消除左递归和提取公共左因子后,任一非终结符的终结首符集互不相交。此时,若不属于任一

12、非终结符的终结首符集,则可进行有效的自上而下分析,如LL(1)分析。然而,由于(yuy)消除左递归和提取公共左因子后,文法中引进了大量-生成式,这就引出了自动匹配问题。第27页/共80页第二十八页，共80页。对于(duy)文法GE:ETEE+TE|TFTT*FT|F(E)|i考虑输入串i+i#EETFTi+ETFTi(3)自动自动(zdng)匹配匹配问题问题第28页/共80页第二十九页，共80页。当A面临输入(shr)符a时,若aFIRST(A)且FIRST(A),则需要考虑自动匹配问题。对于上述算术表达式文法,若输入(shr)串为i/i,即使让T进行自动匹配,/也不能与后面的符号匹配,此时就

13、没必要进行自动匹配。第29页/共80页第三十页，共80页。因此,只有当前输入(shr)符能与A后第一个终结符匹配成功时,才让A自动得到匹配。这就要求分析前先求出紧跟在A后的终结符,即FOLLOW(A)。第30页/共80页第三十一页，共80页。FOLLOW(A)的定义(dngy)对文法GS的任一非终结符A,定义(dngy)FOLLOW(A)=a|SAa,aVT若SA,则规定#FOLLOW(A)*即FOLLOW(A)是所有句型中紧跟(jnn)在A之后的终结符或#。因SS,故#FOLLOW(S)*0第31页/共80页第三十二页，共80页。自动匹配条件当非终结符A面临输入(shr)符a时,若aFIRS

14、T(A)且FIRST(A),则仅当aFOLLOW(A)时,才使A自动匹配。缺少任一条件,均不自动匹配。第32页/共80页第三十三页，共80页。若输入(shr)符aFIRST(A)且aFOLLOW(A),则当FIRST(A)时仍需回溯。因此,对于存在-生成式的非终结符A,若要进行无回溯的自上而下分析,则FIRST(A)与FOLLOW(A)应互不相交。第33页/共80页第三十四页，共80页。确定(qudng)的自上而下分析的文法条件:LL(1)文法条件文法不含左递归;文法中每个非终结符的各个候选式的终结首符集互不相交;对文法的任一非终结符A,若A的终结首符集包含,则FIRST(A)FOLLOW(A

15、)=第34页/共80页第三十五页，共80页。递归下降分析法是一种自上而下分析法,文法的每个非终结符对应一个(y)递归过程。分析过程从文法开始符出发,执行一组递归过程,这样向下推导直到推出句子。3.递归下降递归下降(xijing)分析器分析器第35页/共80页第三十六页，共80页。若文法不含左递归且每个非终结符的候选式无公共左因子,则可构造不带回溯(hus)的递归下降分析程序。该程序由一组过程组成,每个过程对应文法的一个非终结符。这样的分析程序也称为递归下降分析器。第36页/共80页第三十七页，共80页。例如,对于不含左递归的算术表达式文法,其对应(duyng)的递归下降分析器如下:voidE(

16、)T();E();voidE()if(lookahead=+)match(+);T();E();第37页/共80页第三十八页，共80页。voidT()F();T();voidT()if(lookahead=*)match(*);F();T();第38页/共80页第三十九页，共80页。voidF()if(lookahead=i)match(i);elseif(lookahead=()match();E();if(lookahead=)match();elseerror();elseerror();第39页/共80页第四十页，共80页。说明:考虑E的产生式:E+TE|E有两个候选式,E面临输入(s

17、hr)符+时第一个候选式工作,面临其它符号时E自动匹配。第40页/共80页第四十一页，共80页。假定递归函数的调用以栈的形式模拟,下面分析输入串#i1*(i2+i3)#的语法分析过程:首先,将#和文法开始(kish)符E压入栈中。当语法分析进行到栈中仅剩#而输入串指针已指向输入串尾部的#时,则语法分析成功。分析过程如下图所示:第41页/共80页第四十二页，共80页。E#TE#FT E#T E#iFT E#*E)T E#TE)T E#(FT E)T E#T E)T E#iE)T E#TE)T E#+FT E)T E#T E)T E#iE)T E#T E#E#输入(shr)串i1*(i2+i3)的

18、语法分析过程)第42页/共80页第四十三页，共80页。递归程序法的优缺点:优点(yudin):(1)易于处理递归成分(2)易于写出程序(3)易懂缺点:(1)需要编写的程序是可递归的(2)程序量大(3)出错处理定位不准确第43页/共80页第四十四页，共80页。LL(1)分析法又称预测分析法,是一种无回溯(hus)的非递归自上而下分析法.LL(1)的含义:第一个L表明自左至右扫描输入串;第二个L表明最左推导;1表明向右查看1个符号。LL(k)文法:向前查看k个符号才能确定选用哪个产生式。4.LL(1)分析法分析法(预测预测(yc)分析法分析法)第44页/共80页第四十五页，共80页。4.1表驱动的

19、LL(1)分析器LL(1)分析法的基本思想:根据输入串的当前输入符确定选用某一个产生式进行推导,当该输入符与推导的第一个符号相同(xintn)时,再取输入串的下一个符号,继续确定下一步推导应选的产生式,如此下去,直到推出输入串为止。一个LL(1)分析器由一张LL(1)分析表(预测分析表)、一个先进后出分析栈和一个控制程序(表驱动程序)组成。第45页/共80页第四十六页，共80页。a1a2aian#分析表M控制程序输入串:栈顶#x1xj输出分析栈图3-14LL(1)分析器第46页/共80页第四十七页，共80页。对LL(1)分析器的几点说明:(1)输入串是待分析的符号串,它以#作为结束标志。(注:

20、#VT但不是文法符号)(2)分析栈存放分析过程的文法符号。分析开始时栈底先放一个(y)#,再压入文法开始符。当分析栈中仅剩#且输入串指针指向串尾#时,分析成功。第47页/共80页第四十八页，共80页。(3)分析表用一个矩阵M表示。矩阵M的每一行与文法的一个非终结符相关联,每一列与文法的一个终结符或#关联。MA,a中的内容为一条A的产生式,表示当A面临输入(shr)符a时应采用的候选式。当MA,a中的内容为空时,表示A不应面临输入(shr)符a,即输入(shr)串含语法错误。第48页/共80页第四十九页，共80页。(4)控制程序根据分析栈栈顶符号x和当前输入符a决定(judng)分析器的动作:若

21、xa“#”,则分析成功。若xa“#”,即栈顶符号x与当前输入符a匹配,则将x从栈顶弹出,输入串指针后移,继续对下一个字符进行分析。若x为非终结符A,则查分析表元素A,a:第49页/共80页第五十页，共80页。i.若MA,a为一产生式,则A自栈顶弹出,MA,a中产生式的右部符号(fho)逆序入栈;若MA,a为A,则只将A自栈顶弹出。ii.若MA,a为空,则发现语法错误,调用出错处理程序进行处理。第50页/共80页第五十一页，共80页。控制程序描述如下:把#和文法开始符依次入栈;把第一个输入(shr)符读入a;do把栈顶符号弹出并放入x中;if(xVT)if(x=a)读入下一输入(shr)符a;e

22、lseerror();elseif(Mx,a=“xy1y2yk”)把y1y2yk按逆序入栈;输出“xy1y2yk”;elseerror();while(x!=“#”)第51页/共80页第五十二页，共80页。例一个(y)文法的LL(1)分析表如下所示,试给出输入串aadl的分析过程。输入串aadl的分析过程(guchng)如下:abld#A AaA A AABlA A BBdB B BbB B 第52页/共80页第五十三页，共80页。符号栈当前输入符输入串 说明#Aaadl#弹出栈顶符,将AaA右部逆序入栈#Aaaadl#匹配,弹出栈顶符a,读入下一输入符a#Aadl#弹出栈顶符,AABl右部逆

23、序入栈#lBAadl#弹出栈顶符,AaA右部逆序入栈#lBAaadl#匹配,弹出栈顶符a,读入下一输入符d#lBAdl#由A仅弹出栈顶符号A#lBdl#弹出栈顶符,BdB右部逆序入栈#lBddl#匹配,弹出栈顶符d,读下一输入符l#lBl#由B仅弹出栈顶符号B#ll#匹配,弹出栈顶符l,读下一输入符#匹配,分析成功第53页/共80页第五十四页，共80页。LL(1)分析器中除了分析表不同外,分析栈、控制程序都相同,故构造(guzo)一个LL(1)分析器实际上就是构造(guzo)文法的LL(1)分析表。为了构造(guzo)分析表M,需要预先定义FIRST集和FOLLOW集。4.2 LL(1)分析分

24、析(fnx)表的构造表的构造第54页/共80页第五十五页，共80页。假定(jidng)是文法GS的任一符号串,(VTVN)*,FIRST()a|a,aVT若,则规定FIRST(),即FIRST()是的所有可能推出的首终结符或。*第55页/共80页第五十六页，共80页。(1)FIRST集的构造方法对任一终结符a,FIRST(a)=a。对每个非终结符X连续使用下述规则(guz),直到FIRST集不再增大为止。若有Xa,则把a加入FIRST(X);若有X,则把加入FIRST(X);若有XY,YVN,则把FIRST(Y)的所有非元素都加入FIRST(X);若有XY1Y2Yk,而Y1Yi1都有,则把FI

25、RST(Yj)(j=1,2,i)的所有非元素都加入FIRST(X);若Y1Yk均有,把加入FIRST(X).第56页/共80页第五十七页，共80页。例试构造文法GE的FIRST集。GE:ETE,E+TE|TFT,T*FT|F(E)i解:FIRST(E)=+,;FIRST(T)=*,;FIRST(F)(,i;由TF知,把FIRST(F)的所有非元素(yuns)加入FIRST(T),故FIRST(T)=(,i;由ET知,把FIRST(T)的所有非元素(yuns)加入FIRST(E),故FIRST(E)=(,i。FIRST(E)=(,iFIRST(E)=+,FIRST(T)=(,iFIRST(T)=

26、*,FIRST(F)(,i第57页/共80页第五十八页，共80页。对文法GS的任何(rnh)非终结符A,定义FOLLOW(A)=a|SAa,aVT若SA,则规定#FOLLOW(A)即FOLLOW(A)是所有句型中出现在紧随A之后的终结符或#。*第58页/共80页第五十九页，共80页。(2)FOLLOW集构造方法方法:对每个非终结符A,连续使用下述规则(guz),直到FOLLOW(A)不再增大止.对文法开始符S,把#加入FOLLOW(S)若有AB(可为空),则将FIRST()加入FOLLOW(B);若有AB或AB且,则把FOLLOW(A)加入到FOLLOW(B)。*第59页/共80页第六十页，共

27、80页。例试构造文法GE的FOLLOW集。GE:ETEE+TE|TFTT*FT|F(E)|i解法(jif)1:1)FOLLOW(E)=#2)对于产生式ETE,因FIRST(E)FOLLOW(T),故FOLLOW(T)=+因FOLLOW(E)FOLLOW(E),故FOLLOW(E)=#由ETE且E知,FOLLOW(E)FOLLOW(T),故FOLLOW(T)=+,#FIRST(E)=(,iFIRST(E)=+,FIRST(T)=(,iFIRST(T)=*,FIRST(F)(,i第60页/共80页第六十一页，共80页。对于(duy)产生式E+TE,FIRST(E)FOLLOW(T)FOLLOW(E

28、)FOLLOW(E)由E+TE且E知,FOLLOW(E)FOLLOW(T),故FOLLOW(T)=+,#对于(duy)产生式TFT,因FIRST(T)FOLLOW(F),故FOLLOW(F)=*因FOLLOW(T)FOLLOW(T),故FOLLOW(T)=+,#由TFT且T知,FOLLOW(T)FOLLOW(F),故FOLLOW(F)=*,+,#FIRST(E)=(,iFIRST(E)=+,FIRST(T)=(,iFIRST(T)=*,FIRST(F)(,i第61页/共80页第六十二页，共80页。对于(duy)产生式T*FT,FIRST(T)FOLLOW(F)FOLLOW(T)FOLLOW(T

29、)由T*FT且T知,FOLLOW(T)FOLLOW(F),故FOLLOW(F)=*,+,#对于(duy)产生式F(E)因FIRST()FOLLOW(E),故FOLLOW(E)=#,)第一轮结束(jish),FOLLOW集如下:FOLLOW(E)=),#FOLLOW(F)=*,+,#FOLLOW(T)=+,#FOLLOW(T)=+,#FOLLOW(E)=#第62页/共80页第六十三页，共80页。第二轮循环(xnhun)：3)对于产生式ETE,因FOLLOW(E)FOLLOW(E),故FOLLOW(E)=#,)由ETE且E知,FOLLOW(E)FOLLOW(T),故FOLLOW(T)=+,#,)对

30、于产生式E+TE,FOLLOW(E)FOLLOW(E)由E+TE且E知,FOLLOW(E)FOLLOW(T),故FOLLOW(T)=+,#,)第一轮结束(jish):FOLLOW(E)=),#FOLLOW(F)=*,+,#FOLLOW(T)=+,#FOLLOW(T)=+,#FOLLOW(E)=#第63页/共80页第六十四页，共80页。对于(duy)产生式TFT,因FOLLOW(T)FOLLOW(T),故FOLLOW(T)=+,#,)由TFT且T知,FOLLOW(T)FOLLOW(F),故FOLLOW(F)=*,+,#,)对于(duy)产生式T*FT,FOLLOW(T)FOLLOW(T)由T*F

31、T且T知,FOLLOW(T)FOLLOW(F),故FOLLOW(F)=*,+,#,)对于(duy)产生式F(E),第二轮无需考虑。第64页/共80页第六十五页，共80页。第二轮结束(jish):FOLLOW(F)=*,+,#,)FOLLOW(T)=+,#,)FOLLOW(T)=+,#,)FOLLOW(E)=#,)FOLLOW(E)=),#第三轮循环(xnhun)：(略)最终(zuzhn)的FOLLOW集如下:FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#第65页/共80页第六十六页，共80页。例

32、试构造(guzo)文法GE的FOLLOW集。GE:ETEE+TE|TFTT*FT|F(E)|i解2:1)FOLLOW(E)=#2)由ETE知,FIRST(E)FOLLOW(T),FOLLOW(T)=+由E+TE,FIRST(E)属由TFT知,FIRST(T)FOLLOW(F),FOLLOW(F)=*由T*FT知,FIRST(T)属由F(E)|i知,FIRST()FOLLOW(E),FOLLOW(E)=),#FIRST(E)=(,iFIRST(E)=+,FIRST(T)=(,iFIRST(T)=*,FIRST(F)(,i第66页/共80页第六十七页，共80页。3)由ETE知,FOLLOW(E)F

33、OLLOW(E),FOLLOW(E)=),#由ETE且E知,FOLLOW(E)F.(T),FOLLOW(T)=+,),#由E+TE知,FOLLOW(E)属于(shy)由E+TE且E知,FOLLOW(E)F.(T),FOLLOW(T)=+,),#由TFT知,FOLLOW(T)FOLLOW(T),FOLLOW(T)=+,),#由TFT且T知,FOLLOW(T)F.(F),FOLLOW(F)=*,+,),#由T*FT知,FOLLOW(T)属 由T*FT且T知,FOLLOW(T)F.(F),FOLLOW(F)=*,+,),#考虑F(E)|i FOLLOW(T)=+FOLLOW(F)=*FOLLOW(E

34、)=),#第67页/共80页第六十八页，共80页。FOLLOW集如下(rxi):FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#第68页/共80页第六十九页，共80页。(3)构造分析(fnx)表M1)对每个产生式A1|n执行i),ii):i)对FIRST(A)中每个终结符a,把Ai加到MA,a中,其中i为终结首符集含a的候选式或唯一候选式;ii)若FIRST(A),则对任何属于FOLLOW(A)的终结符b,将A加入MA,b;2)把所有无定义的MA,a标记为出错。第69页/共80页第七十页，共80页

35、。例试构造文法GE的LL(1)分析(fnx)表GE:ETE,E+TE|TFT,T*FT|F(E)i解:首先构造FIRST集:FIRST(E)=+,FIRST(T)=*,FIRST(F)=(,iFIRST(T)=(,iFIRST(E)=(,i第70页/共80页第七十一页，共80页。其次(qc)构造FOLLOW集:FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#第71页/共80页第七十二页，共80页。最后构造(guzo)文法GE的LL(1)分析表:i+*()#EETEETEEE+TEEETTFTTFT

36、TTT*FTTTFFiF(E)若一个文法(wnf)的LL(1)分析表不含多重入口,则称该文法(wnf)为LL(1)文法(wnf)。FOLLOW(E)=),#FOLLOW(T)=+,),#FIRST(E)=+,FIRST(T)=*,FIRST(F)=(,iFIRST(T)=(,iFIRST(E)=(,i第72页/共80页第七十三页，共80页。一个CFG文法是LL(1)文法的条件:(1)文法不含左递归。(2)文法中每个非终结符的各个候选式的终结首符集互不相交(xingjio)。(3)对文法的任一非终结符A,若A的候选终结首符集包含,则FIRST(A)FOLLOW(A)=第73页/共80页第七十四页

37、，共80页。例if-else语句的文法GS为:GS:SiESeSiESaEb其中e遵从(zncng)最近匹配原则,试改造文法并构造其LL(1)分析表解:通过提取公共左因子,得文法GS:GS:SiESSaSeS|Eb第74页/共80页第七十五页，共80页。首先(shuxin)求每个非终结符的FIRST集:FIRST(S)=i,a,FIRST(S)=e,FIRST(E)=bSiESS|aSeS|Eb第75页/共80页第七十六页，共80页。其次(qc)求非终结符的FOLLOW集:1)FOLLOW(S)=#;2)由SES知,FIRST(S)FOLLOW(E)FOLLOW(E)=i,a由SSS知,FIR

38、ST(S)FOLLOW(S),FOLLOW(S)=e,#3)由SSS知,FOLLOW(S)FOLLOW(S),FOLLOW(S)=e,#由SSS且S知,FOLLOW(S)SiESS|aSeS|Eb由此可得,FOLLOW(E)=i,aFOLLOW(S)=e,#FOLLOW(S)=e,#第76页/共80页第七十七页，共80页。最后构造文法(wnf)GS 的分析表:ieab#SSiESSSaSSeSSSEEbFOLLOW(E)=i,aFOLLOW(S)=e,#FOLLOW(S)=e,#FIRST(S)=i,a,FIRST(S)=e,FIRST(E)=b第77页/共80页第七十八页，共80页。ieab#SSiESSSaSSeSSEEb由于分析表含多重入口,故文法GS不是LL(1)文法,但由于e遵从最近匹配(ppi)原则,故在MS,e栏置SeS,于是得无二义性的LL(1)分析表:第78页/共80页第七十九页，共80页。练习题：P96-99例题(lt)1,例题(lt)2,例题(lt)3P99-1001.(1)(3)2.(1)(2)(3)第79页/共80页第八十页，共80页。