資源描述：
《編譯第五章終版.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第5章自頂向下語(yǔ)法分析方法5.1確定的自頂向下分析思想5.2LL(1)文法的判別5.3某些非LL(1)文法到LL(1)文法的等價(jià)變換5.4不確定的自頂向下分析思想5.5確定的自頂向下分析方法5.6典型例題及解答引言1、語(yǔ)法分析的地位是編譯程序的核心部分。2、語(yǔ)法分析的任務(wù)識(shí)別由詞法分析得出的單詞序列是否是給定文法的句子。3、語(yǔ)法分析方法自頂向下分析和自底向上分析自頂向下分析包括確定分析和不確定分析自底向上分析包括算符優(yōu)先分析和LR分析引言4、語(yǔ)法分析的方式1）自上而下語(yǔ)法分析反復(fù)使用不同產(chǎn)生式進(jìn)行推導(dǎo)以謀求與
2、輸入符號(hào)串相匹配。2）自下而上語(yǔ)法分析對(duì)輸入符號(hào)串尋找不同產(chǎn)生式進(jìn)行歸約直到文法開(kāi)始符號(hào)。注：這里所說(shuō)的輸入符號(hào)指詞法分析所識(shí)別的單詞引言自頂向下分析法：也就是從文法的開(kāi)始符號(hào)出發(fā)，企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的句子，則必能推出，反之必然出錯(cuò)。自頂向下分析法又可分為確定的和不確定的兩種。確定的分析方法:需對(duì)文法有一定的限制，但由于實(shí)現(xiàn)方法簡(jiǎn)單、直觀，便于手工構(gòu)造或自動(dòng)生成語(yǔ)法分析器。不確定的方法:即帶回溯的分析方法，這種方法實(shí)際上是一種窮舉的試探方法，因此效率低，代價(jià)高，因而極
3、少使用。自下而上分析法：從輸入串出發(fā)進(jìn)行歸約，最終歸約為文法開(kāi)始符。從葉結(jié)點(diǎn)出發(fā)，向上歸結(jié)出以文法開(kāi)始符為根結(jié)點(diǎn)的語(yǔ)法分析樹(shù)。引言回顧在“文法和語(yǔ)言”一章中介紹的關(guān)于句子、句型和語(yǔ)言的定義及什么叫最左推導(dǎo)、最右推導(dǎo)和規(guī)范推導(dǎo)的基本概念。有文法G[S]，若S?*x，且x∈V*則稱(chēng)x是文法G[S]的句型。有文法G[S]，若S?*x，且x∈VT*，則稱(chēng)x是文法G[S]的句子。例：G[S]：S→0S1，S→01可有推導(dǎo)S?0S1?00S11?000S111?00001111說(shuō)明00001111是G[S]的句子。引言最
4、左（最右）推導(dǎo)：在推導(dǎo)的任何一步α?β(其中α、β是句型)，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換。最右推導(dǎo)被稱(chēng)為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱(chēng)為規(guī)范句型。句型的分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。舉例：文法：G={VN,VT,S,P}P：S→aAcBeA→b
5、AbB→d判斷輸入串a(chǎn)bbcde是否為文法的句子。（1）自頂向下最左推導(dǎo)：s?aAcBe?aAbcBe?abbcBe?abbcdeSAaBcebAbd文法：G={VN,VT,S,P}P：S→aAcBeA→b
6、AbB
7、→d判斷輸入串a(chǎn)bbcde是否為文法的句子。（2）自底向上abbcdeabbcBeabAcBeaAcBeSSAaBcebAbd引言句型分析的有關(guān)問(wèn)題①如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？假定要被替換的最左非終結(jié)符號(hào)是V，且左部為V的規(guī)則有n條：V→A1
8、A2
9、…
10、An，那么如何確定用哪個(gè)右部去替換V呢？②如何識(shí)別可歸約的串？在自下而上的分析方法中，在分析程序工作的每一步，都是從當(dāng)前串中尋找一個(gè)子串，看它是否能歸約到文法的某個(gè)非終結(jié)符號(hào)，該子串稱(chēng)為“可歸約串”。5.1確定的自頂向下分析思想例：若有文法G1[S]:
11、S→pA
12、qBA→cAd
13、aB→dB
14、b識(shí)別輸入串w=pccadd是否是G1[S]的句子 試探推導(dǎo)過(guò)程：S?pA?pcAd?pccAdd?pccadd5.1確定的自頂向下分析思想G1[S]:S→pA
15、qBA→cAd
16、aB→dB
17、b這個(gè)文法有以下兩個(gè)特點(diǎn)：①每個(gè)產(chǎn)生式的右部都由終結(jié)符號(hào)開(kāi)始。②如果兩個(gè)產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開(kāi)始。5.1確定的自頂向下分析思想若有文法G2[S]:S→Ap
18、BqA→a
19、cAB→b
20、dB識(shí)別輸入串w=ccap是否是G2[S]的句子，那么試探推出輸入串的推導(dǎo)過(guò)程
21、為：S?Ap?cAp?ccAp?ccap5.1確定的自頂向下分析思想G2[S]:S→Ap
22、BqA→a
23、cAB→b
24、dB文法的特點(diǎn)是：①產(chǎn)生式的右部不全是由終結(jié)符開(kāi)始。②如果兩個(gè)產(chǎn)生式有相同的左部，它們的右部是由不同的終結(jié)符或非終結(jié)符開(kāi)始。③文法中無(wú)空產(chǎn)生式。FIRST集的定義:設(shè)G=(VT,VN,P，S)是上下文無(wú)關(guān)文法FIRST(?)={a
25、??*a?,a∈VT,?,?∈V*}FIRST(?)={a
26、??*a……,a∈VT}若??*ε則規(guī)定ε∈FRIST(?)FIRST(?)為?的開(kāi)始符號(hào)或首符號(hào)集。在文法
27、G2中，F(xiàn)IRST(Ap)＝{a,c}FIRST(Bq)＝{b,d}返回分析前兩個(gè)確定的文法選擇哪個(gè)產(chǎn)生式可以看其first集結(jié)論：因此當(dāng)文法含有形如Ａ?α?β產(chǎn)生式時(shí)，其中A∈VN，α、β∈V*，若α和β都不能同時(shí)推導(dǎo)出空，則當(dāng)FIRST(α)∩FIRST(β)=?時(shí)，對(duì)于非終結(jié)符A的替換可唯一的確定候選。FIRST()集的構(gòu)造：對(duì)每一個(gè)文法符號(hào)x?(VN∪V?),構(gòu)造first(x)時(shí)，只要連續(xù)
