編譯原理課件chap04(陳火旺).ppt

1、第四章語法解析自頂向下解析，第四章語法解析自頂向下解析，因?yàn)楦呒壵Z言的語法結(jié)構(gòu)適合用上下無關(guān)語法來描述，所以以上下文無關(guān)語法為語法解析的基礎(chǔ)。 本章和下一章介紹了編譯程序結(jié)構(gòu)中典型的解析方法4.1解析器功能解析是編譯過程的核心部分。 其作用是，在字句解析中認(rèn)識單詞符號串的基礎(chǔ)上，解析普計(jì)程儀柱的語法構(gòu)造是否符合語法規(guī)則進(jìn)行判定。 下圖顯示了解析器在編譯程序中的位置。第四章語法解析自頂向下解析、源計(jì)程儀、詞法解析、單詞符號、刪除以下單詞、語法解析、詞法解析、解析樹、編譯后續(xù)、符號表、解析器位于編譯計(jì)程儀中的常用方法、自頂向下分析、自下而上分析、確定不確定、運(yùn)算符優(yōu)先分析LR分析、 第四章語法分析

2、自頂向下分析、自頂向下語法分析方法、自頂向下分析法從語法的開始符號推導(dǎo)出與輸入的單詞串完全匹配的句子。 如果可以導(dǎo)出，那么該輸入列就是給定的語法句子，如果不能導(dǎo)出，那么該輸入列就不是給定的語法句子。 第四章語法分析-自頂向下分析，如已知符號串S=cad語法GZ: ZcAd Aab|a求解SL(GZ )，分析過程建立語法樹，使語法樹的末端節(jié)點(diǎn)與給定符號串一致。 選擇匹配塔斯克為a，第四章語法分析-自頂向下分析、6、6、3.a的右符號串匹配輸入串a(chǎn)有兩個右部分，選擇一個，再導(dǎo)出Aab檢驗(yàn)，完成a-a匹配，b-d不匹配的Aa檢查a-a匹配d-d匹配末端節(jié)點(diǎn)根據(jù)輸入cad與cad的匹配，建立衍生序列E

3、cAdcad cadL(G(E ) )，S=cad GZ: ZcAd Aab|a，分析工作要素進(jìn)行替換，假定最左邊的非終止符是b，并且有n個規(guī)則： BA1|A2|An 第四章語法分析-自頂向下分析，1 .分析過程具有預(yù)測性，對輸入符號串屬于哪個語法成分進(jìn)行預(yù)測，并根據(jù)該語法成分的語法建立語法樹。 2、分析過程是一種試驗(yàn)過程，是用盡一切方法(選擇不同的規(guī)則)制作語法樹的過程，由于是試驗(yàn)過程，失敗是免不得，分析過程需要追溯進(jìn)行，因此我們也稱之為追溯該方法的自頂向下分析方法。 第四章語法分析-自頂向下分析、自頂向下分析中存在的問題和解決方法、自頂向下分析方法的基本缺點(diǎn)：不能處理具有左遞歸性的語法，自

4、頂向下分析為什么不能處理左遞歸語法，1左遞歸語法：左遞歸語法上溯及問題，第四章語法分析-自頂向下分析，10、10、 如果在匹配輸入串的過程中，輪到恰好在非終止符u中直接匹配輸入串，那么假定在u的右部符號串u中匹配，如果使用u的語法具有間接的左遞歸，也會發(fā)生上述問題，但是環(huán)的環(huán)形口袋更大因?yàn)閳?zhí)行自頂向下解析必須刪除語法的左遞歸，所以在介紹了直接刪除左遞歸的方法的基礎(chǔ)上，還介紹了一般的左遞歸刪除方法。為什么自頂向下解析不能處理左遞歸語法？ 第四章語法分析自頂向下分析、11、11、刪除直接左遞歸：11、11、規(guī)則1 (提因子)、I )知道Ux | xy，并且能夠?qū)ξ臋n的長度進(jìn)行更有效的分析。 ii

5、) uxy|xz y1y2wy1w 2解： Ux (y1 (y2 | w2 ) | | z )得到的： Ux U U y1 y1 | | z y1 y2 | w2，如果是已知的PP|，則可以改寫為： P P P P|。 示例2 ge:e:3360=t * f|t/f|ft 33603360=f|t * f|t/f解：從左遞歸到右遞歸的更改： e :3360=t第四章語法分析自頂向下分析，通常，p的所有生成表達(dá)式為PP1| p2|p1m|1 假設(shè)各自不是以p開始的話，消除p的直接左遞歸性就是改寫這些個規(guī)則的第四章語法解析自頂向下解析，14，14，消除一般的左遞歸，將1.g的非終止符整理為任意順序

6、A1，A2，An， 將a133603360=1|2設(shè)定為2.fori :=1tondobeginforj :=1將toi-1 doaiajr這樣的形式的規(guī)則替換為Ai (1|2|k) r。 其中Aj 1|2|k是當(dāng)前所有aj的消除規(guī)則ai規(guī)則的直接。 第四章語法解析-自頂向下解析、例：語法Gs按S Qc|c Q Rb|b R Sa|a、非終止符順序進(jìn)行排序，在RSa|a QRb|b SQc|c、的4.s的右部代入q，進(jìn)行SSabc|abc|bc|c，5.s的直接左遞歸s (ABC|BC|) 最后得到語法3360，s(abc|最后得到的語法3360，s (ABC|BC|c ) sabcs|qsa

7、b|ab|brsa|a， 其中關(guān)于q和r的規(guī)則是由多元規(guī)則壓縮而成的s(abc|bc|c )，最后得到的語法形式上可能有所不同，但要證明其等價(jià)性并不容易。第四章語法分析-自頂向下分析、自頂向下語法分析方法、自頂向下分析分為確定性和不確定性兩種自頂向下確定性分析法雖然在語法上有一定的局限性，但簡單直觀、手工作業(yè)和自動結(jié)構(gòu)簡單的自頂向下不真實(shí)自我分析法是一種具有回溯的分析方法，效率高、成本高、使用少。 第四章語法分析-自頂向下分析，一，確定性的自頂向下分析思想1，方法：從開始符號開始，不斷地替換非終止符，可以唯一地選擇用現(xiàn)在的單詞符號替換的生成式。 例1 :語法G(S):SpA SqB AcAd

8、Aa輸入列W=pccadd自頂向下的導(dǎo)出過程為：第四章語法解析-自頂向下解析、a，對應(yīng)的語法樹：spappd第四章語法分析自頂向下分析，例1 :語法G(S ) : SpA SqB AcAd Aa該語法的特征： (1)各生成式的右部是從終止符開始的；(2)如果兩個生成式中存在相同的左部，則它們的右部是從不同的終止符開始的。 對于這種語法，分析過程可以是唯一確定的，因?yàn)樗梢愿鶕?jù)當(dāng)前輸入符號確定選擇導(dǎo)出哪種生成公式。第四章語法分析-自頂向下分析，例2 :語法G(S )是S Ap S Bq A acA BbdB這一語法特征： (1)生成式的右部并非全部從終止符開始。 (2)如果兩個生成式具有相同的左

9、部，則它們的右部從不同的終止符或者非終止符開始。 (3)沒有空閑發(fā)生式。 ccap是如何根據(jù)輸入列的第一個符號確定生成公式的呢？ 第四章語法分析-自頂向下分析，例2 :語法G(S )是： S Ap S Bq A acA BbdB輸入W=ccap推導(dǎo)：自頂向下推導(dǎo)過程是：第四章語法分析-自頂向下分析，例2 :語法G(S ) 是： S Ap S Bq A acA BbdB輸入W=ccap推導(dǎo)：自頂向下推導(dǎo)過程是： S Ap cAp ccAp ccap語法樹是：a，第四章語法分析(2)如果兩個生成式具有相同的左部，則它們的右部是從不同的終止符或者非終止符開始。 (3)沒有空閑發(fā)生式。 ccap是如何

10、根據(jù)輸入列的第一個符號確定生成公式的呢？ 第四章語法解析自頂向下解析，第二章，開始符號集合的定義：如果將G=(VT，VN，p，s )作為上下文相關(guān)語法，將開始符號集合作為First()=a | a，aVT，則規(guī)定First ()。 上例中的中文法則為SAp|Bq A a | cA B b | dB則： FIRST(Ap)=？ FIRST(Bq)=？ 為生成表達(dá)式規(guī)則的右部生成開始符號集合，第4章語法解析自頂向下解析，第2章，開始符號集合的定義：如果將G=(VT，VN，p，s )作為上下文相關(guān)語法，將開始符號集合作為First()=的話，則規(guī)定first ()。 上例的中文法則為SAp|Bq A

11、 a | cA B b | dB則： FIRST(Ap)=a、c。 FIRST(Bq)=b，d，對于生成式規(guī)則的右部生成開始符號集合，第四章語法解析自頂向下解析，根據(jù)從輸入列的第一個符號如何確定生成式、及當(dāng)前輸入象征符屬于哪個發(fā)生式右部的開始象征符集合，確定選擇導(dǎo)出相應(yīng)的發(fā)生式。第四章語法分析-自頂向下分析，例3 :語法GS:SAA|dabas|w=輸入Abd，導(dǎo)出過程為：第四章語法分析-自頂向下分析，例3 :語法gs:s，S aA abAS abS abd非終止符a面對輸入符號d，d不屬于a的任何候選前綴定徑套， a的候補(bǔ)前綴定徑套包含第4章語法解析-自頂向下解析，如果某個非終止符的生成式中

12、包含空生成式，則根據(jù)在第2步驟中導(dǎo)出的生成式是如何決定的，后跟符號集合的決定，3、將后跟符號集合的定義： G=(VT，VN，p，s )定義為上下文相關(guān)語法，AVN， 對于將s設(shè)為開始符號、Follow(A)=a | S uA且aVT的非終止符，如果是SA，則可將#Follow(A) (#表示輸入列的終止符或句括號)寫作#，如果是SA，則可將Follow(A)a|SAa、aVT寫作#。 例4 :例2中語法GS求出： sap|bqaa|cab|dbfollow集。 解： Follow(S)=？ Follow(A)=？ Follow(B)=？ 第四章語法解析-自頂向下解析，換言之，F(xiàn)ollow(A )是所有句型中緊跟在a之后出現(xiàn)的終止符或“#”。 例4 :例2中語法GS求出： sap|bqaa|cab|dbfollow集。、解： follow (s )=# follow (a )=p follow (b )=q，第四章語法解析自頂向下解析、自頂向下語法解析要解決的重要問題由假定要被置換的最左非的規(guī)則的選擇集合決定。 第四章語法解析自頂向下解析，4，選擇集合的定義給定的上下文相關(guān)語法的生成式a，如果是AVN，V*則Select(A)=First ()，如果是select ()，第四章語法分析-自頂向下分析，5，LL(1)語法的定義：語法中不包含左遞歸的