碎碎念
為什麼這本書叫做
龍書(Dragon book)
？
這本書很有意思，它的書名是
《Compilers: Principles, Techniques, and Tools》
，也就是編譯器的原則、技術和工具。但它卻畫出了一個恐龍和騎士，恐龍身上寫的是
Complexity of Compiler Design
，也就是
複雜的編譯器設計
，騎士的盾上寫的是
Syntax Directed Granslation
，也就是文法翻譯。騎士的劍上看的不是很清楚，我猜測應該是優秀的編譯器的意思。這是征服複雜性的隐喻。優秀的編譯器會直接征服複雜的編譯，複雜的編譯設計永遠無法攻破文法翻譯。
什麼是編譯原理
計算機是隻認識二進制的，但是我們平常開發中根本不會使用二進制進行開發，我們使用的都是 Java、C 這類的進階語言，每種語言都會經過一系列的轉換才能被計算機識别，那麼到底是誰做的這項工作呢？一個被稱為
編譯器(compiler)
的大佬出場了。
語言處理器
首先考慮一下一個例子，你如何才能和老外對話？你是不是需要學英語？我們有一些同學可能認為英語難學，經常會在英語書上做一些漢語标記友善了解。
那麼，誰做了由英語到
友善記憶
的英語之間的轉換呢？答案是你的大腦。是以，我們可以歸納一下這個過程。
因為我們懂漢語（自己的一套文法規則），我們把英語（需要學習的語言）轉換為我們便于了解的漢語（大腦翻譯規則），我們才能學會英語和老外對話（轉換為目智語言）。
這裡我說一點：昨天晚上外出遛狗有個老黑和中國女生對話，中國女生竟然講英文？？？？？？這可是中國本土好麼，為什麼外國人來到中國不講漢語偏要中國人講英文？？？你去外國旅遊你會講中文嗎？？？這是一個基本認知問題，别怪我偏執。我認為外國人要來我們國家最基本的一點就是：你要學中文。
回到正題，我們上面舉出的這個學英語的例子，其實就是一個由原程式經過某種機制轉換，把它變成目智語言的過程。也就是
編譯器就是一個翻譯官的角色，它負責把源程式的文法翻譯成目标程式能夠了解的文法。
回到計算機中，我們肯定需要目标程式來做一些事情的。
也就是，我們通過某個管道獲得的輸入資訊，會經過編譯器的轉換，變為輸出資訊進行展示。
除了編譯器之外，還有一種稱為
解釋器(interpreter)
的語言處理器，它不是做翻譯工作的，而是把使用者提供的輸入執行源程式中指定的操作。
我們熟知的 Java 語言，就結合了編譯和解釋的過程，我們寫的 Java 源檔案首先被編譯成
位元組碼(bytecode)
，位元組碼是一種中間碼，它通常被看成是可執行的二進制檔案。然後再由 Java 虛拟機對位元組碼解釋執行。這樣，在一台機器上編譯的位元組碼就能夠在其他機器上解釋執行，這種展現了 Java 語言的
平台無關性
。
為了提高編譯速度，Java 中有一種
just-in-time,JIT
即時編譯器會一邊編譯一邊執行。
一個源檔案程式可能被劃分為多個子產品，并存放在多個檔案中，還需要把檔案連結在一起，是以，除了編譯器之外，還需要一種能連結檔案的部件參與，
預處理器(preprossor)
是做這件事情的。如下圖所示
預處理器經過預處理後會作為輸入傳遞給編譯器，編譯器對源程式進行編譯，編譯完成後生成彙編代碼，作為彙編器的輸入傳遞給彙編器，彙編器進行彙編處理轉換為機器代碼，注意這個時候還不是目标代碼，還要經過連結器與系統庫函數進行連結，最後由加載器把目标代碼加載到記憶體中執行
編譯器的結構
我們上面大概了解了一下語言的處理過程，下面我們就來了解一下編譯器的内部結構，編譯器内部其實具有兩種結構：
分析(analysis)
部分和
整合(synthesis)
部分。
分析過程相當于是把源程式分成多個結構，每個結構都有特定的文法格式進行校驗，在經由每個校驗後，如果不滿足指定的文法格式則進行提醒，使使用者進行修改。分析部分還會收集有關源程式的資訊，會把收集到的資訊存放在一個被稱為
符号表(symbol table)
的資料結構中。符号表和中間表示形式一起傳給
整合
整合過程是根據分析過程傳遞的資訊來構造使用者期待的目标程式。分析和整合統稱為
前端(front end)
和
後端(back end)
，哈哈哈哈。
這裡你需要知道
符号表(Symbol Table)
的概念：符号表是編譯器使用和維護的資料結構，由辨別符和類型組成。符号表的主要作用是幫助編譯器快速定位。
下面是一個編譯器的典型結構
下面我們就針對編譯器結構的每一層進行描述和讨論
詞法分析
詞法分析(Lexical Analyzer)
是編譯器的第一個步驟，它也被稱為
掃描(scanning)
。詞法分析器通過讀入外部的字元流對其進行掃描，并且把它們組成有意義的
詞素(lexeme)
序列，對于每個詞素，詞法分析器都會産生
詞法單元(token)
作為輸出。這個詞法單元會傳遞給下一個步驟，也就是文法分析。
這裡需要解釋一下 Token 、詞素和詞法分析器的概念
我們常用的程式設計語言就是具有詞素的單詞和符号的集合，比如 C 語言中有 ()，-> 等等。關鍵字 if...while...，變量或函數名稱以及數字和字元串常量也被視為詞素。并不是所有的自負都屬于詞素，例如空格和注釋就不屬于。
詞法分析器用來分析詞素有兩個規則
- 跳過不能以字母開頭的字元
- 然後找到剩餘的最長字首，也就是詞素
這兩句話比較抽象，舉個例子來說明一下
比如 C 語言中有這麼一個語句
ifx = 20*30;
那麼第一個詞素就是 ifx，為什麼不是 if 呢？因為 if 不是最長的字首。然後後面的詞素依次是 =，20，*，30和；。
詞素、詞法分析器、token 的關系如下
詞素是 Token 的執行個體，詞法分析器的主要任務就是從源程式中讀取字元并産生 token。token 也是有結構的，一般結構如下
在詞法分析生成的
token
中，第一個詞 token-name 是文法分析期間使用的抽象符号，第二個詞 attribute-value 指向的是符号表中關于這個詞法單元的條目數。
我們舉個例子來看一下詞法分析的拆解過程。
比如現在源程式中有一個指派語句
income = mainjob + sideline // 收入 = 主業 + 副業
這個指派語句中的字元可以組合成如下詞素，并轉換成為 token，并傳遞給文法分析階段。
- 首先，income 是一個詞素，它會被映射為 <id,1>，其中 id 是表示的
辨別符(identifier)
- 然後是指派符号 = ，它也是一個詞素，被映射稱為 token 中的 < = >。這個 token 不需要屬性值，是以沒有第二個詞。
- mainjob 是一個詞素，它被映射成為 token 中的 <id,2>，2 是 mainjob 對應的符号表條目
- +也是一個詞素，它被映射稱為 < + >，沒有條目數
- sideline 是一個詞素，它被映射稱為 token 中的 <id,3>，3 是 sideline 對應的符号表條目
是以，經過詞法分析後，上面的源程式會變為
<id,1> < = > <id,2> < + > <id,3>
在上面的表達式中， = 和 + 分别表示指派和加法運算符的抽象符号。用圖來表示的話就是
文法分析
編譯器的第二個步驟是
文法分析(syntax analysis)
或者稱為
解析(parsing)
。文法分析器使用由詞法分析器生成的各個詞法單元的第一個分量來建立樹形的中間表示。常用的方法就是
文法樹(syntax tree)
。編譯器的後續步驟都會使用這個文法結構來幫助分析源程式，并聲稱目标程式。
語義分析
語義分析是由
語義分析器(semantic analyzer)
完成的，它使用文法樹和符号表中的資訊來檢查源程式是否和語言定義的語義一緻。語義分析器也收集類型資訊，并把這些資訊放在文法樹或者符号表中，以便後續的中間代碼生成器使用。
語義分析會進行
類型檢查(type checking)
，這是語義分析器的一個最重要的功能。編譯器會檢查每個運算符是否具有比對的運算分量。舉個例子比如設計語言要求一個數組的下标是整數，如果你用浮點數座位下标，編譯器就會出錯。
某些程式設計語言比如 Java 會允許
自動類型轉換(coercion)
。如果整數和浮點數進行運算，編譯器會把整數轉換為浮點數。
中間代碼生成
在源程式的文法分析和語義分析完成後，很多編譯器生成一個明确的低級類機器語言的中間表示。我們可以把中間表示形式看作是抽象，中間形式的代碼應該具有兩個重要的性質：易于生成，并且能夠輕松的被翻譯。一般常用的一種是
三位址指令(three-address instructions)
的中間表示形式。我們後面會細說。
代碼優化
代碼優化會試圖改進代碼以便生成更好的目标代碼。
更好
通常情況下意味着更快，但是也可能會有其他目标，比如更短或能耗更低的目标代碼。
代碼生成
代碼生成通過中間代碼作為輸入，并把它映射為目智語言。如果目智語言是機器代碼的話，那麼必須要為每個變量配置設定寄存器或記憶體位置。解釋一下上面的運作結果。
每個指令的第一個運算分量指定了一個目标位址，各個指令中的 F 告訴我們它處理的是
浮點數
, 上面代碼首先把 id3 裝載進 R2 寄存器中，然後把 id2 裝載進 R1 寄存器中，再對 R1 目标進行 R1 和 R2 寄存器相加的操作。最後把寄存器 R1 的值存放到 id1 的位址中。
符号表管理
我們上面提到了符号表的概念，它是一個編譯器很重要的功能。符号表能夠記錄源程式中使用變量的名稱，并收集和每個名稱相關的屬性資訊。它相當于一個秘書的作用。符号表還記錄了每個變量名字的條目。後面我們會詳細的介紹符号表。
編譯器構造工具
和軟體開發一樣，寫編譯器的人可以充分利用現代的軟體開發環境進行開發。通常也有 語言編輯器、調試工具、版本管理、測試工具等。除此之外，還需要一些更專業的工具來實作編輯器不同階段的代碼生成。
一些常用的編譯器構造工具有
- 文法分析器生成器：可以根據程式設計語言的文法描述自動生成文法分析器
- 掃描器生成器：可以根據一個語言的文法單元的正則描述生成詞法分析器
- 文法制導的翻譯引擎：用于生成一組周遊分析樹并聲稱中間代碼
- 代碼生成器：用于把中間代碼轉換為目标代碼
- 資料流分析引擎：用于分析輸入是如何傳遞到另一部分的
- 編譯器構造工具：提供用于構造編譯器不同階段的例程
程式設計語言的發展曆程
計算機從 20 世紀 40 年代建立至今都隻能了解二進制語言，亘古不變。這個 0 、 1 組成的序列能夠告訴計算機以什麼樣的順序執行怎樣的運算。運算本身是很底層的：比如把一個資料從一個位置進行移動；把兩個寄存器的内容進行相加、比較兩個值，為了避免如此枯燥的運算，我們開發了各種各樣的程式設計語言，但是計算機底層的計算方式一直沒變，是以學習哪個技術成本效益高，明白了嗎？下面我們就來一起認識一下程式設計語言的曆程。
進階設計語言
首先被開發出來的是 20 世紀 50 年代的
彙編語言
，5 年後發生了重要的進步，用于科學計算的
Fortran
被開發出來，用于商業處理的
Cobol
語言和用于符号計算的
Lisp
語言被開發出來；然後接下來的時間，慢慢很多程式設計語言被開發出來，比如 C、C++、Java、JavaScript、Python 等。後面還有用于資料處理的 SQL 語言。
語言分類
說到給這些程式設計語言分類，那可是有太多了，不過我們專注一下高頻的分類。
如何完成計算任務的語言稱為
強制式(imperative)
語言，而把程式中指明要進行哪些計算的語言稱為
聲明式(declarative)
語言。 C、C++、Java 這些都是強制式語言，它們能夠改變程式的狀态；聲明式比如 HTML Prolog 等。
馮·諾伊曼
語言指的是以馮·諾伊曼計算機體系為基礎的程式設計語言，今天很多程式設計語言都是馮·諾伊曼語言
面向對象語言(object-oriented language)
是一種描述對象的語言，比如 C、C++、Java
腳本語言(scripting language)
是具有高層次的解釋型語言，它通常把多個過程
粘
在一起，比如 JavaScript、Perl、PHP、Python 等。
程式設計語言基礎
下面我們主要探讨程式設計語言的研究中最重要的術語和它們的差別，假設讀者已經了解過 C、C++、C#、Java 中任意一種語言。
靜态和動态的差別
編譯器需要能夠對程式作出判定，如果語言能夠讓編譯器靜态（非運作）時候決定某個問題，那麼我們說這個語言使用了一種
靜态(static)
政策，或者說能夠在
編譯時刻(compile time)
決定。如果讓編譯器在運作時決定某個政策，那麼就是
動态政策(dynamic policy)
，或者被認為是
運作時決定(run time)
還有一個問題是聲明的
作用域(scope)
，如果能夠通過閱讀程式就能确定一個聲明的作用域，那麼這個語言就是
靜态作用域(static scope)
，或者說是
詞法作用域(lexical scope)
。否則這個語言使用的是
動态作用域(dynamic scope)
。動态作用域的指向對象是幾個聲明中的一個，并不惟一。
C 和 Java 都使用了靜态作用域，比如 Java 中的
static
關鍵字，下面是一段代碼示例
public static int x;
這段代碼在建立完成後就能夠确定它的作用域，因為 static 聲明的變量是類變量，類變量的執行個體能確定隻有一個個（不太清楚的小夥伴可以參考我的這篇文章 都說變量有七八種，到底誰是 Java 的親兒子）
如果你去掉了 static ，那麼這個變量的作用域和在記憶體中的配置設定就無法确定，編譯器無法在運作之前确定所有這些位置。
靜态綁定和動态綁定
同樣的，名字到位置也區分靜态綁定和動态綁定，如果能在非運作條件下唯一确定名字到位置，那麼就是靜态綁定，如果要在程式運作時才能确定名字和位置的綁定，那麼就是動态綁定。
靜态作用域和塊結構
大多數程式設計語言都提供了作用域這麼一個結構，比如 Java 中的
private,protected,public
等關鍵字的使用，提供了有效的作用域控制。
塊結構也是一種作用域，使用塊結構表示的含義是在
塊内部(block)
作用範圍有效，塊使用
{}
來界定一個塊。
這種文法允許在任意函數或者方法的内部嵌入一個塊，這種嵌套結構也被稱為 塊結構(block structure)
參數傳遞機制
參數傳遞機制主要描述的是形式參數和實際參數的關聯。大多數程式設計語言都支援兩種調用：
值傳遞
引用傳遞
值傳遞
引用傳遞
| 作者：cxuan 本文版權歸作者所有，未經作者允許不能轉載，轉載需要聯系，否則追究法律責任的權利。 如果文中有什麼錯誤，歡迎指出。以免更多的人被誤導。 |