你管這叫屠龍之技？
碎碎念
為什么這本書叫做 龍書(Dragon book)？
這本書很有意思，它的書名是 《Compilers: Principles, Techniques, and Tools》，也就是編譯器的原則、技術(shù)和工具。但它卻畫出了一個(gè)恐龍和騎士，恐龍身上寫的是 Complexity of Compiler Design，也就是復(fù)雜的編譯器設(shè)計(jì)，騎士的盾上寫的是 Syntax Directed Granslation，也就是語(yǔ)法翻譯。騎士的劍上看的不是很清楚，我猜測(cè)應(yīng)該是優(yōu)秀的編譯器的意思。這是征服復(fù)雜性的隱喻。優(yōu)秀的編譯器會(huì)直接征服復(fù)雜的編譯，復(fù)雜的編譯設(shè)計(jì)永遠(yuǎn)無(wú)法攻破語(yǔ)法翻譯。
什么是編譯原理
計(jì)算機(jī)是只認(rèn)識(shí)二進(jìn)制的，但是我們平常開發(fā)中根本不會(huì)使用二進(jìn)制進(jìn)行開發(fā)，我們使用的都是 Java、C 這類的高級(jí)語(yǔ)言，每種語(yǔ)言都會(huì)經(jīng)過(guò)一系列的轉(zhuǎn)換才能被計(jì)算機(jī)識(shí)別，那么到底是誰(shuí)做的這項(xiàng)工作呢？一個(gè)被稱為 編譯器(compiler) 的大佬出場(chǎng)了。
語(yǔ)言處理器
首先考慮一下一個(gè)例子，你如何才能和老外對(duì)話？你是不是需要學(xué)英語(yǔ)？我們有一些同學(xué)可能認(rèn)為英語(yǔ)難學(xué)，經(jīng)常會(huì)在英語(yǔ)書上做一些漢語(yǔ)標(biāo)記方便理解。
那么，誰(shuí)做了由英語(yǔ)到方便記憶 的英語(yǔ)之間的轉(zhuǎn)換呢？答案是你的大腦。所以，我們可以歸納一下這個(gè)過(guò)程。
因?yàn)槲覀兌疂h語(yǔ)（自己的一套語(yǔ)法規(guī)則），我們把英語(yǔ)（需要學(xué)習(xí)的語(yǔ)言）轉(zhuǎn)換為我們便于理解的漢語(yǔ)（大腦翻譯規(guī)則），我們才能學(xué)會(huì)英語(yǔ)和老外對(duì)話（轉(zhuǎn)換為目標(biāo)語(yǔ)言）。
這里我說(shuō)一點(diǎn)：昨天晚上外出遛狗有個(gè)老黑和中國(guó)女生對(duì)話，中國(guó)女生竟然講英文？？？？？？這可是中國(guó)本土好么，為什么外國(guó)人來(lái)到中國(guó)不講漢語(yǔ)偏要中國(guó)人講英文？？？你去外國(guó)旅游你會(huì)講中文嗎？？？這是一個(gè)基本認(rèn)知問(wèn)題，別怪我偏執(zhí)。我認(rèn)為外國(guó)人要來(lái)我們國(guó)家最基本的一點(diǎn)就是：你要學(xué)中文，千萬(wàn)不要抱著英語(yǔ)為上的心態(tài)，漢語(yǔ)不輸任何語(yǔ)言。
回到正題，我們上面舉出的這個(gè)學(xué)英語(yǔ)的例子，其實(shí)就是一個(gè)由原程序經(jīng)過(guò)某種機(jī)制轉(zhuǎn)換，把它變成目標(biāo)語(yǔ)言的過(guò)程。也就是
編譯器就是一個(gè)翻譯官的角色，它負(fù)責(zé)把源程序的語(yǔ)法翻譯成目標(biāo)程序能夠理解的語(yǔ)法。
回到計(jì)算機(jī)中，我們肯定需要目標(biāo)程序來(lái)做一些事情的。
也就是，我們通過(guò)某個(gè)渠道獲得的輸入信息，會(huì)經(jīng)過(guò)編譯器的轉(zhuǎn)換，變?yōu)檩敵鲂畔⑦M(jìn)行展示。
除了編譯器之外，還有一種稱為 解釋器(interpreter) 的語(yǔ)言處理器，它不是做翻譯工作的，而是把用戶提供的輸入執(zhí)行源程序中指定的操作。
我們熟知的 Java 語(yǔ)言，就結(jié)合了編譯和解釋的過(guò)程，我們寫的 Java 源文件首先被編譯成 字節(jié)碼(bytecode)，字節(jié)碼是一種中間碼，它通常被看成是可執(zhí)行的二進(jìn)制文件。然后再由 Java 虛擬機(jī)對(duì)字節(jié)碼解釋執(zhí)行。這樣，在一臺(tái)機(jī)器上編譯的字節(jié)碼就能夠在其他機(jī)器上解釋執(zhí)行，這種體現(xiàn)了 Java 語(yǔ)言的平臺(tái)無(wú)關(guān)性。
為了提高編譯速度，Java 中有一種 just-in-time,JIT 即時(shí)編譯器會(huì)一邊編譯一邊執(zhí)行。
一個(gè)源文件程序可能被劃分為多個(gè)模塊，并存放在多個(gè)文件中，還需要把文件鏈接在一起，所以，除了編譯器之外，還需要一種能鏈接文件的部件參與，預(yù)處理器(preprossor) 是做這件事情的。如下圖所示
預(yù)處理器經(jīng)過(guò)預(yù)處理后會(huì)作為輸入傳遞給編譯器，編譯器對(duì)源程序進(jìn)行編譯，編譯完成后生成匯編代碼，作為匯編器的輸入傳遞給匯編器，匯編器進(jìn)行匯編處理轉(zhuǎn)換為機(jī)器代碼，注意這個(gè)時(shí)候還不是目標(biāo)代碼，還要經(jīng)過(guò)鏈接器與系統(tǒng)庫(kù)函數(shù)進(jìn)行鏈接，最后由加載器把目標(biāo)代碼加載到內(nèi)存中執(zhí)行
編譯器的結(jié)構(gòu)
我們上面大概了解了一下語(yǔ)言的處理過(guò)程，下面我們就來(lái)了解一下編譯器的內(nèi)部結(jié)構(gòu)，編譯器內(nèi)部其實(shí)具有兩種結(jié)構(gòu)：分析(analysis)部分和 整合(synthesis) 部分。
分析過(guò)程相當(dāng)于是把源程序分成多個(gè)結(jié)構(gòu)，每個(gè)結(jié)構(gòu)都有特定的語(yǔ)法格式進(jìn)行校驗(yàn)，在經(jīng)由每個(gè)校驗(yàn)后，如果不滿足指定的語(yǔ)法格式則進(jìn)行提醒，使用戶進(jìn)行修改。分析部分還會(huì)收集有關(guān)源程序的信息，會(huì)把收集到的信息存放在一個(gè)被稱為 符號(hào)表(symbol table) 的數(shù)據(jù)結(jié)構(gòu)中。符號(hào)表和中間表示形式一起傳給整合部分。
整合過(guò)程是根據(jù)分析過(guò)程傳遞的信息來(lái)構(gòu)造用戶期待的目標(biāo)程序。分析和整合統(tǒng)稱為 前端(front end) 和 后端(back end) ，哈哈哈哈。
這里你需要知道符號(hào)表(Symbol Table) 的概念：符號(hào)表是編譯器使用和維護(hù)的數(shù)據(jù)結(jié)構(gòu)，由標(biāo)識(shí)符和類型組成。符號(hào)表的主要作用是幫助編譯器快速定位。
下面是一個(gè)編譯器的典型結(jié)構(gòu)
下面我們就針對(duì)編譯器結(jié)構(gòu)的每一層進(jìn)行描述和討論
詞法分析
詞法分析(Lexical Analyzer)是編譯器的第一個(gè)步驟，它也被稱為 掃描(scanning)。詞法分析器通過(guò)讀入外部的字符流對(duì)其進(jìn)行掃描，并且把它們組成有意義的詞素(lexeme)序列，對(duì)于每個(gè)詞素，詞法分析器都會(huì)產(chǎn)生詞法單元(token) 作為輸出。這個(gè)詞法單元會(huì)傳遞給下一個(gè)步驟，也就是語(yǔ)法分析。
這里需要解釋一下 Token 、詞素和詞法分析器的概念
我們常用的編程語(yǔ)言就是具有詞素的單詞和符號(hào)的集合，比如 C 語(yǔ)言中有 ()，-> 等等。關(guān)鍵字 if...while...，變量或函數(shù)名稱以及數(shù)字和字符串常量也被視為詞素。并不是所有的自負(fù)都屬于詞素，例如空格和注釋就不屬于。
詞法分析器用來(lái)分析詞素有兩個(gè)規(guī)則
跳過(guò)不能以字母開頭的字符 然后找到剩余的最長(zhǎng)前綴，也就是詞素
這兩句話比較抽象，舉個(gè)例子來(lái)說(shuō)明一下
比如 C 語(yǔ)言中有這么一個(gè)語(yǔ)句
ifx = 20*30;
那么第一個(gè)詞素就是 ifx，為什么不是 if 呢？因?yàn)?if 不是最長(zhǎng)的前綴。然后后面的詞素依次是 =，20，*，30和；。
詞素、詞法分析器、token 的關(guān)系如下
詞素是 Token 的實(shí)例，詞法分析器的主要任務(wù)就是從源程序中讀取字符并產(chǎn)生 token。token 也是有結(jié)構(gòu)的，一般結(jié)構(gòu)如下
在詞法分析生成的 token 中，第一個(gè)詞 token-name 是語(yǔ)法分析期間使用的抽象符號(hào)，第二個(gè)詞 attribute-value 指向的是符號(hào)表中關(guān)于這個(gè)詞法單元的條目數(shù)。
我們舉個(gè)例子來(lái)看一下詞法分析的拆解過(guò)程。
比如現(xiàn)在源程序中有一個(gè)賦值語(yǔ)句
income = mainjob + sideline // 收入 = 主業(yè) + 副業(yè)
這個(gè)賦值語(yǔ)句中的字符可以組合成如下詞素，并轉(zhuǎn)換成為 token，并傳遞給語(yǔ)法分析階段。
首先，income 是一個(gè)詞素，它會(huì)被映射為 <id,1>，其中 id 是表示的
標(biāo)識(shí)符(identifier)的抽象符號(hào)，而 1 指的是符號(hào)表中 income 在符號(hào)表中的條數(shù)。然后是賦值符號(hào) = ，它也是一個(gè)詞素，被映射稱為 token 中的 < = >。這個(gè) token 不需要屬性值，所以沒(méi)有第二個(gè)詞。
mainjob 是一個(gè)詞素，它被映射成為 token 中的 <id,2>，2 是 mainjob 對(duì)應(yīng)的符號(hào)表?xiàng)l目
+也是一個(gè)詞素，它被映射稱為 < + >，沒(méi)有條目數(shù)
sideline 是一個(gè)詞素，它被映射稱為 token 中的 <id,3>，3 是 sideline 對(duì)應(yīng)的符號(hào)表?xiàng)l目
所以，經(jīng)過(guò)詞法分析后，上面的源程序會(huì)變?yōu)?/p>
<id,1> < = > <id,2> < + > <id,3>
在上面的表達(dá)式中， = 和 + 分別表示賦值和加法運(yùn)算符的抽象符號(hào)。用圖來(lái)表示的話就是
語(yǔ)法分析
編譯器的第二個(gè)步驟是 語(yǔ)法分析(syntax analysis) 或者稱為 解析(parsing)。語(yǔ)法分析器使用由詞法分析器生成的各個(gè)詞法單元的第一個(gè)分量來(lái)創(chuàng)建樹形的中間表示。常用的方法就是 語(yǔ)法樹(syntax tree)。編譯器的后續(xù)步驟都會(huì)使用這個(gè)語(yǔ)法結(jié)構(gòu)來(lái)幫助分析源程序，并生成目標(biāo)程序。
語(yǔ)義分析
語(yǔ)義分析是由 語(yǔ)義分析器(semantic analyzer) 完成的，它使用語(yǔ)法樹和符號(hào)表中的信息來(lái)檢查源程序是否和語(yǔ)言定義的語(yǔ)義一致。語(yǔ)義分析器也收集類型信息，并把這些信息放在語(yǔ)法樹或者符號(hào)表中，以便后續(xù)的中間代碼生成器使用。
語(yǔ)義分析會(huì)進(jìn)行類型檢查(type checking)，這是語(yǔ)義分析器的一個(gè)最重要的功能。編譯器會(huì)檢查每個(gè)運(yùn)算符是否具有匹配的運(yùn)算分量。舉個(gè)例子比如設(shè)計(jì)語(yǔ)言要求一個(gè)數(shù)組的下標(biāo)是整數(shù)，如果你用浮點(diǎn)數(shù)作為下標(biāo)，編譯器就會(huì)出錯(cuò)。
某些程序設(shè)計(jì)語(yǔ)言比如 Java 會(huì)允許自動(dòng)類型轉(zhuǎn)換(coercion)。如果整數(shù)和浮點(diǎn)數(shù)進(jìn)行運(yùn)算，編譯器會(huì)把整數(shù)轉(zhuǎn)換為浮點(diǎn)數(shù)。
中間代碼生成
在源程序的語(yǔ)法分析和語(yǔ)義分析完成后，很多編譯器生成一個(gè)明確的低級(jí)類機(jī)器語(yǔ)言的中間表示。我們可以把中間表示形式看作是抽象，中間形式的代碼應(yīng)該具有兩個(gè)重要的性質(zhì)：易于生成，并且能夠輕松的被翻譯。一般常用的一種是 三地址指令(three-address instructions)的中間表示形式。我們后面會(huì)細(xì)說(shuō)。
代碼優(yōu)化
代碼優(yōu)化會(huì)試圖改進(jìn)代碼以便生成更好的目標(biāo)代碼。更好通常情況下意味著更快，但是也可能會(huì)有其他目標(biāo)，比如更短或能耗更低的目標(biāo)代碼。
代碼生成
代碼生成通過(guò)中間代碼作為輸入，并把它映射為目標(biāo)語(yǔ)言。如果目標(biāo)語(yǔ)言是機(jī)器代碼的話，那么必須要為每個(gè)變量分配寄存器或內(nèi)存位置。解釋一下上面的運(yùn)行結(jié)果。
每個(gè)指令的第一個(gè)運(yùn)算分量指定了一個(gè)目標(biāo)地址，各個(gè)指令中的 F 告訴我們它處理的是 浮點(diǎn)數(shù), 上面代碼首先把 id3 裝載進(jìn) R2 寄存器中，然后把 id2 裝載進(jìn) R1 寄存器中，再對(duì) R1 目標(biāo)進(jìn)行 R1 和 R2 寄存器相加的操作。最后把寄存器 R1 的值存放到 id1 的地址中。
符號(hào)表管理
我們上面提到了符號(hào)表的概念，它是一個(gè)編譯器很重要的功能。符號(hào)表能夠記錄源程序中使用變量的名稱，并收集和每個(gè)名稱相關(guān)的屬性信息。它相當(dāng)于一個(gè)秘書的作用。符號(hào)表還記錄了每個(gè)變量名字的條目。后面我們會(huì)詳細(xì)的介紹符號(hào)表。
編譯器構(gòu)造工具
和軟件開發(fā)一樣，寫編譯器的人可以充分利用現(xiàn)代的軟件開發(fā)環(huán)境進(jìn)行開發(fā)。通常也有 語(yǔ)言編輯器、調(diào)試工具、版本管理、測(cè)試工具等。除此之外，還需要一些更專業(yè)的工具來(lái)實(shí)現(xiàn)編輯器不同階段的代碼生成。
一些常用的編譯器構(gòu)造工具有
語(yǔ)法分析器生成器：可以根據(jù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述自動(dòng)生成語(yǔ)法分析器 掃描器生成器：可以根據(jù)一個(gè)語(yǔ)言的語(yǔ)法單元的正則描述生成詞法分析器 語(yǔ)法制導(dǎo)的翻譯引擎：用于生成一組遍歷分析樹并生成中間代碼 代碼生成器：用于把中間代碼轉(zhuǎn)換為目標(biāo)代碼 數(shù)據(jù)流分析引擎：用于分析輸入是如何傳遞到另一部分的 編譯器構(gòu)造工具：提供用于構(gòu)造編譯器不同階段的例程
程序設(shè)計(jì)語(yǔ)言的發(fā)展歷程
計(jì)算機(jī)從 20 世紀(jì) 40 年代創(chuàng)建至今都只能理解二進(jìn)制語(yǔ)言，亙古不變。這個(gè) 0 、 1 組成的序列能夠告訴計(jì)算機(jī)以什么樣的順序執(zhí)行怎樣的運(yùn)算。運(yùn)算本身是很底層的：比如把一個(gè)數(shù)據(jù)從一個(gè)位置進(jìn)行移動(dòng)；把兩個(gè)寄存器的內(nèi)容進(jìn)行相加、比較兩個(gè)值，為了避免如此枯燥的運(yùn)算，我們開發(fā)了各種各樣的編程語(yǔ)言，但是計(jì)算機(jī)底層的計(jì)算方式一直沒(méi)變，所以學(xué)習(xí)哪個(gè)技術(shù)性價(jià)比高，明白了嗎？下面我們就來(lái)一起認(rèn)識(shí)一下程序設(shè)計(jì)語(yǔ)言的歷程。
高級(jí)設(shè)計(jì)語(yǔ)言
首先被開發(fā)出來(lái)的是 20 世紀(jì) 50 年代的匯編語(yǔ)言，5 年后發(fā)生了重要的進(jìn)步，用于科學(xué)計(jì)算的 Fortran 被開發(fā)出來(lái)，用于商業(yè)處理的 Cobol 語(yǔ)言和用于符號(hào)計(jì)算的 Lisp 語(yǔ)言被開發(fā)出來(lái)；然后接下來(lái)的時(shí)間，慢慢很多編程語(yǔ)言被開發(fā)出來(lái)，比如 C、C++、Java、JavaScript、Python 等。后面還有用于數(shù)據(jù)處理的 SQL 語(yǔ)言。
語(yǔ)言分類
說(shuō)到給這些編程語(yǔ)言分類，那可是有太多了，不過(guò)我們專注一下高頻的分類。
如何完成計(jì)算任務(wù)的語(yǔ)言稱為 強(qiáng)制式(imperative)語(yǔ)言，而把程序中指明要進(jìn)行哪些計(jì)算的語(yǔ)言稱為 聲明式(declarative)語(yǔ)言。C、C++、Java 這些都是強(qiáng)制式語(yǔ)言，它們能夠改變程序的狀態(tài)；聲明式比如 HTML Prolog 等。
馮·諾伊曼 語(yǔ)言指的是以馮·諾伊曼計(jì)算機(jī)體系為基礎(chǔ)的編程語(yǔ)言，今天很多編程語(yǔ)言都是馮·諾伊曼語(yǔ)言
面向?qū)ο笳Z(yǔ)言(object-oriented language) 是一種描述對(duì)象的語(yǔ)言，比如 C、C++、Java
腳本語(yǔ)言(scripting language) 是具有高層次的解釋型語(yǔ)言，它通常把多個(gè)過(guò)程粘在一起，比如 JavaScript、Perl、PHP、Python 等。
程序設(shè)計(jì)語(yǔ)言基礎(chǔ)
下面我們主要探討程序設(shè)計(jì)語(yǔ)言的研究中最重要的術(shù)語(yǔ)和它們的區(qū)別，假設(shè)讀者已經(jīng)了解過(guò) C、C++、C#、Java 中任意一種語(yǔ)言。
靜態(tài)和動(dòng)態(tài)的區(qū)別
編譯器需要能夠?qū)Τ绦蜃鞒雠卸ǎ绻Z(yǔ)言能夠讓編譯器靜態(tài)（非運(yùn)行）時(shí)候決定某個(gè)問(wèn)題，那么我們說(shuō)這個(gè)語(yǔ)言使用了一種 靜態(tài)(static) 策略，或者說(shuō)能夠在 編譯時(shí)刻(compile time) 決定。如果讓編譯器在運(yùn)行時(shí)決定某個(gè)策略，那么就是動(dòng)態(tài)策略(dynamic policy)，或者被認(rèn)為是 運(yùn)行時(shí)決定(run time) 。
還有一個(gè)問(wèn)題是聲明的作用域(scope)，如果能夠通過(guò)閱讀程序就能確定一個(gè)聲明的作用域，那么這個(gè)語(yǔ)言就是靜態(tài)作用域(static scope)，或者說(shuō)是 詞法作用域(lexical scope)。否則這個(gè)語(yǔ)言使用的是 動(dòng)態(tài)作用域(dynamic scope)。動(dòng)態(tài)作用域的指向?qū)ο笫菐讉€(gè)聲明中的一個(gè)，并不惟一。
C 和 Java 都使用了靜態(tài)作用域，比如 Java 中的 static 關(guān)鍵字，下面是一段代碼示例
public static int x;
這段代碼在創(chuàng)建完成后就能夠確定它的作用域，因?yàn)?static 聲明的變量是類變量，類變量的實(shí)例能確保只有一個(gè)個(gè)（不太清楚的小伙伴可以參考我的這篇文章 都說(shuō)變量有七八種，到底誰(shuí)是 Java 的親兒子）
如果你去掉了 static ，那么這個(gè)變量的作用域和在內(nèi)存中的分配就無(wú)法確定，編譯器無(wú)法在運(yùn)行之前確定所有這些位置。
靜態(tài)綁定和動(dòng)態(tài)綁定
同樣的，名字到位置也區(qū)分靜態(tài)綁定和動(dòng)態(tài)綁定，如果能在非運(yùn)行條件下唯一確定名字到位置，那么就是靜態(tài)綁定，如果要在程序運(yùn)行時(shí)才能確定名字和位置的綁定，那么就是動(dòng)態(tài)綁定。
靜態(tài)作用域和塊結(jié)構(gòu)
大多數(shù)編程語(yǔ)言都提供了作用域這么一個(gè)結(jié)構(gòu)，比如 Java 中的 private,protected,public 等關(guān)鍵字的使用，提供了有效的作用域控制。
塊結(jié)構(gòu)也是一種作用域，使用塊結(jié)構(gòu)表示的含義是在塊內(nèi)部(block) 作用范圍有效，塊使用 {} 來(lái)界定一個(gè)塊。
這種語(yǔ)法允許在任意函數(shù)或者方法的內(nèi)部嵌入一個(gè)塊，這種嵌套結(jié)構(gòu)也被稱為
塊結(jié)構(gòu)(block structure)。
參數(shù)傳遞機(jī)制
參數(shù)傳遞機(jī)制主要描述的是形式參數(shù)和實(shí)際參數(shù)的關(guān)聯(lián)。大多數(shù)編程語(yǔ)言都支持兩種調(diào)用：值傳遞和 引用傳遞
值傳遞
在值傳遞(call-by-value) 中，會(huì)對(duì)實(shí)參求值或拷貝，這些值被放在屬于被調(diào)用的形式參數(shù)的內(nèi)存位置上，這種調(diào)用方式在 C 和 Java 中都會(huì)使用，值調(diào)用的結(jié)果是，實(shí)參本身不會(huì)改變。但是在 C 中，我們可以傳遞一個(gè)指針，使得變量的值能夠被修改。
引用傳遞
在 引用傳遞(call-by-reference) 中，實(shí)際參數(shù)的地址作為相應(yīng)的形式參數(shù)的值被傳遞給調(diào)用者。在被調(diào)用者的代碼中使用形式參數(shù)，實(shí)現(xiàn)方法是沿著這個(gè)指針找到調(diào)用者指明的內(nèi)存位置。因此，改變實(shí)際參數(shù)相當(dāng)于改變了形式參數(shù)。
完
往期推薦
??
