第一章 編譯與鏈接

一、被隱藏了的程序

1、在linux下，用gcc來編譯hello world程式時，假設源代碼檔案名為hello.c

$gcc hello.c
$./a.out
Hello World

上述程序可以分解為4個步驟：
預處理（Prepressing）、編譯（Compilation）、匯編（Assembly）和鏈接（Linking);

補充：實際上 gcc 這個命令只是一些后臺程式的包裝，它會根據不同的引數要求去呼叫 預編譯編譯程式ccl、匯編器 as、聯結器 Id，

2.預編譯

對于hello.c 預編譯的時候，需要用到預編譯器 cpp
第一步預編譯的程序相當于如下命令（-E表示只進行預編譯）：

$gcc -E hello.c -o hello.i
or
$cpp hello.c > hello.i

預編譯程序主要處理那些源代碼檔案中的以"#“開始的預編譯指令，比如”#include"、"#define"等，主要處理規則如下∶

● 將所有的"#define"洗掉，并且展開所有的宏定義，
●處理所有條件預編譯指令，比如"#if"、"#ifdef"、"#elif"、"#else"、"#endif"，
●處理"#include"預編譯指令，將被包含的檔案插入到該預編譯指令的位置，注意，這個程序是遞回進行的，也就是說被包含的檔案可能還包含其他檔案，
● 洗掉所有的注釋"//“和”/* */"，
●添加行號和檔案名標識，比如#2"hello.c"2，以便于編譯時編譯器產生除錯用的行號資訊及用于編譯時產生編譯錯誤或警告時能夠顯示行號，
●保留所有的#pragma 編譯器指令，因為編譯器須要使用它們，
經過預編譯后的.i檔案不包含任何宏定義，因為所有的宏已經被展開，并且包含的檔案也已經被插入到.i 檔案中，所以當我們無法判斷宏定義是否正確或頭檔案包含是否正確時，可以查看預編譯后的檔案來確定問題，

3.編譯

變異程序就是把預處理完成的檔案（hello.i）進行一系列詞法分析，語法分析，語意分析，優化后生成相應的匯編代碼檔案，

 $gcc -S hello.i -o hello.s
 or
 $gcc -S hello.c -o hello.s

現在版本的 GCC 把預編譯和編譯兩個步驟合并成一個步驟，使用一個叫做 ccl 的預編譯編譯程式來完成這兩個步驟，
這個程式位于"/usr/lib/gcc/i486-linux-gnu/4.1/"，我們也可以直接呼叫 ccl 來完成它∶

$ /usr/lib/gcc/i486-linux-gnu/4.1/ccl hello.c

對于C 語言的代碼來說，這個預編譯和編譯的程式是 ccl；對于 C++來說，有對應的程式叫做cclplus;
Objective-C是cclobj；fortran 是 f771；java是 jcl，

所以實際上 gcc 這個命令只是這些后臺程式的包裝，它會根據不同的引數要求去呼叫 預編譯編譯程式ccl、匯編器 as、聯結器 Id，

4、匯編

匯編器是將匯編代碼轉變成機器可以執行的指令，每一個匯編陳述句幾乎都對應一潭訓器指令，匯編的程序只需要根據 匯編指令和機器指令對照表一一翻譯就可以了，匯編程序可以呼叫匯編器 as 來完成：

$as hello.s -o hello.o
or
$gcc -c hello.s -o hello.o 
or
$gcc -c hello.c -o hello.o

5、鏈接

用 ld 才可以產生一個能夠正常運行的 HelloWorld 程式∶

?$ld -static /usr/lib/crt1.o /ugr/lib/crti.o/uar/lib/gcc/i486-1linux-gnu/4.1.3/crtbeginr.o?-
?L/ugr/lib/gcc/i486-1inux-gnu/4.1.3 -L/ugr/lib-L/1ib hello.o--start-group-1gcc -1gcc_eh -
?1c --end-group /usr/lib/gcc/1486-1inux-gnu/4.1.3/crtend.o/ugr/lib/crtn.o

如果把所有的路徑都省略掉，那么上面的命令就是∶

ld -static crt1.o crti.o crtbeginT.o hello.o-start-group -lgcc-lgcc_eh -lc-end-group crtend.o 
crtn. o

二、編譯器擔任的角色

1、編譯器做了什么

編譯程序一般可分為6步：掃描（詞法分析）、語法分析、語意分析、源代碼優化、代碼生成、目標代碼優化，

從現在往下，我們以一個C語言源代碼為例：

array[index] = (index + 4) * (2 + 6);

2、詞法分析

將源代碼輸入到掃描器（Scanner）,掃描器將源代碼的字符分割成一系列 記號（Token），
上面程式包含28個非空字符，產生16個記號，

詞法分析產生的記號一般可以分為如下幾類∶關鍵字、識別符號、字面量（包含數字、字串等）和特殊符號（如加號、等號），
在識別記號的同時，掃描器也完成了其他作業：比如 將識別符號存放到符號表，將數字、字串常量存放到文字表等，以備后面的步驟使用，

有一個叫做 lex 的程式可以實作詞法掃描，它會按照用戶之前描述好的詞法規則將輸入的字串分割成一個個記號，
因為這樣一-個程式的存在，編譯器的開發者就無須為每個編譯器開發一個獨立的詞法掃描器，而是根據需要改變詞法規則就可以了，用戶設立不同的詞法規則，就可以將字串分割成不同的記號

另外對于一些有預處理的語言，比如 C 語言，它的宏替換和檔案包含等作業一般不歸入編譯器的范圍而交給一個獨立的前處理器，

3、語法分析

語法分析是完成了對運算式語法層面的分析，不進行運算式是否有意義的判斷，
語法分析器（Grammar Parser） 對 掃描器已經產生的記號 進行語法分析，采用了 背景關系無關語法（Context-free Grammar） 產生 語法樹（Syntax Tree）.語法樹是以運算式為節點的樹，
上面例子經過語法分析器以后形成的語法樹如圖：

正如前面詞法分析有 lex 一樣，語法分析也有一個現成的工具叫做 yacc（Yet Another Compiler Compiler），

yacc也像 lex 一樣，可以根據用戶給定的語法規則對輸入的記號序列進行決議，從而構建出一棵語法樹，

對于不同的編程語言，編譯器的開發者只須改變語法規則，而無須為每個編譯器撰寫一個語法分析器，所以它又被稱為"編譯器編譯器（Compiler Compiler)"，

4、語意分析

語意分析器（Semantic Analyzer 來完成語意分析，判斷運算式是否有意義，編譯器所能分析的語意是 靜態語意（Static Semantic）,靜態語意就是 在編譯期可以確定的語意；動態語意（Dynamic Semantic 就是只有在運行期才能確定的語意，

靜態語意 通常包括 宣告和型別的匹配，型別的轉換，

• 比如當一個浮點型的運算式賦值給一-個整型的運算式時，其中隱含了一個浮點型到整型轉換的程序，語意分析程序中需要完成這個步驟；
• 比如將一個浮點型賦值給一個指標的時候，語意分析程式會發現這個型別不匹配，編譯器將會報錯，

動態語意一般指在運行期出現的語意相關的問題.

• 比如將 0作為除數是一個運行期語意錯誤，

經過語意分析階段以后，整個語法樹的運算式都被標識了型別，如果有些型別需要做隱式轉換，語意分析程式會在語法樹中插入相應的轉換節點，

5、中間代碼生成

現代的編譯器有著很多層次的優化，在源代碼級別會有一個優化程序，
源代碼級優化器（Source Code Optimizer）會在源代碼級別進行優化，上面（2＋6）這個運算式可以被優化掉，因為它的值在編譯期就可以被確定，

我們看到（2 + 6）這個運算式被優化成8，直接在語法樹上作優化比較困難，所以源代碼優化器往往將整個語法樹轉換成 中間代碼（Intermediate Code），它是語法樹的順序表示，中間代碼已經非常接近目標代碼了，

中間代碼一般跟目標機器和運行時環境是無關的，比如它不包含資料的尺寸、變數地址和暫存器的名字等，

中間代碼有很多種型別，在不同的編譯器中有著不同的形式，比較常見的有：
三地址碼（Three-address Code） 和 P-代碼（P-Code），

最基本的三地址碼是這樣的：x = y op z
這個三地址碼表示將變數 y 和 z 進行 op 操作以后，賦值給x，
這里 op 操作可以是算數運算，比如加減乘除等，也可以是其他任何可以應用到 y 和z的操作，

我們上面的例子中的語法樹可以被翻譯成三地址碼后是這樣的∶

 t1 = 2 ＋6;
 t2 = index + 4;
 t3 = t2 * t1;
 array [index] = t3;

為了使所有的操作都符合三地址碼形式，這里利用了 t1 t2和 t3 臨時變數，

在三地址碼的基礎上進行優化時，優化程式會將 2+6 的結果計算出來，得到t1=8，然后將后面代碼中的t1 替換成數字 8，另外還可以省去一個臨時變數 t3，因為 t2 可以重復利用，經過優化以后的代碼如下∶

t2 = index + 4;
t2 = t2 * 8;
array[index] = t2;

中間代碼使得編譯器可以被分為前端和后端，

編譯器前端負責產生機器無關的中間代碼，編譯器后端將中間代碼轉換成目標機器代碼，

這樣對于一些可以跨平臺的編譯器而言，它們可以針對不同的平臺使用同一個前端和針對不同機器平臺的數個后端，

6、目標代碼生成與優化

目標代碼生成與優化這整個程序都屬于編譯器后端，

編譯器后端主要包括代碼生成器（Code Generator） 和 目標代碼優化器（Target Code Optimizer），

• 代碼生成器將中間代碼 轉換成 目標機器代碼，這個程序十分依賴于目標機器，因為不同的機器有著不同的字長、暫存器、整數資料型別和浮點數資料型別等，

對于上面例子中的中間代碼，代碼生成器可能會生成下面的代碼序列（x86 匯編語言）∶

movl index, %ecx            ; value of index to ecx 
addl $4,  %ecx              ; ecx = ecx + 4 
mull $8,  %ecx              ; ecx = ecx * 8
movl index, %eax            ; value of index to eax
movl %ecx,  array(,eax,4)   ; array[index] = ecx

• 最后 目標代碼優化器對上述的目標代碼進行優化，比如選擇合適的尋址方式、使用位移來代替乘法運算、洗掉多余的指令等，

上面的例子中，乘法由一條相對復雜的基址比例變址尋址（Base Index Scale Addressina） 的 lea指令完成，隨后由一條 mov 指令完成最后的賦值操作，這條 mov 指令的尋址方式與 lea 是一樣的，

movl      index, %edx
leal      32(, %edx, 8),   %eax
movl      %eax, array(, %edx, 4 )

程式定義其他模塊的全域變數和函式在最終運行時的絕對地址都要在最終鏈接的時候才能確定，

所以現代的編譯器可以將一個源代碼檔案編譯成一個未鏈接的目標檔案，然后由聯結器最終將這些目標檔案鏈接起來形成可執行檔案，

三、聯結器年齡比編譯器長

1、原來的生活

在以前人們撰寫程式時，將所有源代碼都寫在同一個檔案中，發展到后來一個程式源代碼的檔案長達數百萬行，以至于人類已經沒有能力維護這個程式了，

原始的鏈接概念遠在高級程式語言發明之前就已經存在了，在最開始的時候，程式員先把一個程式在紙上寫好，當然 當時沒有很高級的語言，用的都是機器語言，甚至連匯編語言都沒有，當程式須要被運行時，程式員人工將他寫的程式寫入到存盤設備上，最原始的存盤設備之一就是紙帶，即在紙帶上打相應的孔，

我們假設有一種跳轉指令，它的高 4 位是 0001，表示這是一條跳轉指令; 低 4位存放的是跳轉目的地的絕對地址，
某個程式的第一條指令就是一條跳轉指令，它的目的地址是第 5 條指令（注意，第 5 條指令的絕對地址是 4），

程式并不是一寫好就水遠不變化的，它可能會經常被修改，
比如我們在第 1條指令之后、第5條指令之前插入了一潭訓多條指令，那么第 5條指令及后面的指令的位置將會相應地往后移動，原先第一條指令的低4 位的數字將需要相應地調整，在這個程序中，程式員需要人工重新計算每個子程式或跳轉的目標地址，當程式修改的時候，這些位置都要重新計算，十分繁瑣又耗時，并且很容易出錯，這種重新計算各個目標的地址程序被叫做重定位（ Relocation），

如果我們有多條紙帶的程式，這些程式之間可能會有類似的跨紙帶之間的跳轉，這種程式經常修改 導致 跳轉目標地址變化 在程式擁有多個模塊的時候更為嚴重，

2、匯編語言與符號

匯編語言使用接近人類的各種符號和標記來幫助記憶，比如指令采用兩個或三個字母的縮寫，記住"jump"比記住 0001XXXX 是跳轉（jump）指令容易得多了;

匯編語言還可以使用符號來標記位置，比如一個符號"divide"表示一個除法子程式的起始地址，比記住 從某個位置開始的 第幾條指令 是除法子程式方便得多，
比如前而面紙帶程式中，我們把第5條指令開始的子程式命名為"foo"，那么第一條指今的匯編就是; jmp foo

當然人們可以使用這種符號命名子程式或跳轉目標以后，不管這個 “foo” 之前插入或減少了多少條指令 導致"foo" 目標地址發生了什么變化，匯編器在每次匯編程式的時候會重新計算"foo"這個符號的地址，然后把所有參考到 “foo” 的指今 修正到這個正確的地址，

符號（Symbol）這個概念隨著匯編語言的普及迅速被使用，它用來表示一個地址，這個地址可能是一段子程式（后來發展成函式）的起始地址，也可以是一個變數的起始地址，

3、代碼的模塊化&層次結構組織

后來人們開始將代碼按照功能或性質劃分，分別形成不同的功能模塊，不同的模塊之間按照層次結構或其他結構來組織，

這個在現代的軟體源代碼組織中很常見
在 C 語言中，最小的單位是變數和函式，若干個變數和函陣列成一個模塊，存放在一個"，c"的源代碼檔案里，然后這些源代碼檔案按照目錄結構來組織，
在Java 中，每個類是一個基本的模塊，若干個類模塊組成一個包（Package），若干個包組合成一個程式，

現代的大型軟體往往擁有成千上萬個模塊，這些模塊之間相互依賴又相對獨立，

• 這種按照 層次化 及 模塊化 存盤 和 組織 源代碼 有很多好處，比如代碼更容易閱讀、理解、重用，每個模塊可以單獨開發、編譯、測驗，改變部分代碼不需要編譯整個程式等，

模塊之間如何組合的問題可以歸結為模塊之間如何通信的問題，

最常見的屬于靜態語言的C/C++模塊之間通信有兩種方式，一種是模塊間的函式呼叫，另外一種是模塊間的變數訪問，

• 函式訪向須知道目標函式的地址，變數訪問也須知道目標變數的地址，所以這兩種方式都可以歸結為一種方式，那就是模塊間符號的參考，

四、模塊拼裝——靜態鏈接

人們把每個源代碼模塊獨立地編譯，然后按照須要將它們"組裝"起來，這個組裝模塊的程序就是鏈接(Linking），

鏈接的主要內容就是：把各個模塊之間相互參考的部分都處理好，使得各個模塊之間能夠正確地銜接，

聯結器所要做的作業 其實跟前面所描述的"程式員人工調整地址"本質上沒什么兩樣，只不過現代的高級語言的諸多特性和功能，使得編譯器、聯結器更為復雜，功能更為強大，

從原理上來講，聯結器的作業是：把一些指令對其他符號地址的參考加以修正，

鏈接程序主要包括了地址和空間分配 （Address and Storage Allocation）、符號決議（Symbol Resolution）和重定位（Relocation） 等這些步驟，

符號決議有時候也被叫做符號系結（Symbol Binding ）、名稱系結（Name Binding ）、名稱決議（Name Resolution），甚至還有叫做地址系結（Address Binding ）、指令系結（Instruction Binding）的，大體上它們的意思都一樣，但從細節角度來區分，它們之間還是存在一定區別的，比如"決議"更傾向于靜態鏈接，而**“系結” 更傾向于動態鏈接**，即它們所使用的范圍不一樣，
在靜態鏈接，我們將統一稱為符號決議，

每個模塊的源代碼檔案 （如.c）檔案經過編譯器編譯成目標檔案（Object File，一般擴展名為.o 或.obj），目標檔案（模塊）和庫（Library）一起鏈接形成最終可執行檔案，

最常見的庫就是運行時庫（Runtime Library），它是支持程式運行的基本函式的集合，

庫其實是一組目標檔案的包，就是一些最常用的代碼編澤成目標檔案后打包存放，

五、小結

程式在經過 編譯： 掃描、語法分析、語意分析、源代碼優化、代碼生成和目標代碼優化 之后，源代碼終干被編譯成了目標代碼，但是這個目標代碼中有—個問題是∶ index 和 array 的地址還沒有確定，

如果我們要把目標代碼使用匯編器編譯成真正能夠在機器上執行的指令，那么 index 和 array 的地址應該從哪兒得到呢?

假設index 和 array 和 fun() 定義在 a.c檔案中，在b.c檔案中使用;

• 如果 index 和 array定義在跟上面的源代碼同一個編譯單元里面（定義和使用在同一個檔案里），
  那么編譯器可以為 index 和 array 分配空間，確定它們的地址;

在編譯之后，形成匯編代碼，就已經確定了array和index的地址

• 如果index 和 array是定義在其他的程式模塊（沒有定義在一起，定義和使用不在同一個檔案）呢?

b.c 在編譯的時候并不知道 呼叫的 變數或函式 的地址，所以編譯器暫時 將 呼叫這些變數和函式 的指令 的目標地址 擱置，等待 所有的模塊（檔案）編譯匯編之后，聯結器將目標地址修正

使用聯結器，可以直接參考其他模塊的函式和全域變數而無須知道它們的地址，因為聯結器在鏈接的時候，會根據你所參考的符號 index&array&fun ，自動去相應的a.c 模塊查找 index&array&fun的地址，然后將 b.c 模塊中所有參考到index&array&fun的指令重新修正，讓它們的目標地址為真止的index&array&fun的地址，

這就是靜態鏈接的最基本的程序和作用，

目標代碼中有變數定義在其他模塊，該怎么辦?

事實上，定義在其他模塊的 全域變數和函式 在 最終運行時 的 絕對地址 都要 在 最終鏈接 的時候 才能確定，
所以現代的編譯器可以將一個源代碼檔案編譯成一個未鏈接的目標檔案，然后由聯結器最終將這些目標檔案鏈接起來形成可執行檔案，

在這一章中，我們首先回顧了從程式源代碼到最終可執行檔案的 4個步驟∶預編譯、編譯、匯編、鏈接，
分析了它們的作用及相互之間的聯系，IDE 集成開發工具 和 編譯器 默認的命令 通常將 這些步驟 合并成一步，使得我們通常很少關注這些步驟，

我們還詳細回顧了上面這 4 個步驟中的主要部分，即編譯步驟，介紹了編譯器 將 C 程式源代碼 轉變成 匯編代碼的若干個步驟∶詞法分析、語法分析、語意分析、中間代碼生成、目標代碼生成與優化，

最后我們介紹了鏈接的歷史和靜態鏈接的一系列基本概念∶ 重定位、符號、符號決議、目標檔案、庫、運行庫等概念，