【教学课件】第5章自顶向下语法分析方法.ppt
编译原理编译原理第5章 自顶向下语法分析方法 确定的自顶向下分析思想 LL(1)文法的判别 某些非LL(1)文法到LL(1)文法的等 价变换 不确定的自顶向下分析思想 确定的自顶向下分析方法返回目录编译原理编译原理确定的自顶向下分析思想文法G1S:SpASqBAcAdAaBdBBbW=pccadd自顶向下的推导过程：自顶向下的推导过程：S S pA pA pcAd pcAd pccAdd pccAdd pccadd pccadd语法树：语法树：SpASpAcA dSpAcA dcA dSpAcA dcA da编译原理编译原理这个文法的特点：1.每个产生式的右部都由终终结符号结符号开始。2.如果两个产生式有相同的左部，那么它们的右部由不同的不同的终结符开始。文法文法G1S:SpASqBAcAdAaBdBBb编译原理编译原理文法G2S:SApSBqAaAcABbBdBW=ccap自顶向下的推导过程：自顶向下的推导过程：S S Ap Ap cAp cAp ccAp ccAp ccap ccap语法树：语法树：SApSApcASApcAcASApcAcAa编译原理编译原理这个文法的特点：1.每个产生式的右部不全是由终结符号开始。2.如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。3.文法中无空产生式。文法文法G1S:SApSBqAaAcABbBdB编译原理编译原理定义：设 G=(VT,VN,S,P)是上下文无关文法，FIRST()FIRST()=a|a a,a VT,V+,V*,若 ，则规定FIRST()*调用返回编译原理编译原理FIRST(Ap)=a,cFIRST(Bq)=b,d文法文法G2S:SApSBqAaAcABbBdB编译原理编译原理文法G3S:SaASdAbASAW=abd试图试图推导的过程：推导的过程：S S aA aA ababA AS S abS abS abd abd编译原理编译原理定义：设 G=(VT,VN,S,P)是上下文无关文法，AVN,S是开始符号。FOLLOW(FOLLOW(A A)=a|S A且aFRIST(),VT*,V+若S A,且 ，则规定#FOLLOW(A)即：FOLLOW(A)=a|S FOLLOW(A)=a|S AaAa,a,aVVT T 若S A，则规定#FOLLOW(A)#作为输入串的结束符，或称为句子括号，如：#输入串#*调用返回编译原理编译原理对A，A其中AVN,VN*，当和不同时推导出空时（设 不推导出空，推导出空），则当FIRST()(FIRST()FOLLOW(A)=时，对于非终结符A的替换仍可唯一地确定候选。编译原理编译原理定义：给定上下文无关文法的产生式A，AVN,V*，若 ，则SELECT(A)=FIRST()如果 ，则SELECT(A)=FIRST()FOLLOW(A)*调用返回编译原理编译原理定义：一个上下文无关文法是LL(1)文法的充要条件是：对每个非终结符A的两个不同产生式A和A，满足SELECT(A)SELECT(A)=其中,不同时能 。*编译原理编译原理LL(1)文法的含义：第一个L L表示：自顶向下分析是从左向右扫描从左向右扫描输入串输入串。第二个L L表示：分析过程中将用最左推导最左推导。1 1表示：只需向右看一个符号向右看一个符号便可决定如何推导（即选择哪个产生式进行推导）。类似也可以有LL(K)LL(K)文法：需向前查看K个符号才可确定选用哪个产生式。编译原理编译原理文法GS是否是LL(1)文法:SaASdAbASA SELECT(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,#,SELECT(SaA)SELECT(Sd)=ad=SELECT(AbAS)SELECT(A)=ba,d,#,=所以该文法是所以该文法是LL(1)文法。文法。编译原理编译原理设文法GS 为:SaASSbAbAASELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b,SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b,所以该文法不是所以该文法不是LL(1)文法。文法。编译原理编译原理GS:SaASSbAbAA对输入串对输入串W=abW=ab进行推导：进行推导：S S a aA AS S abAS abAS abS abS 出错出错S S a aA AS S aS aS ab ab编译原理编译原理LL(1)文法的判别1.求出能推出的非终结符2.计算FIRST集3.计算FOLLOW集4.计算SELECT集5.判别是否是LL(1)文法编译原理编译原理例：设文法GS 为:SABSbCAAbBBaDCADCbDaSDc判断它是否是LL(1)文法。编译原理编译原理1.求出能推出的非终结符SABSbCAAbBBaDCADCbDaSDc非终结符SABCD初值未定未定未定未定未定第一次扫描是是否第二次扫描是否编译原理编译原理2.计算FIRST集1.1.若若X X V V,则则FIRST(X)=XFIRST(X)=X2.2.若若X X V VN N,且有产生式且有产生式X Xaa，则则aFIRST(X)aFIRST(X);若若X X也是一条产生式也是一条产生式,则则 FIRST(X)FIRST(X).3.3.若若X XYY是一个产生式且是一个产生式且Y Y V VN N,则把则把FIRST(Y)FIRST(Y)中的所有非中的所有非 元元素都加到素都加到FIRST(X)FIRST(X)中中;若若X X Y Y1 1Y Y2 2YYK K 是一个产生式是一个产生式,Y Y1 1,Y,Y2 2,Y,Y(i-1)(i-1)都是非终结都是非终结符符,而且而且,对于任何对于任何j,1j,1j j ii-1,FIRST(Y-1,FIRST(Yj j)都含有都含有(即即Y Y1 1.Y.Y(i-1)(i-1),),则把则把FIRST(YFIRST(Yj j)中的所有非中的所有非 元元素都加到素都加到FIRST(X)FIRST(X)中中;特别是特别是,若所有的若所有的FIRST(YFIRST(Yj j,j=1,2,K)j=1,2,K)均含有均含有,则把则把 加到加到FRIST(X)FRIST(X)中中.*编译原理编译原理SABSbCAAbBBaDCADCbDaSDcFIRST(S)=(FIRST(A)-)FIRST(B)-)b=a,b,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,cFIRST(AB)=a,b,FIRST(AD)=a,b,c编译原理编译原理3.计算FOLLOW集1.对于文法的开始符号S,置#于FOLLOW(S)。;2.若B是一个产生式,则把 FIRST()加至FOLLOW(B)中;3.若B是一个产生式,或B是 一个产生式而 (即FIRST()），则把FOLLOW（A），加至FOLLOW（B）中*编译原理编译原理SABSbCAAbBBaDCADCbDaSDcFOLLOW(S)=#FOLLOW(D)FOLLOW(A)=aa,cFOLLOW(S)FOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FOLLOW(B)FOLLOW(C)FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#编译原理编译原理4.计算SELECT集SABSbCAAbBBaDCADCbDaSDcFIRST(S)=a,b,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,cFIRST(AB)=a,b,FIRST(AD)=a,b,cSELECT(SAB)=a,b,#SELECT(SbC)=bSELECT(A)=a,c,#,SELECT(Ab)=bSELECT(B)=#,SELECT(BaD)=aSELECT(CAD)=a,b,cSELECT(Cb)=bSELECT(DaS)=aSELECT(Dc)=cFOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#该文法不是LL(1)文法。编译原理编译原理某些非LL(1)文法到LL(1)文法的等价变换 提取左公共因子 消除左递归编译原理编译原理提取左公共因子A|导致SELECT(A)SELECT(A)，因此非LL(1)文法。等价变换为A(|)，然后：AAA|A1|2|n 变换为A(1|2|n)，然后：AAA 1|2|n编译原理编译原理例：文法G1S 为:SaSbSaSS化为：化为：SaS(b|)S进一步化为：进一步化为：SaSAAbAS结果仍然不是LL(1)文法。因此，文法中不含左公共因子只是LL(1)文法的必要条件。w=aabbS=aSA=aaSAA=aaAA=aabA(aaA)编译原理编译原理例：文法G2为:AadABcBaABbB1.化为：化为：AadAaAcAbBcBaABbB2.化为：化为：Aa(d|Ac)AbBcBaABbB3.化为：化为：AaA AbBcAdAAcBaABbB结果是LL(1)文法。编译原理编译原理例：文法例：文法G3SG3S 为为:SaSd SAc AaS Ab1.化为：化为：SaSdSaScSbc AaSAb2.化为：化为：SaS(d|c)Sbc AaSAb3.化为：化为：SaSA SbcAdAcAaSAb结果中A是不可达到的符号。编译原理编译原理例：文法例：文法G4S 为为:SAp|BqAaAp|dBaBq|e1.化为：化为：SaApp|aBqq|dq|eqAaAp|dBaBq|e2.化为：化为：Sa(App|Bqq)Sdq|eqAaAp|dBaBq|e3.化为：化为：SaS Sdq|eqSApp|BqqAaAp|dBaBq|e4.化为：化为：SaS Sdq|eqS aAppp|aBqqq|dpp|eqqAaAp|dBaBq|e利用提取左公共因子利用提取左公共因子利用提取左公共因子利用提取左公共因子无法在有限步骤内无法在有限步骤内无法在有限步骤内无法在有限步骤内替替替替换成无左公共因子的文法。换成无左公共因子的文法。换成无左公共因子的文法。换成无左公共因子的文法。编译原理编译原理结论不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。编译原理编译原理消除左递归直接左递归：AA A VN,V*间接左递归：ABBA A,B VN,V*编译原理编译原理文法G5含有直接左递归：SSaSb所能产生的语言L=ban|n0输入串baaaa#是该语言的句子，但如何用自顶向下分析呢？编译原理编译原理文法文法G6G6含有间接左递归：含有间接左递归：AaBAaBABbABbBAcBAcBdBd输入串输入串adbcbcbcadbcbcbc#AaBadAaBadAaBaAcaBbcaAcbcAaBaAcaBbcaAcbc编译原理编译原理消除直接左递归把直接左递归改写为右递归。如G5:SSaSb(L=ban|n0)改为：SbSSaS|编译原理编译原理消除直接左递归的一般方法：AA1|A2|Am|1|2|n其中：i 不等于，j不以A开头。改为：A 1A|2A|nA A 1A|2A|mA|编译原理编译原理消除间接左递归将间接左递归变为直接左递归，然后消除直接左递归。如文法G6含有间接左递归：AaBABbBAcBdBaBcBBbcBdBaBcB|dB BbcB|编译原理编译原理消除文法中一切左递归的算法1.无回路(A(A(A)2.无空产生式 （1）以某种顺序将文法非终结符排列A1,A2 An （2）for i:=1 to n do begin for j:=1 to i-1 do 用Ai-1|2r|k r替代形如Ai-Ajr的规则,其中Aj-1|2|k是关于Aj的全部产生式;消除Ai规则的直接左递归;end;（3）化简由2得到的文法+编译原理编译原理例：文法G:SQc|cQRb|bRSa|aR Qca|ca|aR Rbca|bca|ca|aR(bca|ca|a)RR bcaR|编译原理编译原理不确定的自顶向下分析思想1.由于相同左部的产生式的右部FIRST集交集不为空引起回溯。设文法GS 为:SxAy Aab|aw=xaySx A ySx A ya bSx A ya试探 回溯 试探编译原理编译原理2.由于相同左部非终结符的右部能 且该非终结符FOLLOW集中含有其右部FIRST集的元素。设文法GS 为:SaASSbAbASA*w=ab#Sa A SSa A Sb A SSa A S b试探再试探回溯编译原理编译原理3.由于文法含有左递归而引起回溯。设文法GS 为:SSaSbw=baa#SbSS aSS abSS aS aSS aS ab编译原理编译原理确定的自顶向下分析方法1.1.递归子程序法递归子程序法实现思想：对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。限制：对文法要求高，必须满足LL(1)文法；由于递归调用多，速度慢，占用空间多。编译原理编译原理2.2.预测分析法预测分析法预测分析器：预测分析程序（P.88）先进后出栈预测分析表编译原理编译原理预测分析表的构造表达式文法：E E+T|TT T*F|FF i|(E)编译原理编译原理构造过程1.1.判断文法是否为判断文法是否为LL(1)LL(1)文法文法消除左递归：E E+T|TT T*F|FF i|(E)E TEE +TE|T FTT *FT|F i|(E)编译原理编译原理可推出 的非终结符表：E TEE +TE|T FTT *FT|F i|(E)EETTF否是否是否编译原理编译原理各非终结符的FIRST集和FOLLOW集：FIRST(E)=(,i FIRST(E)=+,FIRST(T)=(,i FIRST(T)=*,FIRST(F)=(,i FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#E TEE +TE|T FTT *FT|F i|(E)查看FOLLOW定义查看FIRST定义编译原理编译原理各产生式的SELECT集：E TEE +TE|T FTT *FT|F i|(E)SELECT(E TE)=(,i SELECT(E +TE)=+SELECT(E )=,),#SELECT(T FT)=(,i SELECT(T *FT)=*SELECT(T )=,+,),#SELECT(F (E)=(SELECT(F i)=i FIRST(E)=(,i FIRST(E)=+,FIRST(T)=(,i FIRST(T)=*,FIRST(F)=(,i FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#查看SELECT定义是LL(1)文法。编译原理编译原理2.2.构造预测分析表构造预测分析表SELECT(E TE)=(,i SELECT(E +TE)=+SELECT(E )=,),#SELECT(T FT)=(,i SELECT(T *FT)=*SELECT(T )=,+,),#SELECT(F (E)=(SELECT(F i)=i i+*()#ETETEE+TE TFTFTT *FT F i(E)运行：i i+*()#E ETETE TETEEE +TE+TE T TFTFT FTFTTT *FT*FT F F i i(E)E)分析栈分析栈#E#ET#ETF#ETi#ET#E#ET+#ET#ETF#ETi#ET#ETF*#ETF#ETi#ET#E#剩余串剩余串i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#i*i#i*i#i*i#*i#*i#i#i#产生式产生式ETETFTF ii i 匹配匹配匹配匹配T E +TE+匹配匹配匹配匹配T FTF ii i 匹配匹配匹配匹配T *FT*匹配匹配匹配匹配F ii i 匹配匹配匹配匹配T E 接受接受接受接受例：输入 i+i*i
