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

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

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

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

對文法的任何非終結符,當要它去匹配輸入串時，能夠根據它所面臨的輸入符號準確地指派它的一個候選去執行任務，并且此候選的工作結果應是確信無疑的。即：

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

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

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

FＴ’

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

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