編譯原理總復(fù)習(xí)ppt課件

1、編譯原理編譯原理總復(fù)習(xí)總復(fù)習(xí)4題型及分值題型及分值4教材各章知識(shí)點(diǎn)概覽教材各章知識(shí)點(diǎn)概覽1.2題型及分值題型及分值4一、判斷題一、判斷題 （15=5）4二、填空題二、填空題 （115=15）4三、選擇題（三、選擇題（25=10）4四、名詞解釋題四、名詞解釋題 （35=15）4五、計(jì)算題五、計(jì)算題 (5小題小題) （5+10+15+15+10=55）3教材各章知識(shí)點(diǎn)概覽教材各章知識(shí)點(diǎn)概覽4第一章第一章 引論引論4第二章第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述高級(jí)語(yǔ)言及其語(yǔ)法描述4第三章第三章 詞法分析詞法分析4第四第四 章語(yǔ)法分析章語(yǔ)法分析自上而下分析自上而下分析4第五章第五章 語(yǔ)法分析語(yǔ)法分析自下而上分析

2、自下而上分析4第六章屬性文法和語(yǔ)法制導(dǎo)翻譯第六章屬性文法和語(yǔ)法制導(dǎo)翻譯4第七第七 章章 語(yǔ)義分析和中間代碼產(chǎn)生語(yǔ)義分析和中間代碼產(chǎn)生4第八章第八章 符號(hào)表符號(hào)表4第十章第十章 優(yōu)優(yōu) 化化4第一章第一章 引論引論4基本概念基本概念 翻譯程序，編譯程序，編譯前端、編譯后端4編譯過(guò)程的五個(gè)階段，各階段的任務(wù)及其依循的規(guī)則、描述工具分別是編譯過(guò)程的五個(gè)階段，各階段的任務(wù)及其依循的規(guī)則、描述工具分別是什么？什么？4編譯錯(cuò)誤的種類(lèi)編譯錯(cuò)誤的種類(lèi) 語(yǔ)法錯(cuò)誤、語(yǔ)義錯(cuò)誤5第一章第一章 引論引論4程序翻譯的兩種方式，它們的區(qū)別程序翻譯的兩種方式，它們的區(qū)別 編譯方式、解釋方式4編譯程序的生成方法編譯程序的生成方法

3、 用機(jī)器語(yǔ)言/匯編語(yǔ)言作工具 用高級(jí)語(yǔ)言作工具 自編譯方式 建立專(zhuān)門(mén)的編制編譯程序的有效工具6第二章第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述高級(jí)語(yǔ)言及其語(yǔ)法描述4基本概念基本概念 文法、上下文無(wú)關(guān)文法、推導(dǎo)、句型、句子、 語(yǔ)言、語(yǔ)義、詞法規(guī)則、語(yǔ)法規(guī)則、語(yǔ)義規(guī)則4名字和標(biāo)識(shí)符及其區(qū)別名字和標(biāo)識(shí)符及其區(qū)別4數(shù)組，內(nèi)情向量、表達(dá)式數(shù)組，內(nèi)情向量、表達(dá)式4最左推導(dǎo)、最右推導(dǎo)、語(yǔ)法分析樹(shù)及其與推導(dǎo)之間的關(guān)系最左推導(dǎo)、最右推導(dǎo)、語(yǔ)法分析樹(shù)及其與推導(dǎo)之間的關(guān)系4文法的二義性及其消除文法的二義性及其消除7第二章第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述高級(jí)語(yǔ)言及其語(yǔ)法描述4語(yǔ)句的分類(lèi)語(yǔ)句的分類(lèi) 功能上：說(shuō)明性語(yǔ)句、執(zhí)行性語(yǔ)句 形式上

4、： 簡(jiǎn)單句、復(fù)合句、分程序4形式語(yǔ)言分類(lèi)形式語(yǔ)言分類(lèi)(chomsky,1956) 0型 普通（短語(yǔ)）文法 1型 上下文有關(guān)文法 2型 上下文無(wú)關(guān)文法 3型 線(xiàn)性（正規(guī)、正則）文法8第三章第三章 詞法分析詞法分析4基本概念基本概念 DFA、NFA、狀態(tài)等價(jià)4詞法分析器的功能及其輸出形式詞法分析器的功能及其輸出形式4單詞符號(hào)的種類(lèi)單詞符號(hào)的種類(lèi) 關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符4正規(guī)式正規(guī)式 NFA DFA 最少化最少化DFA（注意：狀態(tài)函數(shù)定義不完整之情（注意：狀態(tài)函數(shù)定義不完整之情形）形）4詞法分析器的自動(dòng)產(chǎn)生工具：詞法分析器的自動(dòng)產(chǎn)生工具： LEX 4狀態(tài)轉(zhuǎn)換圖的構(gòu)造狀態(tài)轉(zhuǎn)換圖的構(gòu)造(標(biāo)識(shí)

5、符、整數(shù)標(biāo)識(shí)符、整數(shù))9第四第四 章語(yǔ)法分析章語(yǔ)法分析自上而下分析自上而下分析4語(yǔ)法分析的方法語(yǔ)法分析的方法 自上而下、自下而上4自上而下分析的基本思想自上而下分析的基本思想4自上而下分析面臨的主要問(wèn)題自上而下分析面臨的主要問(wèn)題 左遞歸、回溯4自上而下分析的基本方法自上而下分析的基本方法 LL（1）分析法、遞歸下降分析器4LL（1）的含義，）的含義，LL（1）文法的判別）文法的判別10第四第四 章語(yǔ)法分析章語(yǔ)法分析自上而下分析自上而下分析4LL(1)分析器的組成部分分析器的組成部分 輸入緩沖區(qū)、分析棧、分析表、總控程序4LL(1)分析的四種動(dòng)作分析的四種動(dòng)作 成功、匹配、推導(dǎo)、報(bào)錯(cuò)4預(yù)測(cè)分析表

6、的構(gòu)造預(yù)測(cè)分析表的構(gòu)造 左遞歸的消除（直接、間接） FIRST、FOLLOW集的計(jì)算 LL(1)文法的判定及其分析表的構(gòu)造11第五章第五章 語(yǔ)法分析語(yǔ)法分析自下而上分析自下而上分析4基本概念基本概念 短語(yǔ)、直接短語(yǔ)、句柄、素短語(yǔ)、最左素短語(yǔ)、規(guī)范歸約與規(guī)范推導(dǎo)4自下而上分析的基本思想及其核心自下而上分析的基本思想及其核心4自下而上分析的基本方法自下而上分析的基本方法 算符優(yōu)先分析法（非規(guī)范歸約） LR分析法（規(guī)范歸約）4給定一個(gè)文法的句型，找出其短語(yǔ)、直接短語(yǔ)、句柄、素短語(yǔ)和最左素給定一個(gè)文法的句型，找出其短語(yǔ)、直接短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)短語(yǔ)12第五章第五章 語(yǔ)法分析語(yǔ)法分析自下而上分

7、析自下而上分析4LR分析法的基本思想及其組成部分分析法的基本思想及其組成部分 思想：記住歷史、展望未來(lái)、定奪現(xiàn)在 組成：輸入緩沖區(qū)、分析棧（狀態(tài)、符號(hào)）、分析表（動(dòng)作、轉(zhuǎn)換）、總控程序4可歸約串的刻畫(huà)方式可歸約串的刻畫(huà)方式 算符優(yōu)先：最左素短語(yǔ) LR分析法：句柄4LR(0)、LR(1)、LR(k)、SLR的含義的含義13第五章第五章 語(yǔ)法分析語(yǔ)法分析自下而上分析自下而上分析4LR分析器的四種動(dòng)作分析器的四種動(dòng)作 移進(jìn)、歸約、接受、報(bào)錯(cuò)4LR分析法可能遇到的問(wèn)題及其解決辦法分析法可能遇到的問(wèn)題及其解決辦法 移進(jìn)歸約 沖突 歸約歸約 沖突4語(yǔ)法分析器的自動(dòng)產(chǎn)生工具語(yǔ)法分析器的自動(dòng)產(chǎn)生工具 YACC

8、14第五章第五章 語(yǔ)法分析語(yǔ)法分析自下而上分析自下而上分析4算符優(yōu)先關(guān)系表的構(gòu)造算符優(yōu)先關(guān)系表的構(gòu)造 算符文法及其算符優(yōu)先文法的判定 FIRSTVT、LASTVT集的構(gòu)造 算符優(yōu)先表的構(gòu)造 優(yōu)先表與優(yōu)先函數(shù)之間的關(guān)系4LR（0）、）、SLR、LALR（1）、）、LR（1）分析表的構(gòu)造）分析表的構(gòu)造 拓廣文法、構(gòu)造LR(0)或LR(1)項(xiàng)目集規(guī)范簇、構(gòu)造相應(yīng)LR分析表15第六章屬性文法和語(yǔ)法制導(dǎo)翻譯第六章屬性文法和語(yǔ)法制導(dǎo)翻譯4基本概念基本概念 S屬性文法 L屬性文法4屬性的分類(lèi)屬性的分類(lèi) 綜合屬性 繼承屬性4抽象語(yǔ)法樹(shù)的表示抽象語(yǔ)法樹(shù)的表示16第七第七 章章 語(yǔ)義分析和中間代碼產(chǎn)生語(yǔ)義分析和中

9、間代碼產(chǎn)生 4常見(jiàn)的中間代碼的幾種形式常見(jiàn)的中間代碼的幾種形式 后綴式（逆波蘭式）、三地址代碼（三元式、四元式、間接三元式）、DAG圖表示、抽象語(yǔ)法樹(shù)4后綴式（逆波蘭式）的表示后綴式（逆波蘭式）的表示4各類(lèi)語(yǔ)句的翻譯（四元式）各類(lèi)語(yǔ)句的翻譯（四元式） 表達(dá)式（算術(shù)及布爾）、賦值語(yǔ)句、數(shù)組、IF語(yǔ)句、WHILE語(yǔ)句17第八章第八章 符號(hào)表符號(hào)表 4符號(hào)表的基本組成、基本操作符號(hào)表的基本組成、基本操作 組成：名字欄和信息欄 操作：查表、填表、訪(fǎng)表、更新、刪除4符號(hào)表的組織方式符號(hào)表的組織方式 直接方式、間接方式4符號(hào)表的構(gòu)造和處理方法符號(hào)表的構(gòu)造和處理方法 線(xiàn)性表、二叉樹(shù)、雜湊（哈希）18第八章第

10、八章 符號(hào)表符號(hào)表 4內(nèi)情向量的基本表項(xiàng)內(nèi)情向量的基本表項(xiàng) 維數(shù)、首地址、各維界差、各維上界、各維下屆、數(shù)組元素類(lèi)型、地址不變量19第十章第十章 優(yōu)優(yōu) 化化4基本概念基本概念 優(yōu)化、基本塊、局部?jī)?yōu)化4優(yōu)化遵循的原則優(yōu)化遵循的原則 等價(jià)原則、有效原則、合算原則4常見(jiàn)的優(yōu)化的幾種方法常見(jiàn)的優(yōu)化的幾種方法 刪除公共子表達(dá)式、復(fù)寫(xiě)傳播、刪除無(wú)用代碼、合并已知量、代碼外提、強(qiáng)度削弱、刪除歸納變量。（后三種涉及循環(huán)優(yōu)化）20第十章第十章 優(yōu)優(yōu) 化化4基本塊的劃分及其程序流圖的構(gòu)造基本塊的劃分及其程序流圖的構(gòu)造 21習(xí)題講解習(xí)題講解4計(jì)算題計(jì)算題 注意復(fù)習(xí)書(shū)上的例題及其平時(shí)作業(yè)題。在復(fù)習(xí)時(shí)，一定要親手獨(dú)立做一遍！注意復(fù)習(xí)書(shū)上的例題及其平時(shí)作業(yè)題。在復(fù)習(xí)時(shí)，一定要親手獨(dú)立做一遍！22習(xí)題講解習(xí)題講解4計(jì)算題計(jì)算題4構(gòu)造與下列正規(guī)式等價(jià)的最少化DFA 1(0|1)*101 (0|1)*(00|11)(0|1)*23習(xí)題講解習(xí)題講解4計(jì)算題計(jì)算題4令文法G為： EE-T|T TT/F|F F（E）|i（1）消除文法的左遞歸并構(gòu)造其LL(1)分析表（2）構(gòu)造該文法的算符優(yōu)先分析表24習(xí)題講解習(xí)題講解4計(jì)算題計(jì)算題（3）分析該文法是否為L(zhǎng)R(0)、LR(1)、SLR、LALR文法，若是構(gòu)造相應(yīng)分析表（4）