6.2 決定論的文法樹：巴科斯-瑙爾範式（BNF）的誕生#
一份報告引發的匯流#
1958 年，一場在蘇黎世的會議（ACM + GAMM 聯合）產生了 ALGOL 58 報告——第一個國際合作的程式語言設計（美國與歐洲各半，針對 Fortran 的美國中心主義與 COBOL 的商業化，學術界想要一門「純粹的演算法語言」）。
報告的問題：描述語法用的是散漫的英語，歧義叢生。巴庫斯隨後在 1959 年的巴黎 UNESCO 會議論文中，提出了一套記號法來精確描述 ALGOL 58。
丹麥的彼得·瑙爾（Peter Naur） 在編輯 ALGOL 60 報告時，把這套記號法系統化並首次用於完整定義一門語言——這就是 BNF（Backus–Naur Form）。瑙爾後來回憶，他並不知道喬姆斯基的工作，是獨立「重新發明」了 CFG 記法；經過提醒，ALGOL 60 報告的修訂版正式引用了喬姆斯基。理論與工程在一份報告的編輯過程中焊接——這是本書「數學搶跑、工程提貨」模式的又一案例。
BNF 長什麼樣#
ALGOL 60 的條件語句：
<if 語句> ::= if <布林表達式> then <無標號語句>
<條件語句> ::= <if 語句> | <if 語句> else <語句>
<識別字> ::= <字母> | <識別字><字母> | <識別字><數字>
::=讀作「定義為」|表示「或」<...>是非終端符號
BNF 的偉大之處不是發明（CFG 已存在），而是「社會化」：它讓語言規範從散文變成可機械檢查的數學對象。一門程式語言從此可以：
- 被無歧義地寫進文件（避免 Fortran 各廠商方言叢生的混亂）
- 被自動生成解析器（1960s 末的工具化伏筆）
- 被證明性質（歧義性、可解析性）
ALGOL 60 報告因此被稱為「史上最被引用的程式語言文件」——它開創的不只是語言，還有「語言規範」這個文體本身。
從文法到語法樹：決定論的勝利#
BNF 的推導天然產生推導樹（語法樹）：
<expr> ::= <expr> + <term> | <term>
<term> ::= <term> * <factor> | <factor>
<factor> ::= ( <expr> ) | <數字>
2 + 3 * 4 的兩種樹：
+ *
/ \ / \
2 * + 4
/ \ / \
3 4 2 3
同一字串兩棵樹 = 文法有歧義（第一棵 = 14，第二棵 = 20）。工程解法：運算優先級被編碼進文法的層次（expr→term→factor 的層層包裹）。
這裡有深刻的設計哲學：程式語言與自然語言的最大差異是——程式語言的語法樹必須唯一。喬姆斯基證明自然語言必然歧義（這是創造力的來源），而程式語言的設計目標是機械可判定、唯一確定。「決定論的文法樹」是工程對語言學的翻轉：人類溝通需要歧義的容錯，機器溝通需要歧義的排除。
解析器的兩大策略（工程與理論的再握手）#
| 策略 | 思想 | 複雜度 | 代表 |
|---|---|---|---|
| 自頂向下（LL） | 從起始符號向下展開 | 線性（需消除左遞歸） | 遞歸下降（Go、Rust、Python PEG） |
| 自底向上（LR） | 從 token 歸約回起始符號 | 線性（表格大） | yacc/bison、GCC（Knuth 1965 LR 理論） |
遞歸下降的復興值得記錄：1970s–2000s 工業界多用 LR 生成器；2010s 起手工遞歸下降（錯誤訊息友善、IDE 增量解析）成為新主流——工具的易讀性壓倒了理論的完備性，這與 AI 時代人類需要「能讀懂的解析器」的需求一致（第 17 章伏筆）。
BNF 的後裔與變體#
- EBNF（擴展版）：加
?*+，今天幾乎所有語言規範的寫法 - PEG（解析表達文法，2004）：確定性的「優先選擇」語義，把歧義用順序排除——Python 3.9 起採用
- 語法圖（鐵路圖）：Pascal 報告用圖形文法——視覺化規範的先驅
- 形式驗證中的文法：從 AST 生成測試用例（fuzzing 的語法導向變體）
制度史：標準之戰#
BNF 時代也是標準政治的開端：
- ALGOL 60 的國際委員會模式（學術共識）vs Fortran 的廠商事實標準（IBM 主導）vs COBOL 的政府標準（國防部）——三種標準化制度並行競爭
- ALGOL 委員會內部的分歧（字元集的歐美之爭、短路求值之辯）預告了後世所有語言委員會（C++、ECMA、Rust RFC）的劇本：技術議題總是包裹著社群與商業利益
- 瑙爾 2005 年獲圖靈獎——寫規範的人與寫編譯器的人同樣載入史冊