作者簡介：

程磊，某手機大廠系統開發工程師，閱碼場榮譽總編輯，最大的愛好是鉆研Linux內核基本原理。

• 一、編譯系統的形成與發展

  • 1.1 手工硬件編程

  • 1.2 面向硬件編程

  • 1.3 高級語言編程

  • 1.4 編譯系統的組成

• 二、編譯系統的邏輯結構

  • 2.1 狹義編譯

  • 2.2 最狹義編譯

  • 2.3 鏈接過程

  • 2.4 組建系統

• 三、編譯原理簡介

  • 3.1 詞法分析

  • 3.2 語法分析

  • 3.3 語義分析

  • 3.4 中間碼生成

  • 3.5 中間碼優化

  • 3.6 機器碼生成

  • 3.7 機器碼優化

  • 3.8 小型編譯器推薦

• 四、靜態鏈接與動態鏈接

  • 4.1 靜態鏈接

  • 4.2 動態鏈接

  • 4.3 實例解析

• 五、總結回顧

一、編譯系統的形成與發展

什么是編譯器？為什么要有編譯器？編譯器的作用是什么？編譯系統的組成部分有哪些，它們之間的關系是什么？有一句名言說的非常好：了解一件事情最好從它的歷史開始。要想對整個編譯系統有個全面透徹地理解，我們就必須要先去認真研究它的發展歷史。下面我們就來看一下編譯系統的發展歷史。

1.1 手工硬件編程

最早開始的時候，我們是手工硬件編程，注意是手工硬件編程，不是面向硬件編程。手工硬件編程是程序員直接用手去改變計算機中的跳線連接方式來編程。把所有的跳線連接都改完之后，插上電源，按執行按鈕，計算機就可以執行程序了。很顯然這種編程方式很原始、很low、很麻煩。如果我們有兩個程序A和B，我們執行完A之后想要執行B，就要先把A毀掉之后再把B給手工編到硬件上去才能執行B。下次再需要執行A的時候還需要重新再把A編到硬件上。這是多么的麻煩，于是大神馮諾依曼就提出了一個想法叫做存儲程序設計，就是我們把程序存儲到存儲器上，計算機每次運行的時候都去存儲器讀指令來執行就可以了。存儲程序設計是一個非常偉大的想法，是計算機歷史上發展的一大步。以前當我看到書上對存儲程序設計大加贊賞時，我就非常疑惑不解，存儲程序，還用你說，程序不是本來就存在硬盤上嗎，這不是理所應當的嗎，這有什么好夸獎的。當我們對一個東西習以為常、司空見慣的時候，我們就會覺得這個東西沒什么，但是實際上這個東西的提出或者發明是非常偉大的。就好比我們都站著走路覺得這個沒什么，這不是應該的嗎，本來就是這樣。但是實際上人類直立行走是人從動物進化到人的過程中非常重要的一步，如果沒有直立行走，人類現在說不定還是生活在原始森林里的動物。好，我們接著往下說，有了存儲程序設計，我們就從手工硬件編程進化到了面向硬件編程。

1.2 面向硬件編程

面向硬件編程又分為1.0 二進制編程、2.0 手工匯編編程、3.0 匯編編程三個版本。由于計算機硬件采取的是二進制實現方式，所以1.0版本的面向硬件編程就是二進制編程，就是直接用一堆0110101來編程。計算機為什么要采用二進制的方式來實現而不是采用人類最熟悉的十進制方式或者其他進制方式來實現呢？這里面有多個原因，首先是因為二進制是最簡單的進制，不可能有比二進制更簡單的進制了。二是因為硬件的很多特征正好可以簡單對應到二進制的0和1上，比如高電壓是1，低電壓是0，通路是1，斷路是0，非常方便，便于實現。三是因為邏輯運算布爾代數正好可以對應到二進制0和1上。如果采取3進制、5進制、8進制、10進制，將會面臨著很多的麻煩。采用二進制也存在一個問題，就是人類熟悉10進制，不熟悉2進制，這個問題可以通過在顯示的時候把2進制轉換為10進制來解決，人們用電腦時看到的都會是10進制數，沒有影響。

有了二進制編程，我們就可以直接書寫處理器能直接識別和執行的二進制指令來編程了，比手工硬件編程方便了很多。但是顯然直接書寫一堆0110101的代碼，很違背直覺，很難寫，也很容易出錯。如果不小心把某個0寫成了1，想把這個錯誤找出來都非常困難。于是人們想出了一個方法，我先在草稿紙上用偽代碼編程，比如，加法的指令是10101010，我先用 ADD 來代替。等把程序寫好了，我再一個一個地把 ADD SUB JMP 等這些指令助記符手工轉換成0110，再輸入到電腦上去執行。我們把這種編程方式叫做手工匯編編程，這種編程方式和手工硬件編程、二進制編程相比都有很大的進步，但是依然很麻煩。于是我們就想，把助記符轉換成二進制指令的這個過程，我能不能用程序來實現呢，何必非要自己手工去做呢，于是就有了匯編器程序。我們把二進制指令叫做機器語言，把助記符指令叫做匯編語言，你用匯編語言寫的程序叫做匯編程序，匯編器程序把你寫的匯編程序轉換成二進制程序，然后就可以運行了。匯編器程序也是程序啊，該用什么語言來寫呢，顯然此時只能用二進制編程或者手工匯編編程來寫匯編器程序，我們把這個匯編器叫做盤古匯編器。盤古匯編器的特點是它是手工產生的，不需要匯編或者編譯來生成。盤古匯編器有了之后，就可以對所有的匯編程序進行匯編了，此時我們就進入了匯編編程時代。既然所有的程序都能用匯編語言編寫了，那么我們能不能用匯編語言再寫一個匯編器呢，答案是能，我們把這個匯編器叫做女媧匯編器。我們用盤古匯編器匯編女媧匯編器的源碼，得到二進制的女媧匯編器，然后就可以用二進制的女媧匯編器匯編女媧匯編器的源碼，又得到了新的二進制女媧匯編器。從此我們就可以拋棄盤古匯編器了，實現二進制女媧匯編器和源碼女媧匯編器的雞生蛋、蛋生雞的循環了。我們就可以不斷地改善女媧匯編器的源碼，實現女媧匯編器的進化，并且還可以編譯其他匯編程序。

第一個編譯器是怎么來的？

在此我們提前回答一個問題，編譯器也是程序，也需要被編譯，那么第一個編譯器是怎么來的，是誰編譯的呢。第一個C語言編譯器是用B語言寫的，用B語言編譯器編譯的，有個這個盤古C語言編譯器，我們就可以再用C語言來重新寫一個C語言編譯器了，叫做女媧C語言編譯器。用二進制的C語言盤古編譯器編譯源碼形式的女媧C語言編譯器，就得到了二進制的女媧C語言編譯器，然后二進制的女媧C語言編譯器再去編譯源碼形式的女媧C語言編譯器，就可以實現類似女媧匯編器的循環了。同理你會問那么第一個B語言編譯器是怎么來的呢，第一個B語言編譯器是用BCPL語言書寫的，是用BCPL語言編譯器編譯的。一直這么追問下去，第一個編譯器是怎么實現的呢？第一個編譯器是用匯編語言寫的，匯編器匯編出來的。再往前推，第一個匯編器是手工書寫的二進制代碼。所以編譯器的源頭是我們人類直接用機器語言書寫的盤古匯編器，它不需要編譯也不需要匯編，能直接在機器上運行。

1.3 高級語言編程

面向硬件編程3.0版本–匯編編程，雖然已經很先進了，但它仍然是面向硬件編程啊，程序員仍然需要了解很多的硬件細節，不能專注于程序自身的邏輯。實際上絕大部分程序，它的功能實現都和硬件無關，而且用匯編語言寫的程序不具有跨平臺性，程序員要為每個硬件平臺都寫一份程序或者要移植一下，這非常麻煩。能不能發明一種語言，屏蔽各種硬件細節，只注重于實現程序自身的邏輯，實現源碼級的跨平臺性呢，于是高級語言誕生了。第一個高級語言大概是Algol吧，然后從Algol一路發展到BCPL、B、C、C++、JAVA、C# 等。在高級語言里面沒有各種硬件指令，沒有寄存器，沒有復雜的尋址模式，取而代之的是各種數據類型的數據定義，和對數據的直觀操作，以及if、for、while、switch等控制語句，還有一些更高級的語法構造如類、模板等，都是用接近于人類自然語言的方式來表達的，可讀性非常強。如果想要了解學習一些高級語言，如C和C++，可以參看《深入理解C與C++》。

編譯器的定義：好，說到這里，大家對什么是編譯器心里應該已經很明白了。我們來總結一下，什么是編譯器，編譯器是人類和計算機之間的一個矛盾的產物。這個矛盾就是計算機能夠理解和執行二進制格式的程序卻不能理解和執行文本格式的程序。而人類正好相反，人類能理解和書寫文本格式的程序卻難以理解和書寫二進制格式的程序。于是編譯器出現了，用來幫助人類解決這個矛盾。人類書寫文本格式的程序，編譯器給翻譯成二進制格式的程序，計算機再來執行。

1.4 編譯系統的組成

上面我們把什么是編譯器給解釋清楚了，我們再繼續順著這個思路來解釋一下什么是鏈接、加載和組建。剛開始的時候，程序都很簡單，一個C文件就搞定了，我們可以把一個C文件直接編譯成可執行程序。但是后來隨著程序越來越龐大，再把程序全寫到一個C文件里就不合適了，一個C文件寫幾千行還算合理，但是寫幾萬行，幾十萬行甚至幾百萬行就不合理了。于是我們把程序寫到多個文件里，每個文件單獨編譯，生成中間目標文件，再把這些中間目標文件連接合并成一個可執行程序，這個連接合并過程就叫做鏈接，執行鏈接的程序叫做鏈接器。后來隨著程序的更加復雜龐大，這種鏈接方式也有問題，因為有很多公共程序，你把它們都鏈接到每個程序中，這樣每個程序都自己包含一份庫程序，這會導致浪費大量的磁盤空間，而且運行時也很浪費物理內存，如果一個庫程序更新了，每個可執行程序都要重新鏈接一遍，也很麻煩。為了解決這幾個問題，于是誕生了動態鏈接，于是就把之前的鏈接方式叫做靜態鏈接。我們把一些公共庫程序做成動態鏈接庫，每個可執行程序鏈接到動態庫時只是在程序內部做了一個鏈接記錄，并不會把動態庫復制到可執行程序本身，這樣整個磁盤里面就只有一份這個動態庫。運行時，這個動態庫也只需要加載進物理內存一次，然后分別映射到不同進程的虛擬內存空間中就可以了，這個動作叫做加載。至此我們明白了編譯、鏈接、靜態鏈接、動態鏈接、加載這幾個概念，做編譯的是編譯器，做鏈接的是鏈接器，做加載的是加載器。

下面我們說一說什么是組建，假設我們有個軟件由十幾個文件夾幾百個C文件組成，我們每次想編譯時該怎么做，一個一個地編譯每個C文件，然后再把所有的中間目標文件靜態鏈接、動態鏈接起來生成最終的可執行程序，每次都手工輸入那么多命令是多么麻煩啊。我們該怎么辦，一個最簡單直接的方式是把這些命令都寫到腳本里，后面每次都執行這個腳本就可以了。這個想法很好，也解決了問題，但是還存在問題，就是寫這個腳本比較麻煩，修改這個腳本也比較麻煩。于是就出現了一些可以自動生成這個腳本的方法，你寫一些簡單的配置和規則，然后用一個程序處理這個規則，就可以自動生成這個腳本，再執行這個腳本就可以編譯整個程序了。后來你發現，你的解析程序解析你的規則文件后，直接在內部生成這個腳本執行這個腳本就可以了，沒必要非要把這個腳本顯式地寫出來再去執行，這一套東西就叫做組建系統。組建系統由兩部分組成，解析程序和規則文件。最著名的組建系統就是make了，make由兩部分組成，make程序和Makefile文件。你按照Makefile的要求去書寫Makefile文件，然后執行make命令就可以編譯整個程序了。后來隨著程序的更加龐大和復雜化，Makefile也變得越來越龐大越難以書寫了，于是又產生了元組建系統，來幫你生成Makefile文件。元組建系統也由兩部分組成，解析程序和規則文件，你按照它的要求書寫規則文件，然后執行解析程序生成Makefile，然后再執行make命令編譯整個程序。針對make的比較著名的元組建系統有CMake、autoconf/automake等。由于make運行時需要把每個文件夾下Makefile都include進來，這對于小規模的程序來說還能忍受，但是當程序非常龐大、源碼下的文件夾比較多的時候，這個耗時就難以忍受了，于是人們開發出了ninja組建系統，它運行時只解析一個build文件，運行效率就比較高。不過要手工寫ninja的build文件是很麻煩的，對大型程序來說幾乎是不現實的，所以對ninja組建系統幾乎是必配元組建系統，當只修改源碼內容時可以直接運行ninja命令，但是當程序結構發生變化時必須要先運行一下元組建系統重新生成一下ninja的build文件。

現在我們看到整個編譯系統由3部分組成，編譯、鏈接、組建，執行它們的分別是編譯器、鏈接器、組建系統。我們在命令行編譯一個程序的時候，只需要調用一個組建命令，組建系統就會幫我們自己編譯、鏈接整個程序，還會做一些其他輔助工作如打包、簽名等。有些同學可能會說我從來沒用過什么編譯器、鏈接器、組建系統，我每次編程都是直接寫程序，然后直接按一個按鈕就行了，這個東西就叫做集成開發環境，它把文本編輯器、編譯器、鏈接器、組建系統、調試器都集成在一起了，可以方便大家的開發工作，但也使得很多人都不了解它背后的工作原理。所以說命令行雖然不太好用，但是它的不太好用是指學會用它比較麻煩，但是一旦學會用它，你會發現它非常強大，而且同時你對它背后的原理也理解地比較深刻。

很多時候我們在工作的時候會經常說到編譯這個詞，但是在不同的場景下它的含義是不一樣的。下面我們來進行一下名詞解析，說一下編譯的四種不同含義:

• 最廣義的編譯：就是組建過程，包括編譯、鏈接、打包、簽名等
• 廣義的編譯：包括狹義的編譯和鏈接
• 狹義的編譯：就是單指編譯，把源文件編譯成目標文件的過程
• 最狹義的編譯：就是編譯原理中的編譯，不包括開頭的預處理和最后的匯編過程(如果有的話)。

編譯原理里面講的編譯就是指這個最狹義的編譯，一般是沒有這個匯編過程的，就是直接生成目標文件，如果有匯編過程的則不包括匯編過程，很多編譯器采取的方式是有匯編的過程的。

為什么要在這里做個名詞解析呢，因為在工作和一些討論中會因為大家說的編譯這個詞的含義不同而產生一些說不清的爭論。比如說我們在編譯整個程序的時候，我們只會說編譯這個程序，而不會去說組建這個程序，也不會去說編譯加鏈接加打包這個程序，這樣說會顯得很別扭，所以很多時候會因為編譯的含義不同而產生一些不必要的爭論。例如有一次服務器編譯出錯了，我說編譯出錯了，有一個同事說編譯沒有錯，是打包出錯了。還有一次有個同事編譯出錯了，讓我幫忙看看是怎么回事，我看了之后說編譯過程沒問題，鏈接階段出錯了，找不到符號，他一臉疑惑的說，這編譯不是出錯了嗎。還有些同學不明白編譯原理中的編譯和工作中的編譯的不同，會問一些非常有意思的問題，比如有人問過我，預處理的時候為什么不能提前發現語法錯誤呢，我說預處理的時候還沒到編譯階段呢，他說預處理不是編譯嗎。如果我們知道了編譯的四個不同廣度的含義就能更好地溝通清楚我們要表達的意思。

二、編譯系統的邏輯結構

前面一章我們對編譯的概念和編譯系統的組成已經有了基本的了解，這一章我們來具體講講它們之間的結構關系和每個組成部分的功能作用。

2.1 狹義編譯

我們首先來看一下狹義編譯：

狹義編譯是對一個源文件和n個頭文件進行的編譯，它包含預處理、最狹義編譯和匯編三個過程。預處理是對源文件中的預處理指令進行處理的過程，預處理指令包括頭文件包含指令(#include)、宏定義指令(#define)、取消宏定義指令(#undef)、條件編譯指令(#if #ifdef #ifndef #else #elif #endif)和其他一些編譯指令。預處理過程會把所有被包含的頭文件插入到源文件中，并對其它預處理指令進行處理，最終生成一個編譯單元 .i文件。然后對編譯單元進行最狹義的編譯，也就是編譯原理里面所說的編譯。編譯原理里面說最狹義編譯最后可以生成匯編文件也可以直接生成目標文件沒有匯編過程，但是書里一般都是按照直接生成目標文件來講的，而現實中的編譯器一般都是生成匯編文件，最后再經歷一個匯編過程。匯編是把匯編文件生成目標文件的過程，目標文件里面包含可直接執行的機器指令，但是整個文件還不是可執行格式。

2.2 最狹義編譯

最狹義編譯是編譯原理中的編譯。編譯原理是一門非常艱深課程，是計算機科學中最有技術含量的領域之一，是理論和實現都極其難以理解的一門科學。我們這里不準備詳細講解編譯原理的知識，只是對其框架進行大概的介紹。我們先看一張圖：

我們按照直接生成目標文件的方式來講，因為這樣整個編譯器結構比較完整，如果是生成匯編文件的話，那么機器碼生成這塊就不存在了。編譯器一般都分成前端和后端兩個部分，前端負責對語言本身進行解析，后端負責機器碼生成。為什么要分成前端和后端兩個部分呢，因為前端和后端并不是必然關聯的，分開之后可以有更大的靈活性。靈活性主要有兩個方面，對于同一種語言來說，語法解析我們只需要實現一次就行了，當語言需要移植到另一個CPU架構時，只需要實現后端就可以了。對于不同的語言來說，對于同一個CPU架構我們沒必要實現多個后端，所有的語言都可以共用同一個后端，當編譯器需要支持新的語言的時候，只需要實現前端就行了。前端包括詞法分析、語法分析(句法分析)、語義分析，后端包括中間碼生成、中間碼優化、機器碼生成、機器碼優化，下一章將會對其進行稍微詳細的介紹。

2.3 鏈接過程

經過狹義編譯之后我們得到了目標文件，但是目標文件并不是最終的可執行程序，我們需要把目標文件鏈接起來才能生成可執行程序。程序執行時生成進程，進程是由一個exe主程序和n個so庫程序組成，主程序和庫程序都是由目標文件和靜態庫文件通過靜態鏈接生成的。靜態鏈接分為隱式靜態鏈接和顯式靜態鏈接，隱式靜態鏈接是目標文件和目標文件直接合并在一起，顯式靜態鏈接是目標文件和靜態庫進行鏈接，本質上還是和靜態庫里面的目標文件進行鏈接。隱式靜態鏈接和顯式靜態鏈接區別不大，本質上是沒有區別的，只是在編譯命令上有形式上的區別。Exe對so，so對so，是動態鏈接的，動態鏈接分為半動態鏈接和完全動態鏈接，兩者的本質是相同的，都是動態鏈接的，也就是說沒有復制文件的過程，但是兩者的實現形式還是有很大差異的。半動態鏈接就是我們平常所說的動態鏈接，它在編程時需要include so的頭文件，在編譯時需要指定so所在的路徑，鏈接后生產的文件中會記錄這個so的相關信息，在進程啟動時加載器會加載這個so，在程序運行時調用了這個so的函數的時候會去動態解析符號。完全動態鏈接是指在代碼中通過函數dlopen加載相應的so，通過函數dlsym查找要調用的函數的符號，然后去調用這個函數，使用完了之后可以通過dlclose卸載這個so。完全動態鏈接不需要include相應的頭文件，編譯時也不需要指定so的路徑，運行時如果找不到so，dlopen會返回NULL，程序不會崩潰，用完了之后還可以把so卸載了。相反，對于半動態鏈接，如果編譯時找不到so就會編譯不過，運行時找不到so程序就會啟動失敗，程序運行的過程中也不可能把so給卸載移出進程的內存空間。

下面看一下編譯時鏈接的過程：

編譯時鏈接，不僅會進行靜態鏈接，也會進行半動態鏈接的第一步。下面再看一下半動態鏈接的啟動加載和完全動態鏈接：

進程啟動時首先是fork創建進程的殼，然后exec加載進程的主程序hello.exe和加載器ld.so。然后進程返回用戶空間，執行權交給ld，ld會根據主程序文件中的動態段的信息去加載所有的so文件，并完成重定位工作，最后把執行權交給主程序。主程序首先執行的并不是main函數，而是_start函數，_start函數會調用 __libc_start_main函數,此函數會完成進程環境的初始化，最后調用main函數。進入了main函數就是程序執行的主體了，程序如果執行到了dlopen函數，就會去加載相應的so文件。

2.4 組建系統

組建系統英語是build system，也有翻譯成構建系統的。什么是組建系統呢，如果你每次編譯程序都要執行一大堆gcc ld 命令，那是多么的麻煩，有了組建系統你每次只需要執行一個簡單的命令，就能編譯整個程序了。下面我們以使用最普遍的組建系統make為例簡單地講一講。make命令會在同目錄下尋找文件Makefile，然后解析并執行它。Makefile的內容包含5個部分，1.變量定義，2.顯示規則，3.隱式規則，4.文件指示，5注釋。變量定義相當于C語言中的宏，使用時會被替換到相應的位置。顯示規則說明了如何生成一個文件，顯示規則包含3部分，目標、依賴和命令。由于很多規則模式是很常用的，所以make內置了一些規則，我們沒必要把規則寫全，make會自動推導。文件指示類似于C語言中的預處理命令，如#include可以包含下層makefile。注釋是以#開頭的行。

顯示規則的格式如下，隱式規則沒有命令部分。

三、編譯原理簡介

前面我們講了一下最狹義編譯，也就是編譯原理中的編譯。這里我們把編譯原理給大家簡單介紹一下，就不展開詳細討論了，因為編譯原理實在是太深了，想要深入研究的同學可以去看參考文獻里推薦的書籍。我們先來看一下編譯的總體過程：

3.1 詞法分析

什么是詞法分析，為什么要進行詞法分析呢？詞法分析是把一個一個的字符變成一個一個的單詞(Token)。單詞，英文是Token，漢語有翻譯成記號的，也有翻譯成符號的，它是源代碼的最小邏輯單位。詞法分析的作用就相當于我們小時候的學的如何斷句，把一句話分成一個一個的詞，詞有名詞代詞動詞形容詞副詞介詞連詞等，它們再組成了一句話的主謂賓定狀補。類似的，詞法分析中從源代碼字符流中分出一個一個的單詞，并對單詞進行屬性分類，方便后面進一步地分析：句法分析(語法分析)，把單詞組成句子。詞法分析的基本原則也比較簡單，主要就是按照空格劃分，按照換行劃分，但是又不完全如此，又有一些特殊情況。比如 a=b+c，雖然沒有一個空格，但是并不能整體上看成一個單詞，而是要把它看成是 a、=、b、+、c，五個單詞。又比如 s = “hello world”,雖然“hello world”中間有一個空格，但是并不能把它看成是兩個單詞，而是把它看成是一個單詞。

詞法分析器分析出來的單詞都有哪些類別呢，一共有5種類別，分別是關鍵字、標識符、常量、操作符、分界符。關鍵字其實也算是標識符，只不過是特殊的標識符，它是計算機語言標準規定的具有特殊含義的標識符，主要有兩類，一類是表示數據類型的，比如int、long、float等，另一類是表達流程的，比如if、while、for。標識符是普通的標識符，是程序員為程序中的實體起的名字，主要分為兩類，分別是變量名和函數名。常量就是程序中的字面常量，包括整數型常量、浮點型常量、字符常量、字符串常量、布爾常量等。操作符是用來進行一些運算的符號，如進行算術運算的 + - x / % 等運算符，進行比較操作的 > >= < <= == != 等，進行邏輯運算的 && || ！等運算符，還有進行移位運算、賦值操作、條件操作等操作符。分界符是沒有啥具體含義用來分割一些邏輯單元的邊界的符號，如分號；表達一個語句的結束，大括號{}表達一個代碼塊或者函數的開始和結束，小括號用來表示表達式、函數參數等的分界。

那么我們該用什么方法進行詞法分析呢，比如我們可以使用正則表達式，使用有限狀態機，包括不確定性有限狀態機(NFA)和確定性有限狀態機(DFA),這方面的具體細節可以參看參考文獻里的書籍。

我們該怎么得到一個詞法分析器呢？有兩種方法，一種是手工編寫代碼，一種是用工具幫你生成。手工編寫的好處是自由靈活高效，缺點是麻煩費腦子，工具生成的優點是簡單快捷，缺點是不夠靈活，沒法自定義。目前大部分主流編譯器采取的都是手工編寫詞法分析器。由于詞法分析的過程像是掃描，所以詞法分析又叫做掃描，詞法分析器又叫做掃描器。一個比較著名的詞法分析器生成工具是flex。

詞法分析把源代碼的字節流變成了單詞流，并標記了單詞的類別，并把標識符的相關信息等放入了符號表，這些都會作為下一步句法分析的輸入。

3.2 語法分析

我們有了單詞，單詞可以組成句子，句子可以構成段落，段落可以組成文章，一篇美妙的文章就這么誕生了。對于簡單的文學作品是這樣的，對于復雜的文學作品如《紅樓夢》《三國演義》，有更高一層的結構，一篇文章只是其中的一回。同樣的，一個程序也是類似的結構，簡單的程序只有一個c文件，復雜的程序有很多的c文件，一個c文件就是一篇文章，是編譯的基本單元。具體來說，預處理之后的c文件才是一個編譯單元。從前面的描述我們可以看出來，一個編譯單元，它的結構是樹狀的，它的葉子節點的底層節點是單詞。語法分析就是把這些底層節點(單詞)一步一步地生成一棵樹的過程，這棵樹就是抽象語法樹(AST)。這顆樹的根節點就是編譯單元，編譯單元的子節點有兩類，分別是聲明和定義，聲明包括變量聲明和函數聲明，定義包括變量定義和函數定義。變量聲明、函數聲明和變量定義，都比較簡單，都是一句，它們的子節點很快就到了葉子節點(單詞)。函數定義比較復雜，首先包括函數簽名和函數體，函數體又是由很多語句組成的，語句又有很多的類型。下面我們來畫一下編譯單元的抽象語法樹。

下面我們再來看一個具體的賦值語句 a=b+c; 的抽象語法樹。

生成一個編譯單元的抽象語法樹是一個非常復雜的事情，那么該如何生成這個抽象語法樹呢？有兩類方法，一類是自頂向下方法，包括遞歸下降算法和LL算法，一個是自底向上方法，包括SR算法和LR算法。具體細節請參看參考文獻中的書籍。

3.3 語義分析

經過詞法分析和語法分析，我們得到了抽象語法樹，但是此時得到的結果只能保證程序是形式上合法的，并不能保證程序在語義上是合理的有意義的。比如給指針賦值浮點數，形式上是個賦值操作，實際上是沒有意義的。因此此時要進行語義分析，保證程序在邏輯上是有意義的，沒法發現語義不合法的就報錯，停止編譯。

3.4 中間碼生成

現在的編譯器都不是直接生成機器代碼，而是先生成一種中間語言的代碼。這么做是為了，1.使得所有的語言都可以用同一個后端，同一個語言可以輕松添加對新CPU架構的支持，2.所有語言都可以使用同樣的機器無關的代碼優化方法，避免重復實現優化算法。中間語言一般采取三地址碼的形式，每個三地址碼都是一個四元組(運算符，操作數1，操作數2，結果),由于每個四元組都包含了三個變量，即每條指令最多有三個操作數，所以被稱為三地址碼。中間碼生成是把抽象語法樹轉化為中間語言的過程。

3.5 中間碼優化

對中間碼進行優化，優化的原則是不改成程序本身的執行結果的情況下，減少程序執行的代碼量，能提高程序執行的效率。優化的方法有，常量表達式優化，直接把常量表達式的結果計算出來，避免其在運行時再去計算。公共子表達式消除，若兩個表達式有相同的子表達式，則只對它們計算一遍，復用計算的結果。復制傳播，某些變量的值并未被改變過便賦給其他變量，則可直接引用原值本身。死代碼消除，有些代碼不會被執行到，把它們刪除。無用代碼消除，有些代碼的執行沒有意義，對程序沒有作用，把它們刪除。代碼外提，有些在循環中的代碼，在每次循環中的計算結果都是一樣的，把它放在循環外只計算一遍就行了。還有很多其他優化方法就不一一列舉了，具體情況請參看參考文獻中的書籍。

3.6 機器碼生成

編譯程序的目的是為了把源碼翻譯成最終能在機器上執行運行的程序，所以編譯器最后要把中間碼轉換為機器碼。

3.7 機器碼優化

生成目標代碼時要考慮優化，生成最高效的代碼，有三個因素需要考慮，1.同一個效果可能有多個不同的指令都能實現，選擇最優的指令，2.充分利用寄存器，減少訪問內存的次數，3.在不影響程序正確性的情況下對指令進行重排序，提高代碼的運行效率。

3.8 小型編譯器推薦

當我們學習了編譯原理之后，非常想通過研究實際的編譯器代碼來深入理解編譯原理。但是目前最流行的兩個編譯器GCC、LLVM代碼都非常龐大，不適合拿來入手。為此我推薦幾個市面上比較流行的小型編譯器，代碼都比較短小簡單，大家可以用來研究編譯原理。

1. c4

一個非常簡單的解釋型C編譯器，整個代碼只有一個文件500多行，包含4個函數。可以解釋執行一些簡單的C程序，更神奇的是可以解釋執行自己。源碼地址：https://github.com/rswier/c4

2. ucc

ucc是曾任小米公司MIUI首席架構師的汪文俊同學在研究生期間花了一年多的時間寫的。Ucc 代碼簡潔易懂，結構清晰，易于學習和掌握。鄒昌偉編寫的書籍《C編譯器剖析》就是以ucc為源代碼來解析編譯器實現的。源碼地址：https://github.com/sheisc/ucc162.3

3. chibicc

一個簡單而又優雅的小型編譯器，實現了大多數 C11 特性，而且能成功編譯git、sqlite等源碼。源碼地址：https://github.com/rui314/chibicc

4. tcc

一個小型但是又非常完整的編譯器，不僅實現了編譯器前端，還實現了匯編器和鏈接器。源碼地址：https://github.com/TinyCC/tinycc

四、靜態鏈接與動態鏈接

當程序變得越來越龐大之后，我們就會對程序進行模塊劃分。最先使用的模塊方式是文件，把程序放到不同的源代碼中，最后編譯鏈接成一個可執行文件。當程序變得更龐大了之后，我們會把程序劃分為好幾個執行體，每個執行體實現一個單獨的功能邏輯。執行體分為主執行體，也就是exe可執行程序，和庫執行體，也就是so動態共享庫。主執行體有且只有一個，庫執行體有n個，n 大于等于 0。執行體一般對應一個源碼文件夾，源碼文件夾還可以有多個層級。我們對每個源碼文件進行編譯，得到一個目標文件，執行體都是由若干個目標文件靜態鏈接而生成的。目標文件、主執行體、庫執行體，它們都要有一定的格式。不同的操作系統可以采用不同的格式，Windows用的是PE格式，UNIX(包括Linux)用的是ELF格式。ELF是一個總體格式，對上，目標文件、主執行體、庫執行體又有不同的子類型格式，對下，在不同的硬件平臺上它們又有具體的格式。大家經常把靜態庫和動態庫放在一起來對比，導致人們習慣性認為它倆是非常對稱的。實際上它倆只是稍微有一些對稱性，它們的不對稱性還是很大的。靜態庫和動態庫最大的區別就是，靜態庫會被復制進被鏈接的程序中，而動態庫不會。也就是這一點區別導致了它們本質性的區別，動態庫是執行體，而靜態庫不是，靜態庫是組成執行體的原料。

頭文件的目的和意義：當整個程序只有一個源文件的時候，是沒有頭文件的。當程序被放到多個源文件的時候，由于每個源文件都是單獨編譯的，編譯的時候并不知道其他源文件的信息，所以需要頭文件來提供其他源文件的信息。頭文件里面主要放的是變量聲明、函數聲明、數據類型聲明。頭文件里面盡量只放聲明性的東西，不要放定義性東西。聲明和定義的區別是，聲明性的東西不分配內存空間，定義性的東西分配內存空間。如果在頭文件里面放定義性的東西的話，由于頭文件會被包含到很多源文件中，所以會導致這個定義會有很多份，這在大多數情況下都不是想要的情況。有一種情況可以在頭文件中放定義，那就是有些比較短小的又想要內聯的函數可以放在頭文件中。

4.1 靜態鏈接

我們經常把鏈接到靜態庫叫靜態鏈接，其實目標文件的合并也是靜態鏈接。它倆形式上雖然不太相同，但是本質上是一樣的。靜態庫僅僅是對目標文件的打包而已，鏈接到靜態庫實際上還是目標文件的合并。為了區分兩者，我們把前者叫做顯式靜態鏈接，后者叫做隱式靜態鏈接。如果我們的程序有兩個源文件組成，那么最終生成程序的時候就是兩個目標文件的合并，也就是隱式靜態鏈接。而我們鏈接到靜態庫的顯示靜態鏈接，和這個隱式靜態鏈接沒有區別。明白了這件事，我們就容易想明白一個問題，那就是我們的程序如果依賴于一個靜態庫，那么這個靜態庫的依賴，我們需要在本程序里要再聲明一次。因為靜態庫在這個意義上和你自己的某個C文件沒有區別，相當于是你自己對外部的依賴。這點和動態庫就有很大的不同，你依賴于動態庫，并不需要知道動態庫依賴于誰。

顯式靜態鏈接的編譯命令和動態鏈接的命令是一樣的，和隱式靜態鏈接不一樣，但是在處理邏輯上正好反了過來。

4.2 動態鏈接

動態鏈接也分為兩種，我們經常說的動態鏈接叫半動態鏈接，通過dlopen進行的鏈接叫做完全動態鏈接。因為dlopen確實是完全動態的，只有dlopen代碼執行到了才會進行鏈接，執行不到根本就不會鏈接。而半動態鏈接，你在編譯時就要在命令參數中指明要鏈接的動態庫，鏈接后動態庫的信息會被放到被鏈接的執行體的動態段里面。程序啟動的時候加載器還會把一個程序所依賴的所有動態庫都加載到進程的地址空間，并做好重定位。你對動態庫中的函數的調用，直到你第一次調用時才會進行函數地址解析。完全動態鏈接，dlopen的時候加載動態庫，dlsym的時候進行函數地址解析，dlclose還能把動態庫給移出進程的地址空間。

半動態鏈接和完全動態鏈接所使用的動態庫格式是一樣的，沒有啥區別，不同的是使用它們的方式。

4.3 實例解析

下面我們寫一個hello程序來演示一下隱式靜態鏈接、顯示靜態鏈接、半動態鏈接、完全動態鏈接，它們的區別和用法。所有的文件截圖如下：

hello.c

#include?
#include?

#include?"hello_static_implicit.h"
#include?"hello_static_explicit.h"
#include?"hello_dynamic_partial.h"


void?say_hello_direct()
{
?printf("say?hello?direct
");
}

int?main(int?argc,?char?const?*argv[])
{

?printf("----------------------------------
");
?say_hello_direct();
?printf("----------------------------------
");
?say_hello_static_implicit();
?printf("----------------------------------
");
?say_hello_static_explicit();
?printf("----------------------------------
");
?say_hello_dynamic_partial();
?printf("----------------------------------
");
?void?*handle?=?dlopen("./libhello_dynamic_full.so",?RTLD_LAZY);
?void?(*say_hello_dynamic_full)(void);
?say_hello_dynamic_full?=?(void?(*)(void))dlsym(handle,?"say_hello_dynamic_full");
?say_hello_dynamic_full();
?dlclose(handle);
?printf("----------------------------------
");

?return?0;
}

hello_static_implicit.c

#include?

#include?"hello_static_explicit.h"


void?say_hello_static_explicit()
{
?printf("say?hello?static?explicit
");
}

其他幾個文件是類似的，就不再貼出代碼了。

Makefile

#?This?is?hello?link?program

CFLAGS?+=?-std=c99?-g?-Wall


all?:?hello?libhello_dynamic_full.so

hello?:?hello.o?hello_static_implicit.o?libhello_static_explicit.a?libhello_dynamic_partial.so
?gcc?-o?hello?hello.o?hello_static_implicit.o?-Wl,-rpath=.?-L.?-lhello_static_explicit?-lhello_dynamic_partial

hello.o?:?hello.c?hello_static_implicit.h?hello_static_explicit.h?hello_dynamic_partial.h
?gcc?-o?hello.o?-c?hello.c

hello_static_implicit.o?:?hello_static_implicit.c?hello_static_implicit.h
?gcc?-o?hello_static_implicit.o?-c?hello_static_implicit.c

hello_static_explicit.o?:?hello_static_explicit.c?hello_static_explicit.h
?gcc?-o?hello_static_explicit.o?-c?hello_static_explicit.c

libhello_static_explicit.a?:?hello_static_explicit.o
?ar?rv?libhello_static_explicit.a?hello_static_explicit.o

libhello_dynamic_partial.so?:?hello_dynamic_partial.c?hello_dynamic_partial.h
?gcc?-o?libhello_dynamic_partial.so?-shared?hello_dynamic_partial.c

libhello_dynamic_full.so?:?hello_dynamic_full.c
?gcc?-o?libhello_dynamic_full.so?-shared?hello_dynamic_full.c

.PHONY?:
clean:
?rm?-f?hello?*.o?*.a?*.so

從Makefile中可以看出他們的鏈接關系。下面是程序運行的結果：

可以看出hello程序可以直接調用本文件內的函數，也可以調用隱式靜態鏈接中的函數，也可以調用顯示靜態鏈接也就是鏈接到靜態庫的函數，也可以調用半動態鏈接中的so的函數，也可以通過dlopen、dlsym進行完全動態鏈接。前三者在調用方式上沒有區別，都是先聲明后調用，最后一個不需要聲明函數，但是需要手動解析函數的地址，并賦值給函數指針才能調用。

我把演示代碼放到GitHub上了，大家可以參考一下 https://github.com/orangeboyye/hello-link

五、總結回顧

本文中，我們先回顧了編譯系統的發展歷史，理解了編譯系統各個組成部分的原理和相互之間的關系，然后又介紹了各個模塊內部的知識。都是一些簡單的概念性的介紹，想要深入學習的同學可以去研究參考文獻中的書籍。　　

審核編輯：湯梓紅