01 / 導讀
導讀
引用
Thain, D. (2020). Introduction to Compilers and Language Design (2nd ed.). Self-published. Free official edition: https://dthain.github.io/books/compiler/
章節概要
第1章：引言
開篇一章承擔了前言的作用。它把編譯器定義為從源語言到目標語言的翻譯器，區分編譯器與直譯器（Java 位元組碼和即時編譯是介於兩者之間的情形），並說明學習這門學科的理由，從寫出更好的程式碼到構建小型領域專用語言。Thain 主張學習編譯器的方法就是親手寫一個：用 C 語言編寫，面向廣泛使用的處理器。他還說明，與大多數編譯器教材相比，本書對最佳化理論著墨較少，而更多討論工程實現和語言設計中的取捨。
第2章：快速瀏覽
這一短章先把編譯器放到 Unix 工具鏈中（前處理器、編譯器本體、組譯器、靜態與動態連結器），再列出編譯器內部的各個階段：掃描器、語法分析器、語義例程、中間表示、最佳化器和程式碼生成器。一條語句 height = (width+56) * factor(foo); 被完整地跟蹤到每個階段：從記號到抽象語法樹，再到擁有無限暫存器的線性 IR，最後得到 X86 組合語言。練習要求讀者手動執行工具鏈的每一步，並比較不同的最佳化級別。
第3章：掃描
本章從語言需要哪些種類的記號講起，給出一個用 ungetc 回退字元的手寫 C 掃描器，然後說明為什麼需要更嚴格的方法。它定義正規表示式、確定型與非確定型有限自動機，以及三種轉換演算法（正規表示式轉 NFA、用子集構造法把 NFA 轉為 DFA、Hopcroft 式 DFA 最小化）。在解釋有限自動機為何無法匹配任意深度的巢狀括號之後，本章轉向 Flex 掃描器生成器並給出完整的規格檔案，最後討論關鍵字處理、原始碼位置跟蹤等實際問題。
第4章：語法分析
這是全書理論性最強的一章。它定義上下文無關文法、推導和二義性，然後展開 LL(1) 分析：消除左遞迴和公共字首、計算 FIRST 和 FOLLOW 集合，並編寫遞迴下降分析器和表驅動分析器。後半部分講自底向上分析：移進-歸約分析、LR(0) 自動機、SLR、規範 LR(1) 和 LALR，並配有完整的自動機和分析表範例。本章最後梳理各文法類之間的關係（LL(1) ⊂ SLR ⊂ LALR ⊂ LR(1) ⊂ CFG），並介紹喬姆斯基層級。
第5章：語法分析實踐
本章藉助 Bison 語法分析器生成器把理論付諸實踐。基於同一個算術表示式的 LALR 文法，依次構建三個程式：只判斷輸入是否合法的驗證器、在分析過程中直接計算結果的直譯器，以及先構建表示式樹、再對其求值或列印的版本。這為讀者編寫專案語言的完整語法分析器做好準備。
第6章：抽象語法樹
本章為課程專案所用的類 C 語言 B-Minor 定義抽象語法樹，由五種 C 結構組成：宣告、語句、表示式、型別和引數。它仔細區分這些術語，展示每種程式片段如何映射為樹節點，最後用 Bison 動作自動構建整棵樹。
第7章：語義分析
語義分析被表述為先進行名字解析、再進行型別檢查。本章先從三個維度考察型別系統（安全或不安全、靜態或動態、顯式或隱式），配有 C、C#、Go 和 Rust 的簡短範例，並討論結構體、聯合、變體型別以及不同型別之間轉換等設計選擇。隨後它規定嚴格的 B-Minor 型別系統，用作用域堆疊構建巢狀符號表，解析宣告和表示式中的名字，實現 expr_typecheck 和 stmt_typecheck，並就如何寫出有用的錯誤資訊給出建議。
第8章：中間表示
本章比較幾種 IR 及其取捨。它從 AST 本身出發，接著介紹有向無環圖（DAG），在其中公共子表示式可以共享、常數摺疊也很容易；然後是控制流圖、靜態單賦值形式、線性（三地址）IR 和堆疊式機器 IR。來自 GCC 的 GIMPLE、LLVM 和 Java 虛擬機器的真實範例展示了生產系統如何運用這些思想。
第9章：記憶體組織
在生成程式碼之前，本書先解釋執行中的程式如何使用記憶體：程式碼、資料、堆和堆疊這幾個邏輯段，以及硬體分段如何被分頁取代。它給出 malloc 和 free 的一個簡單鏈結串列實現，比較基於堆疊和基於暫存器的呼叫約定，說明編譯器如何定位全域變數、區域變數、引數和陣列元素，並介紹程式載入。
第10章：組合語言
Thain 認為編譯器只需要指令集中的一小部分（大約 30 條指令），並以兩組平行、各自獨立的小節講授兩種架構。對於 X86-64 和 ARM，本章依次介紹暫存器與資料型別、定址方式、算術運算、比較與跳轉（或分支）、堆疊、呼叫約定（X86 採用 System V ABI），以及完整的葉函式和非葉函式，最後說明 64 位 ARM 的差異。
第11章：程式碼生成
本章用一種刻意簡單的方法生成可執行的 X86-64 程式碼：把每個 AST 節點單獨處理。它先建立管理臨時暫存器和標籤的輔助函式，再以後序遍歷編寫 expr_codegen，處理函式呼叫，生成語句、條件表示式和宣告，並指出更好的程式碼留待下一章。練習要求完成整個程式碼生成器、與 gcc 的輸出進行比較，並可選地為 ARM 或 LLVM 增加第二個後端。
第12章：最佳化
最後一章是概覽而非完整論述。它區分區域、全域和過程間最佳化，並首先建議程式設計師在依賴編譯器之前先改進演算法、做效能剖析。接著介紹高層變換（常數摺疊、強度削減、迴圈展開、程式碼外提、函式內聯、死程式碼檢測）、低層變換（窺孔最佳化和基於樹覆蓋的指令選擇），以及利用活躍範圍、衝突圖和圖著色進行暫存器分配。簡短的小節提醒讀者注意會改變程式含義的最佳化，以及最佳化之間的相互影響。
附錄 A–C：課程專案範例、B-Minor 語言、編碼規範
附錄 A 把學期專案安排為一系列作業（掃描器、語法分析器、美化列印器、型別檢查器、可選的 IR、程式碼生成器、可選的語言擴充）。附錄 B 有意通過範例而不是形式文法來描述 B-Minor，讓學生自己提煉出精確的規格。附錄 C 列出作者對 C 專案的編碼要求，例如使用版本控制、"從可執行到可執行"地推進，以及刪除死程式碼。
核心概念
第1–2章：引言與快速瀏覽
- 編譯器與直譯器：編譯器輸出翻譯後的程式，直譯器直接執行源程式；即時編譯則把兩者結合起來。
- 編譯器的階段：掃描器、語法分析器、語義例程、IR、最佳化器和程式碼生成器，每個階段處理前一階段的輸出。
第3章：掃描
- 正規表示式與有限自動機：描述記號模式的兩種等價方式；正規表示式可轉為 NFA，再轉為 DFA，並可最小化。
- 掃描器生成器：如 Flex，把一組帶有 C 動作的正規表示式轉換成掃描器程式碼的工具。
第4章：語法分析
- 上下文無關文法：左側只有一個非終結符的規則，能夠描述正規表示式無法表達的巢狀結構。
- LL(1) 分析：根據當前非終結符和一個向前看記號選擇規則的自頂向下分析，通常寫成遞迴下降形式。
- LR 分析：由自動機驅動的自底向上移進-歸約分析；LALR 是生成器採用的實用折中方案。
第5–6章：語法分析實踐與抽象語法樹
- Bison 動作：附加在文法規則上的 C 程式碼，用於在分析過程中驗證、解釋或構建樹節點。
- 抽象語法樹：由宣告、語句、表示式、型別和引數組成的樹，記錄程式結構而不包含語法分析的細節。
第7章：語義分析
- 型別系統的維度：安全/不安全、靜態/動態、顯式/隱式，共同刻畫一門語言如何檢查值。
- 符號表：把名字映射到宣告的作用域堆疊，用於在型別檢查之前解析每個識別符號。
第8章：中間表示
- DAG：一種簡化的圖狀 IR，共享公共子表示式，使常數摺疊變得直接。
- 靜態單賦值（SSA）：每個變數只被賦值一次的形式，可簡化許多分析。
第9–10章：記憶體組織與組合語言
- 邏輯段：程序地址空間中程式碼、資料、堆和堆疊的常規佈局。
- 呼叫約定：關於傳遞引數、返回值和儲存暫存器的約定規則，例如 System V ABI。
第11–12章：程式碼生成與最佳化
- 後序程式碼生成：在處理完子節點之後再為節點生成指令，用臨時暫存器儲存中間值。
- 圖著色暫存器分配：根據活躍範圍構建衝突圖並對其著色，使相互衝突的變數分到不同的暫存器。
- 強度削減：用代價更低的等價運算替換昂貴的運算，例如把乘法換成移位。
評析
優點
- 一個專案貫穿始終。 每一章都服務於同一個 B-Minor 編譯器，練習大多是擴充這個編譯器的程式碼。附錄 A 把它整理成現成的作業序列，使本書很容易用於一學期的課程。
- 真實的工具和目標平臺。 讀者用 C 編寫程式碼，使用 Flex 和 Bison，閱讀 GIMPLE、LLVM 和 JVM 的範例，並生成真實的 X86-64 程式碼（另有平行的 ARM 內容）。"大約 30 條指令就夠用"的說法讓組合語言學習保持在可控範圍內。
- 語言設計是內容的一部分。 語義分析一章比較了 C、C#、Go 和 Rust 在型別系統上的不同選擇；B-Minor 本身也有意設計了一些特別之處（Pascal 風格的型別語法、需要型別推斷的
print語句、需要執行時支援的運算子），以引發討論。 - 篇幅短、易讀。 全書約 230 頁，每個演算法都配有小型實例（子集構造、LR 自動機、
x=(a+10)*(a+10)的 DAG、暫存器衝突圖），而不是依賴密集的形式化符號。
局限
- 最佳化與分析內容較少。 作者對此毫不諱言：第12章只是一次瀏覽，SSA 形式只在第8章簡短出現，活躍性和可達性等分析只是勾勒而未深入展開。打算從事編譯器研究的學生之後需要更進階的教材。
- 預設讀者熟悉 C 並具備一定架構知識。 全書程式碼都是 C，第9–10章對記憶體佈局和呼叫約定講得很快；沒有學過系統或計算機組織課程的學生會覺得吃力。
- 練習分佈不均。 第3章和第4章有紙筆練習，但第9章和第10章完全沒有練習；專案語言又有意只用範例來規定，需要教師幫助或仔細閱讀才能消除含糊之處。
- 語言覆蓋面較窄。 書中的模型是靜態型別、類 C 的過程式語言。垃圾回收、閉包和面向物件特性沒有涉及，動態型別只在第7章的一般性討論中出現。
在課程中的定位
在本課程書單中，Thain 的書與 Robert Nystrom 的 Crafting Interpreters 同為入門讀物，是篇幅緊湊、以專案驅動的選擇。兩者互為補充：Nystrom 用手寫語法分析器為一門動態型別語言構建直譯器，而 Thain 為一門靜態型別語言構建編譯器，講授文法理論（LL 與 LR 分析）以及掃描器和語法分析器生成器，並最終生成真實的組合語言程式碼。想同時理解語法分析背後的理論和通向本機程式碼之路的學生，應從 Thain 開始。
Cooper 和 Torczon 的 Engineering a Compiler 以及 Aho、Lam、Sethi 和 Ullman 的 Compilers: Principles, Techniques, and Tools 是自然的下一步；Thain 本人推薦後者作為全面的研究生水平參考書，而這兩本書通常被認為對最佳化和分析的論述遠比第12章深入。Pierce 的 Types and Programming Languages 列在第7章的延伸閱讀中，適合想了解 Thain 只作非形式化處理的型別系統形式理論的讀者。
如何使用本書
本書面向已經能熟練使用 C 程式設計、並修過資料結構和計算機組織或架構入門課程的大學部學生。不要求事先具備編譯器或形式語言背景；自動機和文法在第3、4章從零講起。
無論是學期課程還是自學，都建議按書中順序並配合附錄 A 的作業進行。第1–2章可以一次讀完。用 Flex 完成第3章，用 Bison 完成第4–5章，並做關於 FIRST/FOLLOW 集合和 LR 自動機的紙筆練習，因為這些是大多數課程考查的內容。第6章和第7章是專案的核心（AST 和型別檢查器）。如果像作者在自己課程中那樣直接從 AST 生成程式碼，第8章可以略讀。在編寫第11章的程式碼生成器之前先讀第9章和第10章；第10章可先只讀 X86 或 ARM 中的一半。第12章可作為最後幾週的擴充選題清單。
每完成一個階段，都用小程式進行測試後再繼續，並按練習的建議把自己的輸出與 gcc -S 的結果比較。作者網站連結了一個 GitHub 倉庫，其中有範例掃描器和語法分析器、專案起始程式碼以及每個階段的測試案例。
版本與來源
本導讀依據第二版（2020），閱讀的是作者官方頁面 https://dthain.github.io/books/compiler/（也可通過 compilerbook.org 造訪）提供的完整免費 PDF（compilerbook.pdf，修訂日期為 2026 年 7 月 28 日）。內容取材於致謝頁、完整目錄和插圖目錄、全部十二章（第1–2章全文；第3–12章的開頭、每個小節標題、核心範例以及章末練習和延伸閱讀），以及附錄 A–C。