構(gòu)建編譯器的實(shí)踐方法一直在不斷變化，部分是因?yàn)樘幚砥骱拖到y(tǒng)的設(shè)計(jì)會(huì)發(fā)生變化。例如，當(dāng)我們?cè)?998年開始寫作本書初版時(shí)，一些同事對(duì)書中指令調(diào)度方面的內(nèi)容頗感疑惑，因?yàn)閬y序執(zhí)行威脅到了指令調(diào)度，很有可能會(huì)使其變得不再重要。現(xiàn)在第2版已經(jīng)付印，隨著多核處理器的崛起和爭(zhēng)取更多核心的推動(dòng)，順序執(zhí)行流水線再次展現(xiàn)吸引力，因?yàn)檫@種流水線占地較少，設(shè)計(jì)者能夠?qū)⒏�多核心放置在一塊芯片上。短期內(nèi)，指令調(diào)度仍然很重要。
　　同時(shí)，編譯器構(gòu)建社區(qū)還將繼續(xù)產(chǎn)生新的思路和算法，并重新發(fā)現(xiàn)原本有效但在很大程度上卻被遺忘的舊技術(shù)。圍繞著寄存器分配中弦圖（chordal graph）使用（參見13.5.2節(jié)）的最新研究頗為令人振奮。該項(xiàng)工作承諾可以簡(jiǎn)化圖著色分配器（graph-coloring allocator）的某些方面。Brzozowski的算法是一種DFA最小化技術(shù)，可以追溯到20世紀(jì)60年代早期，但卻已有數(shù)十年未在編譯器課程中講授了（參見2.6.2節(jié)）。 該算法提供了一種容易的路徑，可以從子集構(gòu)造（subset construction）的實(shí)現(xiàn)得到一個(gè)最小化DFA的實(shí)現(xiàn)。編譯器構(gòu)建方面的現(xiàn)代課程本該同時(shí)包括這兩種思想。
　　那么，為了讓學(xué)習(xí)者準(zhǔn)備好進(jìn)入這個(gè)不斷變化的領(lǐng)域，我們?cè)撊绾卧O(shè)計(jì)編譯器構(gòu)建課程的結(jié)構(gòu)呢？我們相信，這門課應(yīng)該使每個(gè)學(xué)生學(xué)會(huì)建立新編譯器組件和修改現(xiàn)存編譯器所需的各項(xiàng)基本技能。學(xué)生既需要理解籠統(tǒng)的概念，如鏈接約定中隱含的編譯器、鏈接器、裝載器和操作系統(tǒng)之間的協(xié)作，也需要理解微小的細(xì)節(jié)，如編譯器編寫者如何減少每個(gè)過(guò)程調(diào)用時(shí)保存寄存器的代碼總共所占的空間。
　　第2版中的改變
　　本書提供了兩種視角：編譯器構(gòu)建領(lǐng)域中各問(wèn)題的整體圖景，以及各種可選算法方案的詳細(xì)討論。在構(gòu)思本書的過(guò)程中，我們專注于該書的可用性，使其既可作為教科書，又可用做專業(yè)人士的參考書。為此，我們特別進(jìn)行了下述改動(dòng)。
　　改進(jìn)了闡述思想的流程，以幫助按順序閱讀本書的學(xué)生。每章章首簡(jiǎn)介會(huì)解釋該章的目的，列出主要的概念，并概述主題相關(guān)內(nèi)容。書中的示例已經(jīng)重寫過(guò)，使得章與章之間的內(nèi)容具有連續(xù)性。此外，每章都從摘要和一組關(guān)鍵詞開始，以幫助那些會(huì)將本書用做參考書的讀者。
　　在每節(jié)末尾都增加了本節(jié)回顧和復(fù)習(xí)題。復(fù)習(xí)題用于快速檢查讀者是否理解了該節(jié)的要點(diǎn)。
　　關(guān)鍵術(shù)語(yǔ)的定義放在了它們被首次定義和討論的段落之后。
　　大量修訂了有關(guān)優(yōu)化的內(nèi)容，使其能夠更廣泛地涵蓋優(yōu)化編譯器的各種可能性。
　　現(xiàn)在的編譯器開發(fā)專注于優(yōu)化和代碼生成。對(duì)于新雇用的編譯器編寫者來(lái)說(shuō)，他們往往會(huì)被指派去將代碼生成器移植到新處理器，或去修改優(yōu)化趟，而不會(huì)去編寫詞法分析器或語(yǔ)法分析器。成功的編譯器編寫者必須熟悉優(yōu)化（如靜態(tài)單賦值形式的構(gòu)建）和代碼生成領(lǐng)域當(dāng)前最好的實(shí)踐技術(shù)（如軟件流水線）。他們還必須擁有相關(guān)的背景和洞察力，能理解未來(lái)可能出現(xiàn)的新技術(shù)。最后，他們必須深刻理解詞法分析、語(yǔ)法分析和語(yǔ)義推敲（semantic elaboration）技術(shù)，能構(gòu)建或修改編譯器前端。
　　本書是一本教科書、一門教程，幫助學(xué)生接觸到現(xiàn)代編譯器領(lǐng)域中的各種關(guān)鍵問(wèn)題，并向?qū)W生提供解決這些問(wèn)題所需的背景知識(shí)。從第1版開始，我們就維持了各主題之間的基本均衡。前端是實(shí)用組件，可以從可靠的廠商購(gòu)買或由某個(gè)開源系統(tǒng)改編而得。但是，優(yōu)化器和代碼生成器通常是對(duì)特定處理器定制的，有時(shí)甚至針對(duì)單個(gè)處理器型號(hào)定制，因?yàn)樾阅車?yán)重依賴于所生成代碼的底層細(xì)節(jié)。這些事實(shí)影響到了當(dāng)今構(gòu)建編譯器的方法，它們也應(yīng)該影響我們講授編譯器構(gòu)建課程的方法。
　　本書結(jié)構(gòu)
　　本書內(nèi)容劃分為篇幅大致相等的四個(gè)部分。
　　第一部分（第2章～第4章）涵蓋編譯器前端及建立前端所用工具的設(shè)計(jì)和構(gòu)建。
　　第二部分（第5章～第7章）探討從源代碼到編譯器的中間形式的映射，這些章考查前端為優(yōu)化器和后端所生成代碼的種類。
　　第三部分（第8章～第10章）介紹代碼優(yōu)化。第8章提供對(duì)優(yōu)化的概述。第9章和第10章包含了對(duì)分析和轉(zhuǎn)換的更深入的處理，本科課程通常略去這兩章。
　　第四部分（第11章～第13章）專注于編譯器的后端所使用的算法。
　　編譯的藝術(shù)性與科學(xué)性
　　編譯器構(gòu)建的內(nèi)容有兩部分，一是將理論應(yīng)用到實(shí)踐方面所取得的驚人成就，一是對(duì)我們能力受限之處的探討。這些成就包括：現(xiàn)代詞法分析器是通過(guò)應(yīng)用正則語(yǔ)言的理論自動(dòng)構(gòu)建識(shí)別器而建立的；LR語(yǔ)法分析器使用同樣的技術(shù)執(zhí)行句柄識(shí)別，進(jìn)而驅(qū)動(dòng)了一個(gè)移進(jìn)歸約語(yǔ)法分析器；數(shù)據(jù)流分析巧妙有效地將格理論應(yīng)用到程序分析中；代碼生成中使用的近似算法為許多真正困難的問(wèn)題提供了較好的解。
　　另一方面，編譯器構(gòu)建也揭示了一些難以解決的復(fù)雜問(wèn)題。用于現(xiàn)代處理器的編譯器后端對(duì)兩個(gè)以上的NP完全問(wèn)題（指令調(diào)度、寄存器分配，也許還包括指令和數(shù)據(jù)安排）采用了近似算法來(lái)獲取答案。這些NP完全問(wèn)題，雖然看起來(lái)與諸如表達(dá)式的代數(shù)重新關(guān)聯(lián)這種問(wèn)題相近（示例見圖7-1）。但后者有著大量的解決方案，更糟的是，對(duì)于這些NP完全問(wèn)題來(lái)說(shuō)，所要的解往往取決于編譯器和應(yīng)用程序代碼中的上下文信息。在編譯器對(duì)此類問(wèn)題近似求解時(shí)，會(huì)面臨編譯時(shí)間和可用內(nèi)存上的限制。好的編譯器會(huì)巧妙地混合理論、實(shí)踐知識(shí)、技術(shù)和經(jīng)驗(yàn)。
　　打開一個(gè)現(xiàn)代優(yōu)化編譯器，你會(huì)發(fā)現(xiàn)各式各樣的技術(shù)。編譯器使用貪婪啟發(fā)式搜索來(lái)探索很大的解空間，使用確定性有限自動(dòng)機(jī)來(lái)識(shí)別輸入中的單詞。不動(dòng)點(diǎn)算法被用于推斷程序行為，通過(guò)定理證明程序和代數(shù)化簡(jiǎn)器來(lái)預(yù)測(cè)表達(dá)式的值。編譯器利用快速模式匹配算法將抽象計(jì)算映射到機(jī)器層次上的操作。它們使用線性丟番圖方程和普瑞斯伯格算術(shù)（Pressburger arithmetic）來(lái)分析數(shù)組下標(biāo)。最后，編譯器使用了大量經(jīng)典的算法和數(shù)據(jù)結(jié)構(gòu)，如散列表、圖算法和稀疏集實(shí)現(xiàn)方法等。
　　本書嘗試同時(shí)闡釋編譯器構(gòu)建的藝術(shù)和科學(xué)這兩方面內(nèi)容。通過(guò)選取足夠廣泛的題材，向讀者表明，確實(shí)存在一些折中的解決方案，而設(shè)計(jì)決策的影響可能是微妙而深遠(yuǎn)的。另一方面，本書也省去了某些長(zhǎng)期以來(lái)都列入本科編譯器構(gòu)建課程的技術(shù)，隨著市場(chǎng)、語(yǔ)言和編譯器技術(shù)或工具可用性方面的改變，這些技術(shù)已變得不那么重要了。
　　講述方法
　　編譯器構(gòu)建是一種工程設(shè)計(jì)實(shí)踐。每個(gè)方案的成本、優(yōu)點(diǎn)和復(fù)雜程度各異，編譯器編寫者必須在多種備選方案中做出抉擇。每個(gè)決策都會(huì)影響到最終的編譯器。最終產(chǎn)品的質(zhì)量，取決于抉擇過(guò)程中所做的每一個(gè)理性決斷。
　　因而，對(duì)于編譯器中的許多設(shè)計(jì)決策來(lái)說(shuō)，并不存在唯一的正確答案。即使在“理解透徹”和“已解決”的問(wèn)題中，設(shè)計(jì)和實(shí)現(xiàn)中的細(xì)微差別都會(huì)影響到編譯器的行為及其產(chǎn)生的代碼的質(zhì)量。每個(gè)決策都涉及許多方面。舉例來(lái)說(shuō)，中間表示的選擇對(duì)于編譯器中其余部分有著深刻的影響，無(wú)論是時(shí)間和空間需求，還是應(yīng)用不同算法的難易程度。但實(shí)際上確定該決策時(shí)，通�？晒┰O(shè)計(jì)者考慮的時(shí)間并不多。第5章考察了中間表示的空間需求，以及其他一些應(yīng)該在選擇中間表示時(shí)考慮的問(wèn)題。在本書中其他地方，我們會(huì)再次提出該問(wèn)題，既會(huì)在正文中直接提出，也會(huì)在習(xí)題里間接提出。
　　本書探索了編譯器的設(shè)計(jì)空間，既從深度上闡釋問(wèn)題，也從廣度上探討可能的答案。它給出了這些問(wèn)題的某些解決方法，并說(shuō)明了使用這些方案的約束條件。編譯器編寫者需要理解這些問(wèn)題及其答案，以及所作決策對(duì)編譯器設(shè)計(jì)的其他方面的影響。只有這樣，編寫者才能作出理性和明智的選擇。
　　思想觀念
　　本書闡釋了我們?cè)跇?gòu)建編譯器方面的思想觀念，這是在各自超過(guò)25年的研究、授課和實(shí)踐過(guò)程中發(fā)展起來(lái)的。例如，中間表示應(yīng)該展示最終代碼所關(guān)注的那些細(xì)節(jié)，這種理念導(dǎo)致了對(duì)底層表示的偏愛。又比如，值應(yīng)該駐留在寄存器中，直至分配器發(fā)現(xiàn)無(wú)法繼續(xù)保留它為止，這種做法產(chǎn)生了使用虛擬寄存器的例子，以及僅在無(wú)可避免時(shí)才將值存儲(chǔ)到內(nèi)存的例子。每個(gè)編譯器都應(yīng)該包括優(yōu)化，它簡(jiǎn)化了編譯器其余的部分。多年以來(lái)的經(jīng)驗(yàn)，使得我們能夠理性地選擇書的主題和展現(xiàn)方式。
　　關(guān)于編程習(xí)題的選擇
　　編譯器構(gòu)建方面的課程，提供了在一個(gè)具體應(yīng)用程序（編譯器）環(huán)境中探索軟件設(shè)計(jì)問(wèn)題的機(jī)會(huì)，任何具備編譯器構(gòu)建課程背景的學(xué)生，都已經(jīng)透徹理解了該應(yīng)用程序的基本功能。在多數(shù)編譯器設(shè)計(jì)課程中，編程習(xí)題發(fā)揮了很大的作用。
　　我們以這樣的方式講授過(guò)這門課：學(xué)生從頭到尾構(gòu)建一個(gè)簡(jiǎn)單的編譯器，從生成的詞法分析器和語(yǔ)法分析器開始，結(jié)束于針對(duì)某個(gè)簡(jiǎn)化的RISC指令集的代碼生成器。我們也以另一種方式講授過(guò)這門課程，學(xué)生編寫程序來(lái)解決各個(gè)良好自包含的問(wèn)題，諸如寄存器分配或指令調(diào)度。編程習(xí)題的選擇實(shí)際上非常依賴于本課程在相關(guān)課程中所扮演的角色。
　　在某些學(xué)校，編譯器課程充當(dāng)高年級(jí)的頂級(jí)課程，將來(lái)自許多其他課程的概念匯集到一個(gè)大型的實(shí)際設(shè)計(jì)和實(shí)現(xiàn)項(xiàng)目中。在這樣的課程中，學(xué)生應(yīng)該為一門簡(jiǎn)單的語(yǔ)言編寫一個(gè)完整的編譯器，或者修改一個(gè)開源的編譯器，以支持新的語(yǔ)言或體系結(jié)構(gòu)特性。這門課程可以按本書的內(nèi)容組織，從頭到尾講授本書的內(nèi)容。
　　在另外一些學(xué)校，編譯器設(shè)計(jì)出現(xiàn)在其他課程中，或以其他方式呈現(xiàn)在教學(xué)中。此時(shí)，編譯器設(shè)計(jì)教師應(yīng)該專注于算法及其實(shí)現(xiàn)，比如局部寄存器分配器或樹高重新平衡趟這樣的編程習(xí)題。在這種情況下，可以選擇性講解本書中的內(nèi)容，也可以調(diào)整講述的順序，以滿足編程習(xí)題的需求。例如，在萊斯大學(xué)，我們通常使用簡(jiǎn)單的局部寄存器分配器作為第一個(gè)編程習(xí)題，任何具有匯編語(yǔ)言編程經(jīng)驗(yàn)的學(xué)生，都可以理解該問(wèn)題的基本要素。但這種策略，需要讓學(xué)生在學(xué)習(xí)第2章之前，首先接觸第13章的內(nèi)容。
　　不管采用哪種方案，本課程都應(yīng)該從其他課程取材。在計(jì)算機(jī)組織結(jié)構(gòu)、匯編語(yǔ)言編程、操作系統(tǒng)、計(jì)算機(jī)體系結(jié)構(gòu)、算法和形式語(yǔ)言之間，存在著明顯的關(guān)聯(lián)。盡管編譯器構(gòu)建與其他課程的關(guān)聯(lián)不那么明顯，但這種關(guān)聯(lián)同等重要。第7章中討論的字符復(fù)制，對(duì)于網(wǎng)絡(luò)協(xié)議、文件服務(wù)器和Web服務(wù)器等應(yīng)用程序的性能而言，都發(fā)揮著關(guān)鍵的作用。第2章中用于詞法分析的技術(shù)可以應(yīng)用到文本編輯和URL過(guò)濾等領(lǐng)域。第13章中自底向上的局部寄存器分配器是最優(yōu)離線頁(yè)面替換算法MIN的“近親”。
　　補(bǔ)充材料
　　還有一些補(bǔ)充的資源可用，可幫助讀者改編本書的內(nèi)容，使之適用于自己的課程。這包括作者在萊斯大學(xué)講授這門課程的一套完整的講義以及習(xí)題答案。讀者可以聯(lián)系本地的Elsevier業(yè)務(wù)代表，詢問(wèn)如何獲取這些補(bǔ)充材料 。
　　致謝
　　許多人參與了第1版的出版工作，他們的貢獻(xiàn)也體現(xiàn)在第2版中。許多人指出了第1版中的問(wèn)題，包括Amit Saha、Andrew Waters、Anna Youssefi、Ayal Zachs、Daniel Salce、David Peixotto、Fengmei Zhao、Greg Malecha、Hwansoo Han、Jason Eckhardt、Jeffrey Sandoval、John Elliot、Kamal Sharma、Kim Hazelwood、Max Hailperin、Peter Froehlich、Ryan Stinnett、Sachin Rehki、Sa·nak Ta··rlar、Timothy Harvey和Xipeng Shen，在此向他們致謝。我們還要感謝第2版的審閱者，包括Jeffery von Ronne、Carl Offner、David Orleans、K. Stuart Smith、John Mallozzi、Elizabeth White和Paul C. Anagnostopoulos。Elsevier的產(chǎn)品團(tuán)隊(duì)，特別是Alisa Andreola、Andre Cuello和Megan Guiney，在將草稿轉(zhuǎn)換成書的過(guò)程中發(fā)揮了關(guān)鍵作用。所有這些人都以其深刻的洞察力和無(wú)私的幫助，從各個(gè)重要方面提升了本書的質(zhì)量。
　　最后，在過(guò)去5年中，無(wú)論是從精神方面，還是從知識(shí)方面，許多人都為我們提供了莫大的支持。首先，我們的家庭和萊斯大學(xué)的同事都在不斷地鼓勵(lì)我們。特別感謝小女Christine和Carolyn，她們耐心容忍了無(wú)數(shù)次關(guān)于編譯器構(gòu)建方面各種主題的長(zhǎng)時(shí)間討論。Nate McFadden以其耐心和出色的幽默感，從開始到出版，一直指導(dǎo)著本書的工作。Penny Anderson對(duì)于日常行政事務(wù)管理方面的幫助對(duì)于本書的完成至關(guān)重要。對(duì)所有這些人，我們表示衷心的感謝。