從高階語言到機器語言

眾所周知，計算機中執行的指令是由二進位制編碼的0和1組成，最早的程式設計師通過在紙帶上打孔來編寫程式，有孔表示1，無孔表示0，經過光電掃描輸入電腦，這種0和1序列我們稱之為機器語言。

0和1看的人頭都大了，人們厭煩這種複雜且易出錯的編碼方式，進而發明了組合語言，組合語言只是充當一個助記符的作用，但好歹人們不用寫010101010，而是可以用mov、add這種人們一看就知道其含義的符號來書寫程式，久而久之，人們在組合語言的基礎上又發展了高階語言，也就是我們現在看到的各種語言，如C、C++、Python等，不論是物件導向的還是程式導向的，都可以歸結到高階語言。

人們用高階語言來工作、程式設計，但機器只識別機器語言，這中間肯定就存在一個轉換的過程。這個過程平時在我們程式設計序的過程中並不會注意，我們常用的程式設計環境如VS、dev c++、Delphi等這種IDE（整合式開發環境）都為我們封裝好了一切，只要我們點選執行或構建按鈕，源程式就會變成可以在機器上執行的機器程式碼，而這個被忽略的過程就是我們今天的重點。

我們會以C語言的經典程式HelloWorld作為例子，參考《程式設計師的自我修養——連結、裝載和庫》的內容，通過實操為讀者一步步展現這個過程的具體步驟。

在Linux中，當我們使用GCC來編譯該程式時，只需要用最簡單的命令

$ gcc hello.c
$ ./a.out
hello world

事實上，這個過程可以分解為4個步驟，分別是預處理（Preprocess）、編譯（Compilation）、組合（Assembly）和連結（Linking）。順便提一句，轉化為機器程式碼後，當我們執行該程式還涉及到將機器程式碼載入到記憶體中執行的過程，這個過程我們稱之為裝載，但我們本文不進行詳細闡述。

預處理

我們在編寫C和C++程式的時候，經常會用到#號開頭的語句，如#include、#define、#ifdef等語句，這些語句在預處理過程中就發揮著重要作用。

原始檔hello.c和相關的標頭檔案被預編譯器cpp預編譯為一個字尾為.i的檔案

$ gcc -E hello.c -o hello.i

或者

$ cpp hello.c > hello.i

生成結果如下：

我們可以看到，一個本來不到十行的程式，經過預處理後，已經變成了一個863行的程式，說明前處理器向程式中加了許多的內容，我們原先的幾行程式碼也被放在了最後。

預編譯過程主要處理那些原始檔中的以"#"開始的預編譯指令，主要處理規則如下：

• 將所有的#define刪除，並將所有的宏定義進行展開。程式中我們的RET宏被替換為了0。

• 處理所有的條件預編譯指令，比如#ifdef、#elif等。

• 處理#include預編譯指令，將被包含的檔案插入到該預編譯指令的位置。注意，這個過程是遞迴進行的，也就是說被包含的檔案可能還包含其他檔案。

  

  左側為stdio.h的內容，右側為hello.i的內容，可以看到stdio.h檔案的內容經過預處理後直接拷貝到了hello.i檔案中。

• 刪除所有的註釋"//"和"/* */"。hello.c程式中//use macro這條註釋在hello.i中已經消失了。

• 新增行號和檔名標識，比如#2 "hello.c" 2，以便編譯時編譯器產生偵錯用的行號資訊以及用於編譯時產生編譯錯誤或警告時可以顯示行號。

• 保留所有的#pragma編譯器指令，因為編譯器需要使用他們。（比如在vs中我們常用的#pragma warning (disable : 4996)來禁止編譯器產生對使用不安全函數的警告）

記得上過的課上又提到過，由於宏的不規範定義會導致一些錯誤，而預處理後的程式所有宏均被替代，因此可以通過檢視預處理後的.i檔案來判斷宏定義是否正確或標頭檔案包含是否正確。

編譯

編譯過程就是把預處理完的檔案進行一系列詞法分析、語法分析、語意分析及優化後生成相應的組合檔案。

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

上面的組合風格為AT&T的，我們可以加些引數將其轉換為Intel風格的，且去掉cfi宏。

$ gcc -S hello.i -o hello.s -masm=intel -fno-asynchronous-unwind-tables

可以看到.string後面跟著字串"hello world!"，值得注意的是，生成的組合程式碼中函數printf被替換成了puts，這是因為當printf只有一個單一引數時，與puts是十分類似的，於是GCC的優化策略就將其替換以提高效能。

下面我們對編譯過程進行詳細介紹

編譯器實現了從源程式到語意上等價的目標程式的對映，這個對映可以分為兩部分：分析部分和綜合部份。

分析（analysis）部分將源程式分解為多個組成要素，並在這些要素上加上語法結構，然後利用這個結構建立該源程式的一箇中間表示。分析部分還會收集有關源程式的資訊，並把資訊存放在一個稱為符號表（symbol table）的資料結構中，符號表將和中間表示形式一起傳送給綜合部份。

綜合（synthesis）部分根據中間表示和符號表中的資訊來構造使用者期待的目標程式。

分析部分經常被稱為編譯器的前端（front end），它和目標機器無關；而綜合部份稱為後端（back end），與目標機器有關，前端和後端分離導致我們可以更好地開發編譯器，編譯器開發者便不用為每個CPU架構開發一整套編譯器，而是重新編寫後端即可，也不用為每一種高階語言開發一整套編譯器，只需要更改前端即可。

• 詞法分析（lexical analysis）

  讀入組成源程式的字元流，並將它們組織成為有意義的詞素（lexeme）序列，對於每個詞素，詞法分析器產生詞法單元（token）作為輸出。

• 語法分析（syntax analysis）

  使用由詞法分析器生成的各個詞法單元token來建立樹形的中間表示，該中間表示給出了詞法分析產生的詞法單元流的語法結構，一個常用的表示是語法樹（syntax tree），樹中的每個內部節點表示一個運算，而該結點的子節點表示該運算的分量。

  

• 語意分析（semantic analysis）

  語法分析僅僅是完成了對錶示式語法層面的分析，但是它並不瞭解這個語句是否真正有意義，比如C語言裡面兩個指標作乘法運算是沒有意義的，但這個語句在語法上是合法的。編譯器所能分析的語意是靜態語意（Static Sematic），即編譯期間可以確定的語意，與之對應的動態語意（Dynamic Sematic）就是隻有在執行期才能確定的語意。比如將零作為除數是一個執行期語意錯誤。

  語意分析使用語法樹和符號表中的資訊來檢查源程式是否和語言定義的語意一致。它同時也收集型別資訊，並把這些資訊存放在語法樹或符號表中，以便在隨後的中間程式碼生成過程中使用。語意分析的一個重要部分是型別檢查（type checking），編譯器檢查每個運運算元是否具有匹配的運算分量。

• 中間程式碼生成

  根據語意分析的輸出，生成類機器語言的中間表示，比如三地址碼和P-程式碼。三地址碼類似於組合語言的指令組成（但還不是組合語言），每個指令具有三個運算分量，每個運算分量都像一個暫存器。這種中間程式碼一般跟目標機器和執行時環境無關。

  比如a = b + c * （4 + 2）的原始碼最後生成的中間程式碼模樣大概為：

  t0 = 2 + 4
  t1 = id3 * t0
  t2 = id2 + t1
  id1 = t3
  

• 中間程式碼優化

  改進中間程式碼，生成更好的目的碼，比如上面的中間程式碼可以優化為：

  t1 = id3 * 6
  id1 = id2 + t1
  

  中間程式碼使得編譯器可以被分為前端和後端。編譯器前端負責產生機器無關的中間程式碼，編譯器後端將中間程式碼轉換為目的碼。這樣對於一些可以跨平臺的編譯器而言，可以針對不同的平臺使用同一個前端和針對不同機器平臺的後端。

• 目的碼生成

  這個過程非常依賴於目標機器，因為不同的機器有著不同的字長、暫存器等，如果目標語言是x86組合語言，那麼上面的中間程式碼產生的目的碼可能為：

  mov edx, DWORD PTR [ebp - 8]			;[ebp-8]裡面為c的值
  mov eax, edx							;eax = c
  add eax, eax							;eax = 2c
  add eax, edx							;eax = 3c
  add eax, eax							;eax = 6c
  mov edx, eax							;edx = 6c
  mov eax, DWORD PTR [ebp - 12]			;[ebp - 12]裡面為b的值
  add eax, edx							;eax = b + 6c
  

組合

組合過程就是將組合語言轉換為機器語言。由於組合指令是機器指令的助記符，每一個組合語句幾乎都對應一條機器指令，所以組合器的組合過程相對於編譯器來講比較簡單，沒有複雜的語法，也沒有語意，也不需要做指令優化，只是根據組合指令和機器指令的對照表一一翻譯就可以。

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

或者

$ as hello.s -o hello.o

此時的目標檔案hello.o是一個可重定位目標檔案（Relocatable File），如果使用文字編輯器檢視hello.o會看到一堆亂碼，我們需要採用反組合技術檢視hello.o檔案內容

$ objdump -sd hello.o -M intel

由於還未進行連結，目標檔案的符號的虛擬地址無法確定，於是我們看到字串「hello world!」的地址為0x0000，傳給puts函數的引數（即hello world字串的地址）也為00000000，而call puts機器語言中的0xfffffffc（小端）為-4，表示相對PC定址，puts函數的地址為0x1e - 4 = 0x1a，我們可以看到0xfffffffc和之前的0x00000000一樣，存放的並不是puts函數的地址，只是一個臨時的假地址，因為在編譯的時候，編譯器並不知道puts函數的地址，分配地址的事情交給連結器來做。

連結

連結可以分為靜態連結和動態連結兩種，GCC預設使用動態連結，新增編譯選項"-static"即可指定使用靜態連結。，這一階段將目標檔案及其依賴庫進行連結，生成可執行檔案。功能主要包括

• 地址和空間分配（Address and Storage Allocation）

• 符號繫結（Symbol Binding）

• 重定位（Relocation）

  將每一個符號的定義與一個記憶體地址進行關聯，然後修改這些符號的參照，使其指向這個記憶體地址。

$ gcc hello.o -o hello -static

使用objdump反組合檢視hello檔案內容

$ objdump -d hello

（使用書中的這個命令一下子顯示出太多內容，於是我自己使用了objdump -d hello | grep '<main>'檢視了main的地址，然後最後用objdump -d hello | grep '80488'檢視了main函數的反組合程式碼。可以看到此時的push和call中的地址都已經修正到了正確的位置。

此時程式也就可以被載入到記憶體中正常執行了。