教学课件第5章自顶向下语法分析方法

资源描述

《教学课件第5章自顶向下语法分析方法》由会员分享，可在线阅读，更多相关《教学课件第5章自顶向下语法分析方法（51页珍藏版）》请在金锄头文库上搜索。

1、编译原理编译原理第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.如果

2、两个产生式有相同的左部，那么它们的右部由不同的不同的终结符开始。文法文法G1S:SpASqBAcAdAaBdBBb编译原理编译原理文法G2S:SApSBqAaAcABbBdBW=ccap自顶向下的推导过程：自顶向下的推导过程：S S Ap Ap cAp cAp ccAp ccAp ccap ccap语法树：语法树：SApSApcASApcAcASApcAcAa编译原理编译原理这个文法的特点：1.每个产生式的右部不全是由终结符号开始。2.如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。3.文法中无空产生式。文法文法G1S:SApSBqAaAcABbBdB编译原理编译原理定

3、义：设 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(FOLL

4、OW(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*，若，则SELEC

5、T(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个符号才可确定选用哪个产生式。编

6、译原理编译原理文法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,

7、所以该文法不是所以该文法不是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.求出能推出的非终结符SABSbCAAbBBaDCAD

8、CbDaSDc非终结符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)中中;

9、 ;若若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)均含有均含

10、有 , ,则把则把加到加到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()），则把F

11、OLLOW（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

12、(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)

16、右部的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# #AaBadAaBadA

17、aBaAcaBbcaAcbcAaBaAcaBbcaAcbc编译原理编译原理消除直接左递归把直接左递归改写为右递归。如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

19、法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.递归子程序法递归子程序法实现思想：对文法中每个非终结符编写一个递归过程，每个过程的功能

21、 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

22、*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)

23、= * , 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

24、 )= ( 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

展开阅读全文

教学课件第5章自顶向下语法分析方法

最新文档