第一章 引論
1.1什麼叫編譯程序
1.1.1程序設計語言的發展
機器語言、彙編語言、高級語言
隨着計算機應用需求的不斷增長，人們希望能有功能更強、抽象級別更高的語言來支持程序設計，於是就產生了面向各類應用的程序設計語言。這些語言的共同特徵是便於人類的理解與使用，因此被稱爲面向人類的語言或高級語言。表1.1列出了幾種面向機器和麪向人類的語言及其表現形式。
表1.1 面向機器和麪向人類語言舉例
1．通用程序設計語言
通用程序設計語言是繼彙編語言之後發展起來的應用最廣的一類語言，如人們常用的FORTRAN、Pascal、C/C++、Ada83/Ada95、Java等語言。這類語言的特徵是：語言結構符合人類的思維特徵，如直接使用表達式進行數學運算；具有很高抽象程度，如引入過程與類等機制；程序設計中強調邏輯過程，即程序員要考慮事情的前因後果，不但要設計做什麼，還要考慮怎麼做，如條件或循環的判斷等。
2．數據查詢語言
與通用程序設計語言相比，數據查詢語言的抽象程度更高，它只要求程序員具有清晰的邏輯思維能力，設計好做什麼，而忽略怎麼做這樣的實現細節，從而使得對大量複雜數據的處理變得輕鬆簡單。
3．形式化描述語言
形式化描述語言的代表之一是編譯器構造中常用的工具YACC的語言。這類語言的核心部分是基於數學基礎的產生式，設計人員只需利用產生式描述語言結構的文法，就可以構造出識別該語言結構的識別器。
4．其他面向特定應用領域的語言
隨着計算機應用領域的不斷拓展，先後出現了多種面向特定應用領域的高級語言，如面向互聯網應用的HTML、XML，面向計算機輔助設計的MATLAB，面向集成電路設計的VHDL、Verilog，面向虛擬現實的VRML等等。這些形形色色、多不勝數的計算機語言推動了計算機應用的飛速發展，使得計算機成爲人類生活中不可缺少的重要部分。
1.1.2 語言之間的翻譯
1、「編譯」：將高級語言編寫的程序通過一個翻譯程序的加工，使之轉變爲與其等價的目標語言程序，這種翻譯程序，稱它爲「編譯程序」。
2、編譯系統：編譯程序與運行系統合稱編譯系統
高級語言之間的翻譯，一般被稱爲轉換，如FORTRAN到Ada的轉換等，或者被稱爲預處理，如SQL到C/C++的預處理等。
高級語言可以直接翻譯成機器語言，也可以翻譯成彙編語言，這兩個翻譯過程被稱爲編譯。從彙編語言到機器語言的翻譯被稱爲彙編。
運行編譯程序的計算機稱宿主機，運行編譯程序所產生目標代碼的計算機稱目標機。若一個編譯程序產生不同於其宿主機的機器代碼，則稱它爲交叉編譯程序。上述這些翻譯模式一般被認爲是正向工程。
在一些特定情況下需要逆向工程，如把機器語言翻譯成彙編語言，或者把彙編語言翻譯成高級語言，分別稱它們爲反彙編和反編譯。值得一提的是，反編譯是一件十分困難的事情。
圖1.1 語言之間的翻譯模式
圖1.1給出了一些常見的語言之間的翻譯模式。在圖1.1中，語言分爲三個層次：高級語言、彙編語言、機器語言。設分別有兩個高級語言L1和L2，兩個彙編語言A1和A2，以及兩個機器語言M1和M2。
3、 編譯器與解釋器
編譯器(Compiler)一詞是Grace Murray Hopper在20世紀50年代初提出來的，而被公認爲最早的編譯器是50年代末研製的FORTRAN編譯器。
從用戶的觀點來看，編譯器是一個黑盒子，如圖1.2(a)所示。源程序的翻譯和翻譯後程序的運行是兩個獨立的不同階段。首先是編譯階段，用戶輸入源程序，經過編譯器的處理，生成目標程序。然後是目標程序的運行階段，根據目標程序的要求進行適當的數據輸入，最終得到運行結果。
解釋器採用另一種方式翻譯源程序。它不像編譯器那樣，把源程序的翻譯和目標程序的運行分割開來，而是把翻譯和運行結合在一起進行，翻譯一段源程序，緊接着就執行它。這種方式被稱爲解釋。在計算機應用中，凡是可以採用編譯方式的地方，幾乎都可以採用解釋的方式，圖1.2(b)是一個解釋器的工作模型。
假設有源程序：
read(x); write("x=",x);
則編譯器的輸入是此源程序。目標程序的輸入如果是3，則輸出是x=3。
而對於解釋器，則輸入端既包括上述源程序，又包括3，其輸出同樣是x=3。
可以看出，編譯器的工作相當於在翻譯一本原著，計算機運行編譯後的目標程序，相當於閱讀一本譯著，原著(或原作者)和譯著者並不在場，主角是譯著。
而解釋器的工作相當於在進行同聲翻譯，計算機運行解釋器，相當於我們直接通過翻譯聽外賓講話，外賓和翻譯均需到場，主角是翻譯。
圖1.2 編譯器與解釋器工作方式的對比
解釋器與編譯器的主要區別在於：運行目標程序時的控制權
在解釋器而不在目標程序。
解釋器有以下兩個優點:
(1) 具有較好的動態特性:運行時，由於源程序也參與其中，因此可修改，且可提供較好的出錯診斷，從而爲用戶提供數據對象的類型可以動態改變，並允許用戶對源程序進了交互式的跟蹤調試功能。
(2) 簡單、小巧
http://www.turbozv.com/read.php?511.1.3基本術語
1.源程序(Source program)
2.目標程序(Objectcode)
3.翻譯程序(Translator)
4.彙編程序(Assembler)
5.編譯程序(Compiler)
6.解釋程序(Interpreter)
1.2、編譯過程概述
編譯過程與外文翻譯類似。
編譯程序的工作過程可劃分五個階段：
1、詞法分析
2、語法分析
3、語義分析和中間代碼生成
4、代碼優化
5、目標代碼生成
1.詞法分析(LexicalAnalysis)：
從左到右一個字符一個字符的讀入源程序，對構成源程序的字符串進行掃描和分解，從而識別出一個個單詞（也稱單詞符號或簡稱符號）
例如某程序片段如下:
var
sum, first, count ：real；
begin
sum ：= first + count * 10 ；
end．
詞法分析階段通過對該程序片段的掃描、分解，將會把組成這段程序的字符識別爲如下單詞序列：
1．保留字 var 2．標識符 sum
3．逗號 ， 4．標識符 first
5．逗號 ， 6．標識符 count
7．冒號 ： 8．保留字 real
9．分號 ； 10．保留字 begin
11．標識符 sum 12．賦值號 ：=
13．標識符 first 14．加號 +
15．標識符 count 16．乘號 *
17．整數 10 18．保留字 end
19．界符 ．
我們用id1，id2和id3分別表示sum,first和count三個標識符的內部形式，那麼分析後，sum：= first + count * 10
可表示爲：id1：= id2 + id3 * 10
2.語法分析(SyntaxAnalysis)：
在詞法分析的基礎上將單詞序列分解成各類語法單位，如「表達式」，「語句」，「分程序」，「程序」 等等，例如，上例中的賦值語句通過語法分析可用以下語法樹(Parsetree)表示出來。
3.語義分析(SyntacticAnalysis)：
語義分析是在語法分析程序確定出語法單位後，審查有無語義錯誤，併爲代碼生成階段收集類型信息。
(1)語法分析和語義分析是以密切合作的方式工作的。
(2) 語義分析的重要工作之一是進行語義檢查,併爲代碼生成收集類型信息(類型檢查、變量是否聲明、類型是否一致、變量是否已有值等)。
4.中間代碼生成：(Generationof intermediate code)
完成語法分析和語義處理工作後，編譯程序將源程序變成一種內部表示形式，這種內部表示形式叫做中間語言或稱中間代碼，它是一種結構簡單、含義明確的記號系統。
例如，四元式的形式爲：
（算符，運算對象1，運算對象2，結果）
對於賦值語句：position：= initial + rate * 60
可以生成如下所示的四元式：
(IntToReal , 60 , — , t1)
( * , id3 , t1 , t2 )
(+ , id2 , t2 , t3)
(:= , t3 , — , id1 )
5.代碼優化(Optimizationof code)：
爲了使生成的目標代碼更爲高效，可以對產生的中間代碼進行變換或進行改造，這就是代碼的優化。
代碼優化工作可以在不同的編譯階段進行，其中對中間代碼的優化尤其重要。
6.代碼生成(Generationof code)：
目標代碼生成階段的任務就是是把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或彙編指令代碼。
對於上面所述源程序：position：=initial+rate*60對應的中間代碼可生成下面的某彙編代碼：
( * , id3 , 60.0 , t1 )
( + , id2 , t1 , id1)
MOVF id3, R2
MULF 60.0, R2
MOVF id2, R1
ADDF R1, R2
MOV R1, id1
目標代碼生成是編譯器的最後一個階段。在生成目標代碼時要考慮以下幾個問題：計算機的系統結構、指令系統、寄存器的分配以及內存的組織等。
編譯器生成的目標程序代碼可以有多種形式。
(1) 彙編語言形式(Assembly Language Format):編譯器生成彙編語言形式的代碼序列。一般來講，生成彙編指令代碼比生成二進制代碼序列在處理上要簡單且易讀，而且，由於彙編語言仍然是符號形式的，所以特別便於實現交叉編譯。它的弱點是編譯之後還要經過一次彙編。
(2)可重定位二進制代碼形式(Relocatable Binary Format):
這實際上是編譯器常採用的一種目標代碼。編譯器生成二進制代碼模塊，模塊內地址以模塊首地址相對尋址，經過鏈接程序進行鏈接。鏈接時還需把程序中所引用的預定義標準例程和其它已編譯過的模塊包括進來，最後形成一個可直接運行的代碼序列。
(3)內存形式(Memory-ImageFormat):
編譯器生成的代碼序列直接被裝入原編譯器所在的位置並被立即執行，也就是編譯後馬上運行。這類形式在英文中也被稱爲Load-and-Go。由於這種形式不生成以文件形式存放在磁盤上的目標代碼，也沒有被鏈接的過程，因而這種形式特別適合初學者或在程序的調試階段使用。它的弱點是運行一次就需要編譯一次。
由於這三種形式各有其它形式無法替代的特點，有些編譯器同時提供這三種或者其中兩種形式，用戶可以根據需要選擇使用。
7.符號表(Symbol Table)
主要應用於以下情況：
收集符號的屬性信息：當分析到標識符的說明部分時，收集有關標識符的屬性，並存於符號表中；
作爲進行語法的合法性檢查的依據：同一個標識符可能在程序的不同地方出現，有關符號的屬性是在不同的情況下收集的，需要檢查標識符在上下文中的一致性和合法性，而符號表正是進行這種檢查的依據；
作爲目標代碼生成階段地址分配的依據：每個變量在目標代碼生成時都需要確定其對應的存儲地址，編譯程序在完成了對變量的地址分配後，將其存於符號表中，可以通過符號表獲取每個變量對應的存儲地址。
8.錯誤檢測(Detectionof Errors)
源程序中常常存在各種各樣的錯誤：即使對一個熟練的程序員來說，也很難做到一次上機就能得到預期的結果。所以，對於源程序錯誤處理的程度，是作爲衡量一個編譯程序良莠的主要標準之一。一個好的編澤程序應將源程序中的錯誤儘可能多地診察出來，如果有可能的話，對錯誤進行適當的校正。這樣就可以使程序員及時發現和改正錯誤，從而減少上機編譯的次數，以節約機時，節省費用；
錯誤檢測處理與符號表管理工作一樣，貫穿整個編譯過程。
二、編譯階段的組合 ——前端和後端
前端(Front-End)——與目標機無關的部分
包括分析部分(詞法、語法、語義分析)、中間代碼生成、與目標己無關的優化以及這部分的符號表管理錯誤處理
後端(Back-End)——與目標機有關部分
包括代碼生成、與目標機有關的優化以及這部分的符號表管理和錯誤處理工作
不同的前端和不同的後端相互配合可以得到不同的編譯器：