1、編 譯 原 理 復 習 提 綱注： 為老師劃紅線的標了重點的； 未整理到的會注明“翻書“，或者有相關吐槽點；歡迎使用繼J2EE后，第二彈復習材料；來 , 讓 我 們 一 起 開 心 、快 樂 、 愉 悅 的 復 習 吧 _ 選擇，填空，簡單(概念),綜合(詞法分析、自動機、中間代碼)(四五六章)，例子，課后習題第一章1. 編譯原理=形式語言+編譯技術2. 程序設計語言的定義涉及：語法、語義、語用、語境。 3. 匯編程序：把匯編語言程序翻譯成等價的機器語言程序（機器指令序列） 4. 編譯程序：把高級語言程序翻譯成等價的低級語言程序 5. 程序的翻譯的兩種方式：解釋方式和翻譯方式 解釋執行方式：

2、解釋程序，逐個語句地模擬執行翻譯執行方式： 翻譯程序，把程序設計語言程序翻譯成等價的目標程序6. 計算機程序的編譯過程，一般分為五個階段：詞法分析、語法分析、語義分析及中間代碼生成、代碼優化、目標代碼生成 詞法分析的任務：掃描源程序的字符串，識別出的具有獨立意義的最小語法單位（標識符或無正負號數等） 語法分析是：語法分析讀入詞法分析程序識別出的符號，根據給定的語法規則，識別出各個語法結構。在詞法分析的基礎上的，語法分析不考慮語義。語義分析：是檢查程序語義的正確性，解釋程序結構的含義，語義分析包括檢查變量是否有定義，變量在使用前是否具有值，數值是否溢出等。語法分析完成之后，編譯程序通常就依據語言

3、的語義規則，利用語法制導技術把源程序翻譯成某種中間代碼。所謂中間代碼是一種定義明確、便于處理、獨立于計算機硬件的記號系統，可以認為是一種抽象機的程序代碼優化：是對前一階段產生的中間代碼進行等價變換，以便產生速度快、空間小的目標代碼編譯的最后一個階段是目標代碼生成，其主要任務是把中間代碼翻譯成特定的機器指令或匯編程序7. 編譯劃分成前端和后端。 編譯前端的工作包括詞法分析、語法分析、語義分析。編譯前端只依賴于源程序，獨立于目標計算機。前端進行分析。 編譯后端的工作主要是目標代碼的生成和優化后端進行綜合。獨立于源程序，完全依賴于目標機器和中間代碼。把編譯程序分為前端和后端的優點是：可以優化配置不同

4、的編譯程序組合，實現編譯重用，保持語言與機器的獨立性。8. 編譯程序的分類：1.診斷型編譯程序（找錯） 2.優化型編譯程序（產生空間小速度快） 3.交叉型編譯程序（一些設備上的嵌入式應用軟件一般是在另外類型的計算機上設計和開發，經過編譯、運行、和測試后再經過一次編譯產生出在上述設備上可以運行的目標代碼這類編譯程序稱之為交叉型編譯程序） 4.可變目標型編譯程序Lex是通用的詞法分析生成器，它的輸入是描述單詞結構的正規式，輸出的就是詞法分析程序。9. 預處理器：它是在編譯程序真正開始翻譯源程序之前調用的一個獨立的程序，以便加快和簡化翻譯工作。預處理器可以刪除源程序中的注釋、空格符等與程序無關的部分

5、，執行宏代換等工作。第二章1. 符號，字母表，符號串，符號串的長度計算 P18，子符號串是假定有一個非空符號串，其中的若干個相繼符號組成的部分。 符號串的簡單運算XY ，Xn 2. 符號串集合的概念：若集合A中的一切元素都是某字母表上的符號串，A就為該字母表上的符號串集合。符號串集合的乘積運算，方冪運算，閉包與正閉包的概念 P19，P20 A0 =3. 重寫規則，簡稱規則：一個重寫規則是一個有序對(U,u)。寫作： U:=u 。其中U是一個符號，u是有窮非空符號串。定義2.10 非終結符（Vn）：規則左部出現的符號； 終結符（Vt）：不是非終結符的符號，決不會出現在規則左部。 右部僅是單個非終

6、結符號的規則構成了特殊的一類，稱為單規則。 文法的概念：文法GZ是有窮非空的重寫規則集合，其中Z是識別符號，G是文法名。定義2.11 P23 識別符號.P23 文法的第一個重寫規則的左部符號為識別符號。BNF表示法 P6：描述程序設計語言的形式體系，稱為元語言。“：=”“|”元語言連接符或稱元符號。 直接推導和直接規約，廣義推導廣義規約，P24 ：設G是一文法，如果對于某些符號串x與y，能寫出v=xUy 與 w=wuy，且U:=u是G中的規則，則說符號串v直接推導到或直接產生符號串w，記作v=>w。或者說，w是v的直接推導，w直接規約到v。上述，v、wV+，x、yV*，可以有x=y=，這

7、樣對文法G的任何規則U:=u，有U=>u。總可由左部U直接推導到右部u，或由右部u直接規約到左部U。定義2.13 最左推導，最右推導P624. 句型和句子 P26定義2.16 文法GZ，符號串x是從識別符號Z推導所得的，即Z=>* x xV+，即稱符號串x是該文法G的一個句型。如果一個句型x僅由終結符號所組成，即Z=>* x xVT+，稱該句型x為該文法G的一個句子或一個字。 短語，簡單短語定義2.17 文法GZ，w=xuy是該文法的一個句型，有Z=>*xUy,UVN，且U=>+ u，uV+。則稱u是句型w中相應于U的短語。如果滿足Z=>* xUy，且U=&

8、gt;u，則稱u是句型w中相對于U的簡單短語。 句柄P26，P27一個句型的最左簡單短語稱為該句型的句柄。存在且唯一，特例是僅由識別符號組成的句型。5. 語言的定義 P31定義2.19 文法GZ，由該文法描述的語言用L(GZ)，則L(GZ)=x|Z=>* x，且xVT+。Z=>* x，因而x是文法GZ的一個句型，其次，xVT+，即x全由終結符號所組成。所以x是文法GZ的句子。可見由某文法描述的語言是該文法的一切句子的集合，是所有終結符號串所組成集合的一個真子集，即，L(G)VT+。6. 遞歸，左遞歸P32，消除左遞歸7. 文法的形式化定義36定義定義2.21 Chomsky文法G是

9、一個四元組(VN，VT，P，Z)，其中，VN是非終結符號集，VT是由終結符號組成的字母表，P是有窮非空的重寫規則集，Z是識別符號，ZVN。從0型到3型，限制越來越大。0型文法，短語結構文法型文法，上下文有關文法 CSG 2型文法，上下文無關文法 CFG：高級程序語言。3型文法，正則文法RG：詞法。3型語言類 2型語言類 1型語言類 0型語言類 但四種語言本身之間沒有必然的包含關系 P383型語言的定義 ：3型語言或正則語言所對應的自動機稱為有窮狀態自動機。 P412型語言 下推自動機1型語言 線性界限自動機0型語言 圖靈機8. 文法的壓縮P50， 消去規則左遞歸P51（看例題2.24） （這個

10、絕逼的重要啊小伙伴們）9. 語法分析樹的構造，能根據語法樹來尋找短語，直接短語，句柄。(P66習題2第3條)子樹的末端結點符號串是相對于子樹根的短語。 定理2.710. 文法的二義性問題P60，文法的二義性是不可判定的。 某文法的同一個句子存在兩個不同的語法分析書，則稱該句子是有二義性的。第三章1. 詞法分析的功能 P69：讀入源程序字符串，識別開具有獨立含義的最小語法單位，進行有利于下一階段分析的工作，預加工處理。2. 詞法分析器可以有兩種實現模式：完全融合模式（大多采用）和相對獨立模式。完全獨立方式 P71：詞法分析程序作為單獨一遍來實現，從而把詞法分析與語法分析工作截然分開。這時詞法分析

11、程序讀入整個源程序字符串，把它加工成等價的屬性字形式的符號串，作為下一遍中語法分析程序的輸入。好處：1. 符號語法可用簡單文法描述，建立有效分析技術；2. 獨立研究詞法與語法兩方面的特性；3. 就同一個語言，為每種不同機器編寫一個詞法分析程序；每個詞法分析程序產生相同的符號內部表示形式供該語法分析程序使用即可。3. 有窮狀態自動機的概念，如何從正則文法構造有窮狀態轉換自動機 P72(例3.1) P116習題6第1題4. 如何從有窮狀態轉換自動機構造正則文法P74 (自己翻書，哥累了)5. 正則文法是無二義性的。6. 知道確定有窮狀態自動機DFA五元組（K，M，S，F），五個字母的含義。P757

12、. 非確定有窮狀態自動機NFA， 如何將NFA轉化為DFA P82 （看懂表3-3） P117習題6第6題8. DFA的化簡，P85（例3.7） 習題6第8題 這個也是重點思密達；9. 屬性字由符號類和符號值組成。特定符號類，一個符號類對應一個符號值：關鍵字、括號，運算符。非特定符號類：標示符，無符號整數。符號類識別不同類的符號，符號值識別同類的不同符號 P90 (彩蛋：文檔解鎖密碼是527072163)10. 字符表，符號機內表示對照表，標示符表，無符號整數表各自的定義和作用P93 詞法分析程序的大致思路字符表：列出在源程序中可能出現的一切字符，詞法分析程序輸入源程序字符串掃描字符時查看此表

13、。字符表中的一切字符構成文法的字母表。符號機內表示對照表：給出源程序中可能出現的一切特定符號及相應的機內表示。識別特定符號時查看此表。未查到，識別出不是合法的符號。標識符表：用來登錄源程序中出現的一切標識符。特定的標識符只登錄一次，從而使得在屬性字符號值處無需填入標識符本身。無正負號整數表：識別出無正負號整數時，登錄在無正負號整數表中，以此表的序號作為其屬性字符號值。第四章 語法分析-自頂向下1. 帶回溯的自頂向下分析方法P121 （一般采用最左或者最右推導）2. 無回溯的自頂向下分析方法，必須符合的條件：無左遞歸性，無回溯性。3. 預測分析技術： 消去文法左遞歸P51 （上面有）； 構造fi

14、rst集合和follow集合P138構造預測分析表P139 （自己翻書去！） 輸出計算過程本身 P1344. LL（1）文法的定義 P1405. 語法分析樹建立的方式可以分為自頂向下與自底向上兩大類分析技術。6. 無回溯的自頂向下的分析技術需要文法滿足兩個條件：無回溯和無左遞歸。P125第五章 語法分析-自底向上1. 規范分析：最右推導被稱為規范推導，最左規約被稱為規范規約。 P1452. 分析所需要解決的兩個基本問題：找出要被歸約的短語u；確定歸約到哪個非終結符號U3. 一個符號串的前綴是指該串的任一部分。一個規范句型的前綴若不含句柄之后的任何符號就稱為活前綴4. 基本方法：移入規約法 P1

15、47 四個動作之一：移進、歸約、接受、報錯5. 算符優先分析技術： P150 定義5.2 （你看到這句話時，我已經快扛不住了；） 構造算符優先關系表 P151-154 算符優先識別算法（翻書！）6. LR(k)分析技術 ,要知道其中定義:圓點在產生式最右端的項目稱為可歸約項，如EE+T· ；圓點后面是終結符的項目稱為移進項 ，如EE·+T ； 圓點后面是非終結符的項目稱為待約項 ， 如EE+·T。項，項集，項集的閉包特征有窮狀態機 CFSM. P183。（翻書） CFSM表中無不適定狀態的稱為LR(0) 文法SLR（1）文法：各個簡單向前看k集合互不相交 P191

16、LALR文法：構造LR（1）項，然后合并同心項，生成LALR 規約沖突 P199 （翻書）LR（k）文法。第六章1. 語義分析的基本功能：確定類型；類型檢查；識別含義，作相應的語意處理；其他一些靜態語義檢查。 P2152. 語義分析以語法分析部分的輸出（語法分析樹或其他等價內部中間表示）為輸入，輸出中間表示代碼，甚至目標代碼。 P2153. 語義是上下文相關的4. 語法制導翻譯技術 （翻書 大概P299）5. 抽象語法樹 P297（翻書吧，這個沒節操）6. 逆波蘭式 P300（同上）7. 四元組P306（同上上，碎一地）第七章1. 代碼優化的定義 P348 ，代碼優化進行的是等價變換，為優化進行努力是值得的。2. 基本塊的概念：指程序順序執行的語句序列，其中只有一個入口和一個出口，入口就是其中的第個語句，出口就是其中的最后一個語句。對一個基本塊來說，執行時只從其入口進入，從其出口退出。基本塊可以用源代碼、匯編、指令等表示。對基本塊的優化：合并常量計算，消除公共子表達式，消減計算強度，刪除無用代碼。對循環的優化：循環不變表達式外提，歸納變量刪除，計算強度消減。3. 代碼優化的三個過程：P350 各自的含義控制流分析 > 數據流分析 > 變換控制流分析：識別出循環數據流分析：進行數據流信息的收集；變化：分析中間表示代碼。4. 代碼優化是基于中間表示代碼進行的5