第4章-自頂向下語法分析方法

第4章自頂向下語法分析方法確定的自頂向下分析思想LL(1)文法的判別某些非LL(1)文法到LL(1)文法的等價變換不確定的自頂向下分析思想確定的自頂向下分析方法確定的自頂向下分析思想文法G1[S]:

S→pA

S→qB

A→cAd

A→a

B→dB

B→bW=pccadd自頂向下的推導過程：SpApcAdpccAddpccadd語法樹：SpASpAcAdSpAcAdcAdSpAcAdcAda這個文法的特點：每個產(chǎn)生式的右部都由終結(jié)符號開始。如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開始。文法G1[S]:

S→pA

S→qB

A→cAd

A→a

B→dB

B→b文法G2[S]:

S→Ap

S→Bq

A→a

A→cA

B→b

B→dBW=ccap自頂向下的推導過程：SApcApccApccap語法樹：SApSApcASApcAcASApcAcAa這個文法的特點：每個產(chǎn)生式的右部不全是由終結(jié)符號開始。如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符或非終結(jié)符開始。文法中無空產(chǎn)生式。文法G1[S]:

S→Ap

S→Bq

A→a

A→cA

B→b

B→dB定義：設(shè)G=(VT,VN,S,P)是上下文無關(guān)文法，

FIRST(α)={a|αaβ,a∈VT,α,β∈V*}

若αε，則規(guī)定ε∈FIRST(α)**調(diào)用返回FIRST(Ap)={a,c}FIRST(Bq)={b,d}文法G2[S]:

S→Ap

S→Bq

A→a

A→cA

B→b

B→dB文法G3[S]:

S→aA

S→d

A→bAS

A→εW=abd試圖推導的過程：SaAabASabSabd定義：設(shè)G=(VT,VN,S,P)是上下文無關(guān)文法，A∈VN,S是開始符號。

FOLLOW(A)={a|SA且a∈FRIST(), ∈VT*,∈V+}

若SA,且

ε，則規(guī)定#∈FOLLOW(A)即：FOLLOW(A)={a|S…Aa…,a∈VT}

若S…A，則規(guī)定#∈FOLLOW(A)#作為輸入串的結(jié)束符，或稱為句子括號，如：

#輸入串#*****調(diào)用返回對

A→α

A→β

其中A∈VN,α,β∈VN*當α和β不同時推導出空時（設(shè)α不推導出空，β推導出空），則當FIRST(α)∩(FIRST(β)∪FOLLOW(A))=Φ時，對于非終結(jié)符A的替換仍可唯一地確定候選。定義：給定上下文無關(guān)文法的產(chǎn)生式A→α，A∈VN,α∈V*，

若αε，則SELECT(A→α)=FIRST(α)

如果αε，則SELECT(A→α)=FIRST(α)∪FOLLOW(A)**調(diào)用返回定義：一個上下文無關(guān)文法是LL(1)文法的充要條件是：

對每個非終結(jié)符A的兩個不同產(chǎn)生式A→α和A→β，滿足

SELECT(A→α)∩SELECT(A→β)=Φ

其中α,β不同時能ε*LL(1)文法的含義：第一個L表示：自頂向下分析是從左向右掃描輸入串。第二個L表示：分析過程中將用最左推導。

1表示：只需向右看一個符號便可決定如何推導（即選擇哪個產(chǎn)生式進行推導）。類似也可以有LL(K)文法：需向前查看K個符號才可確定選用哪個產(chǎn)生式。文法G[S]是否是LL(1)文法:

S→aA

S→d

A→bAS

A→εSELECT(S→aA) ={a}

SELECT(S→d) =pw60xvc

SELECT(A→bAS) =

SELECT(A→ε) ={a,d,#,ε}SELECT(S→aA)∩SELECT(S→d)={a}∩nnqovk5=Φ

SELECT(A→bAS)∩SELECT(A→ε)=∩{a,d,#,ε}=Φ所以該文法是LL(1)文法。設(shè)文法G[S]為:

S→aAS

S→b

A→bA

A→εSELECT(S→aAS) ={a}

SELECT(S→b) =

SELECT(A→bA) =

SELECT(A→ε) ={a,b,ε}SELECT(S→aAS)∩SELECT(S→b)={a}∩=Φ

SELECT(A→bA)∩SELECT(A→ε)=∩{a,b,ε}≠Φ所以該文法不是LL(1)文法。G[S]:

S→aAS

S→b

A→bA

A→ε對輸入串W=ab進行推導：SaASabASabS出錯SaASaSabLL(1)文法的判別求出能推出ε的非終結(jié)符計算FIRST集計算FOLLOW集計算SELECT集判別是否是LL(1)文法例：設(shè)文法G[S]為:

S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

判斷它是否是LL(1)文法。1.求出能推出ε的非終結(jié)符S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c非終結(jié)符SABCD初值未定未定未定未定未定第一次掃描是是否第二次掃描是否2.計算FIRST集1.若XV,則FIRST(X)={X}2.若XVN,且有產(chǎn)生式Xa…，則a∈FIRST(X);

若X也是一條產(chǎn)生式,則∈FIRST(X).3.若XY…是一個產(chǎn)生式且YVN,則把FIRST(Y)中的所有非元素都加到FIRST(X)中;若XY1Y2…YK

是一個產(chǎn)生式,Y1,Y2,…,Y(i-1)都是非終結(jié)符,而且,對于任何j,1≤j≤i-1,FIRST(Yj)都含有(即Y1..Y(i-1)

),則把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特別是,若所有的FIRST(Yj,

j=1,2,…,K)均含有,則把加到FRIST(X)中.*S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→cFIRST(S)=(FIRST(A)-{ε})∪FIRST(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β是一個產(chǎn)生式,則把FIRST(β)\{}加至FOLLOW(B)中;3.若Ａ→αB是一個產(chǎn)生式,或Ａ→αBβ是一個產(chǎn)生式而β

(即FIRST(β)），則把FOLLOW（A），加至FOLLOW（B）中．*S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→cFOLLOW(S)={#}∪FOLLOW(D)FOLLOW(A)={a}∪{a,c}∪FOLLOW(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集S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→cFIRST(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(S→AB)={a,b,ε,#}SELECT(S→bC)=SELECT(A→ε)={a,c,#,ε}SELECT(A→b)=SELECT(B→ε)={#,ε}SELECT(B→aD)={a}SELECT(C→AD)={a,b,c}SELECT(C→b)=SELECT(D→aS)={a}SELECT(D→c)={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)文法。等價變換為A→α(β|γ)，然后：

A→αA'

A'→β|γA→αβ1|αβ2|…|αβn變換為A→α(β1|β2|…|βn)

，然后：

A→αA'

A'→β1|β2|…|βn例：文法G1[S]為:

S→aSb

S→aS

S→ε化為：

S→aS(b|ε)

S→ε進一步化為：

S→aSAA→bA→εS→ε結(jié)果仍然不是LL(1)文法。

因此，文法中不含左公共因子只是LL(1)文法的必要條件。w=aabbS=>aSA

=>aaSAA

=>aaAA

=>aabA(aaA)例：文法G2為:

A→ad

A→Bc

B→aA

B→bB1.化為：

A→adA→aAcA→bBcB→aA

B→bB2.化為：A→a(d|Ac)A→bBcB→aA

B→bB3.化為：A→aA'A→bBcA'→dA'→AcB→aA

B→bB結(jié)果是LL(1)文法。例：文法G3[S]為:

S→aSd

S→Ac

A→aS

A→b1.化為：

S→aSd

S→aScS→bc

A→aS

A→b2.化為：S→aS(d|c)

S→bcA→aS

A→b3.化為：S→aSA'

S→bcA'→dA'→cA→aS

A→b結(jié)果中A是不可達到的符號。例：文法G4[S]為:

S→Ap|Bq

A→aAp|d

B→aBq|e1.化為：

S→aApp|aBqq|dq|eq

A→aAp|d

B→aBq|e2.化為：S→a(App|Bqq)

S→dq|eqA→aAp|d

B→aBq|e3.化為：S→aS'S→dq|eqS'→App|Bqq

A→aAp|d

B→aBq|e4.化為：S→aS'S→dq|eqS'→aAppp|aBqqq|dpp|eqq

A→aAp|d

B→aBq|e利用提取左公共因子無法在有限步驟內(nèi)替換成無左公共因子的文法結(jié)論不一定每個文法的左公共因子都能在有限的步驟內(nèi)替換成無左公共因子的文法。一個文法提取了左公共因子后，只解決了相同左部產(chǎn)生式右部的FIRST集不相交問題，當改寫后的文法不含空產(chǎn)生式，且無左遞歸時，則改寫后的文法是LL(1)文法，否則還需用LL(1)文法的判別方式進行判斷才能確定是否為LL(1)文法。消除左遞歸直接左遞歸：

A→Aβ AVN,βV*間接左遞歸：

A→Bβ

B→Aα A,BVN,α,βV*文法G5含有直接左遞歸：

S→Sa

S→b

所能產(chǎn)生的語言L={ban|n≥0}

輸入串baaaa#是該語言的句子，但如何用自頂向下分析呢？文法G6含有間接左遞歸：

A→aB

A→Bb

B→Ac

B→d

輸入串a(chǎn)dbcbcbc#

A→aB→ad

A→aB→aAc→aBbc→aAcbc…消除直接左遞歸把直接左遞歸改寫為右遞歸。如G5:

S→Sa

S→b

(L={ban|n≥0})改為：

S→bS'

S'→aS'|ε消除直接左遞歸的一般方法：A→Aα1|Aα2|…|Aαm|β1|β2|…|βn

其中：αi不等于ε，βj不以A開頭。

改為：A→β1A'|β2A'|…|βnA'

A'→α1A'|α2A'|…|αmA'|ε消除間接左遞歸將間接左遞歸變?yōu)橹苯幼筮f歸，然后消除直接左遞歸。如文法G6含有間接左遞歸：

A→aB

A→Bb

B→Ac

B→d

B→aBc

B→Bbc

B→dB→aBcB'|dB'

B'→bcB'|ε消除文法中一切左遞歸的算法1.無回路(A(A(A)2.無空產(chǎn)生式（1）以某種順序?qū)⑽姆ǚ墙K結(jié)符排列A1,A2…An（2）fori:=1tondobegin

forj:=1toi-1do用Ai-->1|2r…|kr替代形如Ai-->Ajr的規(guī)則,其中Aj-->1|2…|k是關(guān)于Aj的全部產(chǎn)生式;消除Ai規(guī)則的直接左遞歸;

end;（3）化簡由2得到的文法+例：文法G:

S→Qc|c

Q→Rb|b

R→Sa|aR→Qca|ca|aR→Rbca|bca|ca|aR→(bca|ca|a)R'R'→bcaR'|ε參考P.84不確定的自頂向下分析思想1.由于相同左部的產(chǎn)生式的右部FIRST集交集不為空引起回溯。 S→xAy A→ab|aw=xaySxAySxAyabSxAya試探回溯試探2.由于相同左部非終結(jié)符的右部能ε且該非終結(jié)符FOLLOW集中含有其右部FIRST集的元素。設(shè)文法G[S]為:

S→aAS

S→b

A→bAS

A→ε*w=ab#SaASSaASbASSaASεb試探

再試探回溯3.由于文法含有左遞歸而引起回溯。設(shè)文法G[S]為:

S→Sa

S→bw=baa#SbSSaSSabSSaSaSSaSab確定的自頂向下分析方法1.遞歸子程序法實現(xiàn)思想：對文法中每個非終結(jié)符編寫一個遞歸過程，每個過程的功能是識別由該非終結(jié)符推出的串，當某非終結(jié)符的產(chǎn)生式有多個候選時能夠按LL(1)形式可唯一地確定選擇某個候選進行推導。限制：對文法要求高，必須滿足LL(1)文法；由于遞歸調(diào)用多，速度慢，占用空間多。2.預測分析法預測分析器：預測分析程序（P.88）先進后出棧預測分析表預測分析表的構(gòu)造表達式文法：E→E+T|TT→T*F|FF→i|(E)構(gòu)造過程1.判斷文法是否為LL(1)文法消除左遞歸：E→E+T|TT→T*F|FF→i|(E)E→TE'

E'→+TE'|εT→FT'

T'→*FT'|εF→i|(E)可推出ε的非終結(jié)符表：E→TE'

E'→+TE'|εT→FT'

T'→*FT'|εF→i|(E)EE'TT'F否是否是否各非終結(jié)符的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→TE'

E'→+TE'|εT→FT'

T'→*FT'|εF→i|(E)查看FOLLOW定義查看FIRST定義各產(chǎn)生式的SELECT集：E→TE'

E'→+TE'|εT→FT'

T'→*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')={+,),#}FOLL