喬姆斯基譜系：形式語言的數學階層#

1956 年，費城賓州大學資訊理論研討會上，宣讀了一篇題為〈Three Models for the Description of Language〉的論文。作者是一位二十七歲的年輕語言學家，諾姆・喬姆斯基（Noam Chomsky）。他當時正在哈佛學術社會研究中擔任初級研究員，念茲在茲的問題與計算機毫無關係：人類語言的結構究竟該如何用數學描述？行為主義心理學把語言視為刺激與反應的連結，馬克・雅各布森的結構主義語言學則忙著做音位的分類統計。喬姆斯基對這兩者都不滿。他相信語言有一種深層的、可生成的數學結構，而要嚴格地談論它，就必須先定義「文法」與「語言」究竟是什麼。

次年，1957 年，他出版的薄薄一本《句法結構》（Syntactic Structures），篇幅不過百餘頁，卻改寫了語言學，也意外地改寫了計算機科學。

四層階層#

喬姆斯基的洞見在於：文法可以按「產生規則」所受的限制，分成一個嵌套的階層。這個階層的每一層，恰好對應一種計算模型——而這些模型，正是圖靈與邱奇在 1930 年代埋下的可計算性理論：

規則限制越鬆，表達力越強，判定效率也越低。第 3 型文法規定產生規則只能長成 \(A \rightarrow aB\) 或 \(A \rightarrow a\) 的形狀，這種僵硬的線性結構恰好就是有限自動機能夠走過的路徑。第 2 型放寬為允許嵌套替換 \(A \rightarrow \alpha B \beta\)，於是能表達「括號要配對」「if 裡面還可以包 if」這類無限嵌套的結構，代價是機器必須多一根堆疊——下推自動機。

喬姆斯基用這套工具證明了一個當時讓語言學界震動的結果：英語中 "colorless green ideas sleep furiously" 這樣的句子雖然毫無意義，母語者卻都能判斷它是合語法的。統計模型無法捕捉這種「合語法但無意義」的判斷，唯有遞迴的規則系統可以。語言能力不是習得的習慣，而是天賦的結構——這一論斷引爆了認知科學革命，也讓喬姆斯基後來成為二十世紀被引用最多的學者之一，以及美國外交政策最不留情面的政治異議者。

意外的收穫者#

但真正立刻採用這套理論的，是一群距離語言學最遠的人：編譯器工程師。

1950 年代的編譯器開發是一場混亂的手工藝。FORTRAN I 的編譯器動用了 Backus 團隊數年的血汗，語法分析部分是一團為了規避 Bug 而層層加補丁的啟發式程式碼。工程師們憑直覺知道「先把字切成字，再判斷句型」是對的路徑，卻沒有任何理論告訴他們這條路能不能走通、會在哪裡撞牆。

喬姆斯基的階層恰好提供了這張地圖。一個程式語言的「字」——識別字、數字、運算符——它們的形狀是有限的重複與拼接，正是正則文法的小菜一碟；而程式語言整體的巢狀結構（表示式裡套表示式、敘述裡套敘述）則需要上下文無關文法。這意味著：詞法分析可以用有限自動機高效解決，線性時間、無須回溯；語法分析則落在 CFG 的疆域內，有堆疊就能處理任意深度巢狀。

1960 年，ALGOL 60 報告問世，彼得・瑙爾（Peter Naur）採用 John Backus 在 1959 年提出的記法，以一種被後世命名為 BNF（巴克斯–瑙爾範式）的形式，把整個語言的語法寫成一套精確的上下文無關文法。這是程式語言史上第一次，一個語言的定義本身就是一份數學物件。ALGOL 60 報告因此被譽為「程式語言定義的里程碑」——它不僅描述了語言，更示範了語言應當如何被描述。此後 BNF 成為所有語言標準文件的基本格式，FORTRAN、COBOL 的後繼標準、PL/I、Pascal、C，無一例外。

純理論改造工程#

這段歷史最深刻的教訓，在於「動機」與「後果」之間的巨大錯位。喬姆斯基從未想過要幫助編譯器設計——他的目標是理解人類心智，後來更是批判美國的越戰與帝國主義。他建立的形式語言階層，是為了讓語言學擺脫印象式描述、成為一門嚴格科學。然而正是這份「沒有任何應用意圖」的純理論，為整個軟體工業提供了地基。

這並非孤例。圖靈 1936 年的論文本是為了解決希爾伯特的判定問題，結果奠定了所有計算機的理論模型；克林尼（Stephen Kleene）1940 年代研究神經網路的正則事件，其「克林尼星號」\(L^*\) 運算後來成為每個程式設計師日常使用的正則表達式。基礎研究的價值，往往在數十年後、在意想不到的領域以意想不到的方式兌現——而這恰恰是任何以短期應用為導向的資助制度最難容納的邏輯。

1960 年代，業界迅速跟進。IBM 的 PL/I 編譯器、各種 ALGOL 實作，都開始以 CFG 為骨架組織編譯器；大學課堂上，喬姆斯基階層成為編譯理論課程的第一章，並且延續至今。語言學家造的尺，成了工程師量世界的標準量具。

接下來的兩節，我們將沿著這張地圖，走進編譯器前端的內部：先看正則文法如何化身為詞法分析器，再看 CFG 如何在數十年的理論演化後，變成自動生成的解析器。