大連理工大學(xué)編譯原理PPT.ppt

1、溫故知新,上下文無(wú)關(guān)文法,自上而下,自下而上,LL(1)文法,2個(gè)函數(shù),任何兩個(gè)產(chǎn)生式A | 都滿足下列條件： 1、FIRST( ) FIRST( ) = 2、若 * ，那么FIRST() FOLLOW(A) = ,遞歸下降預(yù)測(cè)分析,非遞歸的預(yù)測(cè)分析,3.3 自上而下分析,3.3.6 預(yù)測(cè)分析的錯(cuò)誤恢復(fù) 編譯器的錯(cuò)誤概述 : 詞法錯(cuò)誤，如標(biāo)識(shí)符、關(guān)鍵字或算符拼寫錯(cuò)誤 語(yǔ)法錯(cuò)誤，如算術(shù)表達(dá)式的括號(hào)不配對(duì) 語(yǔ)義錯(cuò)誤，如算符作用于不相容的運(yùn)算對(duì)象 邏輯錯(cuò)誤，如無(wú)窮的遞歸調(diào)用,3.3 自上而下分析,分析器對(duì)錯(cuò)誤處理的基本目標(biāo) 清楚而準(zhǔn)確地報(bào)告錯(cuò)誤的出現(xiàn) 迅速地從每個(gè)錯(cuò)誤中恢復(fù)過(guò)來(lái)，以便診斷后面的錯(cuò)誤，

2、并盡量少出現(xiàn)偽錯(cuò)誤 它不應(yīng)該使正確程序的處理速度降低太多,3.3 自上而下分析,非遞歸預(yù)測(cè)分析在什么場(chǎng)合下發(fā)現(xiàn)錯(cuò)誤 棧頂?shù)慕K結(jié)符和下一個(gè)輸入符號(hào)不匹配 棧頂是非終結(jié)符A，輸入符號(hào)是a，而MA , a是空白,3.3 自上而下分析,非遞歸預(yù)測(cè)分析：采用緊急方式的錯(cuò)誤恢復(fù) 發(fā)現(xiàn)錯(cuò)誤時(shí)，分析器每次拋棄一個(gè)輸入記號(hào)，直到輸入記號(hào)屬于某個(gè)指定的同步記號(hào)集合為止。 同步 詞法分析器當(dāng)前提供的記號(hào)流能構(gòu)成的語(yǔ)法結(jié)構(gòu)，正是語(yǔ)法分析器所期望的。,3.3 自上而下分析,同步記號(hào)集合的選擇 把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號(hào)集合。 if expr then （then是expr的一個(gè)同步記號(hào)）,

3、3.3 自上而下分析,同步記號(hào)集合的選擇 把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號(hào)集合。 把高層結(jié)構(gòu)的開(kāi)始符號(hào)加到低層結(jié)構(gòu)的同步記號(hào)集合中。 a := expr ; if （語(yǔ)句的開(kāi)始符號(hào)作為表達(dá)式的同步符號(hào)，以免遺漏分號(hào)時(shí)忽略一大段程序。）,3.3 自上而下分析,同步記號(hào)集合的選擇 把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號(hào)集合。 把高層結(jié)構(gòu)的開(kāi)始符號(hào)加到低層結(jié)構(gòu)的同步記號(hào)集合中。 把FIRST(A)的終結(jié)符加入A的同步記號(hào)集合。,3.3 自上而下分析,同步記號(hào)集合的選擇 把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號(hào)集合。 把高層結(jié)構(gòu)的開(kāi)始符號(hào)加到低

4、層結(jié)構(gòu)的同步記號(hào)集合中。 把FIRST(A)的終結(jié)符加入A的同步記號(hào)集合。 如果非終結(jié)符可以產(chǎn)生空串，若出錯(cuò)時(shí)棧頂是這樣的非終結(jié)符，則可以使用產(chǎn)生空串的產(chǎn)生式。,3.3 自上而下分析,同步記號(hào)集合的選擇 把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號(hào)集合。 把高層結(jié)構(gòu)的開(kāi)始符號(hào)加到低層結(jié)構(gòu)的同步記號(hào)集合中。 把FIRST(A)的終結(jié)符加入A的同步記號(hào)集合。 如果非終結(jié)符可以產(chǎn)生空串，若出錯(cuò)時(shí)棧頂是這樣的非終結(jié)符，則可以使用產(chǎn)生空串的產(chǎn)生式。 如果終結(jié)符在棧頂而不能匹配，彈出此終結(jié)符。,同步記號(hào)加到表3.1的分析表上,總結(jié)一下出錯(cuò)的三種情況： 1 查表，表項(xiàng)是空白，棧頂不變，輸入串指針

5、后移；（相當(dāng)于拋棄記號(hào)） 2 查表，表項(xiàng)是synch，彈棧，并且彈出的是一個(gè)非終結(jié)符 3 棧頂終結(jié)符和輸入串終結(jié)符不匹配，彈棧，將棧頂終結(jié)符彈出,文法G: S-aSb | P P-bPc | bQc Q-Qa | a （1）它是chomsky哪一型文法？ （2）它生成的語(yǔ)言是什么？ （3）給出提取左因子、消除左遞歸之后的文法G （4）求出文法G每個(gè)非終結(jié)符的First集和Follow集 （5）構(gòu)建文法G的LL（1）預(yù)測(cè)分析表 （6）文法G是否是LL（1）文法 （7）利用非遞歸預(yù)測(cè)分析程序，驗(yàn)證abacb是否是文法G描述的語(yǔ)言的句子,文法G: S-aSb | P P-bPc | bQc Q-Qa

6、 | a （1）它是chomsky哪一型文法？ 答：它是2型文法，即上下文無(wú)關(guān)文法。 （2）它生成的語(yǔ)言是什么？ 答：aibjakcjbi | i=0; j,k=1,文法G: S-aSb | P P-bPc | bQc Q-Qa | a （3）給出提取左因子、消除左遞歸之后的文法 答： S-aSb | P P-bP P-Pc | Qc Q-aQ Q-aQ | ,S-aSb | P P-bP P-Pc | Qc Q-aQ Q-aQ | ,First(S)=a,b First(P)=b First(P)=a,b First(Q)=a First(Q)=a, ,Follow(S)=$,b Follow(P)=$,b,c Follow(P)=$,b,c Follow(Q)=c Follow(Q)=c ,（4）求出每個(gè)非終結(jié)符的First集和Follow集,（5）構(gòu)建LL（1）預(yù)測(cè)分析表