編譯原理——第4章 自頂向下語法分析

1、語法分析的作用語法分析的作用 是編譯程序的核心部分。其作用是識別由詞法分析給出的是編譯程序的核心部分。其作用是識別由詞法分析給出的 單詞符號序列是否是給定文法的正確句子單詞符號序列是否是給定文法的正確句子(程序程序)。語法分析方法概述語法分析方法概述 按照構(gòu)建語法樹的方式可分為自頂向下和自底向上分析。按照構(gòu)建語法樹的方式可分為自頂向下和自底向上分析。1 確定的自頂向下分析思想確定的自頂向下分析思想 綜述：關(guān)鍵是從文法的開始符號出發(fā)，如何根據(jù)當(dāng)前的輸綜述：關(guān)鍵是從文法的開始符號出發(fā)，如何根據(jù)當(dāng)前的輸入符號入符號(單詞單詞)唯一地確定選用哪個產(chǎn)生式向下推導(dǎo)，或構(gòu)唯一地確定選用哪個產(chǎn)生式向下推導(dǎo)，或

2、構(gòu)造一棵相應(yīng)的語法樹。造一棵相應(yīng)的語法樹。 注：該推導(dǎo)一定是最左推導(dǎo)。注：該推導(dǎo)一定是最左推導(dǎo)。第四章第四章 自頂向下語法分析自頂向下語法分析例例1GS: S pA | qB A cAd | a B dB輸入以下單詞序列 : pccadd分析樹將以下面產(chǎn)生式開始 S pA特點(diǎn)：分析時，選取產(chǎn)生式的過程是唯一確定的特點(diǎn)：分析時，選取產(chǎn)生式的過程是唯一確定的例例2type simple | id | array simple of typesimple integer | char | num dotdot num開始符號開始符號 自頂向下分析 自頂向下生成語法樹 考慮右邊的文法:輸入以下單詞序列

3、 : array num dotdot num of integer分析樹將以下面產(chǎn)生式開始 type array simple of type特點(diǎn)：產(chǎn)生式的右部含有非終結(jié)符的情況特點(diǎn)：產(chǎn)生式的右部含有非終結(jié)符的情況輸入 : array num dotdot num of integertypesimpleofarraytypenumnumdotdotsimpletypesimpleofarraytypenumnumdotdotsimpleinteger向前指針向前指針對一個文法符號串的開始符號集合定義如下：對一個文法符號串的開始符號集合定義如下：定義定義1 設(shè)設(shè)G=(VT ，VN ，S，P)

4、是上下文無關(guān)文法是上下文無關(guān)文法FIRST()=a | a，a VT ， ， V * 若若 ，則規(guī)定，則規(guī)定 FIRST() *例例3輸入以下單詞序列 : abd分析樹將以下面產(chǎn)生式開始 S aA特點(diǎn)：某一非終結(jié)符含有空產(chǎn)生式的情況特點(diǎn)：某一非終結(jié)符含有空產(chǎn)生式的情況GS: S aA S d A bAS A 定義一個文法符號的后跟符號的集合：定義一個文法符號的后跟符號的集合：定義定義2 設(shè)設(shè)G=(VT ，VN ，S ，P)是上下文無關(guān)文法是上下文無關(guān)文法A VN , S是文法的開始符號是文法的開始符號FOLLOW(A)=a | S A且且a VT ， a (FIRST()-) ， VT * ,

5、 V + 若若S A 且且 ，則，則# FOLLOW(A)也可定義為：也可定義為： FOLLOW(A)= a | S Aa ，a VT 若若S A ，則，則# FOLLOW(A)這里用這里用#作為輸入串的結(jié)束符或稱為句子括號，如作為輸入串的結(jié)束符或稱為句子括號，如#輸入串輸入串#*綜合以上情況定義選擇集合綜合以上情況定義選擇集合SELECT如下：如下：定義定義3 給定上下文無關(guān)文法的產(chǎn)生式給定上下文無關(guān)文法的產(chǎn)生式A ， A VN ， V * ，若，若 ，則，則SELECT(A )=FIRST()如果如果 ，則，則SELECT(A )=(FIRST()-) U FOLLOW(A)*更進(jìn)一步能夠

6、使用自頂向下分析技術(shù)必須使文法滿足如下條更進(jìn)一步能夠使用自頂向下分析技術(shù)必須使文法滿足如下條件，我們稱滿足條件的文法為件，我們稱滿足條件的文法為LL(1)文法，其定義為：文法，其定義為：定義定義4 一個上下文無關(guān)文法是一個上下文無關(guān)文法是LL(1)文法的充分必要條件是，文法的充分必要條件是，對每個非終結(jié)符對每個非終結(jié)符A的兩個不同產(chǎn)生式，的兩個不同產(chǎn)生式， A ， A 滿足滿足SELECT(A ) SELECT(A )=其中其中、 不同時推出不同時推出例例4GS: S aAS S b A bA A 該文法是否可用確定的自頂向下分析方法分析？該文法是否可用確定的自頂向下分析方法分析？LL(1)文

7、法的判別文法的判別求出能推出求出能推出 的非終結(jié)符的非終結(jié)符計算產(chǎn)生式右部的計算產(chǎn)生式右部的FIRST集集計算非終結(jié)符的計算非終結(jié)符的FOLLOW集集計算產(chǎn)生式的計算產(chǎn)生式的SELECT集集(只針對同一個非終結(jié)符對應(yīng)多只針對同一個非終結(jié)符對應(yīng)多條產(chǎn)生式的情況條產(chǎn)生式的情況)。對第對第4步的結(jié)果兩兩求交集以判斷是否是步的結(jié)果兩兩求交集以判斷是否是LL(1)文法。文法。例例5GS: S AB S bC A b A B B aD C AD C b D aS D c該文法是否可用確定的自頂向下分析方法分析？該文法是否可用確定的自頂向下分析方法分析？3 某些非某些非LL(1)文法到文法到LL(1)文法的

8、等價變換文法的等價變換提取左公共因子提取左公共因子若文法中含有形如若文法中含有形如A |的產(chǎn)生式等價變換為：的產(chǎn)生式等價變換為：A A AA A |推廣到一般形式為：推廣到一般形式為：A 1|2| n提取左公共因子后變?yōu)椋禾崛∽蠊惨蜃雍笞優(yōu)椋篈 A AA A 1|2|n若產(chǎn)生式中仍含有左公共因子，可再次提取。若產(chǎn)生式中仍含有左公共因子，可再次提取。GS: S aSb S aS S 試消除該文法的左公共因子。試消除該文法的左公共因子。GS: A ad A Bc B aA B bB對于產(chǎn)生式右部有非終結(jié)符開始的先替換后提取。對于產(chǎn)生式右部有非終結(jié)符開始的先替換后提取。GS: S aSd S Ac

9、 A aS A b替換后檢查是否有無用產(chǎn)生式產(chǎn)生。替換后檢查是否有無用產(chǎn)生式產(chǎn)生。GS: S Ap|Bq A aAp|d B aBq|e無法消除左公共因子。無法消除左公共因子。請注意以下兩點(diǎn)：請注意以下兩點(diǎn)：不一定每個文法的左公共因子都能在有限的步驟內(nèi)替換不一定每個文法的左公共因子都能在有限的步驟內(nèi)替換成無左公共因子的文法。成無左公共因子的文法。一個文法提取了左公共因子后，只解決了相同左部產(chǎn)生一個文法提取了左公共因子后，只解決了相同左部產(chǎn)生式右部的式右部的FIRST集不相交問題，當(dāng)改寫后的文法不含空集不相交問題，當(dāng)改寫后的文法不含空產(chǎn)生式，且無左遞歸時，則改寫后的文法是產(chǎn)生式，且無左遞歸時，則

10、改寫后的文法是LL(1)文法，文法，否則還需用否則還需用LL(1)文法的判別式進(jìn)行判斷才能確定是否文法的判別式進(jìn)行判斷才能確定是否為為LL(1)文法。文法。含有左遞歸的文法一定不是含有左遞歸的文法一定不是LL(1)文法文法GS: S Sa S b 輸入：輸入：baaa#GS: A aB A Bb B Ac B d 輸入：輸入：adbcbcbc#消除左遞歸消除左遞歸一個文法含有下列形式的一個文法含有下列形式的產(chǎn)生式時稱該文法含有左遞歸：產(chǎn)生式時稱該文法含有左遞歸：A A A VN V * 直接左遞歸直接左遞歸A B B A A , B VN , V * 間接左遞歸間接左遞歸形如形如A A 稱文法

11、中含有間接左遞歸稱文法中含有間接左遞歸消除直接左遞歸：消除直接左遞歸：方法：方法：將直接左遞歸改寫為右遞歸。將直接左遞歸改寫為右遞歸。S Sa | b改寫為改寫為: S bS S aS | 一般情況下，假定關(guān)于一般情況下，假定關(guān)于A的全部產(chǎn)生式是：的全部產(chǎn)生式是：A A1 | A2 | | Am | 1 | 2 | | n消除直接左遞歸后改寫為：消除直接左遞歸后改寫為：A 1 A | 2 A| | n AA 1 A | 2 A | | m A | 消除間接左遞歸：消除間接左遞歸：對于間接左遞歸的消除需先將間接左遞歸變?yōu)橹苯幼筮f歸，對于間接左遞歸的消除需先將間接左遞歸變?yōu)橹苯幼筮f歸，然后再用消除

12、直接左遞歸的方法來消除。然后再用消除直接左遞歸的方法來消除。 GA: A aB A Bb B Ac B d消除文法中一切左遞歸的算法：消除文法中一切左遞歸的算法：把文法的所有非終結(jié)符按某一順序排序把文法的所有非終結(jié)符按某一順序排序按排列的順序逐次消除直接左遞歸按排列的順序逐次消除直接左遞歸去掉無用產(chǎn)生式去掉無用產(chǎn)生式看下例：看下例：GS: S Qc | c Q Rb | b R Sa | a試消除該文法的一切左遞歸試消除該文法的一切左遞歸 4 4 確定自頂向下分析方法確定自頂向下分析方法遞歸子程序法遞歸子程序法預(yù)測分析法預(yù)測分析法遞歸子程序法遞歸子程序法舉例：舉例：E TE E + TE |

13、T FT T * FT | F ( E ) | idmain() TD_E();TD_T() TD_F(); TD_T();TD_E() TD_T(); TD_E();TD_E() token = get_token(); if token = + then TD_T(); TD_E(); TD_F() token = get_token(); if token = ( then TD_E(); match(); else if token.value id then error + EXIT else .TD_T() token = get_token(); if token = * the

14、n TD_F(); TD_T(); 如何處理如何處理 -產(chǎn)生式產(chǎn)生式?注意注意: 并未并未顯示所有出顯示所有出錯條件，造錯條件，造成糾錯延時成糾錯延時.預(yù)測分析法模型預(yù)測分析法模型a+b$YX$Z輸入輸入預(yù)測分析程序預(yù)測分析程序Stack輸出輸出分析表分析表 MA,a(String + 終止符終止符)基于棧與輸入來決定基于棧與輸入來決定采取什么動作采取什么動作空棧標(biāo)識空棧標(biāo)識預(yù)測分析法舉例：預(yù)測分析法舉例：語法語法: E ET | T T T * F | F F i | (E) 輸入輸入 : i + i * i $E TE E + TE | T FT T * FT | F ( E ) | i消除左遞歸消除左遞歸 !預(yù)測分析表預(yù)測分析表 M非終結(jié)符非終結(jié)符輸入字符輸入字符i+*()$EETTFETETFTFiE+TET T*FTF(E)TFTETET E E T $E$ET$ETF$ETi$ET$E$ET+$ET$ETF$ETi$ET$ETF*$ETF$ETi$ET$E$i + i * i$i + i * i$i + i * i$i + i * i$+ i * i$+ i * i$+ i * i$i * i$i * i$i * i$* i$