1、1 編譯程序編譯程序是一種翻譯程序，它將高級語言所寫的源程序翻譯成等價的機器語言或匯編語言的目標程序。2 詞法分析（Lexical analysis或Scanning）和詞法分析程序（Lexical analyzer或Scanner）詞法分析階段是編譯過程的第一個階段。這個階段的任務是從左到右一個字符一個字符地讀入源程序，即對構成源程序的字符流進行掃描然后根據構詞規則識別單詞(也稱單詞符號或符號)。詞法分析程序實現這個任務。詞法分析程序可以使用lex等工具自動生成。 3 語法分析（Syntax analysis或Parsing）和語法分析程序（Parser） 語法分析是編譯過程的一個邏輯階段。

2、語法分析的任務是在詞法分析的基礎上將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達式”等等.語法分析程序判斷源程序在結構上是否正確.源程序的結構由上下文無關文法描述.4 語義分析（Syntax analysis）及中間代碼生成語義分析是編譯過程的一個邏輯階段. 語義分析的任務是對結構上正確的源程序進行上下文有關性質的審查, 進行類型審查.例如一個C程序片斷:int arr2,b;b = arr * 10; 源程序的結構是正確的. 語義分析將審查類型并報告錯誤:不能在表達式中使用一個數組變量,賦值語句的右端和左端的類型不匹配.語義分析時，根據語句的含義，可對它進行翻譯，用另一種語言形式

3、（比源語言更接近于目標語言的一種中間代碼或直接用目標語言）來描述這種語義。5 代碼優化代碼優化的任務是對前階段產生的中間代碼進行等價變換或改造，以期獲得更為高效的，即省時間和空間的代碼。6 目標代碼生成目標代碼的生成的任務是將中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。7 遍8 前端（Frontend）和后端（Back end）有時，常常把編譯的過程分為前端(front end)和后端(back end)，前端由那樣一些階段組成：這些階段的工作主要依賴于源語言而與目標機無關。通常這些階段包括詞法分析、語法分析、語義分析和中間代碼生成，某些優化工作也可在前端做，也包

4、括與前端每個階段相關的出錯處理工作和符號表管理工作。 后端工作指那些依賴于目標機而一般不依賴源語言，只與中間代碼有關的那些階段，即目標代碼生成，以及相關出錯處理和符號表操作。編譯程序和解釋程序9 Lex一個詞法分析程序的自動生成工具。它輸入描述構詞規則的一系列正規式,然后構建有窮自動機和這個有窮自動機的一個驅動程序,進而生成一個詞法分析程序.10 Yacc 一個語法分析程序的自動生成工具。它接受語言的文法,構造一個LALR(1)分析程序.因為它采用語法制導翻譯的思想,還可以接受用C語言描述的語義動作,從而構造一個編譯程序.  Yacc 是 Yet another compiler c

5、ompiler的縮寫.11 源語言（Source language）和源程序（Source program）被編譯程序翻譯的程序稱為源程序,書寫該程序的語言稱為源語言.12 目標語言（Object language or Target language）和目標程序（Object program or Target program） 編譯程序翻譯源程序而得到的結果程序稱為目標程序, 書寫該程序的語言稱為目標語言.13 中間語言（中間表示）（Intermediate language(representation)） 在進行了語法分析和語義分析階段的工作之后，有的編譯程序將源程序變成一種內部表示形

6、式，這種內部表示形式叫做中間語言或中間表示或中間代碼。所謂“中間代碼”是一種結構簡單、含義明確的記號系統，這種記號系統復雜性介于源程序語言和機器語言之間，容易將它翻譯成目標代碼。另外，還可以在中間代碼一級進行與機器無關的優化。常見的中間代碼形式有：逆波蘭式、三元式、四元式、樹形表示和三地址代碼。14 文法（Grammars） 文法是用于描述語言的語法結構的形式規則。文法G定義為四元組(VN，V T，P，S)。其中VN為非終結符號(或語法實體，或變量)集；V T為終結符號集；P為產生式(也稱規則)的集合；產生式(規則)是形如或 a :=b 的(a , b)有序對,其中(VNV T)*且至少含有一

7、個非終結符，而(VNV T)*。VN，V T和P是非空有窮集。S稱作識別符號或開始符號，它是一個非終結符，至少要在一條規則中作為左部出現。 一個文法的例子: G=( VN =A，R, P =0,1 ，P =A0R，A01,RA1, S =A) 15 文法分類（A hierarchy of Grammars） 著名語言學家Noam Chomsky定義了四類文法和四種形式語言類，文法的四種類型分別是0型、1型、2型和3型。幾類文法的差別在于對產生式施加不同的限制，分別是： 0型文法(短語結構文法)(phrase structure grammars)： 設G=(VN，V T，P，S)，如果它的每個

8、產生式是這樣一種結構(VNV T)*且至少含有一個非終結符，而(VNV T)*，則G是一個0型文法。 1型文法（上下文有關文法）(context-sensitive grammars)： 設G=(VN，V T，P，S)為一文法|，若P中的每一個產生式均滿足|，僅僅S除外，則文法G是1型或上下文有關的。 2型文法（上下文無關文法）(context-free grammars)： 設G=(VN，V T，P，S)，若P中的每一個產生式滿足：是一非終結符，(VNV T)*則此文法稱為2型的或上下文無關的。 3型文法（正規文法）(regular grammars)： 設G=(VN，V T，P，S)，若P

9、中的每一個產生式的形式都是AaB或Aa，其中A和B都是非終結符，a是終結符，則G是3型文法或正規文法。 0型文法產生的語言稱為0型語言。 1型文法產生的語言稱為1型語言，也稱作上下文有關語言。 2型文法產生的語言稱為2型語言，也稱作上下文無關語言。 3型文法產生的語言稱為3型語言，也稱作正規語言。 16 句型（Sententialform），句子（Sentence）和語言（Language）設GS是一文法，如果符號串x是從識別符號推導出來的，即有Sx，則稱x是文法GS的句型。若x僅由終結符號組成，即Sx，xV T*，則稱x為GS的句子。 文法G所產生的語言定義為集合xSx，其中S為文法識別符號

10、，且xV T*。可用L(G) 或L(GS)表示該集合。 17 推導（Derive）和語法樹（Parse tree） 推導的概念：分別定義V*中的符號之間的關系直接推導、長度為n（n1）的推導和長度為n（n0）的推導： （1）如是文法G=(VN，V T，P，S)的規則（或說是P中的一個產生式），和是V*中的任意符號，若有符號串v，w滿足：              v，w則說v（應用規則）直接產生w，或說，w是v的直接推導，或說，w直接歸約到v，記做vw。 （2）如果存在直接推

11、導的序列： vw0 w1 w2 wnw，（n>0） 則稱v推導出（產生）w（推導長度為n），或稱w歸約到v。記作vw。 （3）若有vw，或vw，則記作。 語法樹（推導樹）的概念：給定文法G=(VN，V T，P，S)，對于G的任何句型都能構造與之關聯的語法樹（推導樹）。這棵樹滿足下列4個條件： 每個結點都有一個標記，此標記是V的一個符號。 根的標記是S。 若一個結點n至少有一個它自己除外的子孫，并且有標記A，則A肯定在VN中。 如果結點n的直接子孫，從左到右的次序是結點n1，n2， ，nk，其標記分別為A1，A2，Ak，那么AA1A2，Ak一定是P中的一個產生式。 18 二義文法（Ambi

12、guous grammer）如果一個文法存在某個句子對應兩棵不同的語法樹，則說這個文法是二義的。或者說，若一個文法中存在某個句子，它有兩個不同的最左(最右)推導，則這個文法是二義的。 19 短語，句柄 (phrase , sentence handle)令G是一文法，S是文法的開始符號，是文法G的一個句型。如果有：且則稱是句型相對與非終結符 A的短語。特別，如有則稱是句型相對于規則A的直接短語 (也稱簡單短語)。一個句型的最左直接短語稱為該句型的句柄。 20 正規式（regular expression）和它所表示的正規集（regular set）設字母表為,輔助字母表 =,，.，*,(,)。

13、1. 和都是上的正規式，它們所表示的正規集分別為和； 2.任何a，a是上的一個正規式，它所表示的正規集為a； 3.假定1和2都是上的正規式，它們所表示的正規集分別為L(1)和L(2)，那么，(1)，12，1·2和2*也都是正規式，它們所表示的正規集分別為L(1)，L(1)L(2)，L(1)L(2)和(L(1) *。4.僅由有限次使用上述三步驟而定義的表達式才是上的正規式，僅由這些正規式所表示的字集才是上的正規集。 21 確定的有窮狀態自動機DFA(deterministic finite automaton)和不確定的有窮狀態自動機NFA(nondeterministic finit

14、e automaton)我們這里是把DFA和NFA作為正規集的識別工具而介紹的。DFA定義如下：一個確定的有窮自動機(DFA)M是一個五元組：M=(K, ，f，S，Z)其中 1.K是一個有窮集，它的每個元素稱為一個狀態；2. 是一個有窮字母表，它的每個元素稱為一個輸入字符,所以也稱為輸入符號字母表;3.f是轉換函數，是在K×K上的映像，即，如f(ki,a)= kj( kiK, kjK)就意味著，當前狀態為ki，輸入字符為a時，將轉換到下一狀態kj，我們把kj稱作ki的一個后繼狀態;4.SK是唯一的一個初態；5.ZK，是一個終態集，終態也稱可接受狀態或結束狀態。NFA定義如下;一個不確

15、定的有窮自動機(NFA)M是一個五元組，M=(K, ，f，S，Z)其中 1.K是一個有窮集，它的每個元素稱為一個狀態；2. 是一個有窮字母表，它的每個元素稱為一個輸入字符； 3. f是一個從K×*到K的子集的映像.4. SK，是一個非空初態集;5. ZK，是一個終態集。 DFA和NFA的等價定理：對于每個NFA M，存在一個DFA M，使得L（M）L（M），即M和M是等價的。 22 最小狀態DFA(reduced DFA or minimum DFA) 我們說一個確定的有窮自動機是化簡了的，即是說，它沒有多余狀態并且它的狀態中沒有兩個是互相等價的，這種DFA也叫做最小狀態DFA。一個

16、DFA可以通過消除多余狀態和合并等價狀態而轉換成一個與之等價的最小狀態DFA。 24FIRST集設G=(VN，V T，P，S)是上下文無關文法 FIRST()=a，aV T，, V *若，則規定FIRST()。 25FOLLOW集設G=(VN，V T，P，S)是上下文無關文法，AVN，是開始符號FOLLOW(A)=a且aV T，aFIRST()，V T*，V + 若，且，則#FOLLOW(A)。也可定義為：FOLLOW(A)=a|Aa,aV T 若有A，則規定#FOLLOW(A) 這里我們用作為輸入串的結束符，或稱為句子括號，如：輸入串。 26SELECT集給定上下文無關文法的產生式A

17、0; AVN，V *，若，則SELECT(A)= FIRST() 如果，則SELECT(A)=FIRST()FOLLOW(A)。 27左遞歸文法（Left recursive grammar） 一個文法含有下列形式的產生式時。 a)AA       AVN，V * b)ABB      A,BVN，、V * 在a)中也可稱為含有左遞歸的規則或稱直接左遞歸，在b)中為A稱文法中含有左遞歸或間接左遞歸，文法中只要含有a)或含有b)或二者皆有均認為文法是左遞歸的。 28LL（1）文法 滿足如

18、下條件的上下文無關文法稱為LL（1）文法：對每個非終結符A的兩個不同產生式， A，A，滿足 SELECT（A）SELECT（A）其中、不同時能。 LL（1）文法的含義是：第一個L表明自頂向下分析是從左向右掃描輸入串，第二個L表明分析過程中將用最左推導，1表明只需向右看一個符號便可決定如何推導即選擇哪個產生式（規則）進行推導，類似也可以有LL（K）文法，也就是需向前查看K個符號才可確定選用哪個產生式。通常采用K1，個別情況采用K2。 29遞歸子程序法（Recursive-descent） 遞歸子程序法是LL（1）文法的分析程序的一種實現方法。它對應文法中每個非終結符編寫一個遞歸過程，這種分析程序

19、由這一系列遞歸過程的相互調用來完成語法分析工作。 30移進歸約分析（shiftreduce analysis） 自底向上分析方法，也稱移進歸約分析法，它的實現思想是對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄時，（該句柄對應某產生式的右部），就用該產生式的左部非終結符代替相應右部的文法符號串，這稱為一步歸約。重復這一過程直到歸約棧中只剩文法的開始符號時則為分析成功，也就確認輸入串是文法的句子。 31算符文法，算符優先文法(Operator Grammar，Operator Precedence Grammar) 設有文法G，若

20、G中沒有形如UVW的規則，其中V和W為非終結符，則稱G是一個算符文法(Operator Grammar)，即OG文法。設有一不含產生式的算法文法G，如果對任意兩個終結符對a，b之間至多只有·、·和三種關系的一種成立，則稱G是一個算符優先文法(Operator Precedence Grammar)，即OPG文法。 32最左素短語（Most left prime phrase） 設有文法GS，其句型的素短語是一個短語 ，它至少包含一個終結符，并除自身外不包含其它素短語，句型的最左邊的素短語稱最左素短語。 33LR分析 是一種自底向上的語法分析技術,通常稱為LR(K).L是說從

21、左至右掃描輸入串,R是說分析過程所形成的推導是最右推導,K是指在做分析決策時向前察看K個輸入符號.LR分析可用于一大類上下文無關文法,是一種最常用的無回朔的移進歸約分析, 一個LR分析器由分析棧、分析表和總控程序3個部分組成。LR分析器總控程序根據LR分析表，執行4種可能的動作：移進、規約、接受（acc）和報錯。34屬性文法（Attribute grammar） 形式上講，一個屬性文法是一個三元組，（，），一個上下文無關文法；一個屬性的有窮集和關于屬性的斷言或謂詞的有窮集。每個屬性與文法的某個非終結符或終結符相聯。每個斷言與文法的某產生式相聯。如果對中的某一輸入串而言（句子），中的所有斷言對該

22、輸入串的語法樹結點的屬性全為真，則該串也是語言中的句子。編譯程序的靜態語義審查工作就是驗證關于所編譯的程序的斷言是否全部為真。屬性分為兩類：綜合屬性和繼承屬性。35語法制導翻譯（Syntax-directed translation） 在語法分析過程中，隨著分析的步步進展，根據每個產生式所對應的語義子程序（或語義規則描述的語義動作）進行翻譯的辦法稱作語法制導翻譯。 36數組內情向量（array dope vector） 一般編譯程序對數組說明的處理是把數組的有關信息匯集在一個叫做“內情向量”或“信息向量”的表格中，以便以后計算數組元素的地址時引用這些信息。每個數組有一個內情向量。其中的信息包括

23、，數組的類型，維數，各維的上、下界，以及數組的首地址。編譯程序處理數組說明的主要工作是把內情向量登錄在符號表中，這些屬性信息是確定存儲分配時數組所占空間的大小和數組元素位置的依據。 37符號表（symbol table）在編譯程序中符號表用來存放源程序中出現的有關標識符的屬性信息，這些信息集中反映了標識符的語義特征屬性,為進行上下文語義審查和進一步的翻譯使用。 編譯程序處理標識符時主要涉及兩部分內容，其一是標識符本身，其二是標識符相關的信息。符號表上有三種操作：填入、查找和更新。符號表的查找方法有順序查找、二分查找和散列（雜湊）查找法。38運行時的環境及存儲空間所謂運行時的環境是指目標計算機的

24、寄存器和存儲器的結構，以及用來管理存儲器并保存執行過程所需要的信息。存儲空間包括用戶定義的各種類型的數據對象所需要的存儲空間、調用過程所需要的連接單元和組織輸入/輸出所需要的緩沖區及保留中間接過和傳遞參數所需要的臨時單元。存儲空間通常被劃分為：目標區、靜態數據區、棧區和堆區。39靜態存儲分配（Static storage allocation）如果在編譯時能確定目標程序運行中所需的全部數據空間的大小，編譯時安排好目標程序運行時的全部數據空間，確定每個數據對象的存儲位置，稱這種分配策略為靜態存儲分配。40動態存儲分配（Dynamic storage allocation）如果一個程序設計語言允許

25、遞歸過程、可變數組或允許用戶自由申請和釋放空間，那么，就需要采用動態存儲管理技術。因為對于這種程序在編譯時無法知道它在運行時需要多大的存儲空間，它所需要的數據空間的大小需待程序運行時動態地確定。有兩種動態存儲分配方式：棧式（stack）和堆式（heap）。41四元式(quadruples) 四元式是一種中間代碼的形式,是一個有四個域的紀錄結構: 四個域分別稱為 op,arg1,arg2 和 result 即操作符,運算對象1, 運算對象2 和運算結果.一個例子:( + ,a, b, c) 42Display表 為能存取非局部變量而紀錄外包過程的活動記錄地址的數組。即每進入一個過程后，在建立它的

26、活動記錄的同時建立一張嵌套層次顯示表display。這里所提到的“嵌套層次”，是指過程定義的層數，始終假定主程序的層數為0，因此主程序稱為0層過程。如某過程p是在層次為i的過程q內定義的，并且q是包圍p的直接外層，那么p的過程層數為i+1。display是一個指針數組d，也可看做是一個小棧，自頂向下每個單元依次存放著現行層，直接外層，直至最外層（0層，主程序層）等每一層過程的最新活動記錄的地址。 43活前綴(viable prefixes) 和拓廣文法若是文法G中的一個規范推導。如果符號串是的前綴，則稱是G的一個活前綴。也就是說是規范句型的前綴，但它的右端不超過該句型句柄的末端。這里S為對原文

27、法G加了產生式S，S為原文法G的開始符號，S為拓廣后文法G的開始符號。 44LR(0)項目和LR(0)項目集規范族(LR(0)items and canonical collection of sets of LR(0) items)文法G的產生式的右部適當位置添加有一個圓點則稱為一個LR(0)項目。根據小圓點的位置和圓點后是終結符還是非終結符，將一個文法的全部LR(0)項目分為四類：歸約項目、移進項目、待約項目和接受項目。根據圓點所在的位置和圓點后是終結符還是非終結符把項目分為以下幾種：移進項目，形如 A a ab，其中a，b(VNV T)*待約項目，形如 A a Bb，其中a，b(VNV

28、T)*歸約項目，形如 A a ，其中a(VNV T)*接受項目，形如 S S 構成識別一個文法活前綴的DFA項目集(狀態)的全體稱為這個文法的LR(0)項目集規范族。45同心集所謂同心的LR(1)項目集是指在兩個LR(1)項目集中，除搜索符不同之外，核心部分是相同的。46代碼優化（Code Optimization）所謂代碼優化，實質上是對代碼進行等價變換，使得變換后的代碼運行結果與變換前代碼運行結果相同，而運行速度加大或占用存儲空間少，或兩者都有。 代碼優化通常分為兩大類：與機器相關的優化和與機器無關的優化。與機器無關的優化，常見的優化技術：刪除公共子表達式（刪除多余運算）、代碼外提、強度削

29、弱、變換循環控制條件（刪除歸納變量）、合并已知量、復寫傳播和刪除無用賦值。依據優化所涉及的范圍分為：局部優化、循環優化和全局優化。47基本塊（Basic block）和DAG 所謂基本塊，是指程序中一順序執行的語句序列，其中只有一個入口語句和一個出口語句。執行時只能從其入口語句進入，從其出口語句退出。如果有向圖中任一通路都不是環路，則稱該有向圖為無環路有向圖，簡稱。基本塊的DAG表示可用于代碼優化。 在一個基本塊內，可以執行三種優化：刪除多余運算、合并已知量、刪除無用賦值。48控制流程圖（流圖）（Control flow graph）一個控制流程圖就是具有唯一首結點的有向圖。所謂首結點，就是從

30、它開始到控制流程圖中任何結點都有一條通路的結點。 我們可以把一個控制流程圖表示成一個三元組（，），其中，代表圖中所有結點集，代表圖中所有有向邊集，代表首結點。控制流程圖簡稱為流圖。 49循環（Loop） 在程序流圖中，稱具有下列性質的結點序列為一個循環： 它們是強連通的。也即，其中任意兩個結點之間，必有一條通路，而且該通路上各結 點都屬于該結點序列。如果序列只包含一個結點，則必有一有向邊從該結點引到其自身。 它們中間有且只有一個是入口結點。因此，我們定義的循環就是程序流圖中具有唯一入口結點的強連通子圖，從循環外要進入循 環，必須首先經過循環的入口結點。所謂入口結點，是指序列中具有下述性質的結點

31、：從序列外某結點，有一有向邊引到它，或者它就是程序流圖的首結點。 50必經結點（dominators）和必經結點集（dominators set）在程序流圖中，對任意兩個結點m和n，如果從流圖的首結點出發，到達n的任一通路都要經過m，則稱m是n的必經結點，記為m DOM n。流圖中結點的所有必經結點的集合，稱為結點n的必經結點集，記為D（n）。51回邊（back edge）假設ab是流圖中的一條有向邊，如果b DOM a，則稱ab是流圖中的一條回邊。52T型圖（T diagram） 一個編譯程序涉及到三個方面的語言，即源語言、目標語言和編譯程序的書寫語言。為了描述方便通常用T型圖來表示一個編譯程序所涉及到的這三個方面的語言。T型圖的左上角表示源語言，右上角表示目標語言，底部表示書寫語言(實現語言)。 53自展（bootstrap）自展的思想是先用目標機的匯編語言或機器語言書寫源語言的一個子集的編譯程序，然后再用這個子集作為書寫語言，實現源語言的編譯程序，如果把這個過程根據情況分成若干步，像滾雪