1977-龍書#

案件摘要#

1960 年代，形式語言與自動機理論已在 Aho、Hopcroft、Ullman 等人手中成熟，論文散落各處，卻沒有一本書把「如何建造編譯器」整合成一套方法學。1977 年，Bell Labs 的 Alfred Aho 與 Columbia 的 Jeffrey Ullman 聯手出版《Principles of Compiler Design》——封面上一名騎士持劍馴龍，從此「馴服編譯器這條惡龍」成為每個資訊系學生的成人禮。這本書被暱稱為「龍書」，統治編譯器教育近半世紀，無人能撼動。

前因 -- 為什麼會有這個案子#

理論已成熟卻散落：Chomsky 階層（1956）、Knuth 的 LR(k) 分析（1965）、Lewis 與 Stearns 的 LL(k) 理論等成果，都發表在期刊論文中，一般工程師難以觸及；理論與實務之間隔著一道鴻溝。
編譯器寫作被視為巫術：1960 年代每個編譯器都是手工打造的藝術品，FORTRAN I 編譯器耗費 18 人年；沒有系統化的方法，每個新語言、新機器都要重新發明輪子。
Aho 與 Ullman 的背景：兩人合著過《The Theory of Parsing, Translation, and Compiling》（1972-73，兩卷本），內容偏理論；他們意識到需要一本「給工程師的版本」——把理論轉譯成可操作的演算法。
教科書市場空缺：當時僅有的編譯器教材（如 Gries 的《Compiler Construction for Digital Computers》, 1971）偏實務細節，缺乏形式語言理論的統攝。

線索與推理 -- 數學式、程式、理論#

編譯器六階段管線：資料流的抽象#

龍書最重要的貢獻之一，是把編譯器拆成線性管線，每個階段吃進一種表示法、吐出另一種：

\[ \text{原始碼} \to \underbrace{\text{詞法分析}}_{\text{字元}\to\text{Token}} \to \underbrace{\text{語法分析}}_{\text{Token}\to\text{AST}} \to \underbrace{\text{語意分析}}_{\text{AST}\to\text{標註 AST}} \to \underbrace{\text{中間碼生成}}_{\to\text{IR}} \to \underbrace{\text{優化}}_{\text{IR}\to\text{IR}} \to \underbrace{\text{代碼生成}}_{\to\text{機器碼}} \]

每一階段都可獨立替換、獨立測試、獨立教學——這正是抽象化思維的典範。龍書告訴讀者：編譯器不是巫術，而是一條可分析的生產線。

用偽代碼描述管線：

def compile(source):
    tokens    = lexer(source)        # 詞法：正則表達式驅動
    ast       = parser(tokens)       # 語法：上下文無關文法驅動
    checked   = semantic(ast)        # 語意：符號表 + 型別檢查
    ir        = irgen(checked)       # 中間碼：三址碼 (three-address code)
    opt       = optimizer(ir)        # 優化：資料流分析、常數折疊
    return codegen(opt)              # 目標碼：暫存器分配 + 指令選擇

每個函數對應書中的一章，讀者可逐章攻克——這就是「把惡龍切成七段」的戰術。

FIRST 與 FOLLOW 集合：LL(1) 分析的鑰匙#

龍書用形式語言理論統攝語法分析。對文法 \(G\) ，定義：

\[ \text{FIRST}(\alpha) = \{\, a \mid \alpha \Rightarrow^* a\cdots,\ a \in T \,\} \cup (\alpha \Rightarrow^* \epsilon \ \Rightarrow\ \{\epsilon\}) \]

\[ \text{FOLLOW}(A) = \{\, a \mid S \Rightarrow^* \cdots A a \cdots,\ a \in T \,\} \]

FIRST 是某符號串能推導出的開頭終端符號集合；FOLLOW 是某非終端符號在句型中可以出現的後繼終端符號集合。有了這兩組集合，就能建構預測分析表：若 \(a \in \text{FIRST}(\alpha)\) 則在 \(M[A, a]\) 填入 \(A \to \alpha\) ；若 \(\epsilon \in \text{FIRST}(\alpha)\) 且 \(a \in \text{FOLLOW}(A)\) 亦然。無衝突即為 LL(1) 文法，可用一遍掃描的遞迴下降或表格驅動分析器解析。

Python 計算 FIRST 集合#

# 文法：E -> T E' | T E'
#       E'-> + T E' | ε
#       T -> F T'
#       T'-> * F T' | ε
#       F -> ( E ) | id
G = {
    "E":  [["T","E'"]],
    "E'": [["+","T","E'"], ["ε"]],
    "T":  [["F","T'"]],
    "T'": [["*","F","T'"], ["ε"]],
    "F":  [["(","E",")"], ["id"]],
}

def first(sym):
    if sym in ("id", "+", "*", "(", ")"):   # 終端符號
        return {sym}
    out = set()
    for prod in G[sym]:
        head = prod[0]
        if head == "ε" or head == sym:      # 空產生式或左遞迴
            if head == "ε": out.add("ε")
            continue
        f = first(head)
        out |= f - {"ε"}
        if "ε" not in f:                    # FIRST(head) 無 ε 即停
            continue
        out |= {"ε"} if len(prod) == 1 else first(prod[1])
    return out

for nt in G:
    print(f"FIRST({nt}) = {sorted(first(nt))}")
# 輸出：FIRST(F) = ['(', 'id']，其餘非終端皆同——
# 這正確反映 E、E'、T、T'、F 的開頭符號只能是 '(' 或 id

這段程式是遞迴不動點迭代：不斷用子符號的 FIRST 擴充父符號的 FIRST，直到不再變化——龍書中所有分析表建構演算法都是這個模式，LL(1)、LR(0)、LALR 皆是同一思想的變奏。

騎士與龍的寓意#

封面上騎士持劍（寫著 Pascal）迎戰噴火的綠龍，龍鱗上嵌著 "Compiler" 字樣。寓意：編譯器設計是資訊科學中最兇險的巨龍，而形式語言理論是屠龍之劍。第二版（1986，與 Monica Lam 之夫 Ravi Sethi 合著）封面改為騎士凱旋騎龍——龍已被馴服。

結案 -- 後果與影響#

統治編譯器教育：龍書成為全球編譯器課程的標準教材，至今仍是最常引用的教科書；第二版《Compilers: Principles, Techniques, and Tools》（1986，加 Monica Lam 為 2006 修訂版作者）持續再版。
理論與實務的橋樑：把 Chomsky 文法、LR/LALR 分析、資料流分析從論文轉譯成演算法與習題，讓一般學生也能掌握——編譯器課程從此成為資訊系核心必修。
工具化的先聲：書中方法直接催生了 lex/yacc（1975）等編譯器產生器；現代 ANTLR、LLVM 的文件仍以龍書為理論基準。
Aho 獲 2020 年圖靈獎（與 Ullman 共同獲獎），表揚其在形式語言與編譯器理論的奠基貢獻——龍書正是這份遺產最廣為人知的載體。

關鍵人物與文獻#

Alfred Aho（Bell Labs/Columbia）、Jeffrey Ullman（Princeton→Stanford）：龍書作者，2020 年圖靈獎。
John Hopcroft：與 Aho/Ullman 合著《The Design and Analysis of Computer Algorithms》(1974)，形式語言三部曲之一。
文獻：
A. V. Aho, J. D. Ullman, Principles of Compiler Design, Addison-Wesley, 1977.
A. V. Aho, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., 1986/2006.
D. E. Knuth, "On the Translation of Languages from Left to Right," Information and Control 8, 607 (1965).
N. Chomsky, "Three Models for the Description of Language," IRE Trans. IT 2, 113 (1956).