來自公眾號：Java建設(shè)者

為什么這本書叫做龍書(Dragon book)？

這本書很有意思，它的書名是《Compilers: Principles, Techniques, and Tools》，也就是編譯器的原則、技術(shù)和工具。但它卻畫出了一個恐龍和騎士，恐龍身上寫的是Complexity of Compiler Design，也就是復(fù)雜的編譯器設(shè)計，騎士的盾上寫的是Syntax Directed Granslation，也就是語法翻譯。騎士的劍上看的不是很清楚，我猜測應(yīng)該是優(yōu)秀的編譯器的意思。這是征服復(fù)雜性的隱喻。優(yōu)秀的編譯器會直接征服復(fù)雜的編譯，復(fù)雜的編譯設(shè)計永遠無法攻破語法翻譯。

什么是編譯原理

計算機是只認識二進制的，但是我們平常開發(fā)中根本不會使用二進制進行開發(fā)，我們使用的都是 Java、C 這類的高級語言，每種語言都會經(jīng)過一系列的轉(zhuǎn)換才能被計算機識別，那么到底是誰做的這項工作呢？一個被稱為編譯器(compiler)的大佬出場了。

語言處理器

首先考慮一下一個例子，你如何才能和老外對話？你是不是需要學(xué)英語？我們有一些同學(xué)可能認為英語難學(xué)，經(jīng)常會在英語書上做一些漢語標(biāo)記方便理解。

那么，誰做了由英語到方便記憶的英語之間的轉(zhuǎn)換呢？答案是你的大腦。所以，我們可以歸納一下這個過程。

因為我們懂漢語（自己的一套語法規(guī)則），我們把英語（需要學(xué)習(xí)的語言）轉(zhuǎn)換為我們便于理解的漢語（大腦翻譯規(guī)則），我們才能學(xué)會英語和老外對話（轉(zhuǎn)換為目標(biāo)語言）。

這里我說一點：昨天晚上外出遛狗有個老黑和中國女生對話，中國女生竟然講英文？？？？？？這可是中國本土好么，為什么外國人來到中國不講漢語偏要中國人講英文？？？你去外國旅游你會講中文嗎？？？這是一個基本認知問題，別怪我偏執(zhí)。我認為外國人要來我們國家最基本的一點就是：你要學(xué)中文，千萬不要抱著英語為上的心態(tài)，漢語不輸任何語言。

回到正題，我們上面舉出的這個學(xué)英語的例子，其實就是一個由原程序經(jīng)過某種機制轉(zhuǎn)換，把它變成目標(biāo)語言的過程。也就是

編譯器就是一個翻譯官的角色，它負責(zé)把源程序的語法翻譯成目標(biāo)程序能夠理解的語法。

回到計算機中，我們肯定需要目標(biāo)程序來做一些事情的。

也就是，我們通過某個渠道獲得的輸入信息，會經(jīng)過編譯器的轉(zhuǎn)換，變?yōu)檩敵鲂畔⑦M行展示。

除了編譯器之外，還有一種稱為解釋器(interpreter)的語言處理器，它不是做翻譯工作的，而是把用戶提供的輸入執(zhí)行源程序中指定的操作。

我們熟知的 Java 語言，就結(jié)合了編譯和解釋的過程，我們寫的 Java 源文件首先被編譯成字節(jié)碼(bytecode)，字節(jié)碼是一種中間碼，它通常被看成是可執(zhí)行的二進制文件。然后再由 Java 虛擬機對字節(jié)碼解釋執(zhí)行。這樣，在一臺機器上編譯的字節(jié)碼就能夠在其他機器上解釋執(zhí)行，這種體現(xiàn)了 Java 語言的平臺無關(guān)性。

為了提高編譯速度，Java 中有一種just-in-time,JIT即時編譯器會一邊編譯一邊執(zhí)行。

一個源文件程序可能被劃分為多個模塊，并存放在多個文件中，還需要把文件鏈接在一起，所以，除了編譯器之外，還需要一種能鏈接文件的部件參與，預(yù)處理器(preprossor)是做這件事情的。如下圖所示

預(yù)處理器經(jīng)過預(yù)處理后會作為輸入傳遞給編譯器，編譯器對源程序進行編譯，編譯完成后生成匯編代碼，作為匯編器的輸入傳遞給匯編器，匯編器進行匯編處理轉(zhuǎn)換為機器代碼，注意這個時候還不是目標(biāo)代碼，還要經(jīng)過鏈接器與系統(tǒng)庫函數(shù)進行鏈接，最后由加載器把目標(biāo)代碼加載到內(nèi)存中執(zhí)行

編譯器的結(jié)構(gòu)

我們上面大概了解了一下語言的處理過程，下面我們就來了解一下編譯器的內(nèi)部結(jié)構(gòu)，編譯器內(nèi)部其實具有兩種結(jié)構(gòu)：分析(analysis)部分和整合(synthesis)部分。

分析過程相當(dāng)于是把源程序分成多個結(jié)構(gòu)，每個結(jié)構(gòu)都有特定的語法格式進行校驗，在經(jīng)由每個校驗后，如果不滿足指定的語法格式則進行提醒，使用戶進行修改。分析部分還會收集有關(guān)源程序的信息，會把收集到的信息存放在一個被稱為符號表(symbol table)的數(shù)據(jù)結(jié)構(gòu)中。符號表和中間表示形式一起傳給整合部分。

整合過程是根據(jù)分析過程傳遞的信息來構(gòu)造用戶期待的目標(biāo)程序。分析和整合統(tǒng)稱為前端(front end)和后端(back end)，哈哈哈哈。

這里你需要知道符號表(Symbol Table)的概念：符號表是編譯器使用和維護的數(shù)據(jù)結(jié)構(gòu)，由標(biāo)識符和類型組成。符號表的主要作用是幫助編譯器快速定位。

下面是一個編譯器的典型結(jié)構(gòu)

下面我們就針對編譯器結(jié)構(gòu)的每一層進行描述和討論

詞法分析

詞法分析(Lexical Analyzer)是編譯器的第一個步驟，它也被稱為掃描(scanning)。詞法分析器通過讀入外部的字符流對其進行掃描，并且把它們組成有意義的詞素(lexeme)序列，對于每個詞素，詞法分析器都會產(chǎn)生詞法單元(token)作為輸出。這個詞法單元會傳遞給下一個步驟，也就是語法分析。

這里需要解釋一下 Token 、詞素和詞法分析器的概念

我們常用的編程語言就是具有詞素的單詞和符號的集合，比如 C 語言中有 ()，-> 等等。關(guān)鍵字 if...while...，變量或函數(shù)名稱以及數(shù)字和字符串常量也被視為詞素。并不是所有的自負都屬于詞素，例如空格和注釋就不屬于。

詞法分析器用來分析詞素有兩個規(guī)則

跳過不能以字母開頭的字符

然后找到剩余的最長前綴，也就是詞素

這兩句話比較抽象，舉個例子來說明一下

比如 C 語言中有這么一個語句

ifx=20*30;

那么第一個詞素就是 ifx，為什么不是 if 呢？因為 if 不是最長的前綴。然后后面的詞素依次是 =，20，*，30和；。

詞素、詞法分析器、token 的關(guān)系如下

詞素是 Token 的實例，詞法分析器的主要任務(wù)就是從源程序中讀取字符并產(chǎn)生 token。token 也是有結(jié)構(gòu)的，一般結(jié)構(gòu)如下

在詞法分析生成的token中，第一個詞 token-name 是語法分析期間使用的抽象符號，第二個詞 attribute-value 指向的是符號表中關(guān)于這個詞法單元的條目數(shù)。

我們舉個例子來看一下詞法分析的拆解過程。

比如現(xiàn)在源程序中有一個賦值語句

income=mainjob+sideline//收入=主業(yè)+副業(yè)

這個賦值語句中的字符可以組合成如下詞素，并轉(zhuǎn)換成為 token，并傳遞給語法分析階段。

首先，income 是一個詞素，它會被映射為 ，其中 id 是表示的標(biāo)識符(identifier)的抽象符號，而 1 指的是符號表中 income 在符號表中的條數(shù)。

然后是賦值符號 = ，它也是一個詞素，被映射稱為 token 中的 < = >。這個 token 不需要屬性值，所以沒有第二個詞。

mainjob 是一個詞素，它被映射成為 token 中的 ，2 是 mainjob 對應(yīng)的符號表條目

+也是一個詞素，它被映射稱為 < + >，沒有條目數(shù)

sideline 是一個詞素，它被映射稱為 token 中的 ，3 是 sideline 對應(yīng)的符號表條目

所以，經(jīng)過詞法分析后，上面的源程序會變?yōu)?/p>

在上面的表達式中， = 和 + 分別表示賦值和加法運算符的抽象符號。用圖來表示的話就是

語法分析

編譯器的第二個步驟是語法分析(syntax analysis)或者稱為解析(parsing)。語法分析器使用由詞法分析器生成的各個詞法單元的第一個分量來創(chuàng)建樹形的中間表示。常用的方法就是語法樹(syntax tree)。編譯器的后續(xù)步驟都會使用這個語法結(jié)構(gòu)來幫助分析源程序，并生成目標(biāo)程序。

語義分析

語義分析是由語義分析器(semantic analyzer)完成的，它使用語法樹和符號表中的信息來檢查源程序是否和語言定義的語義一致。語義分析器也收集類型信息，并把這些信息放在語法樹或者符號表中，以便后續(xù)的中間代碼生成器使用。

語義分析會進行類型檢查(type checking)，這是語義分析器的一個最重要的功能。編譯器會檢查每個運算符是否具有匹配的運算分量。舉個例子比如設(shè)計語言要求一個數(shù)組的下標(biāo)是整數(shù)，如果你用浮點數(shù)作為下標(biāo)，編譯器就會出錯。

某些程序設(shè)計語言比如 Java 會允許自動類型轉(zhuǎn)換(coercion)。如果整數(shù)和浮點數(shù)進行運算，編譯器會把整數(shù)轉(zhuǎn)換為浮點數(shù)。

中間代碼生成

在源程序的語法分析和語義分析完成后，很多編譯器生成一個明確的低級類機器語言的中間表示。我們可以把中間表示形式看作是抽象，中間形式的代碼應(yīng)該具有兩個重要的性質(zhì)：易于生成，并且能夠輕松的被翻譯。一般常用的一種是三地址指令(three-address instructions)的中間表示形式。我們后面會細說。

代碼優(yōu)化

代碼優(yōu)化會試圖改進代碼以便生成更好的目標(biāo)代碼。更好通常情況下意味著更快，但是也可能會有其他目標(biāo)，比如更短或能耗更低的目標(biāo)代碼。

代碼生成

代碼生成通過中間代碼作為輸入，并把它映射為目標(biāo)語言。如果目標(biāo)語言是機器代碼的話，那么必須要為每個變量分配寄存器或內(nèi)存位置。解釋一下上面的運行結(jié)果。

每個指令的第一個運算分量指定了一個目標(biāo)地址，各個指令中的 F 告訴我們它處理的是浮點數(shù), 上面代碼首先把 id3 裝載進 R2 寄存器中，然后把 id2 裝載進 R1 寄存器中，再對 R1 目標(biāo)進行 R1 和 R2 寄存器相加的操作。最后把寄存器 R1 的值存放到 id1 的地址中。

符號表管理

我們上面提到了符號表的概念，它是一個編譯器很重要的功能。符號表能夠記錄源程序中使用變量的名稱，并收集和每個名稱相關(guān)的屬性信息。它相當(dāng)于一個秘書的作用。符號表還記錄了每個變量名字的條目。后面我們會詳細的介紹符號表。

編譯器構(gòu)造工具

和軟件開發(fā)一樣，寫編譯器的人可以充分利用現(xiàn)代的軟件開發(fā)環(huán)境進行開發(fā)。通常也有語言編輯器、調(diào)試工具、版本管理、測試工具等。除此之外，還需要一些更專業(yè)的工具來實現(xiàn)編輯器不同階段的代碼生成。

一些常用的編譯器構(gòu)造工具有

語法分析器生成器：可以根據(jù)程序設(shè)計語言的語法描述自動生成語法分析器

掃描器生成器：可以根據(jù)一個語言的語法單元的正則描述生成詞法分析器

語法制導(dǎo)的翻譯引擎：用于生成一組遍歷分析樹并生成中間代碼

代碼生成器：用于把中間代碼轉(zhuǎn)換為目標(biāo)代碼

數(shù)據(jù)流分析引擎：用于分析輸入是如何傳遞到另一部分的

編譯器構(gòu)造工具：提供用于構(gòu)造編譯器不同階段的例程

程序設(shè)計語言的發(fā)展歷程

計算機從 20 世紀(jì) 40 年代創(chuàng)建至今都只能理解二進制語言，亙古不變。這個 0 、 1 組成的序列能夠告訴計算機以什么樣的順序執(zhí)行怎樣的運算。運算本身是很底層的：比如把一個數(shù)據(jù)從一個位置進行移動；把兩個寄存器的內(nèi)容進行相加、比較兩個值，為了避免如此枯燥的運算，我們開發(fā)了各種各樣的編程語言，但是計算機底層的計算方式一直沒變，所以學(xué)習(xí)哪個技術(shù)性價比高，明白了嗎？下面我們就來一起認識一下程序設(shè)計語言的歷程。

高級設(shè)計語言

首先被開發(fā)出來的是 20 世紀(jì) 50 年代的匯編語言，5 年后發(fā)生了重要的進步，用于科學(xué)計算的Fortran被開發(fā)出來，用于商業(yè)處理的Cobol語言和用于符號計算的Lisp語言被開發(fā)出來；然后接下來的時間，慢慢很多編程語言被開發(fā)出來，比如 C、C++、Java、JavaScript、Python 等。后面還有用于數(shù)據(jù)處理的 SQL 語言。

語言分類

說到給這些編程語言分類，那可是有太多了，不過我們專注一下高頻的分類。

如何完成計算任務(wù)的語言稱為強制式(imperative)語言，而把程序中指明要進行哪些計算的語言稱為聲明式(declarative)語言。C、C++、Java 這些都是強制式語言，它們能夠改變程序的狀態(tài)；聲明式比如 HTML Prolog 等。

馮·諾伊曼語言指的是以馮·諾伊曼計算機體系為基礎(chǔ)的編程語言，今天很多編程語言都是馮·諾伊曼語言

面向?qū)ο笳Z言(object-oriented language)是一種描述對象的語言，比如 C、C++、Java

腳本語言(scripting language)是具有高層次的解釋型語言，它通常把多個過程粘在一起，比如 JavaScript、Perl、PHP、Python 等。

程序設(shè)計語言基礎(chǔ)

下面我們主要探討程序設(shè)計語言的研究中最重要的術(shù)語和它們的區(qū)別，假設(shè)讀者已經(jīng)了解過 C、C++、C#、Java 中任意一種語言。

靜態(tài)和動態(tài)的區(qū)別

編譯器需要能夠?qū)Τ绦蜃鞒雠卸?，如果語言能夠讓編譯器靜態(tài)（非運行）時候決定某個問題，那么我們說這個語言使用了一種靜態(tài)(static)策略，或者說能夠在編譯時刻(compile time)決定。如果讓編譯器在運行時決定某個策略，那么就是動態(tài)策略(dynamic policy)，或者被認為是運行時決定(run time)。

還有一個問題是聲明的作用域(scope)，如果能夠通過閱讀程序就能確定一個聲明的作用域，那么這個語言就是靜態(tài)作用域(static scope)，或者說是詞法作用域(lexical scope)。否則這個語言使用的是動態(tài)作用域(dynamic scope)。動態(tài)作用域的指向?qū)ο笫菐讉€聲明中的一個，并不惟一。

C 和 Java 都使用了靜態(tài)作用域，比如 Java 中的static關(guān)鍵字，下面是一段代碼示例

publicstaticintx;

這段代碼在創(chuàng)建完成后就能夠確定它的作用域，因為 static 聲明的變量是類變量，類變量的實例能確保只有一個個（不太清楚的小伙伴可以參考我的這篇文章都說變量有七八種，到底誰是 Java 的親兒子）

如果你去掉了 static ，那么這個變量的作用域和在內(nèi)存中的分配就無法確定，編譯器無法在運行之前確定所有這些位置。

靜態(tài)綁定和動態(tài)綁定

同樣的，名字到位置也區(qū)分靜態(tài)綁定和動態(tài)綁定，如果能在非運行條件下唯一確定名字到位置，那么就是靜態(tài)綁定，如果要在程序運行時才能確定名字和位置的綁定，那么就是動態(tài)綁定。

靜態(tài)作用域和塊結(jié)構(gòu)

大多數(shù)編程語言都提供了作用域這么一個結(jié)構(gòu)，比如 Java 中的private,protected,public等關(guān)鍵字的使用，提供了有效的作用域控制。

塊結(jié)構(gòu)也是一種作用域，使用塊結(jié)構(gòu)表示的含義是在塊內(nèi)部(block)作用范圍有效，塊使用{}來界定一個塊。

這種語法允許在任意函數(shù)或者方法的內(nèi)部嵌入一個塊，這種嵌套結(jié)構(gòu)也被稱為塊結(jié)構(gòu)(block structure)。

參數(shù)傳遞機制

參數(shù)傳遞機制主要描述的是形式參數(shù)和實際參數(shù)的關(guān)聯(lián)。大多數(shù)編程語言都支持兩種調(diào)用：值傳遞和引用傳遞

值傳遞

在值傳遞(call-by-value)中，會對實參求值或拷貝，這些值被放在屬于被調(diào)用的形式參數(shù)的內(nèi)存位置上，這種調(diào)用方式在 C 和 Java 中都會使用，值調(diào)用的結(jié)果是，實參本身不會改變。但是在 C 中，我們可以傳遞一個指針，使得變量的值能夠被修改。

引用傳遞

在引用傳遞(call-by-reference)中，實際參數(shù)的地址作為相應(yīng)的形式參數(shù)的值被傳遞給調(diào)用者。在被調(diào)用者的代碼中使用形式參數(shù)，實現(xiàn)方法是沿著這個指針找到調(diào)用者指明的內(nèi)存位置。因此，改變實際參數(shù)相當(dāng)于改變了形式參數(shù)。

原文標(biāo)題：為什么編譯原理被稱為龍書？

文章出處：【微信公眾號：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。