【正文】 … Xn1 Xn LL(1)分析器的邏輯結(jié)構(gòu)： 分析棧、分析表、總控程序 文法符號 根據(jù)棧頂符號 X和當(dāng)前輸入符號 a來決定分析器的動(dòng)作 2022年 2月 16日 編 譯 原 理 在實(shí)際語言中，每一種語法成分都有確定的左右界符，為研究問題方便，統(tǒng)一以‘ $?表示輸入串結(jié)束 分析表：二維矩陣 M A → αi A ∈ Vn 、 αi∈ V* 、 a ∈ VT or $ error M[A,a]= E→TE39。 E39?！?TE39。| ? T→FT39。 T39?！?FT39。| ? F→(E)|i i + * ( ) $ E E → TE39。 E → TE39。 E39。 E39。 → +TE39。 E → ε E → ε T T → FT39。 T → FT39。 T39。 T39。 → ε T39。 → *FT39。 T39。 → ε T39。 → ε F F → i F → (E) 2022年 2月 16日 編 譯 原 理 2022年 2月 16日 編 譯 原 理 總控程序算法描述 push()。 push(S)。 //把 和開始符號 S依次壓進(jìn)棧 a=getsym( ) 。 //讀入第一個(gè)符號給 a flag=1。 while flag { X=pop( ) 。//從棧中彈出 X if(X ∈ VT ) if(X ==a) a=getsym( ) 。 //讀入下一個(gè)符號給 a else error()。 else if(X ==??) if(X ==a) flag=0 。//分析成功 else error()。 else if(M[X,a]==X－＞ X1X2…Xn) // X ∈ Vn查分析表 {X=pop( ) 。 push(Xn…X2X1)。 //若 X1X2…Xn= ε ，則不進(jìn)棧 } else error()。 }//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。 E39?！?TE39。| ? T→FT39。 T39。→*FT39。| ? 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。 ? + T 39。 E39。 T 39。 F i T 39。 F i * F T39。 i ? ? 2022年 2月 16日 編 譯 原 理 構(gòu)造分析表 基本思想： 當(dāng)文法中某一非終結(jié)符出現(xiàn)在棧頂時(shí)，根據(jù)當(dāng)前的輸入符號 ,分析表應(yīng)指示要用該非終結(jié)符里的哪一條產(chǎn)生式規(guī)則(即進(jìn)行下一步最左推導(dǎo) ) 2022年 2月 16日 編 譯 原 理 對文法的每個(gè)產(chǎn)生式 A → α執(zhí)行第 1步和第 2步 對每個(gè)終結(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后面的語法成分去匹配。 例 FOLLOW(E?)={,)} 把所有無定義的 M[A,a]都標(biāo)上 error E’ → ε T’ → ε i + * ( ) E E’ T T’ F E → TE’ E → TE’ E’ → +TE’ E’ → ε T → FT’ T → FT’ T’ → ε T’ → *FT’ T’ → ε F → i F → (E) E→TE39。 E39?！?TE39。| ? T→FT39。 T39?！?FT39。| ? F→(E)|i 【 例 】 2022年 2月 16日 編 譯 原 理 注意 : 用上述算法可以構(gòu)造出任意給定文法的分析表 ,但不是所有文法都能構(gòu)造出上述那種形狀的分析表，即 M[A,a]=一條規(guī)則或 Error. LL(1)分析表不含多重定義 LL(1)文法 二義性文法不是 LL(1)文法 2022年 2月 16日 編 譯 原 理 在 JAVA上廣泛使用的 LL算法 分析工具 Javacc 國際新聞組 : Javacc除了常規(guī)的詞法分析和語法分析以外 ,還提供JJTree等工具來幫助我們建立語法樹 . Javacc在很多地方做得都比 lex和 yacc要人性化 E T E39。 ? + T 39。 E39。 T 39。 F i T 39。 F i * F T39。 i ? ? 2022年 2月 16日 編 譯 原 理 LL(1)分析法的優(yōu)缺點(diǎn) ?效率高于遞歸下降分析法 優(yōu)點(diǎn) ?對文法的限制較多要求文法必須為 LL(1)文法 缺點(diǎn)