詞法與語法分析：從字元流到 AST#

編譯器的「前端」像一座翻譯工廠的進料口：原始碼以位元組流的形態湧入，離開時已化為一棵結構清晰的抽象語法樹。這條流水線上的兩道主工序——詞法分析與語法分析——各自對應喬姆斯基階層的一層，也各自有一段值得細說的歷史。

詞法分析：有限自動機的勝利#

詞法分析器（tokenizer）的工作，是把 while (x >= 10) 這樣的字元流切斷成一串 token：關鍵字 while、識別字 x、關係運算符 >=、整數常數 10。這些字的形狀都能用正則表達式描述：識別字是「字母開頭、後接字母或數字」，可以寫成 \([a-zA-Z][a-zA-Z0-9]^*\)。

數學基礎早在 1950 年代就備齊了。克林尼證明正則表達式與有限自動機刻畫著同一類語言。但把兩者之間的「翻譯」做成高效演算法的，是貝爾實驗室的肯・湯普森（Ken Thompson）——就是那位後來與 Dennis Ritchie 一起創造 UNIX 的人。1968 年，他在《Communications of the ACM》上發表〈Programming Techniques: Regular expression search algorithm〉，提出把正則表達式編譯成非確定性有限自動機（NFA）、再以多狀態並行推進的方式模擬，使比對時間與表達式長度、文字長度都呈線性關係。這篇論文成就了 UNIX 上的 grep——grep 這個名字本身就是「globally search a regular expression and print」的縮寫。湯普森的演算法日後被稱為「湯普森建構法」，直到今天仍是 Rust regex 套件與 Go 的 RE2 所信奉的路線：寧可線性時間，也不要災難性回溯。

有限自動機最小化的理論（確定性自動機 DFA 的狀態數有唯一極小值）也在此期間被整合進來，詞法分析從此成為編譯理論中最「已解決」的部分——效率無懈可擊，工程上甚至可以自動生成。

語法分析：兩大流派#

語法分析就沒有這麼順利。上下文無關文法雖然明確界定了戰場，但如何高效地把 token 流解析成樹，糾纏了研究者整整十五年。

兩大流派由此分野。自頂向下：從起始符號出發，猜測要套用哪條產生規則，再逐層展開。最自然的實作是遞迴下降——為每個非終結符寫一個函式，函式互相遞迴呼叫，程式結構與文法結構一一對應，可讀性極佳。但樸素版本遇到左遞迴會無限迴圈，遇到多個候選規則則需要回溯。1960 年代末，Lewis 與 Stearns 等人提出 LL(k) 的形式化框架，加上「提取左公因子、消除左遞迴」的文法改寫技巧，自頂向下解析才有了穩定的理論地位。

自底向上則反其道而行：從 token 開始，不斷把已讀入的符號「歸約」回非終結符，最後收攏成起始符號。它的數學基礎由高德納（Donald Knuth）奠定。1965 年，年僅二十七歲的 Knuth 發表〈On the Translation of Languages from Left to Right〉，定義了 LR(k) 文法——Left-to-right scan、Rightmost derivation、向前看 k 個符號——並證明這正是「能用線性時間確定性解析」的文法類別的上界。這是一個驚人的理論結果：LR(k) 涵蓋了所有實用的程式語言文法，而且解析嚴格線性。可惜 Knuth 的原始構造產生的狀態表大得驚人。1971 年，DeRemer 提出簡化的 SLR 與 LALR 構造，把表格壓縮到實用尺寸——這正是 Yacc 得以問世的前提。

AST：編譯器的中樞#

解析器的產出是抽象語法樹。與「具體語法樹」不同，AST 剝掉了括號、分號這類語法糖：(a+b)*c 與 ((a)+b)*c 在 AST 裡是同一棵樹。這個中間產物的品質，決定了後續語意分析與優化的成敗，堪稱編譯器的脊椎骨。

值得一提的是，自頂向下流派在 1970 年代還有一項技術性復興。Vaughan Pratt 在 1973 年的 POPL 會議上發表〈Top-down operator precedence〉，提出一種以「結合力優先級」驅動的解析器，處理表示式時既無須文法改寫也無須表格，程式碼短得驚人。Pratt parser 成為後世 Lua、JavaScript 等語言實作的傳家寶；而遞迴下降因其可讀性與優良的錯誤訊息，更在 2000 年代重新成為主流——Go、Rust、Swift 的編譯器前端都是手寫遞迴下降，這是後話。

語法歧義的教訓#

解析理論也反過來塑造了語言設計。最著名的教訓是 C 的宣告語法。C 語言的宣告如 int (*f)(int)（f 是指向函式的指標），把「使用形式」與「宣告形式」合而為一，導致其宣告文法極難解析，甚至出現經典謎題 int (*(*f)(int))[5]。Dennis Ritchie 本人在 1975 年的內部備忘錄中承認，這套語法「對人與編譯器都造成困擾」。C++ 更進一步：模板 a<b,c>::d 在未定型態前根本無法判定是小於運算還是模板引數，迫使編譯器必須在語意資訊齊備前「猜測」語法結構，成為解析理論的夢魘。後繼語言無不記取教訓：Pascal 的 var x : integer、Go 的 var x int、Rust 的 let x: i32，都刻意讓宣告可以從左到右無歧義地讀完。

從字元到 token，從 token 到 AST，前端流水線的每一步都有理論托底。下一節我們將看到，貝爾實驗室如何把這些理論封裝成兩個工具，讓「寫編譯器」從手工藝變成規格驅動的工程。