《第4章 自顶向下语法分析方法【专业课堂）》由会员分享，可在线阅读，更多相关《第4章 自顶向下语法分析方法【专业课堂）（51页珍藏版）》请在金锄头文库上搜索。
1、第第4章章 自顶向下语法分析方法自顶向下语法分析方法确定的自顶向下分析思想确定的自顶向下分析思想LL(1)文法的判别文法的判别某些非某些非LL(1)文法到文法到LL(1)文法的等价变文法的等价变换换不确定的自顶向下分析思想不确定的自顶向下分析思想确定的自顶向下分析方法确定的自顶向下分析方法1确定的自顶向下分析思想确定的自顶向下分析思想文法文法G1S:SpASqBAcAdAaBdBBbW=pccadd自顶向下的推导过程：自顶向下的推导过程：S S pA pA pcAd pcAd pccAdd pccAdd pccadd pccadd语法树：语法树：SpASpAcA dSpAcA dcA dSpA
2、cA dcA da2这个文法的特点：这个文法的特点：1.每个产生式的右部都每个产生式的右部都由由终结符号终结符号开始开始。2.如果如果两个产生式两个产生式有相同有相同的左部的左部，那么它们的，那么它们的右右部由部由不同的不同的终结符开始终结符开始。文法文法G1S:SpASqBAcAdAaBdBBb3文法文法G2S:SApSBqAaAcABbBdBW=ccap自顶向下的推导过程：自顶向下的推导过程：S S Ap Ap cAp cAp ccAp ccAp ccap ccap语法树：语法树：SApSApcASApcAcASApcAcAa4这个文法的特点：这个文法的特点：1.每个产生式的右部每个产生式
3、的右部不全是不全是由由终结符号终结符号开始开始。2.如果如果两个产生式两个产生式有相同的有相同的左部左部，那么它们的，那么它们的右部由右部由不同的不同的终结符终结符或或非终结符非终结符开始开始。3.文法中无空产生式。文法中无空产生式。文法文法G1S:SApSBqAaAcABbBdB5定义：设定义：设 G = (VT ,VN , S , P) 是上下文无关是上下文无关文法，文法，FIRST() = a| a,a VT, V*若若 ，则规定则规定FIRST()* *调用返回6FIRST(Ap)=a,cFIRST(Bq)=b,d文法文法G2S:SApSBqAaAcABbBdB7文法文法G3S:SaA
4、SdAbASAW=abd试图试图推导的过程：推导的过程：S S aA aA ababA AS S abS abS abd abd8定义：设定义：设 G = (VT ,VN , S , P) 是上下文无关文法，是上下文无关文法，AVN , S是开始符号。是开始符号。 FOLLOW(A) = a|a|S S A A 且且a aFRIST(FRIST( ), ), VVT T* *, , VV+ + 若若S S A A ,且且 ，则规定，则规定 #FOLLOW(A)即：即：FOLLOW(A)=a|S Aa ,aVVT T若若S A，则规定则规定 #FOLLOW(A)#作为输入串的结束符，或称为句子括
5、号，如：作为输入串的结束符，或称为句子括号，如：#输入串输入串#* *调用返回9对对AA其中其中AVN , , VN*当当和和不同时推导出空时（设不同时推导出空时（设 不推导出空，不推导出空，推导出空），则当推导出空），则当FIRST()(FIRST()FOLLOW(A)=时，对于非终结符时，对于非终结符A的替换仍可唯一地确定的替换仍可唯一地确定候选。候选。10定义：给定上下文无关文法的产生式定义：给定上下文无关文法的产生式A，AVN , V*，若若 ，则则SELECT(A)=FIRST()如果如果 ，则则SELECT(A)=FIRST()FOLLOW(A)*调用返回11定义：一个上下文无关文
6、法是定义：一个上下文无关文法是LL(1)文法文法的的充要条件是：充要条件是：对每个非终结符对每个非终结符A的两个不同产生式的两个不同产生式A和和A，满足满足SELECT(A)SELECT(A)=其中其中,不同时能不同时能 *12LL(1)文法的含义：文法的含义：第一个第一个L表示：自顶向下分析是表示：自顶向下分析是从左向右扫从左向右扫描描输入串输入串。第二个第二个L表示：分析过程中将用表示：分析过程中将用最左推导最左推导。 1表示：只需表示：只需向右看一个符号向右看一个符号便可决定如何便可决定如何推导（即选择哪个产生式进行推导）。推导（即选择哪个产生式进行推导）。类似也可以有类似也可以有LL(
7、K)文法：需向前查看文法：需向前查看K个个符号才可确定选用哪个产生式。符号才可确定选用哪个产生式。13文法文法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)文法。文法。14设文法设文法GS 为为:SaASSbAbAASELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b,SELE
8、CT(SaAS) SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b,所以该文法不是所以该文法不是LL(1)文法。文法。15GS:SaASSbAbAA对输入串对输入串W=abW=ab进行推导：进行推导：S S a aA AS S abAS abAS abS abS 出错出错S S a aA AS S aS aS ab ab16LL(1)文法的判别文法的判别1.求出能推出求出能推出的非终结符的非终结符2.计算计算FIRST集集3.计算计算FOLLOW集集4.计算计算SELECT集集5.判别是否是判别是否是LL(1)文法文法17例：设文法例：设文法GS 为为:SABSb
9、CAAbBBaDCADCbDaSDc判断它是否是判断它是否是LL(1)文法。文法。181.求出能推出求出能推出的非终结符的非终结符SABSbCAAbBBaDCADCbDaSDc非终结符非终结符SABCD初值初值未定未定未定未定未定未定未定未定未定未定第一次扫描第一次扫描是是是是否否第二次扫描第二次扫描是是否否192.计算计算FIRST集集1.若X X X X V V V V ,则FIRST(X)=X2.若XVN,且有产生式X X X Xa a a a，则aFIRST(X);若X X X X也是一条产生式,则FIRST(X).3.若X X X XY Y Y Y是一个产生式且YVN,则把FIRST
10、(Y)中的所有非元素都加到FIRST(X)中;若X X X X Y Y Y Y1 1 1 1Y Y Y Y2 2 2 2Y Y Y YK K K K 是一个产生式,Y1,Y2,Y(i-1)都是非终结符,而且,对于任何j,1j i-1,FIRST(Yj)都含有(即Y Y Y Y1 1 1 1.Y.Y.Y.Y(i-1)(i-1)(i-1)(i-1) ),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,K)均含有,则把加到FRIST(X)中.* *20SABSbCAAbBBaDCADCbDaSDcFIRST(S)=(FIRST(A)-)
11、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,c213.计算计算FOLLOW集集1.1.对于文法的开始符号对于文法的开始符号S, ,置置#于于FOLLOW(FOLLOW(S) ) 中中; ;2.2.若若B是一个产生式是一个产生式, ,则把则把 FIRST()FIRST() 加至加至FOLLOW(B)FOLLOW(B)中中; ;3.3.若若B是一个产生式是一个产生式, ,或或B是是 一个产生式而一个产生式而 ( (即即 FIRST()FIRST()），），
12、 则把则把FOLLOWFOLLOW（A A），），加至加至FOLLOWFOLLOW（B B）中中* *22SABSbCAAbBBaDCADCbDaSDcFOLLOW(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)= #234.计算计算SELECT集集SABSbCAAbBBaDCADCbDaSDcFIRST(S)=a,b
13、,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)文法。24某些非某
14、些非LL(1)文法到文法到LL(1)文法的等价变换文法的等价变换提取左公共因子提取左公共因子消除左递归消除左递归25提取左公共因子提取左公共因子A|导致导致SELECT(A) SELECT(A)，因此非因此非LL(1)文法。文法。等价变换为等价变换为A(|)，然后：然后：AAA |A1|2|n 变换为变换为A(1|2|n) ，然后：然后：AAA 1|2|n26例：文法例：文法G1S 为为:SaSbSaSS化为：化为：SaS(b|)S进一步化为：进一步化为：SaSAAbAS结果仍然不是LL(1)文法。因此，文法中不含左公共因子只是LL(1)文法的必要条件。w=aabbS=aSA =aaSAA =
15、aaAA =aabA (aaA)27例：文法例：文法G2为为:AadABcBaABbB1.化为：化为：AadAaAcAbBcBaABbB2.化为：化为：Aa(d|Ac)AbBcBaABbB3.化为：化为：AaA AbBcAdAAcBaABbB结果是LL(1)文法。28例：文法例：文法G3S 为为:SaSdSAcAaSAb1.化为：化为：SaSdSaScSbc AaSAb2.化为：化为：SaS(d|c)Sbc AaSAb3.化为：化为：SaSA SbcAdAcAaSAb结果中A是不可达到的符号。29例：文法例：文法G4S 为为:SAp|BqAaAp|dBaBq|e1.化为：化为：SaApp|aB
16、qq|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利用提取左公共因子利用提取左公共因子利用提取左公共因子利用提取左公共因子无法在有限步骤内无法在有限步骤内无法在有限步骤内无法在有限步骤内替替替替换成无左公共因子的文法换成无左公共因子的文法换成无左公共因子的文法换成无左公共因子的文法30结论结论不一定每个文法的左公共因子都能在有限不一定每个文法的左公共因子都
17、能在有限的步骤内替换成无左公共因子的文法。的步骤内替换成无左公共因子的文法。一个文法提取了左公共因子后，只解决了一个文法提取了左公共因子后，只解决了相同左部产生式右部的相同左部产生式右部的FIRST集不相交问题，集不相交问题，当改写后的文法不含空产生式，且无左递当改写后的文法不含空产生式，且无左递归时，则改写后的文法是归时，则改写后的文法是LL(1)文法，否则文法，否则还需用还需用LL(1)文法的判别方式进行判断才能文法的判别方式进行判断才能确定是否为确定是否为LL(1)文法。文法。31消除左递归消除左递归直接左递归：直接左递归：AA AVN, V*间接左递归：间接左递归：ABBA A,BVN
18、, , V*32文法文法G5含有直接左递归：含有直接左递归：SSaSb所能产生的语言所能产生的语言L=ban|n0输入串输入串baaaa#是该语言的句子，但如何用是该语言的句子，但如何用自顶向下分析呢？自顶向下分析呢？33文法文法G6含有间接左递归：含有间接左递归：AaBABbBAcBd输入串输入串adbcbcbc#AaBadAaBaAcaBbcaAcbc34消除直接左递归消除直接左递归把直接左递归改写为右递归。如把直接左递归改写为右递归。如G5:SSaSb(L=ban|n0)改为：改为：SbSSaS|35消除直接左递归的一般方法：消除直接左递归的一般方法：AA1| A2| Am|1|2|n其
19、中：其中： i 不等于不等于 ， j不以不以A开头。开头。 改为：改为：A 1A| 2A | nA A 1A | 2A | mA |36消除间接左递归消除间接左递归将间接左递归变为直接左递归，然后消除将间接左递归变为直接左递归，然后消除直接左递归。如文法直接左递归。如文法G6含有间接左递归：含有间接左递归：AaBABbBAcBdBaBcBBbcBdBaBcB | dB BbcB| 37消除文法中一切左递归的算法消除文法中一切左递归的算法1.无回路无回路(A(A (A) 2.无空产生式无空产生式（1） 以某种顺序将文法非终结符排列以某种顺序将文法非终结符排列A1 ,A2 An（2） for i:
20、=1 to n dobegin for j:=1 to i-1 do 用用Ai- 1| 2r| k r替代替代形如形如Ai- Ajr的规则的规则,其中其中Aj- 1| 2| k是关于是关于Aj的全部产生式的全部产生式;消除消除Ai规则的直接左递归规则的直接左递归; end;（3）化简由化简由2得到的文法得到的文法+38例：例：文法文法G:SQc|cQRb|bRSa|aR Qca|ca|aR Rbca|bca|ca|aR (bca|ca|a)RR bcaR|参考P.8439不确定的自顶向下分析思想不确定的自顶向下分析思想1.由于相同左部的产生式的右部由于相同左部的产生式的右部FIRST集交集交集
21、不为空引起回溯。集不为空引起回溯。SxAyAab|aw=xaySx A ySx A ya bSx A ya试探 回溯 试探402.由于相同左部非终结符的右部能由于相同左部非终结符的右部能 且该且该非终结符非终结符FOLLOW集中含有其右部集中含有其右部FIRST集的元素。集的元素。设文法设文法GS 为为:SaASSbAbASA*w=ab#Sa A SSa A Sb A SSa A S b试探再试探回溯413.由于文法含有左递归而引起回溯。由于文法含有左递归而引起回溯。设文法设文法GS 为为:SSaSbw=baa#SbSS aSS abSS aS aSS aS ab42确定的自顶向下分析方法确定
22、的自顶向下分析方法1.递归子程序法递归子程序法实现思想：对文法中每个非终结符编写一实现思想：对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生非终结符推出的串，当某非终结符的产生式有多个候选时能够按式有多个候选时能够按LL(1)形式可唯一地形式可唯一地确定选择某个候选进行推导。确定选择某个候选进行推导。限制：对文法要求高，必须满足限制：对文法要求高，必须满足LL(1)文法；文法；由于递归调用多，速度慢，占用空间多。由于递归调用多，速度慢，占用空间多。432.预测分析法预测分析法预测分析器：预测分析器：预测分析程
23、序（预测分析程序（P.88）先进后出栈先进后出栈预测分析表预测分析表44预测分析表的构造预测分析表的构造表达式文法：表达式文法：E E+T | TT T*F | FF i | ( E )45构造过程构造过程1.判断文法是否为判断文法是否为LL(1)文法文法消除左递归：消除左递归：E E+T | TT T*F | FF i | ( E )E TEE +TE | T FTT *FT | F i | ( E )46可推出可推出 的非终结符表：的非终结符表：E TEE +TE | T FTT *FT | F i | ( E )EETTF否否是是否否是是否否47各非终结符的各非终结符的FIRST集和集和
24、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定义48各产生式的各产生式的SELECT集：集：E TEE +TE | T FTT *FT | F i | ( E )SE
25、LECT(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)= + , ) ,
26、 # FOLLOW(F)= * , + , ) , # 查看SELECT定义是LL(1)文法。492.构造预测分析表构造预测分析表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 )50运行：运行：i+*()#ETETEE +TE TFTFTT *FT F i ( 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*i51
