前　　言
Crafting a Compiler

自1988年費(fèi)希爾和勒布朗合著的Crafting a Compiler出版以來，情況已經(jīng)發(fā)生了很大變化。雖然教師可能還記得那本書保存在5.25英寸軟盤上的附帶軟件，但現(xiàn)在的大多數(shù)學(xué)生既未曾擁有過也沒有見過這樣的軟盤。學(xué)生在課堂上和課外所體驗(yàn)的編程語言發(fā)生了許多變化。1991年，這本書以兩種形式出現(xiàn)，其中的算法用C語言或Ada語言呈現(xiàn)。雖然現(xiàn)在C語言仍然是一種流行的語言，但Ada語言已經(jīng)變得鮮為人知，沒有達(dá)到預(yù)期的流行程度。C 語言從C語言發(fā)展而來，加入了面向?qū)ο蟮奶匦�。Java是作為一種更簡(jiǎn)單的面向?qū)ο笳Z言開發(fā)的，因其安全性和能在Web瀏覽器中運(yùn)行而受到歡迎。美國(guó)大學(xué)理事會(huì)指定的大學(xué)先修課程已從Pascal改為C ，而后又改為Java。

雖然發(fā)生了很多變化，但學(xué)生還在繼續(xù)學(xué)習(xí)、教師也還在繼續(xù)教授編譯器構(gòu)造這一課程。編譯器和編程語言翻譯領(lǐng)域的研究繼續(xù)快步前進(jìn)，這是因?yàn)榫幾g器以適應(yīng)日益多樣化的體系結(jié)構(gòu)和編程語言為己任。軟件開發(fā)環(huán)境也依賴于編譯器與各種軟件工具鏈組件（如語法感知編輯器、性能剖析工具和調(diào)試器）的成功互動(dòng)。所有的現(xiàn)代軟件都依賴于編譯器來嚴(yán)格檢查錯(cuò)誤并忠實(shí)地翻譯程序。

隨著時(shí)間的推移，一些教科書經(jīng)歷了相對(duì)較小的變化，可能增加了一些新的習(xí)題或示例。而本書則反映了1988年到1991年期間素材的大量實(shí)質(zhì)性的修訂。雖然本書的重點(diǎn)仍然是講授編譯器結(jié)構(gòu)的基本原理，但算法和方法層面已融入最新實(shí)踐：

● 已經(jīng)從實(shí)際應(yīng)用中消失的主題（例如，屬性文法）的相關(guān)內(nèi)容已被盡量壓縮或完全刪除。
● 算法以偽代碼（pseudocode）的形式呈現(xiàn)，這對(duì)于學(xué)習(xí)過本學(xué)科基本算法的學(xué)生來說應(yīng)該很熟悉。偽代碼使對(duì)算法的簡(jiǎn)明表述及對(duì)算法的目的和構(gòu)造的合理討論成為可能。
用特定語言實(shí)現(xiàn)這些算法的細(xì)節(jié)已歸入Crafting a Compiler Supplement，該補(bǔ)充材料可在線獲取，網(wǎng)址為http://www.pearsonhighered.com/fischer/。
● 調(diào)整了語法分析理論和實(shí)踐的組織方式，以適用于各種教學(xué)方法。
有些學(xué)生可能會(huì)在較高層次上學(xué)習(xí)這部分內(nèi)容，以獲得自頂向下和自底向上語法分析的寬廣視野。其他學(xué)生可以更詳細(xì)地研究特定的方法。
● 編譯器的前端和后端由抽象語法樹（Abstract Syntax Tree，AST）銜接，AST是作為語法分析的主要產(chǎn)出而創(chuàng)建的。大多數(shù)編譯器都會(huì)構(gòu)建AST，但是鮮有教科書闡明AST的構(gòu)造和用法。
引入了訪問者模式（visitor pattern），以便在語義分析和代碼生成期間遍歷AST。
● 提供了實(shí)驗(yàn)室練習(xí)供教師使用。
教師可以將其中的一部分作為學(xué)生的練習(xí)，而其他部分則可從我們的課程支持網(wǎng)站
獲得。

有些教科書經(jīng)過修訂，增加了更多的研究生水平的素材。雖然這些內(nèi)容在高級(jí)課程中可能有用，但本書的主要讀者仍然是學(xué)習(xí)編譯器構(gòu)造的本科生。研究生課程可以使用第13章和第14章的內(nèi)容，并將前面的部分作為參考材料。

偽代碼和縮寫
本書的一個(gè)重要變化是，算法不再以任何特定的編程語言（如C或Ada）呈現(xiàn)，而是以偽代碼的形式呈現(xiàn)，所使用的風(fēng)格對(duì)于那些研究過最基本算法的人來說應(yīng)該是熟悉的[CLRS01]。偽代碼通過省略不必要的細(xì)節(jié)來簡(jiǎn)化算法的描述。然而，偽代碼暗示了實(shí)際編程語言中使用的結(jié)構(gòu)，因此實(shí)現(xiàn)應(yīng)該是直接的。本書廣泛使用縮寫（包括首字母縮寫）來簡(jiǎn)化描述，并幫助讀者掌握編譯器構(gòu)造中使用的術(shù)語。例如，在前言中已經(jīng)使用了AST作為抽象語法樹的縮寫。

本書的使用方法
關(guān)于編譯器構(gòu)造的入門課程可以從第1～3章開始。關(guān)于語法分析技術(shù)，可以選擇自頂向下語法分析（第5章）或自底向上語法分析（第6章），但有些教師會(huì)選擇同時(shí)介紹這兩種方法�？梢愿鶕�(jù)需要講授第4章的內(nèi)容，以支持將要學(xué)習(xí)的語法分析技術(shù)。第7章闡述了AST并給出了遍歷AST的訪問者模式。第8章和第9章介紹語義分析的各個(gè)方面，教師可自行決定講授哪些內(nèi)容。如果是一學(xué)期的課程，則可就此結(jié)束。如果是一學(xué)年的課時(shí)，則可繼續(xù)學(xué)習(xí)代碼生成，如下所述。

第10章介紹Java虛擬機(jī)（Java Virtual Machine，JVM），如果學(xué)生要在他們的項(xiàng)目中生成JVM代碼，就應(yīng)講授這些內(nèi)容。第11章介紹虛擬機(jī)代碼生成。希望學(xué)生生成機(jī)器代碼的教師可以跳過第10章和第11章，而只講第12章和第13章。入門課程可以包括第14章開始部分有關(guān)自動(dòng)程序優(yōu)化的內(nèi)容。

第4～6章中涉及語法分析技術(shù)的更多細(xì)節(jié)。第8章和第9章對(duì)類型檢查和語義分析進(jìn)行了廣泛和深入的研究。第10章和第14章介紹高級(jí)概念，如靜態(tài)單賦值（Static Single Assignment，SSA）形式等。第14章涉及程序分析和轉(zhuǎn)換的高級(jí)主題，包括數(shù)據(jù)流框架。第13章和第14章可以作為研究生編譯器課程的基礎(chǔ)，輔以前面的章節(jié)作為參考材料。

各章概述

第1章　引言
該章首先概述了編譯過程。強(qiáng)調(diào)從一組組件來構(gòu)造編譯器的概念。概述了編譯器的歷史，并介紹了生成編譯器組件的工具的使用方法。

第2章　一個(gè)簡(jiǎn)單的編譯器
該章介紹了簡(jiǎn)單語言ac，并討論了將ac轉(zhuǎn)換為另一種語言dc的編譯器的每個(gè)組件。這些組件以偽代碼的形式呈現(xiàn)，完整的代碼可以在Crafting a Compiler Supplement中找到。

第3章　詞法分析理論與實(shí)踐
該章介紹了構(gòu)建編譯器詞法分析組件的基本概念和技術(shù)。具體內(nèi)容包括如何手工編寫詞法分析器以及使用詞法分析器生成器來實(shí)現(xiàn)表驅(qū)動(dòng)的詞法分析器。

第4章　文法和語法分析
該章涵蓋了形式語言的基本概念，包括上下文無關(guān)文法、文法表示、推導(dǎo)以及語法分析樹，還介紹了第5章和第6章中將使用的文法分析算法。

第5章　自頂向下語法分析
自頂向下語法分析是構(gòu)造相對(duì)簡(jiǎn)單的語法分析器的一種流行技術(shù)。該章展示了如何使用顯式代碼或通過構(gòu)造供通用自頂向下語法分析引擎使用的分析表來編寫這樣的語法分析器。該章還討論了語法錯(cuò)誤的診斷、恢復(fù)和修復(fù)。

第6章　自底向上語法分析
大多數(shù)現(xiàn)代編程語言編譯器使用該章介紹的某種自底向上語法分析技術(shù)。從上下文無關(guān)文法自動(dòng)生成這種語法分析器的工具廣泛可用。該章描述了構(gòu)建這些工具的理論，包括一系列日益復(fù)雜的方法，這些方法用來解決阻礙從某些文法構(gòu)建語法分析器的沖突（conflict）。該章還深入討論了文法和語言的二義性（ambiguity），并提出了理解和解決二義性文法的啟發(fā)式方法。

第7章　語法制導(dǎo)翻譯
從編譯器構(gòu)成組件的角度，該章標(biāo)志著本書的中點(diǎn)。前面的章節(jié)已經(jīng)介紹了程序的詞法分析和語法分析。這些章節(jié)的目標(biāo)是構(gòu)造AST。該章介紹AST并闡述用于構(gòu)造、管理和遍歷AST的接口。該章是非常關(guān)鍵的，因?yàn)楹罄m(xù)章節(jié)既依賴于理解AST，也依賴于理解促進(jìn)AST的遍歷和處理的訪問者模式。Crafting a Compiler Supplement包含了一個(gè)關(guān)于訪問者模式的教程，包括從常見實(shí)踐經(jīng)驗(yàn)中提取的示例。

第8章　符號(hào)表和聲明處理
該章強(qiáng)調(diào)使用符號(hào)表作為一個(gè)抽象組件，可在整個(gè)編譯過程中使用。為符號(hào)表定義了一個(gè)精確的接口，并提出了各種實(shí)現(xiàn)問題和解決思路，其中包括對(duì)嵌套作用域?qū)崿F(xiàn)的討論。

該章還介紹了處理符號(hào)聲明所需的語義分析，包括類型、變量、數(shù)組、結(jié)構(gòu)和枚舉，同時(shí)介紹了類型檢查，包括面向?qū)ο箢�、子類和超類�?/p>

第9章　語義分析
對(duì)于在語法分析時(shí)不容易檢查的語言規(guī)范，需要進(jìn)行額外的語義分析，包括檢查各種控制結(jié)構(gòu)，如條件分支和循環(huán)。該章還討論了異常及其在編譯時(shí)所需的語義分析。

第10章　中間表示
該章介紹了編譯器廣泛使用的兩種中間表示。第一種是JVM指令集和字節(jié)碼格式，它已經(jīng)成為表示Java程序編譯結(jié)果的標(biāo)準(zhǔn)格式。對(duì)于有興趣在編譯器項(xiàng)目中使用JVM的讀者，第10章和第11章提供了必要的背景知識(shí)和技術(shù)。另一種表示是SSA形式，它被許多優(yōu)化編譯器使用。該章定義了SSA形式，但要等到第14章才會(huì)介紹它的構(gòu)造，并給出一些必要的定義和算法。

第11章　虛擬機(jī)代碼生成
該章討論針對(duì)虛擬機(jī)（Virtual Machine，VM）的代碼生成。這種目標(biāo)平臺(tái)的優(yōu)點(diǎn)是，運(yùn)行時(shí)支持的許多細(xì)節(jié)都包含在VM中。例如，大多數(shù)VM提供無限數(shù)目的寄存器，因此盡管寄存器分配（register allocation）問題很有趣，但可以推遲到掌握了代碼生成的基本知識(shí)之后再討論。而且，虛擬機(jī)的指令集通常處于比機(jī)器碼更高的級(jí)別。例如，一個(gè)方法調(diào)用通常由單個(gè)VM指令支持，而相同的調(diào)用用機(jī)器代碼實(shí)現(xiàn)可能需要更多指令。

雖然對(duì)生成機(jī)器碼感興趣的讀者可能會(huì)跳過第11章，但我們建議先學(xué)習(xí)這一章，然后再嘗試生成機(jī)器碼級(jí)別的代碼。第11章的思想很容易應(yīng)用于第12章和第13章，但從VM的角度來看，它們更容易理解。

第12章　運(yùn)行時(shí)支持
在VM中嵌入的許多功能都是對(duì)運(yùn)行時(shí)的支持（例如，對(duì)管理存儲(chǔ)的支持）。該章討論為現(xiàn)代編程語言提供所需的運(yùn)行時(shí)支持的各種概念和實(shí)現(xiàn)策略。研究這些內(nèi)容有助于理解虛擬機(jī)的構(gòu)造。對(duì)于那些為目標(biāo)體系結(jié)構(gòu)編寫代碼生成器的人，必須提供運(yùn)行時(shí)支持，因此學(xué)習(xí)第12章的內(nèi)容對(duì)于創(chuàng)建一個(gè)可工作的編譯器來說是必不可少的。
該章討論了靜態(tài)分配存儲(chǔ)、棧分配存儲(chǔ)和堆分配存儲(chǔ)，還討論了對(duì)非局部存儲(chǔ)（nonlocal storage）的引用，以及支持此類引用的幀和顯示表等實(shí)現(xiàn)結(jié)構(gòu)。

第13章　目標(biāo)代碼生成
該章與第11章相似，區(qū)別是代碼生成的目標(biāo)與VM相比是相對(duì)低級(jí)的指令集。這一章全面討論了代碼生成中產(chǎn)生的主題，包括寄存器分配、臨時(shí)變量管理、代碼調(diào)度、指令選擇和一些基本的窺孔優(yōu)化。

第14章　程序優(yōu)化
大多數(shù)編譯器都包含一些改進(jìn)它們生成的代碼的功能。該章介紹編譯器在程序優(yōu)化中常用的一些實(shí)用技術(shù)，還介紹了進(jìn)階的控制流分析結(jié)構(gòu)和算法。通過一些相對(duì)容易實(shí)現(xiàn)的基本優(yōu)化，介紹了數(shù)據(jù)流分析（data flow analysis）。研究了此類優(yōu)化的理論基礎(chǔ)，并討論了SSA形式的構(gòu)造和使用。