【正文】 F i * F T39。 T 39。 ? + T 39?！?FT39。| ? T→FT39。 E39。 i ? ? 2022年 2月 16日 編 譯 原 理 構(gòu)造分析表 基本思想： 當(dāng)文法中某一非終結(jié)符出現(xiàn)在棧頂時，根據(jù)當(dāng)前的輸入符號 ,分析表應(yīng)指示要用該非終結(jié)符里的哪一條產(chǎn)生式規(guī)則(即進行下一步最左推導(dǎo) ) 2022年 2月 16日 編 譯 原 理 對文法的每個產(chǎn)生式 A → α執(zhí)行第 1步和第 2步 對每個終結(jié)符 a ∈ FIRST（ α）， A → α ==M[A,a] 表示： A在棧頂，輸入符號是 a，應(yīng)選擇 α去匹配， 例 FIRST(TE?)= {(,i} 若 ε ∈ FIRST（ α） ,而且 b ∈ FOLLOW(A)，則 A→ α ==M[A,b] 表示： A已經(jīng)匹配輸入串成功，其后繼符號終結(jié)符 b由 A后面的語法成分去匹配。 F i T 39。 E39。| ? F→(E)|i 2022年 2月 16日 編 譯 原 理 步驟 符號棧 讀入符號 剩余符號串 使用產(chǎn)生式 8. ＃ E?T i *i T→ FT? 9. ＃ E?T?F i *i F→ i 10. ＃ E?T? i i *i 11. ＃ E?T? * i T?→ *FT? 12. ＃ E?T?F* * i 13. ＃ E?T?F i F→ i 14. ＃ E?T? i i 15. ＃ E?T? T? → ε 16. ＃ E? E? → ε 17. ＃ accept 2022年 2月 16日 編 譯 原 理 推導(dǎo)過程： E?TE? ?FT?E? ?iT?E ?iE ?i+TE? ?i+FT?E? ? i+iT?E? ?i+i*FT?E? ?i+i*iT?E? ?i+i*iE? ?i+i*i 最左推導(dǎo) E T E39。 T39?！?TE39。 }//end of while 2022年 2月 16日 編 譯 原 理 步驟 符號棧 讀入符號 剩余符號串 使用產(chǎn)生式 1. ＃ E i +i*i E→ TE? 2. ＃ E?T i +i*i T→ FT? 3. ＃ E?T?F i +i*i F→ i 4. ＃ E?T? i i +i*i 5. ＃ E?T? + i*i T? → ε 6. ＃ E? + i*i E→ +TE? 7. ＃ E?T+ + i*i 輸入串為 : i+i*i E→TE39。 push(Xn…X2X1)。//分析成功 else error()。 //讀入下一個符號給 a else error()。 while flag { X=pop( ) 。 //把 和開始符號 S依次壓進棧 a=getsym( ) 。 → ε F F → i F → (E) 2022年 2月 16日 編 譯 原 理 2022年 2月 16日 編 譯 原 理 總控程序算法描述 push()。 T39。 → ε T39。 T39。 E → ε E → ε T T → FT39。 E39。 E → TE39?！?FT39。| ? T→FT39。 E39。 ? 缺點： 在句法分析期間高深度的遞歸調(diào)用影響了分析器的效率，許多時間要花費在遞歸子程序的連接上。 2022年 2月 16日 編 譯 原 理 遞歸下降法的優(yōu)缺點： ? 優(yōu)點： ①最主要一點是編寫速度快； ②由于分析器和文法的緊密對應(yīng)性，容易保證語法分析器的正確性。前面已經(jīng)講過，自頂向下分析不能處理左遞歸文法，若有左遞歸，則應(yīng)改寫文法，但是消除了左遞歸并不等于消除了文法中的所有遞歸性質(zhì)，此時文法有右遞歸性或自嵌入性。 (2)由于 LL(1)文法的任何一對具有相同左部的產(chǎn)生式的SELECT集是不相交的，因此，根據(jù)現(xiàn)行的非終結(jié)符 (已在棧頂 )和當(dāng)前的輸入符號就能唯一地確定分析過程中的下一步動作，也就是說，我們完全可以為 LL(1)文法構(gòu)造一個確定的分析器。 ? return 子程序 P（ A?）： ? L: if ch = ?d? then ? begin ? read(ch)。 goto L ? end ? if ch ? ?d? then error ? P(S)。 ? if ch = ?b? then goto L ? else error ? end ? L: READ(ch)。 ? if ch = ?)? then goto L ? else error ? end ? else if ch ? ?a? then error ? else begin ? READ(ch)。 2022年 2月 16日 編 譯 原 理 2022年 2月 16日 編 譯 原 理 程序設(shè)計 例中的文法 G [S]： ? 子程序 P(S)： ? READ(ch) ? if ch = ?(? then ? begin ? READ(ch)。 2022年 2月 16日 編 譯 原 理 框圖設(shè)計 設(shè)文法 G [S]： S→ (A) ?aAb A→ eA ??dSA? A?→ dA ??? 此文法的遞歸下降程序框圖設(shè)計如下所示。 （ 1）當(dāng)遇到終結(jié)符 a時，則編寫語句： if （當(dāng)前讀入的輸入符號 =a)(匹配 ),讀入下一個符號； if (ch = a） then READ(ch) else error （ 2）當(dāng)遇到非終結(jié)符 A時，則編寫語句調(diào)用相應(yīng)的函數(shù) A（）； （ 3）當(dāng)遇到 A→ε 時，則編寫語句： if（當(dāng)前讀入的符號 ≠ FOLLOW（ A）） ,ERROR( )。在遞歸下降法中，遞歸子程序數(shù)等于文法中的非終結(jié)符個數(shù)。每匹配一個終結(jié)符，則再讀入下一個符號，對于產(chǎn)生式右部的每一個非終結(jié)符，則調(diào)