編譯原理大復(fù)習(xí)講述

1、編譯原理復(fù)習(xí)2課程內(nèi)容要求（希望）牢固掌握基本概念靈活使用基本方法1. 歸納總結(jié)所學(xué)內(nèi)容（鍛煉提高抽象能力）一、引言二、詞法分析三、語法分析四、語義分析語法制導(dǎo)翻譯生成中間代碼學(xué)習(xí)不能走捷徑，付出多少勞動(dòng)就有多少收獲。掌握正確的學(xué)習(xí)方法，學(xué)會(huì)聯(lián)想與歸納總結(jié)。3第一章 引言 語言的翻譯 不同的翻譯形式：匯編、編譯、轉(zhuǎn)換（預(yù)編譯）、逆向翻譯翻譯方法： 4 編譯器的基本組成 5 編譯器的分析綜合模式 編譯器的掃描遍數(shù)與編譯器的編寫 6第二章 詞法分析 構(gòu)詞規(guī)則與詞法分析： 首先規(guī)定單詞形成的規(guī)則，稱為構(gòu)詞規(guī)則；然后根據(jù)構(gòu)詞規(guī)則識(shí)別輸入序列，稱為詞法分析。 主要內(nèi)容： 記號(hào)、模式與單詞 記號(hào)的說明模式

2、的形式化描述（正規(guī)式與正規(guī)集） 記號(hào)的識(shí)別有限自動(dòng)機(jī) 從正規(guī)式到詞法分析器 詞法分析器的作用：濾掉源程序中的無用成分；處理與具體操作系統(tǒng)或機(jī)器有關(guān)的輸入；識(shí)別記號(hào)并交給語法分析器；調(diào)用符號(hào)表管理器和出錯(cuò)處理器進(jìn)行相關(guān)處理。 7 記號(hào)、模式與單詞 模式（pattern）：規(guī)定單詞識(shí)別的規(guī)則 記號(hào)（token）：按照某模式識(shí)別出的一類單詞（記號(hào)種類） 單詞（lexeme）：被識(shí)別出的字符串本身 詞法分析器的輸出：記號(hào)=記號(hào)種類+記號(hào)屬性 記號(hào)的說明模式的形式化描述 正規(guī)式與正規(guī)集：正規(guī)式與正規(guī)集的定義(基本正規(guī)式、三個(gè)運(yùn)算)正規(guī)式的等價(jià)(描述相同的集合)利用正規(guī)式的等價(jià)對(duì)正規(guī)式進(jìn)行化簡(jiǎn)(正規(guī)式的代

3、數(shù)性質(zhì))用正規(guī)式形式化描述模式：如何用正規(guī)式描述程序設(shè)計(jì)語言中常見的記號(hào)，如標(biāo)識(shí)符、數(shù)字、運(yùn)算符和分隔符等正規(guī)式的簡(jiǎn)化形式以及輔助定義與規(guī)則8 記號(hào)的識(shí)別有限自動(dòng)機(jī)（FA） NFA與DFA的定義：FA = (S, , move, s0, F)；NFA與DFA的表示：定義表示、狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換矩陣；NFA與DFA的關(guān)鍵區(qū)別：NFA的不確定性（當(dāng)前狀態(tài)下，對(duì)同一字符可能有多于一個(gè)的下一狀態(tài)轉(zhuǎn)移）；用NFA識(shí)別輸入序列的弱點(diǎn)：嘗試所有路徑才能確定一個(gè)輸入不被接收、回溯帶來的問題；模擬DFA的算法：用DFA識(shí)別記號(hào)。 從正規(guī)式到詞法分析器 構(gòu)造NFA的Thompson算法(與NFA定義的對(duì)應(yīng)關(guān)系)

4、； 模擬NFA的“并行”算法； 從NFA構(gòu)造DFA子集法：smove(S, a)與-閉包(T)的計(jì)算； DFA的最小化可區(qū)分的概念：所有不可區(qū)分的狀態(tài)看作是一個(gè)狀態(tài)； 靈活運(yùn)用各種方法構(gòu)造DFA(正規(guī)式化簡(jiǎn)、狀態(tài)轉(zhuǎn)換圖等)，特別是手工構(gòu)造和算法構(gòu)造的區(qū)別。10第三章 語法分析 語法分析是編譯器中的重要階段之一，可以認(rèn)為是語法制導(dǎo)翻譯模式編譯器的核心。語法分析也有雙重含義：根據(jù)一定的規(guī)則構(gòu)成語言的各種結(jié)構(gòu)，即語法規(guī)則；根據(jù)語法規(guī)則識(shí)別輸入序列（記號(hào)流）中的語言結(jié)構(gòu)，即語法分析。 語法分析的分析對(duì)象是組成語言的句子，句子具有層次結(jié)構(gòu)的特征，表征該結(jié)構(gòu)的最好方法是樹，從而使得對(duì)語法的分析就有了從根到

5、葉子和從葉子到根兩種分析方法。 主要內(nèi)容 程序設(shè)計(jì)語言與文法 有關(guān)推導(dǎo)的基本概念 自上而下分析 自下而上分析 11 程序設(shè)計(jì)語言與文法 正規(guī)式與正規(guī)文法：正規(guī)式與正規(guī)文法用于描述線性結(jié)構(gòu)，如構(gòu)成句子的記號(hào)(終結(jié)符)；識(shí)別正規(guī)語言的自動(dòng)機(jī)是有限自動(dòng)機(jī)，它們的特征是沒有記憶能力； 上下文無關(guān)文法(CFG=(N, T, S, P)：CFG用于描述層次結(jié)構(gòu)，如構(gòu)成程序的句子；識(shí)別CFL的自動(dòng)機(jī)是下推自動(dòng)機(jī)，它是在有限自動(dòng)機(jī)的基礎(chǔ)上增加了一個(gè)下推棧，從而有了簡(jiǎn)單的記憶能力； 文法的分類：0型、1型、2型和3型文法 詞法分析器與語法分析器：FA與PDA12 有關(guān)推導(dǎo)的基本概念 CFG產(chǎn)生語言的基本方法推導(dǎo)

6、：從文法的開始符號(hào)開始，反復(fù)地用產(chǎn)生式的右部替換句型中的非終結(jié)符。 推導(dǎo)的基本概念：句子、直接推導(dǎo)、最左推導(dǎo)、左句型（最右推導(dǎo)、右句型）； 分析樹與語法樹：分析樹和語法樹都反映了語言結(jié)構(gòu)；分析樹還記錄了分析的過程（含有非終結(jié)符）； 文法的二義性：二義性的本質(zhì)是在文法中缺少對(duì)文法符號(hào)優(yōu)先級(jí)和結(jié)合性的限制，從而使得一個(gè)句子可以推導(dǎo)出多于一棵分析樹。 二義性的消除：改寫二義文法為非二義文法； 對(duì)文法符號(hào)施加優(yōu)先級(jí)與結(jié)合性的限制，使得分析的每一步有唯一選擇。 13 自上而下分析 分析方法：推導(dǎo)，從上到下構(gòu)造分析樹，是一種預(yù)測(cè)的、試探的方法； 對(duì)文法的要求：沒有公共左因子和左遞歸； 遞歸下降子程序方法：

7、匹配終結(jié)符，展開非終結(jié)符（子程序調(diào)用） 預(yù)測(cè)分析表方法: 工作方式與過程：PDA（DPDA）、格局與改變格局的動(dòng)作； 預(yù)測(cè)分析表的構(gòu)造：FIRST集合與FOLLOW集合， FIRST與FOLLOW的計(jì)算； LL(1)文法及其判別：預(yù)測(cè)分析表中沒有多重定義條目（推論3.2）。14 自下而上分析 分析方法：歸約(推導(dǎo)的逆過程)，從葉子到根構(gòu)造分析樹；基本概念：短語、直接短語、句柄、歸約、規(guī)范歸約； 采用的方法: 用移進(jìn)-歸約方法實(shí)現(xiàn)剪句柄（格局中的兩個(gè)關(guān)鍵動(dòng)作），關(guān)鍵問題是如何確定棧頂已經(jīng)形成句柄，當(dāng)句柄形成時(shí)，如何判定采用哪個(gè)產(chǎn)生式進(jìn)行規(guī)約；識(shí)別活前綴的DFA：活前綴與LR(0)項(xiàng)目(NFA狀態(tài)

8、)，拓廣文法與子集法構(gòu)造DFA；一個(gè)產(chǎn)生式是一個(gè)識(shí)別活前綴的NFA一個(gè)LR(0)項(xiàng)目是NFA的一個(gè)狀態(tài)15 自下而上分析（續(xù)）DFA分析輸入序列：有效項(xiàng)目、可移進(jìn)項(xiàng)目、可規(guī)約項(xiàng)目、移進(jìn)/歸約沖突、歸約/歸約沖突；解決沖突的方法SLR(1)：簡(jiǎn)單向前看一個(gè)終結(jié)符（計(jì)算歸約項(xiàng)非終結(jié)符的FOLLOW，與可移進(jìn)終結(jié)符比較）； 移進(jìn)-歸約分析表：動(dòng)作表轉(zhuǎn)移表； LR文法與LR分析：LR(0)、SLR(1)、LALR(1)、LR(1)。習(xí)題與試題（略過語法制導(dǎo)翻譯）16第四章 語法制導(dǎo)翻譯生成中間代碼 本章討論程序設(shè)計(jì)語言的靜態(tài)語義分析，并且在語法分析的基礎(chǔ)上生成中間代碼，采用的基本方法是語法制導(dǎo)翻譯。

9、與前兩章詞法分析和語法分析不同的是，詞法分析和語法分析的討論側(cè)重于理論，而本章則側(cè)重于結(jié)合程序設(shè)計(jì)語言的實(shí)際例子討論語言結(jié)構(gòu)的具體翻譯方法和一些實(shí)用的技術(shù)。主要內(nèi)容 語法制導(dǎo)翻譯與中間代碼 符號(hào)表的組織 聲明語句的翻譯 可執(zhí)行語句的翻譯 17 語法制導(dǎo)翻譯與中間代碼語法與語義：語法和語義描述語言的不同方面、二者之間沒有嚴(yán)格界線、語義形式化描述的困難性； 屬性：用屬性表示語義特征（語義值），屬性的計(jì)算和屬性之間的依賴關(guān)系；語法制導(dǎo)翻譯：為產(chǎn)生式配上“語義規(guī)則”并在適當(dāng)?shù)臅r(shí)刻執(zhí)行；語義規(guī)則的兩種形式；分析方法與翻譯方案：以語法分析為基礎(chǔ)，分析樹的作用；中間代碼：為什么生成中間代碼，中間代碼的特征，

10、各種形式的中間代碼及它們之間的關(guān)系，最常用中間代碼形式。 18 聲明語句的翻譯定義與聲明：類型定義與變量聲明，過程定義與過程聲明 變量聲明：符號(hào)表信息的填寫過程聲明：左值與右值參數(shù)傳遞：參數(shù)傳遞的不同形式名字的作用域：靜態(tài)作用域與最近嵌套原則1. 聲明中作用域信息的保存符號(hào)表的條目與信息的存儲(chǔ)（關(guān)鍵字內(nèi)容）作用域信息的保存（棧結(jié)構(gòu)）線性表與散列表 符號(hào)表的組織19 可執(zhí)行語句的翻譯 簡(jiǎn)單算術(shù)表達(dá)式和賦值句的翻譯：語法制導(dǎo)翻譯的設(shè)計(jì)，類型轉(zhuǎn)換； 數(shù)組元素的引用：數(shù)組元素地址計(jì)算的遞推公式，地址的可變部分與不變部分，可變部分計(jì)算的語法制導(dǎo)翻譯； 布爾表達(dá)式短路計(jì)算的翻譯：為什么需要短路計(jì)算，短路計(jì)

11、算的控制流，真出口與假出口，真值鏈與假值鏈； 控制語句的翻譯：控制語句的分類，無條件轉(zhuǎn)移與條件轉(zhuǎn)移，拉鏈/回填技術(shù)； 習(xí)題與試題認(rèn)真復(fù)習(xí)，重點(diǎn)是掌握基本概念。基本概念掌握了，相當(dāng)一部分試題的解就有了。習(xí)題與試題的目的區(qū)別：習(xí)題的目的是通過反復(fù)的練習(xí)理解、掌握所學(xué)知識(shí)，會(huì)有不少繁、難、大量步驟的題；試題的目的是考察對(duì)本課程綜合掌握的情況，特點(diǎn)是短時(shí)間內(nèi)覆蓋大量?jī)?nèi)容。太繁瑣步驟或太難等需要耗費(fèi)大量時(shí)間的題是不可能出的，大部分應(yīng)該是基本概念題，但也會(huì)有一些綜合性的題目。自己要會(huì)辨別什么是主要的什么是次要的，抓什么丟什么?！盎靖拍钜獓?yán)謹(jǐn)（清楚），基本方法要靈活”?？傊痪湓?，學(xué)習(xí)方法的掌握是個(gè)人努力

12、的結(jié)果，單純靠別人教是學(xué)不會(huì)的。21關(guān)于考試 題目類型：選擇題、簡(jiǎn)答題、填空題、判斷題、計(jì)算題 考試范圍：15章講過的內(nèi)容 側(cè)重考察：基本概念與基本方法的掌握易犯的錯(cuò)誤不認(rèn)真審題（對(duì)題目的要求理解錯(cuò)誤：意思理解錯(cuò)、難題想容易、容易題想難。關(guān)鍵問題是基本概念不清楚）所答非所問(例如：沒有要求LL分析卻將文法改為L(zhǎng)L的)畫蛇添足(例如：僅問有無沖突卻將分析表先構(gòu)造出來)1. 偷工減料(例如：有若干問，僅回答部分或問題僅答一半)警示千萬不要作弊！命運(yùn)掌握在自己的手中！實(shí)際試題舉例一、簡(jiǎn)答題1 1（2分）有哪些方法可以去除文法的二義性。2 2（2分）寫出 -(a+b)*c)+d 的后綴式。3（4分）試

13、證明正規(guī)式(ab)*a與a(ba)*是等價(jià)的。1 1 （1）改寫文法 （2）規(guī)定文法符號(hào)的優(yōu)先級(jí)和結(jié)合性2 2 ab+c*d+（或ab+c*-d+）3 3 證明： 考慮L(ab)*a)中的任意一個(gè)串a(chǎn)babab.aba， 由串連接的結(jié)合性可得：a(ba)(ba)(b.a)(ba)，它恰好是L(a(ba)*)，即L(ab)*a)= L(a(ba)*)。 也可以用歸納法證明（提示：以ab重復(fù)0次、1次作為歸納基礎(chǔ)，假設(shè)ab重復(fù)n次成立，證明ab重復(fù)n+1次也成立）。二、填空題1（6分）編譯程序的基本組成有：詞法分析、 、 、中間代碼生成、 、 、 和 。2（1分）正規(guī)式r和s等價(jià)說明 相同。3（2

14、分）不含子串baa的所有a、b符號(hào)串的正規(guī)式是 。4（4分） 已知文法G定義如下： SeT|RT TDR| RdR| Da|bd則FIRST(S)= ，F(xiàn)IRST(D)= ，F(xiàn)IRST(T)= ，F(xiàn)IRST(R)= 。 1 語法分析、語義分析、代碼優(yōu)化、目標(biāo)代碼生成、符號(hào)表管理和出錯(cuò)處理 2 r和s表示的正規(guī)集 3 a*(b|ba)* 4 FIRST(S)= e，d，a，b ，F(xiàn)IRST(D)= a，b ，F(xiàn)IRST(T)= ，a，b ，F(xiàn)IRST(R)= d， 。三、計(jì)算題（1）1（13分）已知一個(gè)NFA如圖。 (a)(4分) 用自然語言簡(jiǎn)要敘述該自動(dòng)機(jī)所識(shí)別的語言 的特點(diǎn)，列舉兩個(gè)它可識(shí)別

15、的串。 (b)（3分）寫出與該自動(dòng)機(jī)等價(jià)的正規(guī)式r。 (c)（6分）用子集法構(gòu)造識(shí)別r的最小DFA。012bba,ba,b 解：含有至少兩個(gè)連續(xù)b的a、b串，例如bb、bbb等。r=(a|b)*bb(a|b)*。直接用狀態(tài)轉(zhuǎn)換矩陣構(gòu)造：初態(tài)：0子集法得：（2是終態(tài)）ab000,10,100,1,20,1,2 0,20,1,20,20,20,1,2令： 0=A，0,1=B，0,1,2=C，0,2=D得：abAABBACCDCDDC最小化DFA得：（C和D不可區(qū)分）abAABBACCCC三、計(jì)算題（2）2（15分）有文法G和G的語法制導(dǎo)翻譯如下：EE1*T E.place=newtemp; emi

16、t(*,E1.place,T.place,E.place; | T E.place=T.place; TT1+F T.place=newtemp; emit(+,T1.place,F.place,T.place; | F T.place=F.place; F(E) F.place=E.place; | id F.place=; (a)（4分）求句型(T+F)*id 的短語、直接短語以及句柄；(b)（4分）根據(jù)語法制導(dǎo)翻譯寫出句子a*b+c*d的中間代碼；(c)（3分）若a=3，b=5，c=7，d=8，請(qǐng)給出中間代碼計(jì)算結(jié)果；(d)（4分）將文法G簡(jiǎn)化為：EE*T|T，TT+F|F

17、，F(xiàn)id。給出它的識(shí)別活前綴的DFA。 解：(a) 短語：(T+F)*id、(T+F)、T+F、id 直接短語：T+F、id 句柄：T+F(b) a*b+c*d的中間代碼： (1) (+, b, c, t1)(2) (*, a, t1, t2)(3) (*, t2, d, t3)(c) 計(jì)算結(jié)果：t3=288 (d) 識(shí)別活前綴的DFA： E.EE.E*TE.TT.T+FT.FF.idEE.EE.*TET.TT.+FTF.Fid.EE*.TT.T+FT.FF.idTT+.FF.idEE*T.TT.+FFETFid*+TididI0I1I2I3I4I5I6I7TT+F.I8F28部分習(xí)題解答習(xí)題

18、2.4寫出下述語言的正規(guī)式描述（1） 由偶數(shù)個(gè)0和奇數(shù)個(gè)1構(gòu)成的所有01串（2） 所有不含子串011的01串（3） 每個(gè)a后面至少緊隨兩個(gè)b的ab串（4） C的形如/*/ 的注釋。其中代表不含*/的字符串思路：分析題意，從最簡(jiǎn)單的例子考慮，然后找出統(tǒng)一規(guī)律（1）的解題步驟：1. 最簡(jiǎn)單的符合要求的串：1、010（還有100、001、111等）2. 所有01均為偶數(shù)的串： A=(00|11)|(01|10)(00|11)*(10|01)*3. 符合要求的所有串：A1A、A0A1A0A（為什么沒有后三個(gè)？）結(jié)果：A1A | A0A1A0A（4） C的形如/*/ 的注釋。其中代表不含*/的字符串思路

19、：注釋中若遇到*：若后邊是/則結(jié)束注釋否則仍然是注釋步驟：1. 注釋串是空；2. 考慮沒有*的注釋；3. 考慮含*的注釋結(jié)果：(4) /* (*|*/)* */（2） 所有不含子串011的01串：1*(01|0)*（3） 每個(gè)a后面至少緊隨兩個(gè)b的ab串：(b|abb)*習(xí)題2.10有一NFA的狀態(tài)轉(zhuǎn)換矩陣下表，其中S為初態(tài)，D為終態(tài)abcSA,BC,DDA,B,CAACBBADCCBAADCBS求出它的最小DFA用正規(guī)式描述DFA所接受的語言問題：根據(jù)DFA寫出對(duì)應(yīng)的正規(guī)式，通常的考慮和步驟是什么？ 再重復(fù)一遍： 正規(guī)式、DFA是從兩個(gè)不同的側(cè)面表示一個(gè)集合(即正規(guī)集)。所以，根本的方法是把

20、正規(guī)集作為橋梁，先分析清楚DFA識(shí)別出的是一個(gè)什么集合，然后再設(shè)計(jì)此集合的正規(guī)式。反之亦然。習(xí)題2.10（2）的解 該DFA從初態(tài)到終態(tài)有三條路徑：b|c|a(a|c)*b，而且是這三條路徑的至少一次重復(fù)，故正規(guī)式為：(b|c|a(a|c)*b)+習(xí)題3.7設(shè)計(jì)一文法G，使得L(G)=|是不以0開始的正奇數(shù)思路：首先根據(jù)集合的描述設(shè)計(jì)幾個(gè)句子，然后從句子中找出規(guī)律（或共性），把它們的性質(zhì)用產(chǎn)生式表示出來。解：正規(guī)式：個(gè)位：13579 個(gè)位以上：0-9* 最高位：1-9三段連起來：1-90-9*13579兩種情況： 1-90-9*13579 | 13579產(chǎn)生式：SACB|BA1|2|3|4|5

21、|6|7|8|9B1|3|5|7|9C|0C|AC習(xí)題 3.17對(duì)于文法G3.4和它所產(chǎn)生的句子-id+id*id 和 -(id+id)*idE E+T|TT T*F|F (G3.4)F (E) |-F|id（1）構(gòu)造基于LR(0)項(xiàng)目集的識(shí)別活前綴的DFA（2）指出DFA中所有含有沖突的項(xiàng)目集，并說明這些沖突可以用SLR(1)方法解決；（3）構(gòu)造文法G3.4的SLR(1)分析表（4）用分析表對(duì)句子-id+id*id 和 -(id+id)*id進(jìn)行分析（以格局變化的方式）（5）根據(jù)（4）的分析給出-id+id*id的分析樹和剪句柄的過程解：作為練習(xí)，本題的每一步都是必要的。相對(duì)來說分析表的構(gòu)造

22、并不重要。習(xí)題 3.17（解）（1）構(gòu)造基于LR(0)項(xiàng)目集的識(shí)別活前綴的DFA（2）指出DFA中所有含有沖突的項(xiàng)目集，并說明這些沖突可以用SLR(1)方法解決； 沖突的項(xiàng)目集:I2，I11 計(jì)算FOLLOW(E)，看*是否在其中（略）構(gòu)造SLR（1）分析表的方法：1可移進(jìn)項(xiàng)直接從DFA上看：actionI,a:=sjgotoI,A:=k2可歸約項(xiàng)分兩步走：若在I狀態(tài)中有A.，首先計(jì)算：FOLLOW(A),然后填寫：actionI,b:=Ri其中：bFOLLOW(A)且A是第i個(gè)產(chǎn)生式。 習(xí)題 4.4假定下述程序分別采用值調(diào)用，引用調(diào)用，復(fù)寫-恢復(fù)和換名調(diào)用，請(qǐng)給出它們的打印結(jié)果。 program main(input output); procedure p(x,y,z); begin y:=y+1; z:=z+x end; begin a:=2; b:=3; p(a+b, a, a); print a end;兩種解題的思路：1. 把自己當(dāng)作計(jì)算機(jī)，按照參數(shù)傳遞的實(shí)現(xiàn)方式“運(yùn)行”一遍程序，得出結(jié)果；2. 找臺(tái)機(jī)子把程序敲進(jìn)去試試（輔助手段）困惑的