編譯原理第4章課件

第四章語法分析—自上而下分析

4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL（1）分析法4.4遞歸下降分析程序構(gòu)造(略)4.5預(yù)測分析程序4.6LL（1）分析中的錯誤處理(略)1§4.１語法分析器的功能1、任務(wù)：在詞法分析識別出單詞符號串的 基礎(chǔ)上，分析并判定程序的語法 結(jié)構(gòu)是否符合語法規(guī)則。2、語法分析器的地位：單詞符號取下一單詞符號語法分析樹符號表詞法分析器語法分析器編譯程序后續(xù)部分源程序2§4.１語法分析器的功能3、本質(zhì)：按文法的產(chǎn)生式，識別輸入符 號串是否為一個句子。4、語法分析方法分類：

自上而下分析法 自下而上分析法 3§4.2自上而下面臨的問題一、基本思想：1、自上而下：從文法的開始符號出發(fā)，向下 推導(dǎo)，推出句子2、主旨：對任何輸入串，試圖用一切可能的 辦法，從開始符號出發(fā)，自上而下 地為輸入串建立一棵語法樹。4§4.2自上而下面臨的問題二、舉例： 自上而下方法的分析過程本質(zhì)上是一種試探過程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過程。5§4.2自上而下面臨的問題SxA

ySxAy**SxAy*例：文法SxAy A**|* 輸入串α:x*y6§4.2自上而下面臨的問題實(shí)現(xiàn)上述帶回溯試探發(fā)的簡單途徑： 讓每個非終結(jié)符對應(yīng)一個遞歸子程序。每個這種子程序可作為一個布爾過程。一旦發(fā)現(xiàn)它的某個候選與輸入串相匹配，就用這個候選去擴(kuò)展語法樹，并返回“真”值；否則，保持原來的語法樹和IP值不變，并返回“假”值。7§4.2自上而下面臨的問題三、困難和缺點(diǎn)1、文法的左遞歸性問題使自上而下的分析過程陷入無限循環(huán)2、回溯問題3、虛假匹配難以消除4、當(dāng)最終報(bào)告分析不成功時(shí),難于知道輸入串中出錯的確切位置5、采用了一種窮盡一切可能的試探法,效率很低,代價(jià)極高8§4.３LL(1)分析法一、左遞歸的消除：1、規(guī)則:（直接左遞歸消除）PPα｜βPPα１|Pα２|…Pαｍ|β１|β２|…|βｎ PβP’ P’αP’|? Pβ1p’|β2P’|…|βnP’ P’α1P’|α2P’|…|αmP’|?9§4.３LL(1)分析法例題：已經(jīng)文法：ＥＥ+Ｔ｜Ｔ ＴＴ＊Ｆ｜Ｆ Ｆ(Ｅ)｜ｉＥＴＥ’Ｅ’+ＴＥ’｜?ＴＦＴ’Ｔ’*ＦＴ’｜?Ｆ(Ｅ)|ｉ10§4.３LL(1)分析法２、消除左遞歸：（１）把文法Ｇ的所有ＶＮ按任一種順序排列成P1,P2,…,Pn;按此順序執(zhí)行；（２）FORi=1TonDo Begin Forj:=1Toi-1Do 把形如PiPjγ的規(guī)則改寫成 Piδ1γ|δ2γ|…|δkγ 其中Pjδ1|δ2|…|δk是關(guān) 于Pj的所有規(guī)則； 消除關(guān)于Pi規(guī)則的直接左遞歸性 End11§4.３LL(1)分析法（３）化簡由（２）所得的文法,即去除那些從開 始符號出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn) 生規(guī)則例題:（間接左遞歸）已知文法G:SQc|c QRb|b RSa|a 試消除其左遞歸?解答12二、消除回溯,提取左因子§4.３LL(1)分析法１、消除回溯必須保證:

對文法的任何非終結(jié)符,當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。即：

若此候選獲得成功匹配，那么，這種匹配決不會是虛假的； 若此候選無法完成匹配任務(wù)，則任何其它候選也肯定無法完成。13§4.３LL(1)分析法例：Ａα１｜α２｜…｜αｎ

設(shè)Ａ所面臨的第一個輸入符號為ａ，若Ａ能根據(jù)不同的輸入符號指派相應(yīng)的候選αｉ作為全權(quán)代表去執(zhí)行任務(wù)，那就肯定無需回溯。在這里Ａ已不再是讓某個候選去試探性地執(zhí)行任務(wù)，而是根據(jù)所面臨的輸入符號ａ準(zhǔn)確地指派唯一的一個候選。14§4.３LL(1)分析法２、當(dāng)不得回溯時(shí)，對文法有什么要求？ ?非終結(jié)符Ａ的各個候選的首符集的交集均為空。分析：Ａαfirst(α)={a|α?a…,a∈VT} 若α??,則規(guī)定?∈first(α)即:first(α)是α的所有可能推導(dǎo)的開頭終結(jié)符或可能的?。此時(shí)，當(dāng)要求A匹配輸入串時(shí)，A根據(jù)它所面臨的第一個輸入符號a，準(zhǔn)確地指派某一個候選前去執(zhí)行任務(wù)；這個候選就是那個終結(jié)首符集含a的α. **15§4.３LL(1)分析法3、A、事實(shí)上，許多文法均存在這樣的非終結(jié)符，其所有候選的終結(jié)首符集并非兩兩不相交。 例如：語句if條件then語句else語句 if條件then語句B、任何把一個文法改造成任何非終結(jié)符的所有 候選首符集兩兩不相交呢？提取公共左因子16§4.３LL(1)分析法代價(jià):大量引進(jìn)新的非終結(jié)符和?_產(chǎn)生式例：Aδβ1|δβ2|…|δβn|γ1|γ2|…|γm (其中,每個γ不以δ開頭)? AδA’|γ1|γ2|…|γm A’β1|β2|…|βn經(jīng)過反復(fù)提取坐因子,就能把每個非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成兩兩不相交.17§4.３LL(1)分析法三、分析條件1、當(dāng)一個文法不含左遞歸,并且滿足每個非終結(jié)符的所有候選首符集兩兩不相交的條件,是不是就一定能進(jìn)行有效的自上而下分析了呢?18§4.３LL(1)分析法例：文法 EE+T|T TT*F|F F（E）|i經(jīng)消去直接左遞歸后變成 ETE’

E’+TE’|? TFT’ T’*FT’|? F（E）｜iＥTE’ＦＴ’+Ｅ’ Ti ? ?

FＴ’

ｉ?輸入串：ｉ＋ｉ； 如右圖所示19§4.３LL(1)分析法２、由上分析是不是就意味著：當(dāng)非終結(jié)符Ａ面臨輸入符號ａ，且ａ不屬于Ａ的任意候選首符集，但Ａ的某個候選首符集包含?時(shí)，就一定可以使Ａ自動匹配？分析：只有當(dāng)ａ是在文法的某個句型中允許跟在Ａ后的終結(jié)符時(shí)，才可能允許Ａ自動匹配，否則，ａ在這里的出現(xiàn)是一種語法錯誤。20§4.３LL(1)分析法Follow(A)={a|A?…Aa…,a∈VT}若S?…A,則規(guī)定#∈follow(A)即:follow(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或“?！?。當(dāng)Ａ面臨輸入符號ａ，且ａ?first（A），但?∈first（A），只有當(dāng)a∈first（A）時(shí)，才可能允許A自動匹配。 **21§4.３LL(1)分析法3、構(gòu)造不帶回溯的自上而下分析的文法的條件：（1）文法不含左遞歸（2）文法中每一個非終結(jié)符A的各個產(chǎn)生式 的候選首符集兩兩不相交即：若Aα1|α2|…αn 則first(αi)∩first(αj)=Φ （ｉ≠ｊ）（３）對文法中的每個非終結(jié)符Ａ，若它存在某個候 選首符集包含?，則first(A)∩follow(A)=Φ若一個文法G滿足以上條件,則稱該文法G為LL(1)文法22§4.３LL(1)分析法4、對LL(1)文法,可對其輸入串進(jìn)行有效的無回溯的自上而下分析：Aα1|α2|…|αn對非終結(jié)符A進(jìn)行匹配,此時(shí)面臨的輸入符號為a(1)若a∈first(αi),則指派αi去執(zhí)行匹配任務(wù)(2)若a不屬于任何一個候選首符計(jì),則若?∈first(αi

),且a∈follow(A),則讓A與?自動匹配否則,a的出現(xiàn)是一種語法錯誤23§4.5預(yù)測分析程序——即LL(１)分析法介紹一、構(gòu)造First和Follow1、構(gòu)造First(x)，x∈VT∪VN連續(xù)使用下述規(guī)則,直至每一個集合First不再增大為止。規(guī)則:(1)若X∈VT,則FIRST(X)={X}。(2)若X∈VN,且有產(chǎn)生式Xa…,則把a(bǔ)加入到FIRST(X)中;若X?也是一條產(chǎn)生式,則把?也加到FIRST(X)中。24§4.5預(yù)測分析程序——即LL(１)分析法介紹(3)若XY…是一個產(chǎn)生式且Y∈VN,則把FIRST(Y)中的所有非?—元素都加到FIRST(X)中;若XY1Y2…Yk是一個產(chǎn)生式,Y1,…Yi-1都是非終結(jié)符,而且,對于任何j,1≤j≤i-1,FIRST(Yj)都含有?(即Y1…Yi-1??),則FIRST(Yi)中的所有非?—元素都加到FIRST(X)中;特別是,若所有的FIRST(Yj)均含有?,j=1,2,…,k,則把?加到FIRST(X)中。*25§4.5預(yù)測分析程序——即LL(１)分析法介紹2、構(gòu)造Follow(A)，A∈VN連續(xù)使用下述規(guī)則,直至每一個集合Follow不再增大為止。規(guī)則:(1)對于文法的開始符號S,置#于FOLLOW(S)中;(2)若AαBβ是一個產(chǎn)生式,則把FIRST(β)\{?}加至FOLLOW(B)中;(3)若AαB是一個產(chǎn)生式,或AαBβ是一個產(chǎn)生式而β??(即?∈FIRST(β)),則把FOLLOW(A)加至FOLLOW(B)中。26§4.5預(yù)測分析程序——即LL(１)分析法介紹舉例:對于文法EE+T|T;TT*F|F;F(E)|i我們可構(gòu)造出每個非終結(jié)符的FIRST和FOLLOW集合:FIRST(E)={(，ｉ} FOLLOW(E)={)，＃｝FIRST(E’)={+，?} FOLLOW(E’)={)，＃}FIRST(T)={（，ｉ} FOLLOW(T)={+，），＃}FIRST(T’)={*，?} FOLLOW(T’)={+，），＃}FIRST(F)={（，ｉ} FOLLOW(F)={*，+，），＃}27§4.5預(yù)測分析程序——即LL(１)分析法介紹二、構(gòu)造分析表構(gòu)造分析表M的算法是:(1)對文法G的每個產(chǎn)生式A執(zhí)行第2步和第3步;(2)對每個終結(jié)符a∈FIRST(α),把Aα加至M[A,a]中;(3)若?∈FIRST(α),則對任何Bfollow(A)把Aα加至M[A,b]中;(4)把所有無定義的M[A,a]標(biāo)上“出錯標(biāo)志”。28§4.5預(yù)測分析程序——即LL(１)分析法介紹舉例：文法EE+T|T;TT*F|F;F(E)|i的 LL(1)分析表如下所示i+*()#EETE’ETE’E’E’+TE’E’?E’?TTFT’TFT