理學第5章-自頂向下語法分析方法

1第5章自頂向下語法分析方法本章基本內(nèi)容確定的自頂向下分析思想LL(1)文法的判別某些非LL(1)文法到LL(1)文法的等價變換不確定的自頂向下分析思想確定的自頂向下分析方法2語法分析是編譯程序的核心部分。語法分析自頂向下自底向上確定分析不確定分析算符優(yōu)先分析LR分析3自頂向下的語法分析是一種典型的語法分析方法。它從文法的開始符號出發(fā)，向下推導推出句子。自頂向下的分析方法主要有兩類：回溯分析方法和預測分析方法。其中，回溯分析方法反復使用不同產(chǎn)生式以試圖匹配輸入串，本質(zhì)上是一種試探過程。由于帶回溯的自頂向下分析實際上采用了一種窮盡一切可能的試探法，因此效率很低，代價極高。嚴重的低效使得這種分析法只有理論意義，而在對于實際得編譯器并不合適。45.1確定的自頂向下分析思想文法G1[S]:

S→pA

S→qB

A→cAd

A→a

B→dB

B→bW=pccadd自頂向下的推導過程：S

pA

pcAd

pccAdd

pccadd語法樹：ddSpASpAcAdSpAcAdcAdSpAcAcAa例5.15這個文法的特點：每個產(chǎn)生式的右部都由終結(jié)符號開始。如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開始。文法G1[S]:

S→pA

S→qB

A→cAd

A→a

B→dB

B→b6文法G2[S]:

S→Ap

S→Bq

A→a

A→cA

B→b

B→dBW=ccap自頂向下的推導過程：S

Ap

cAp

ccAp

ccap語法樹：SApSApcASApcAcASApcAcAa例5.27這個文法的特點：每個產(chǎn)生式的右部不全是由終結(jié)符號開始。如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符或非終結(jié)符開始。文法中無空產(chǎn)生式。文法G1[S]:

S→Ap

S→Bq

A→a

A→cA

B→b

B→dB8W=ccap為輸入串時，其第一個符號是c，這時從S出發(fā)，到底選擇S→Ap還是S→Bq，這就需要知道是從Ap還是Bq能推出ca。為了能知道是否選擇Ap還是Bq，我們作如下定義：9定義5.1：設G=(VT,VN,S,P)是上下文無關(guān)文法FIRST(α)={a|α

aβ,a∈VT,α,β∈V*}

若αε，則規(guī)定ε∈FIRST(α),稱FIRST(α)為α的開始符號集或首符號集。*

*

10集合FIRST的算法設α=X1X2...Xn,Xi∈VN

VT

求FIRST(α)=?首先求出組成α的每一個符號Xi的FIRST集合若Xi∈VT，則FIRST(Xi)={Xi}(2)若Xi∈VN且Xi→a…..|ε，a∈Vt

則FIRST(Xi)={a，ε}11(3)若Xi∈VN且Xi→y1y2…yk，則按如下順序計算FIRST(Xi)

若FIRST(Xi)

FIRST(y1)–{ε}；若ε∈FIRST(y1)則將FIRST(y2)-{ε}加入FIRST(Xi)；若ε∈FIRST(y1)ε∈FIRST(y2)則將FIRST(y3)-{ε}加入FIRST(Xi)........

若ε∈FIRST(yk-1)則將FIRST(yk)-{ε}加入FIRST(Xi)

若ε∈FIRST(y1)～FIRST(yk)

則將ε加入FIRST(Xi)

注意：要順序往下做，一旦不滿足條件，過程就要中斷進行12FIRST(Ap)={a,c}FIRST(Bq)={b,d}文法G2[S]:

S→Ap

S→Bq

A→a

A→cA

B→b

B→dB13文法G3[S]:

S→aA

S→d

A→bAS

A→εW=abd試圖推導的過程：S

aA

abAS

abS

abdSAaSAabASSAabAS

SAabAS

d

輸入串W=abd問：當文法有空產(chǎn)生式時，什么情況下仍可構(gòu)造確定自頂向下分析？14結(jié)論：當某一非終結(jié)符的產(chǎn)生式中有空產(chǎn)生式時它的非空產(chǎn)生式右部的符號集兩兩不相交，并與在推導過程中緊跟該非終結(jié)符右邊可能出現(xiàn)的終結(jié)符集不相交，則仍可構(gòu)造確定自頂向下分析15定義：設G=(VT,VN,S,P)是上下文無關(guān)文法，A∈VN,S是開始符號。

FOLLOW(A)={a|S

A且a∈FRIST(), ∈VT*,

∈V+}

若SA,且

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

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

#輸入串#*

*

*

*

*

16構(gòu)造集合FOLLOW的算法設S,A,B∈Vn,算法：連續(xù)使用以下規(guī)則，直至FOLLOW集合不再擴大若S為識別符號,則把“#”加入FOLLOW(S)中,若有S

…A,則#加入FOLLOW(A).(2)若A→αBβ(β≠ε),則把FIRST(β)-{ε}加入FOLLOW(B)(3)若A→αB

或A→αBβ，且β

ε則把FOLLOW(A)加入FOLLOW(B)*注：FOLLOW集合中不能有ε*17E→TE’E’→+TE’|ε

T→FT’T’→*FT’|ε

F→(E)|i解：1）求FIRST：FIRST(F)={(，i}FIRST(T’)={*,ε}FIRST(T)=FIRST(F)-{ε}={(，i}FIRST(E’)={+,ε}FIRST(E)=FIRST(T)-{ε}={(，i}∴FIRST(TE’)=FIRST(T)-{ε}={(，i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)=FIRST(F)-{ε}={(，i}FIRST(（E）)={(}FIRST(i)={i}18E→TE’E’→+TE’|ε

T→FT’T’→*FT’|ε

F→(E)|iFIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}2）求FOLLOWFOLLOW(E)={#,)}∵因為E是識別符號∴#∈FOLLOW(E)

又F→(E)∴)∈FOLLOW(E)FOLLOW(E’)={#,)}

∵E→TE’∴FOLLOW(E)加入FOLLOW(E’)FOLLOW(T)={+,),#}

∵E’→+TE’∴FIRST(E’)-{ε}加入FOLLOW(T)

又E’

ε，∴FOLLOW(E’)加入FOLLOW(T)FOLLOW(T’)=FOLLOW(T)={+,),#}

∵T→FT’∴FOLLOW(T)加入FOLLOW(T’)FOLLOW(F)={*,+,),#}

∵T→FT’∴FOLLOW(F)=FIRST（T’）-{ε}*又T’

ε

∴FOLLOW(T)加入FOLLOW(F)

19對

A→α

A→β

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

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

如果αε，則SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)*

*

由定義可見，SELECT(Ax)實際上是指在推導過程中，若采用規(guī)則Ax進行推導時，可能推導出的下一個終結(jié)符號組成的集合。注：

SELECT集合中不能有ε21定義5.4：一個上下文無關(guān)文法是LL(1)文法的充要條件是：

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

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

其中α,β不同時能ε*

22LL(1)文法的含義：第一個L表示：自頂向下分析是從左向右掃描輸入串。第二個L表示：分析過程中將用最左推導。

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

S→aA

S→d

A→bAS

A→ε

SELECT(S→aA) ={a}

SELECT(S→d) =sxeitaf

SELECT(A→bAS) =

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

SELECT(A→bAS)∩SELECT(A→ε)=∩{a,d,#,}=Φ所以該文法是LL(1)文法。24設文法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)文法。25G[S]:

S→aAS

S→b

A→bA

A→ε對輸入串W=ab進行推導：S

aAS

abAS

abS

出錯S

aAS

aS

ab265.2LL(1)文法的判別求出能推出ε的非終結(jié)符計算FIRST集計算FOLLOW集計算SELECT集判別是否是LL(1)文法27例：設文法G[S]為:

S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

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

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c非終結(jié)符SABCD初值未定未定未定未定未定第一次掃描是是否第二次掃描是否292.計算FIRST集1.若X

V

,則FIRST(X)={X}2.若X

VN,且有產(chǎn)生式X

a…，則a∈FIRST(X);

若X

也是一條產(chǎn)生式,則

∈FIRST(X).3.若X

Y…是一個產(chǎn)生式且Y

VN,則把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X

Y1Y2…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)中.*

30S→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}313.計算FOLLOW集1.對于文法的開始符號S,置#于FOLLOW(S)中;2.若Ａ→αBβ是一個產(chǎn)生式,則把

FIRST(β)的非空元素加至FOLLOW(B)中;3.若Ａ→αB是一個產(chǎn)生式,或Ａ→αBβ是

一個產(chǎn)生式而β

(即

FIRST(β)），

則把FOLLOW（A），加至FOLLOW（B）中．*

32S→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)={#}334.計算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)文法。345.3某些非LL(1)文法到LL(1)文法的等價變換LL(1)文法是無二義的LL(1)文法不含左遞歸非LL(1)文法的改造提取左公共因子消除左遞歸35提取左公共因子A→αβ|αγ導致SELECT(A→αβ)∩SELECT(A→αγ)≠Φ，因此為非LL(1)文法。先把A→αβ|αγ等價變換為A→α(β|γ)，然后：

A→αA'

A'→β|γ寫成一般形式:A→αβ1|αβ2|…|αβn

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

，然后：

A→αA'

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

S→aSnS→aS

S→ε化為：

S→aS(n|ε)

S→ε進一步化為：

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

因此，文法中不含左公共因子只是LL(1)文法的必要條件。37例：文法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)文法。38例：文法G3[S]為:

S→aSd

S→Ac

A→aS

A→b1.化為：

S→aSd

S→aScS→bc

A→aS

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

S→bc

A→aS

A→b3.化為：S→aSA'

S→bcA'→dA'→cA→aS

A→b結(jié)果中A是不可達到的符號。39例：文法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)替換成無左公共因子的文法40結(jié)論不一定每個文法的左公共因子都能在有限的步驟內(nèi)替換成無左公共因子的文法。一個文法提取了左公共因子后，只解決了相同左部產(chǎn)生式右部的FIRST集不相交問題，當改寫后的文法不含空產(chǎn)生式，且無左遞歸時，則改寫后的文法是LL(1)文法，否則還需用LL(1)文法的判別方式進行判斷才能確定是否為LL(1)文法。41消除左遞歸直接左遞歸：

A→Aβ

A

VN,βV*間接左遞歸：

A→Bβ

B→Aα A,B

VN,α,β

V*42文法G5含有直接左遞歸：

S→Sa

S→b

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

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

A→aB

A→Bb

B→Ac

B→d

輸入串a(chǎn)dbcbcbc#

A→aB→ad

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

S→Sa

S→b

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

S→bS'

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

其中：αi

不等于ε，βj不以A開頭。

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

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

A→aB

A→Bb

B→Ac

B→d

B→aBc

B→Bbc

B→dB→aBcB'|dB'

B'→bcB'|ε47消除文法中一切左遞歸的算法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得到的文法+

48例：文法G:

S→Qc|c

Q→Rb|b

R→Sa|aR→Qca|ca|aR→Rbca|bca|ca|aR→(bca|ca|a)R'R'→bcaR'|ε參考P.9049不確定的自頂向下分析思想1.由于相同左部的產(chǎn)生式的右部FIRST集交集不為空引起回溯。

S→xAy

A→ab|aw=xaySxAySxAyabSxAya試探回溯試探502.由于相同左部非終結(jié)符的右部能ε且該非終結(jié)符FOLLOW集中含有其右部FIRST集的元素。設文法G[S]為:

S→aAS

S→nA→bAS

A→ε*

w=ab#SaASSaASbASSaASεn試探

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

S→Sa

S→nw=naa#SnSSaSSanSSaSaSSaSan525.5確定的自頂向下分析方法1.遞歸子程序法實現(xiàn)思想：對文法中每個非終結(jié)符編寫一個遞歸過程，每個過程的功能是識別由該非終結(jié)符推出的串，當某非終結(jié)符的產(chǎn)生式有多個候選時能夠按LL(1)形式可唯一地確定選擇某個候選進行推導。限制：對文法要求高，必須滿足LL(1)文法；由于遞歸調(diào)用多，速度慢，占用空間多。盡管這樣,它還是許多高級語言的編譯系統(tǒng)經(jīng)常采用的語法分析方法。53具體做法：對語法的每一個非終結(jié)符都編一個分析程序，當根據(jù)文法和當時的輸入符號預測到要用某個非終結(jié)符去匹配輸入串時，就調(diào)用該非終結(jié)符的分析程序。運用遞歸下降分析法進行語法分析時,對于某個非終結(jié)符通過表征規(guī)則右部特征的子程序去匹配輸入串。分析過程則通過自上而下一級一級地調(diào)用子程序來實現(xiàn)，所以稱為遞歸下降分析法。54LL－自左向右掃描、自左向右的分析和匹配輸入串。分析過程表現(xiàn)為最左推導的性質(zhì)。通常把按LL(1)方法完成語法分析任務的程序叫LL(1)分析程序或者LL(1)分析器。此過程有三部分組成:分析表執(zhí)行程序(總控程序）符號棧（分析棧）#執(zhí)行程序分析表#符號棧輸入串在實際語言中，每一種語法成分都有確定的左右界符，為了研究問題方便，統(tǒng)一以‘＃’表示。1、LL分析程序構(gòu)造及分析過程2.預測分析法555555M[A,a]=A→αi

表示當要用A去匹配輸入串時，且當前輸入符號為a時，可用A的第i個選擇去匹配。即當αi≠ε時，有αi

a…;

當αi＝ε時，則a為A的后繼符號。*M[A,a]=error

表示當用A去匹配輸入串時，若當前輸入符號為a，則不能匹配，表示無A

a…,或a不是A的后繼符號.*（1）分析表：二維矩陣M

A→αi

αi∈V*

M[A,a]=或A∈Vnerrora∈Vtor#56（2）符號棧:用于存放分析過程中的文法符號。分析棧初始化時，在棧底壓入一個”#”，然后再壓入文法開始符號。575757執(zhí)行程序主要實現(xiàn)如下操作:1.分析開始時候進行有關(guān)的初始化工作。把#和文法識別符號E推進棧,并讀入輸入串的第一個符a,重復下述過程直到正常結(jié)束或出錯.2.設分析到的某一步，分析棧當前的棧頂符號X和當前輸入符號a,執(zhí)行如下操作:若X∈VT:(1)若X=a=#，分析成功，停止。E匹配輸入串成功.(2)若X=a≠#，則從棧頂彈出X，輸入串的分析指針指向下一個輸入符號。(3)若X≠a，則表示發(fā)現(xiàn)錯誤，調(diào)相應的出錯處理程序（3）執(zhí)行程序:據(jù)分析表和分析?？刂茖斎敕柎姆治龊妥R別#…..X符號棧

X….#a……#585858若X∈Vn，查分析表M，根據(jù)M[X,a]的內(nèi)容決定：

a)

若M[X,a]中為一個規(guī)則，則將X彈出棧，并將此規(guī)則右部的符號序列按倒序壓入分析棧。

注：U在棧頂（最左推導）

b)若M[X,a]為空，則表示出錯，調(diào)出相應的出錯處理程序。

3、反復執(zhí)行2）。59預測分析表的構(gòu)造表達式文法：E→E+T|TT→T*F|FF→i|(E)60構(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)61可推出ε的非終結(jié)符表：E→TE'

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

T'→*FT'|εF→i|(E)EE'TT'F否是否是否62各非終結(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定義63各產(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→F