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

1、1 題型及分值一、判斷題 （15=5）二、填空題 （110=10）三、選擇題（25=10）四、簡(jiǎn)答題 （本題共35分）:其中包括兩個(gè)名詞解釋。五、計(jì)算題 （10+15+15=40） 編譯原理1 題型及分值一、判斷題 （15=5）編譯原理2 教材各章知識(shí)點(diǎn)概覽編譯程序概論 1文法和語(yǔ)言 2詞法分析與有限自動(dòng)機(jī) 3自上而下語(yǔ)法分析方法 4自下而上語(yǔ)法分析方法 5語(yǔ)法制導(dǎo)翻譯和語(yǔ)義分析 6符號(hào)表 7代碼優(yōu)化 8編譯原理2 教材各章知識(shí)點(diǎn)概覽編譯程序概論 1文法和語(yǔ)言 2詞法1、 編譯程序概論 （1）基本概念翻譯程序，編譯程序（2）編譯過(guò)程的五個(gè)階段，各階段的任務(wù)及其依循的規(guī)則、描述工具分別是什么？除

2、了這個(gè)5個(gè)階段之外，還應(yīng)該有哪兩個(gè)重要內(nèi)容？五個(gè)邏輯階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼產(chǎn)生、代碼優(yōu)化和目標(biāo)代碼生成。除了這五個(gè)階段之外，編譯程序的每個(gè)階段都涉及到表格管理和錯(cuò)誤處理這兩個(gè)重要內(nèi)容。編譯原理1、 編譯程序概論 （1）基本概念編譯原理1、 編譯程序概論 （3）編譯錯(cuò)誤的種類(lèi)從編譯程序的角度來(lái)看，源程序中的錯(cuò)誤主要分為：語(yǔ)法錯(cuò)誤 和 語(yǔ)義錯(cuò)誤兩類(lèi)錯(cuò)誤。（4）高級(jí)程序設(shè)計(jì)語(yǔ)言翻譯的兩種方式以及它們的區(qū)別高級(jí)程序設(shè)計(jì)語(yǔ)言的翻譯主要有兩種方式：編譯方式 和 解釋方式。區(qū)別：是否生成目標(biāo)代碼。編譯原理1、 編譯程序概論 （3）編譯錯(cuò)誤的種類(lèi)編譯原理2、 文法和語(yǔ)言 （1）基本概念文

3、法、推導(dǎo)、最左推導(dǎo)、最右推導(dǎo)、句型、句子、語(yǔ)言、文法的二義性（2）對(duì)文法G，能夠給出給定句型或句子的最左推導(dǎo)及最右推導(dǎo)序列，并畫(huà)出其對(duì)應(yīng)的語(yǔ)法分析樹(shù)。（3）能夠計(jì)算某文法的語(yǔ)言。（4）理解文法的二義性，能夠說(shuō)明一個(gè)文法是二義的。編譯原理2、 文法和語(yǔ)言 （1）基本概念編譯原理2、 文法和語(yǔ)言 （5）形式語(yǔ)言分類(lèi)(chomsky,1956)0型 普通（短語(yǔ)）文法 1型 上下文有關(guān)文法2型 上下文無(wú)關(guān)文法3型 線(xiàn)性（正規(guī)、正則）文法3型2型1型0型編譯原理2、 文法和語(yǔ)言 （5）形式語(yǔ)言分類(lèi)(chomsky,1953、 詞法分析與有限自動(dòng)機(jī) （1）基本概念狀態(tài)等價(jià)、DFA的化簡(jiǎn)（2）詞法分析器的任

4、務(wù)及其輸出形式任務(wù)：自左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，按語(yǔ)言的構(gòu)詞規(guī)則識(shí)別出一個(gè)個(gè)單詞，把作為字符串的源程序改造為單詞符號(hào)串的中間程序。輸出形式：二元式 （ 單詞種別， 單詞符號(hào)的屬性值）（3）單詞符號(hào)的種類(lèi)關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符編譯原理3、 詞法分析與有限自動(dòng)機(jī) （1）基本概念編譯原理3、 詞法分析與有限自動(dòng)機(jī) （4）正規(guī)文法、正規(guī)式、有限自動(dòng)機(jī)之間的相互等價(jià)性定理（5）正規(guī)式 NFA DFA 最小化DFA（注意：狀態(tài)函數(shù)定義不完整之情形）（6）狀態(tài)轉(zhuǎn)換圖的構(gòu)造(標(biāo)識(shí)符、整數(shù))編譯原理3、 詞法分析與有限自動(dòng)機(jī) （4）正規(guī)文法、正規(guī)式、有限自動(dòng)4、 自上而下語(yǔ)法分析方法 （1）

5、語(yǔ)法分析的方法根據(jù)語(yǔ)法分析樹(shù)建立方向的不同，將語(yǔ)法分析分成兩類(lèi)：自上而下語(yǔ)法分析方法和自下而上語(yǔ)法分析方法。（2）自上而下分析的基本思想窮舉試探法（3）自上而下分析面臨的兩個(gè)最主要的問(wèn)題左遞歸、回溯（4）自上而下分析的基本方法 LL（1）分析法、遞歸下降分析器編譯原理4、 自上而下語(yǔ)法分析方法 （1）語(yǔ)法分析的方法編譯原理4、 自上而下語(yǔ)法分析方法 （5）左遞歸（直接、間接）和回溯的消除直接左遞歸的消除間接左遞歸的消除排序代入及消除左遞歸化簡(jiǎn)編譯原理4、 自上而下語(yǔ)法分析方法 （5）左遞歸（直接、間接）和回溯4、 自上而下語(yǔ)法分析方法 （5）左遞歸（直接、間接）和回溯的消除回溯的消除：提左公因

6、子編譯原理4、 自上而下語(yǔ)法分析方法 （5）左遞歸（直接、間接）和回溯4、 自上而下語(yǔ)法分析方法 （6）LL(1)的含義LL(1)中的第一個(gè)L表示從左至右掃描輸入串，第二個(gè)L表示最左推導(dǎo)，1表示分析時(shí)每一步只需向前查看一個(gè)符號(hào)。（7）LL(1)分析器的組成部分輸入緩沖區(qū)、分析棧、分析表、總控程序（8）LL(1)分析的四種動(dòng)作成功、匹配、推導(dǎo)、報(bào)錯(cuò)編譯原理4、 自上而下語(yǔ)法分析方法 （6）LL(1)的含義編譯原理4、 自上而下語(yǔ)法分析方法 （9）LL(1)文法的判定條件文法不含左遞歸。文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若則 對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首

7、符集包含，則如果一個(gè)文法G滿(mǎn)足以上條件，則稱(chēng)該文法G為L(zhǎng)L(1)文法。編譯原理4、 自上而下語(yǔ)法分析方法 （9）LL(1)文法的判定條件編4、 自上而下語(yǔ)法分析方法 （10）LL(1)分析方法假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號(hào)為a，關(guān)于A的所有產(chǎn)生式為則LL(1)分析算法如下：若 ，則指派 去執(zhí)行匹配任務(wù)。若a不屬于任何一個(gè)候選首符集，則若屬于某個(gè) 且 ，則讓A與自動(dòng)匹配；否則，a的出現(xiàn)是一種語(yǔ)法錯(cuò)誤。根據(jù)LL(1)文法的條件，每一步這樣的工作都是確信無(wú)疑的。編譯原理4、 自上而下語(yǔ)法分析方法 （10）LL(1)分析方法編譯4、 自上而下語(yǔ)法分析方法 （11）FIRST集和FOLLOW

8、集的構(gòu)造（12）預(yù)測(cè)分析表的構(gòu)造編譯原理4、 自上而下語(yǔ)法分析方法 （11）FIRST集和FOLL5、 自下而上語(yǔ)法分析方法 （1）基本概念短語(yǔ)、直接短語(yǔ)、句柄、素短語(yǔ)、最左素短語(yǔ)、算符文法、算符優(yōu)先文法、LR（0）項(xiàng)目、活前綴、可歸前綴（2）自下而上分析的基本思想及其核心基本思想：移進(jìn)-歸約核心問(wèn)題：可歸約串的界定（3）自下而上分析的基本方法算符優(yōu)先分析法：以最左素短語(yǔ)作為可歸約串，非規(guī)范歸約LR分析法：以句柄作為可歸約串，規(guī)范歸約編譯原理5、 自下而上語(yǔ)法分析方法 （1）基本概念編譯原理5、 自下而上語(yǔ)法分析方法 （4）給定一個(gè)文法的句型，找出其短語(yǔ)、直接短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)方法

9、：首先畫(huà)出句型的語(yǔ)法分析樹(shù)，然后根據(jù)語(yǔ)法樹(shù)尋找。每棵子樹(shù)的葉子結(jié)點(diǎn)自左至右排列構(gòu)成一個(gè)相對(duì)于子樹(shù)根的短語(yǔ)。每棵簡(jiǎn)單子樹(shù)（只有父子兩代）的葉子結(jié)點(diǎn)自左至右排列構(gòu)成一個(gè)直接短語(yǔ)。最左簡(jiǎn)單子樹(shù)的葉子結(jié)點(diǎn)自左至右排列構(gòu)成一個(gè)句柄。將所有短語(yǔ)中至少含一個(gè)終結(jié)符的短語(yǔ)，按長(zhǎng)度從小到大排列，長(zhǎng)度最短的認(rèn)定為素短語(yǔ)，然后考察其余長(zhǎng)度較大的，若不包含更小的素短語(yǔ)，則也為素短語(yǔ)。位于句型中最左邊的素短語(yǔ)即為最左素短語(yǔ)。5、 自下而上語(yǔ)法分析方法 （4）給定一個(gè)文法的句型，找出其5、 自下而上語(yǔ)法分析方法 （5）算符文法與算符優(yōu)先文法算符文法：任意產(chǎn)生式右部不含兩個(gè)連續(xù)的非終結(jié)符，（.QR.）算符優(yōu)先文法：算符文法

10、中任意兩個(gè)終結(jié)符之間至多只含“”、“”、“=”三種關(guān)系之一。算符優(yōu)先文法一定是算符文法。算符優(yōu)先關(guān)系是有序的，但不滿(mǎn)足對(duì)稱(chēng)性和傳遞性，即對(duì)于文法G的終結(jié)符a、b和c：如果aa；如果存在a=b和b=c，不一定有b=a或a=c；如果存在ab和bc，也不能得出ac。5、 自下而上語(yǔ)法分析方法 （5）算符文法與算符優(yōu)先文法5、 自下而上語(yǔ)法分析方法 （6）FIRSTVT集與LASTVT集的計(jì)算FIRSTVT規(guī)則一：若有產(chǎn)生式Pa或 PQa，則aFIRSTVT(P)；規(guī)則二：若aFIRSTVT(Q)且有產(chǎn)生式 PQ，則aFIRSTVT(P) ；規(guī)則三：反復(fù)使用以上兩條規(guī)則，直到FIRSTVT(P)不再增

11、大為止。LASTVT規(guī)則一：若有產(chǎn)生式Pa或 PaQ，則aLASTVT(P)；規(guī)則二：若aLASTVT(Q)且有產(chǎn)生式 PQ，則aLASTVT(P) ；規(guī)則三：反復(fù)使用以上兩條規(guī)則，直到LASTVT(P)不再增大為止。5、 自下而上語(yǔ)法分析方法 （6）FIRSTVT集與LAST5、 自下而上語(yǔ)法分析方法 （7）算符優(yōu)先關(guān)系表的構(gòu)造規(guī)則一：對(duì)形如Pab或PaQb的產(chǎn)生式，有a=b；規(guī)則二：對(duì)形如PaR的產(chǎn)生式，若有bFIRSTVT(R)，則ab；規(guī)則四：對(duì)于語(yǔ)句括號(hào)#，有#=#，且若aFIRSTVT(S)和bLASTVT(S)，則有#。5、 自下而上語(yǔ)法分析方法 （7）算符優(yōu)先關(guān)系表的構(gòu)造5、

12、自下而上語(yǔ)法分析方法 （8）優(yōu)先表與優(yōu)先函數(shù)之間的關(guān)系對(duì)應(yīng)一個(gè)優(yōu)先關(guān)系表的優(yōu)先函數(shù)f和g不唯一，只要存在一對(duì)，就存在無(wú)窮多對(duì)。也有許多優(yōu)先關(guān)系表不存在 對(duì)應(yīng)的優(yōu)先函數(shù)。（9）算符優(yōu)先分析算法最左素短語(yǔ)的尋找依據(jù)：5、 自下而上語(yǔ)法分析方法 （8）優(yōu)先表與優(yōu)先函數(shù)之間的關(guān)系5、 自下而上語(yǔ)法分析方法 （9）算符優(yōu)先分析算法算符優(yōu)先分析的特點(diǎn)：算符優(yōu)先分析一般并不等價(jià)于規(guī)范歸約無(wú)法使用單非產(chǎn)生式(如：TF)進(jìn)行歸約。算符優(yōu)先分析比規(guī)范歸約過(guò)程要快，跳過(guò)了所有的單非產(chǎn)生式?？赡軐⒈緛?lái)不是句子的輸入串誤認(rèn)為是句子。（10）LR分析器的基本思想及其組成部分基本思想：記住歷史、展望未來(lái)、定奪現(xiàn)在組成部分：

13、輸入緩沖區(qū)、分析棧（狀態(tài)、符號(hào)）、分析表（動(dòng)作、轉(zhuǎn)換）、總控程序5、 自下而上語(yǔ)法分析方法 （9）算符優(yōu)先分析算法5、 自下而上語(yǔ)法分析方法 （11）四類(lèi)LR分析表LR分析表是LR分析器的核心，主要有以下幾種分析表：LR(0)表、 SLR(1)表（即簡(jiǎn)單LR表）、LR(1)表（即規(guī)范LR表）、LALR表（即向前LR表）。其中，L代表自左至右掃描輸入串，R代表構(gòu)建最右推導(dǎo)的逆過(guò)程，1代表分析時(shí)每一步至多向前查看一個(gè)符號(hào)，S代表簡(jiǎn)單的。（12）LR分析器的四種動(dòng)作移進(jìn)、歸約、接受、報(bào)錯(cuò)（13）LR分析器的兩種沖突移進(jìn)歸約 沖突 和 歸約歸約 沖突5、 自下而上語(yǔ)法分析方法 （11）四類(lèi)LR分析表5

14、、 自下而上語(yǔ)法分析方法 （14）四類(lèi)不同的項(xiàng)目項(xiàng)目類(lèi)型形 式說(shuō) 明歸約項(xiàng)目A這類(lèi)項(xiàng)目表示句柄恰好包含在棧頂中，即當(dāng)前棧中符號(hào)正好為可歸前綴，應(yīng)按A進(jìn)行歸約。接受項(xiàng)目SS是文法唯一的開(kāi)始符號(hào)。這類(lèi)項(xiàng)目實(shí)際是特殊的歸約項(xiàng)目，即按S進(jìn)行歸約，可直接歸約到文法開(kāi)始符號(hào)，表示分析成功。移進(jìn)項(xiàng)目AaaVT，這類(lèi)項(xiàng)目表示當(dāng)前棧中符號(hào)串為不完全包含句柄的活前綴，為構(gòu)成可歸前綴，需將a移進(jìn)分析棧。待約項(xiàng)目ABBVN，這類(lèi)項(xiàng)目表示當(dāng)前棧中符號(hào)串為不完全包含句柄的活前綴，為構(gòu)成可歸前綴，應(yīng)先把當(dāng)前輸入字符串中的相應(yīng)內(nèi)容先歸約到B。5、 自下而上語(yǔ)法分析方法 （14）四類(lèi)不同的項(xiàng)目項(xiàng)目類(lèi)型形5、 自下而上語(yǔ)法分析方

15、法 （15）四類(lèi)LR分析表的構(gòu)造拓廣文法構(gòu)造LR(0)（LR(0)和SLR分析表）或LR(1)（LR(1)和LALR分析表）項(xiàng)目集規(guī)范簇構(gòu)造相應(yīng)分析表（16）LR文法的特點(diǎn)LR文法肯定是無(wú)二義的，一個(gè)二義文法決不會(huì)是LR文法。LR分析法比預(yù)測(cè)分析法更加一般化。LR(0)文法一定是SLR文法，SLR文法和LALR文法一定是LR(1)文法。5、 自下而上語(yǔ)法分析方法 （15）四類(lèi)LR分析表的構(gòu)造6、 語(yǔ)法制導(dǎo)翻譯和語(yǔ)義分析 （1）基本概念 S屬性文法 、L屬性文法（2）屬性分類(lèi)綜合屬性：用于“自下而上”地傳遞信息。繼承屬性：用于“自上而下”地傳遞信息。終結(jié)符號(hào)只有綜合屬性，由詞法分析器提供。非終結(jié)

16、符既可有綜合屬性也可有繼承屬性，文法開(kāi)始符號(hào)的所有繼承屬性作為屬性計(jì)算前的初始值。（3）語(yǔ)義規(guī)則的表示6、 語(yǔ)法制導(dǎo)翻譯和語(yǔ)義分析 （1）基本概念6、 語(yǔ)法制導(dǎo)翻譯和語(yǔ)義分析 （4）常見(jiàn)的中間代碼的幾種形式后綴式（逆波蘭表示式）圖表示法抽象語(yǔ)法樹(shù)DAG圖三地址代碼四元式三元式間接三元式6、 語(yǔ)法制導(dǎo)翻譯和語(yǔ)義分析 （4）常見(jiàn)的中間代碼的幾種形式6、 語(yǔ)法制導(dǎo)翻譯和語(yǔ)義分析 （5）后綴式（逆波蘭式）的表示把運(yùn)算量（操作數(shù)）寫(xiě)在前面，把運(yùn)算符寫(xiě)在后面（后綴）的一種表達(dá)式表示方法。其歸納定義如下：如果E是一個(gè)變量或常數(shù)，則E的后綴式是E自身。如果E是E1 op E2 形式的表達(dá)式，op是二元操作符，

17、則E的后綴式為E1E2op，其中E1，E2分別是E1和E2的后綴式。若E是（E1）形式的表達(dá)式，則E的后綴式就是E1的后綴式。6、 語(yǔ)法制導(dǎo)翻譯和語(yǔ)義分析 （5）后綴式（逆波蘭式）的表示6、 語(yǔ)法制導(dǎo)翻譯和語(yǔ)義分析 （6）將以下語(yǔ)句翻譯為四元式序列表達(dá)式（算術(shù)及布爾）賦值語(yǔ)句數(shù)組IF語(yǔ)句WHILE語(yǔ)句（7）參數(shù)傳遞的幾種方式傳地址、 傳值、傳名、得結(jié)果6、 語(yǔ)法制導(dǎo)翻譯和語(yǔ)義分析 （6）將以下語(yǔ)句翻譯為四元式序7、 符號(hào)表 （1）符號(hào)表的重要性合理地組織符號(hào)表并選擇好的查表、填表方法是提高編譯程序工作效率的有效辦法。（2）符號(hào)表的基本組成、基本操作組成：一張符號(hào)表的每一項(xiàng)入口包含：名字欄和信息

18、欄 操作：查表、填表、訪(fǎng)表、更新、刪除（3）符號(hào)表的組織方式按照處理對(duì)象的特點(diǎn)，符號(hào)表的組織方式一般可分為直接方式和間接方式。也按標(biāo)識(shí)符的種屬分別建立不同的符號(hào)表。7、 符號(hào)表 （1）符號(hào)表的重要性7、 符號(hào)表 （4）符號(hào)表的構(gòu)造和處理方法符號(hào)表主要有三種構(gòu)造和處理方式：線(xiàn)性表、二叉樹(shù)、雜湊（哈希）。（5）內(nèi)情向量的基本表項(xiàng)在編譯過(guò)程中，碰到數(shù)組的說(shuō)明時(shí)，通常將數(shù)組的有關(guān)信息記錄在一個(gè)內(nèi)情向量表中，這些信息包括：維數(shù)、首地址、各維界差、各維上界、各維下屆、數(shù)組元素類(lèi)型、地址不變量。（6）編程語(yǔ)言中常用的兩條作用域規(guī)則使用前說(shuō)明和塊結(jié)構(gòu)的最近嵌套作用域規(guī)則。7、 符號(hào)表 （4）符號(hào)表的構(gòu)造和處理方法8、 代碼優(yōu)化 （1）基本概念優(yōu)化、基本塊、局部?jī)?yōu)化（2）代碼優(yōu)化遵循的原則 等價(jià)原則、有效原則、合算原則（3）優(yōu)化分類(lèi)根據(jù)編譯階段的不同劃分為：與機(jī)器無(wú)關(guān)的中間代碼優(yōu)化和依賴(lài)于機(jī)器的目標(biāo)代碼優(yōu)化。根據(jù)優(yōu)化對(duì)象所涉及的程序范圍劃分為：局部?jī)?yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。 8、 代碼優(yōu)化 （1）基本概念8、 代碼優(yōu)化 （4）常見(jiàn)的優(yōu)化的幾種方法刪除公共子表達(dá)式、復(fù)寫(xiě)