第4章自顶向下语法分析方法

1、第4章 自顶向下语法分析方法,确定的自顶向下分析思想 LL(1)文法的判别 某些非LL(1)文法到LL(1)文法的等价变换 不确定的自顶向下分析思想 确定的自顶向下分析方法,确定的自顶向下分析思想,文法G1S:SpASqBAcAdAaBdBBb,W=pccadd自顶向下的推导过程： S pA pcAd pccAdd pccadd,语法树：,S,p,A,S,p,A,c,A,d,S,p,A,c,A,d,c,A,d,S,p,A,c,A,d,c,A,d,a,这个文法的特点： 每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。,文法G1S:SpASqBAc

2、AdAaBdBBb,文法G2S:SApSBqAaAcABbBdB,W=ccap自顶向下的推导过程： S Ap cAp ccAp ccap,语法树：,S,A,p,S,A,p,c,A,S,A,p,c,A,c,A,S,A,p,c,A,c,A,a,这个文法的特点： 每个产生式的右部不全是由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。 文法中无空产生式。,文法G1S:SApSBqAaAcABbBdB,定义：设 G = (VT ,VN , S , P) 是上下文无关文法，FIRST() = a| a,a VT, V*若 ，则规定FIRST(),* ,* ,调用返

3、回,FIRST(Ap)=a,c FIRST(Bq)=b,d,文法G2S:SApSBqAaAcABbBdB,文法G3S:SaASdAbASA,W=abd试图推导的过程： S aA abAS abS abd,定义：设 G = (VT ,VN , S , P) 是上下文无关文法，AVN , S是开始符号。 FOLLOW(A) = a|S A且aFRIST(), VT*,V+ 若S A,且 ，则规定 #FOLLOW(A) 即：FOLLOW(A)=a|S Aa ,aVT若S A，则规定 #FOLLOW(A) #作为输入串的结束符，或称为句子括号，如：#输入串#,* ,* ,* ,* ,* ,调用返回,对

4、AA其中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

5、表示：分析过程中将用最左推导。 1表示：只需向右看一个符号便可决定如何推导（即选择哪个产生式进行推导）。 类似也可以有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 为:SaASSbAbAA,SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=

6、bSELECT(A)=a,b,SELECT(SaAS) SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b,所以该文法不是LL(1)文法。,GS:SaASSbAbAA,对输入串W=ab进行推导： S aAS abAS abS 出错 S aAS aS ab,LL(1)文法的判别,求出能推出的非终结符 计算FIRST集 计算FOLLOW集 计算SELECT集 判别是否是LL(1)文法,例：设文法GS 为:SABSbCAAbBBaDCADCbDaSDc判断它是否是LL(1)文法。,1.求出能推出的非终结符,SABSbCAAbBBaDCADCbDaSDc,2.计算FIRST

7、集,1.若XV,则FIRST(X)=X 2.若XVN,且有产生式Xa，则aFIRST(X);若X也是一条产生式,则FIRST(X). 3.若XY是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X Y1Y2YK 是一个产生式,Y1,Y2,Y(i-1)都是非终结符,而且,对于任何j,1j i-1,FIRST(Yj)都含有(即Y1.Y(i-1) ),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,K)均含有,则把加到FRIST(X)中.,* ,SABSbCAAbBBaDCADCbDaSDc,FIRST

8、(S)=(FIRST(A)-)FIRST(B)-)b=a,b, FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,c FIRST(D)=a,c,FIRST(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）中,* ,SABSbCAAbBBaDCADCbDaSDc,FOLLOW(S)=#FOLLOW(D) FO

9、LLOW(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集,SABSbCAAbBBaDCADCbDaSDc,FIRST(S)=a,b, FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,c FIRST(D)=a,c FIRST(AB)=a,b, FIRST(AD)=a,b,c,SELECT(

10、SAB)=a,b,# SELECT(SbC)=b SELECT(A)=a,c,#, SELECT(Ab)=b SELECT(B)=#, SELECT(BaD)=a SELECT(CAD)=a,b,c SELECT(Cb)=b SELECT(DaS)=a SELECT(Dc)=c,FOLLOW(S)= # FOLLOW(A)= a,c,# FOLLOW(B)= # FOLLOW(C)= # FOLLOW(D)= #,该文法不是LL(1)文法。,某些非LL(1)文法到LL(1)文法的等价变换,提取左公共因子 消除左递归,提取左公共因子,A|导致SELECT(A) SELECT(A)，因此非LL(1

11、)文法。 等价变换为A(|)，然后：AAA | A1|2|n 变换为A(1|2|n) ，然后：AAA 1|2|n,例：文法G1S 为:SaSbSaSS,化为：SaS(b|)S,进一步化为：SaSA Ab A S,结果仍然不是LL(1)文法。因此，文法中不含左公共因子只是LL(1)文法的必要条件。,w=aabb S=aSA =aaSAA =aaAA =aabA (aaA),例：文法G2为:AadABcBaABbB,1.化为：Aad AaAc AbBc BaABbB,2.化为： Aa(d|Ac) AbBc BaABbB,3.化为： AaA AbBc Ad AAc BaABbB,结果是LL(1)文法

12、。,例：文法G3S 为:SaSdSAcAaSAb,1.化为：SaSdSaSc Sbc AaSAb,2.化为： SaS(d|c)Sbc AaSAb,3.化为： SaSA Sbc Ad Ac AaSAb,结果中A是不可达到的符号。,例：文法G4S 为:SAp|BqAaAp|dBaBq|e,1.化为：SaApp|aBqq|dq|eqAaAp|dBaBq|e,2.化为： Sa(App|Bqq)Sdq|eq AaAp|dBaBq|e,3.化为： SaS Sdq|eq SApp|BqqAaAp|dBaBq|e,4.化为： SaS Sdq|eq S aAppp|aBqqq|dpp|eqqAaAp|dBaBq

13、|e,利用提取左公共因子无法在有限步骤内替换成无左公共因子的文法,结论,不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。 一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。,消除左递归,直接左递归：AA AVN, V* 间接左递归：ABBA A,BVN, , V*,文法G5含有直接左递归：SSaSb所能产生的语言L=ban|n0输入串baaaa#是该语言的句子，但如何用自顶向下分析呢？,文法G6含有

14、间接左递归：AaBABbBAcBd输入串adbcbcbc#AaBadAaBaAcaBbcaAcbc,消除直接左递归,把直接左递归改写为右递归。如G5:SSaSb(L=ban|n0) 改为：SbSSaS|,消除直接左递归的一般方法： AA1| A2| Am|1|2|n其中： i 不等于 ， j不以A开头。 改为： A 1A| 2A | nA A 1A | 2A | mA |,消除间接左递归,将间接左递归变为直接左递归，然后消除直接左递归。如文法G6含有间接左递归：AaBABbBAcBd,BaBcBBbcBd,BaBcB | dB BbcB| ,消除文法中一切左递归的算法,1.无回路(A(A (A

15、) 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|a,R Qca|ca|a,R Rbca|bca|ca|a,R (bca|ca|a)R,R bcaR|,参考P.84,不确定的自顶向下分析思想,1.由于相同左部的产生式的右部FIRST集交集不为空引起回溯。

16、SxAy Aab|a,w=xay,S,x A y,S,x A y,a b,S,x A y,a,试探,回溯,试探,2.由于相同左部非终结符的右部能 且该非终结符FOLLOW集中含有其右部FIRST集的元素。 设文法GS 为:SaASSbAbASA,* ,w=ab#,S,a A S,S,a A S,b A S,S,a A S,b,试探再试探,回溯,3.由于文法含有左递归而引起回溯。 设文法GS 为:SSaSb,w=baa#,S,b,S,S a,S,S a,b,S,S a,S a,S,S a,S a,b,确定的自顶向下分析方法,1.递归子程序法 实现思想：对文法中每个非终结符编写一个递归过程，每个过

17、程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。 限制：对文法要求高，必须满足LL(1)文法；由于递归调用多，速度慢，占用空间多。,2.预测分析法,预测分析器： 预测分析程序（P.88） 先进后出栈 预测分析表,预测分析表的构造,表达式文法： E E+T | T T T*F | F F i | ( E ),构造过程,1.判断文法是否为LL(1)文法 消除左递归：,E E+T | T T T*F | F F i | ( E ),E TEE +TE | T FTT *FT | F i | ( E ),可推出 的非终结符表：,

18、E TEE +TE | T FTT *FT | F i | ( E ),各非终结符的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 ,FOLL