前 言
Crafting a Compiler
自1988年費(fèi)希爾和勒布朗合著的Crafting a Compiler出版以來，情況已經(jīng)發(fā)生了很大變化。雖然教師可能還記得那本書保存在5.25英寸軟盤上的附帶軟件，但現(xiàn)在的大多數(shù)學(xué)生既未曾擁有過也沒有見過這樣的軟盤。學(xué)生在課堂上和課外所體驗(yàn)的編程語(yǔ)言發(fā)生了許多變化。1991年，這本書以兩種形式出現(xiàn)，其中的算法用C語(yǔ)言或Ada語(yǔ)言呈現(xiàn)。雖然現(xiàn)在C語(yǔ)言仍然是一種流行的語(yǔ)言，但Ada語(yǔ)言已經(jīng)變得鮮為人知，沒有達(dá)到預(yù)期的流行程度。C 語(yǔ)言從C語(yǔ)言發(fā)展而來，加入了面向?qū)ο蟮奶匦浴ava是作為一種更簡(jiǎn)單的面向?qū)ο笳Z(yǔ)言開發(fā)的，因其安全性和能在Web瀏覽器中運(yùn)行而受到歡迎。美國(guó)大學(xué)理事會(huì)指定的大學(xué)先修課程已從Pascal改為C ，而后又改為Java。
雖然發(fā)生了很多變化，但學(xué)生還在繼續(xù)學(xué)習(xí)、教師也還在繼續(xù)教授編譯器構(gòu)造這一課程。編譯器和編程語(yǔ)言翻譯領(lǐng)域的研究繼續(xù)快步前進(jìn)，這是因?yàn)榫幾g器以適應(yīng)日益多樣化的體系結(jié)構(gòu)和編程語(yǔ)言為己任。軟件開發(fā)環(huán)境也依賴于編譯器與各種軟件工具鏈組件（如語(yǔ)法感知編輯器、性能剖析工具和調(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)造的合理討論成為可能。
用特定語(yǔ)言實(shí)現(xiàn)這些算法的細(xì)節(jié)已歸入Crafting a Compiler Supplement，該補(bǔ)充材料可在線獲取，網(wǎng)址為http://www.pearsonhighered.com/fischer/。
● 調(diào)整了語(yǔ)法分析理論和實(shí)踐的組織方式，以適用于各種教學(xué)方法。
有些學(xué)生可能會(huì)在較高層次上學(xué)習(xí)這部分內(nèi)容，以獲得自頂向下和自底向上語(yǔ)法分析的寬廣視野。其他學(xué)生可以更詳細(xì)地研究特定的方法。
● 編譯器的前端和后端由抽象語(yǔ)法樹（Abstract Syntax Tree，AST）銜接，AST是作為語(yǔ)法分析的主要產(chǎn)出而創(chuàng)建的。大多數(shù)編譯器都會(huì)構(gòu)建AST，但是鮮有教科書闡明AST的構(gòu)造和用法。
引入了訪問者模式（visitor pattern），以便在語(yǔ)義分析和代碼生成期間遍歷AST。
● 提供了實(shí)驗(yàn)室練習(xí)供教師使用。
教師可以將其中的一部分作為學(xué)生的練習(xí)，而其他部分則可從我們的課程支持網(wǎng)站
獲得。
有些教科書經(jīng)過修訂，增加了更多的研究生水平的素材。雖然這些內(nèi)容在高級(jí)課程中可能有用，但本書的主要讀者仍然是學(xué)習(xí)編譯器構(gòu)造的本科生。研究生課程可以使用第13章和第14章的內(nèi)容，并將前面的部分作為參考材料。
偽代碼和縮寫
本書的一個(gè)重要變化是，算法不再以任何特定的編程語(yǔ)言（如C或Ada）呈現(xiàn)，而是以偽代碼的形式呈現(xiàn)，所使用的風(fēng)格對(duì)于那些研究過最基本算法的人來說應(yīng)該是熟悉的[CLRS01]。偽代碼通過省略不必要的細(xì)節(jié)來簡(jiǎn)化算法的描述。然而，偽代碼暗示了實(shí)際編程語(yǔ)言中使用的結(jié)構(gòu)，因此實(shí)現(xiàn)應(yīng)該是直接的。本書廣泛使用縮寫（包括首字母縮寫）來簡(jiǎn)化描述，并幫助讀者掌握編譯器構(gòu)造中使用的術(shù)語(yǔ)。例如，在前言中已經(jīng)使用了AST作為抽象語(yǔ)法樹的縮寫。
本書的使用方法
關(guān)于編譯器構(gòu)造的入門課程可以從第1～3章開始。關(guān)于語(yǔ)法分析技術(shù)，可以選擇自頂向下語(yǔ)法分析（第5章）或自底向上語(yǔ)法分析（第6章），但有些教師會(huì)選擇同時(shí)介紹這兩種方法。可以根據(jù)需要講授第4章的內(nèi)容，以支持將要學(xué)習(xí)的語(yǔ)法分析技術(shù)。第7章闡述了AST并給出了遍歷AST的訪問者模式。第8章和第9章介紹語(yǔ)義分析的各個(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章中涉及語(yǔ)法分析技術(shù)的更多細(xì)節(jié)。第8章和第9章對(duì)類型檢查和語(yǔ)義分析進(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)單語(yǔ)言ac，并討論了將ac轉(zhuǎn)換為另一種語(yǔ)言dc的編譯器的每個(gè)組件。這些組件以偽代碼的形式呈現(xiàn)，完整的代碼可以在Crafting a Compiler Supplement中找到。
第3章 詞法分析理論與實(shí)踐
該章介紹了構(gòu)建編譯器詞法分析組件的基本概念和技術(shù)。具體內(nèi)容包括如何手工編寫詞法分析器以及使用詞法分析器生成器來實(shí)現(xiàn)表驅(qū)動(dòng)的詞法分析器。
第4章 文法和語(yǔ)法分析
該章涵蓋了形式語(yǔ)言的基本概念，包括上下文無關(guān)文法、文法表示、推導(dǎo)以及語(yǔ)法分析樹，還介紹了第5章和第6章中將使用的文法分析算法。
第5章 自頂向下語(yǔ)法分析
自頂向下語(yǔ)法分析是構(gòu)造相對(duì)簡(jiǎn)單的語(yǔ)法分析器的一種流行技術(shù)。該章展示了如何使用顯式代碼或通過構(gòu)造供通用自頂向下語(yǔ)法分析引擎使用的分析表來編寫這樣的語(yǔ)法分析器。該章還討論了語(yǔ)法錯(cuò)誤的診斷、恢復(fù)和修復(fù)。
第6章 自底向上語(yǔ)法分析
大多數(shù)現(xiàn)代編程語(yǔ)言編譯器使用該章介紹的某種自底向上語(yǔ)法分析技術(shù)。從上下文無關(guān)文法自動(dòng)生成這種語(yǔ)法分析器的工具廣泛可用。該章描述了構(gòu)建這些工具的理論，包括一系列日益復(fù)雜的方法，這些方法用來解決阻礙從某些文法構(gòu)建語(yǔ)法分析器的沖突（conflict）。該章還深入討論了文法和語(yǔ)言的二義性（ambiguity），并提出了理解和解決二義性文法的啟發(fā)式方法。
第7章 語(yǔ)法制導(dǎo)翻譯
從編譯器構(gòu)成組件的角度，該章標(biāo)志著本書的中點(diǎn)。前面的章節(jié)已經(jīng)介紹了程序的詞法分析和語(yǔ)法分析。這些章節(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)聲明所需的語(yǔ)義分析，包括類型、變量、數(shù)組、結(jié)構(gòu)和枚舉，同時(shí)介紹了類型檢查，包括面向?qū)ο箢悺⒆宇惡统悺?/p>
第9章 語(yǔ)義分析
對(duì)于在語(yǔ)法分析時(shí)不容易檢查的語(yǔ)言規(guī)范，需要進(jìn)行額外的語(yǔ)義分析，包括檢查各種控制結(jié)構(gòu)，如條件分支和循環(huán)。該章還討論了異常及其在編譯時(shí)所需的語(yǔ)義分析。
第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ǔ)言提供所需的運(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)造和使用。
新書資訊![編譯器構(gòu)造 [美]查爾斯·N.費(fèi)希爾 [美]羅恩·K.塞隆 [美]理查德·J.勒布朗](http://pic.book1993.com/Pic)