2020 Alfred Aho & Jeffrey Ullman —— 編譯器的聖經與語言的數學#
「1977 年出版、1986 年再版的『龍書』，是三代編譯器 工程師的共同啟蒙書。兩位作者證明：語言可以是一門 數學。」
案件檔案#
| 項目 | 內容 |
|---|---|
| 得主 | Alfred V. Aho (1941–)、Jeffrey D. Ullman (1942–) |
| 得獎理由 | 編譯器理論與程式語言實作的基礎演算法與理論 |
| 關鍵詞 | 龍書、正則表示式、LR 分析、Aho–Corasick |
前因#
1970s，編譯器是黑魔法：每家廠商憑經驗手搓。 Knuth（1974 案）已給出 LR(k) 分析的理論（1965），但 從文法到可執行解析器的完整路線圖缺失。Aho 與 Ullman 在貝爾實驗室與普林斯頓的師徒網絡中接案。
線索與推理#
線索一：語言的喬姆斯基階層落地#
Chomsky（1956）的形式語言階層被兩人變成工程工具箱：
| 語言類 | 自動機 | 編譯器用途 |
|---|---|---|
| 正則（3 型） | 有限自動機（1976 案的 NFA） | 詞法分析（lex） |
| 上下文無關（2 型） | 下推自動機 | 語法分析 |
| 上下文有關/遞迴可列舉 | 圖靈機 | 語義以上 |
線索二：龍書（1977/1986《Compilers: Principles, Techniques, and Tools》）#
封面武士屠龍（龍 = 編譯器的複雜性）。體系：
前端：詞法（正則→DFA 最小化，Hopcroft 演算法 1986 案）
語法（LL/LR：以棧+動作表，線性時間確定解析）
語義（屬性文法：結點上的方程組求值）
中端：中間表示（IR）+ 資料流最佳化（2006 案的框架）
後端：指令選擇、暫存器分配（1987 案）、排程
把編譯器拆成可獨立證明與替換的階段——工程與理論 的完美介面。yacc/bison（Aho 參與）把 LR 分析自動化： 文法進、解析器出。
線索三：字串比對的經典演算法#
KMP（Knuth–Morris–Pratt, 1977）：O(n+m)，失配函數
Aho–Corasick（1975）：多模式比對
將所有模式建成 trie + 失配邊 = 確定性自動機
grep 的多模式引擎、入侵偵測系統的核心
線索四：理論側翼#
Ullman 與 Hopcroft（1986 案）合著自動機經典教科書； 兩人合著《The Theory of Parsing, Translation, and Compiling》（1972–73）——編譯理論的數學總綱。 Ullman 亦是資料庫理論（資料依賴）與複雜度（二分圖、 join 演算法）的貢獻者；Google 的 Sergey Brin 是其 學生。
理論評析#
本案的偵探學：文法 = 生成語法，解析 = 逆向工程。
LL(1)：由左至右、最左推導、向前看 1 個符號 → 遞迴下降（1984 案）
LR(1)：由左至右、最右推導的逆 → 自底向上、能力最強的確定解析
Knuth 1965：LR(k) ⊇ 一切確定可解析的 CFG
實務取捨：LALR(1)（yacc）= 狀態合併的 LR → 表較小
語言設計者若不懂解析複雜度，語言就不可實作—— ALGOL 60（2005 案）的教訓被制度化。
後果#
- LLVM/GCC/任何現代編譯器的課本骨架；ANTLR/lex/yacc 的理論根。
- 正則表示式從理論玩具變成世界最廣用的「迷你語言」 （grep、sed、Regex 庫）。
關聯案件#
→ 1974-Donald-Knuth與演算法分析及TAOCP、1986-Hopcroft-Tarjan與演算法及資料結構、2006-Frances-Allen與編譯器最佳化