前　　言
Crafting a Compiler

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

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

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

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

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

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

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

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

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

各章概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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