從手寫剖析器到文法編譯器
在這一階梯裡，你親手寫過遞迴下降剖析器，接著由下往上追蹤過移入歸約機器，再見過最壞情況也安全的 CYK 與 Earley 演算法。每一種，對每一份文法都是實打實的工。下一個顯而易見的願望是：把這份文法寫下一次，然後讓一支程式替你產生剖析器。這支程式就是剖析器產生器——把它想成一個編譯器，只不過它的原始語言是文法規則，輸出則是剖析器程式碼。經典的一對是 yacc（Yet Another Compiler-Compiler，1975）與它的自由軟體重寫版 bison；在別的生態系裡你會遇到 ANTLR、menhir 或 tree-sitter，但想法都一樣。
關鍵在於，yacc 與 bison 並不在剖析時跑 CYK 或 Earley。它們建出的是你在第 3 篇研究過的 LR 剖析表——具體說是一種叫 LALR(1) 的變體——並輸出一個快速、由表格驅動的移入歸約剖析器，在輸入上以線性 O(n) 時間執行。CYK 與 Earley 很通用（任何上下文無關文法都能應付，連有歧義的也行），代價是 O(n^3)；bison 這類工具拿這份通用性換取速度，回過頭來它就會堅持你的文法落在確定性的 LR 家族之內。當你的文法不在其中，它會告訴你——而且很大聲——而那場對話，正是真正工作的大半。
一份文法檔長什麼樣子
一份 bison 輸入檔，會把每條文法規則配上一段程式碼——稱為語意動作（semantic action）——這段碼會在剖析器依該規則歸約時執行。回想第 1 篇：剖析器並不吞食原始字元；一個掃描器／詞法分析器已先把文字切成像 NUM、PLUS、LPAREN 這樣的詞元。文法寫在這些詞元名稱之上，而一次歸約，正正是你已辨識出一個完整片語、可以對它做點事的那一刻——通常就是建出結果樹的一個節點。
一個具體的例子：規則 `expr : expr PLUS term` 也許帶著動作 `$ = makeNode(+, 1, $3)`。這裡 $1 與 $3 代表右邊第一個與第三個符號的值（兩個子運算式），而 $$ 是這條規則替它左邊回交的值。於是這個動作把子節點的值接線成一個新的加號節點，再往上傳。把文法拆成分層的 expr／term／factor 規則——其中 `factor` 涵蓋一個 NUM 或一個帶括號的 expr——也等於在我們還沒談優先序之前，就把「乘法比加法綁得更緊」直接編進了文法的形狀裡。
在 $1、$3、$$ 之間流動的值，是指向樹節點的指標，而它們組裝出來的東西，就是一棵抽象語法樹（AST）。這是整個前端最深的回報。一棵剖析樹（又稱具體語法樹）記下了每一條被觸發的文法規則，包括 term、factor 這類記帳用的非終端，以及括號這類雜訊；而 AST 把這些全丟掉，只留下意義——對 `1 + 2 * 3`，它是一個加號節點，其右子節點是一個乘號節點，忠實地記下乘法先發生。下游的一切（型別檢查、最佳化、產碼）走的都是這棵 AST，而不是原始文字。
衝突：當剖析器決定不了
把一份有歧義、或只是笨拙的文法交給產生器，它就建不出確定性的表——會有一個表格欄位，它不知道該怎麼辦。那就是一次衝突，而它有兩種口味。一個移入歸約衝突是說：在同一個前瞻詞元下，剖析器既可以移入（再讀些輸入，賭這個片語還沒完），也可以歸約（宣告片語已完成、套用規則）。一個歸約歸約衝突則是說：兩條不同的規則都來認領同一個已完成的片語。衝突不是隨機的失敗；它是產生器在告訴你，這份文法真的有歧義，或者落在了 LR 的單詞元前瞻搆不到的地方。
教科書級的移入歸約衝突，是懸盪 else（dangling else）：在 `if C1 then if C2 then S1 else S2` 裡，這個 `else` 是貼在內層的 `if`，還是外層的？在天真的文法下兩棵剖析樹都合法，所以一見到 `else`，剖析器分不清該歸約內層的 if 述句（不帶 else 就把它收掉），還是移入這個 `else`（把它交給內層的 if）。真實語言用一條規則來了結它——「else 貼向最近的、尚未配對的 if」——而剖析器產生器讓你把這個選擇編進去，不必把文法改寫成沒人看得懂的樣子。
優先序：保留歧義，卻把它化解
處理算術文法有兩種辦法。一是用上面那種分層的 expr／term／factor 規則把結構焙烤進去——清楚，但每加一個運算子文法就腫一圈。另一種是寫下那條極短卻有歧義的規則 `expr : expr OP expr`，再把優先序與結合性當作獨立的指示宣告出來。產生器保留那份小巧的文法，卻用你的宣告去化解歧義所造出的每一個移入歸約衝突。這是衝突解決的日常用法，也是真實文法檔得以保持小巧的原因。
%left PLUS MINUS /* lowest precedence, left-associative */
%left TIMES DIVIDE /* higher precedence, left-associative */
%right POWER /* highest, right-associative: 2^3^2 = 2^(3^2) */
%%
expr : expr PLUS expr
| expr TIMES expr
| expr POWER expr
| NUM
;
/* The grammar is ambiguous, but %left/%right lines below resolve
every shift-reduce conflict:
- later %left/%right line = higher precedence
- %left prefers REDUCE (a-b-c parses as (a-b)-c)
- %right prefers SHIFT (a^b^c parses as a^(b^c)) */留意這個精確的機制：對 `expr . OP expr`（那個點是剖析器所在之處）的衝突，是靠比較堆疊上那個運算子的優先序，與即將到來的前瞻運算子的優先序來了結的。堆疊上的較高，就現在歸約；即將到來的較高，就移入。優先序相等時，退回看結合性——%left 歸約，%right 移入。所以「優先序與結合性」並不是含糊的揮手；它是一條確定性的規則，專門用來填 LR 表中那些恰好起衝突的欄位。文法在紙上仍有歧義，但那個剖析器是徹底確定性的。
超越程式語言
文法與剖析器，不只是給原始碼用的。自然語言剖析用上下文無關（以及更豐富）的文法，替英文或中文句子指派句法結構，而在這裡，那些舒適的假設以發人深省的方式崩解。人類語言處處有歧義——`I saw the man with the telescope`（我用望遠鏡看見那人／我看見那個帶著望遠鏡的人）有兩棵都說得通的剖析樹，而沒有任何優先序指示能挑出對的那一棵，因為對的那棵取決於意義，而非句法。所以自然語言剖析器通常保留通用的 O(n^3) Earley 或 CYK 機制，並以機率去排序眾多可能的樹，而不是強逼出單一的確定性答案。
同樣的「文法加剖析」想法，也遠遠延伸到語言之外：剖析結構化的資料格式（JSON、一個網路封包的標頭、一個日期字串）、驗證設定檔、剖析一局西洋棋的記譜或一條化學式、讀懂標記語言的巢狀結構。只要你手上有一串帶有巢狀、遞迴結構的詞元，這一階梯的機制就派得上用場。結構越乾淨，越可能一個確定性的 LR 或 LL 剖析器就夠用；越凌亂、越人性，你就越要伸手去拿那些通用演算法。
退一步，把整個階梯看成一道弧。一個正規語言的掃描器把字元變成詞元；一個由上而下的 LL 剖析器，或一個由下而上的 LR 剖析器，把詞元變成一棵樹，而FIRST 與 FOLLOW 集和句柄是其中的局部決策工具；CYK 與 Earley 則為那些對前兩者都太棘手的文法待命；而剖析器產生器把致勝策略打包起來，讓你再也不必手寫那張表。你寫下的文法是規格；你得到的剖析器，就是某個字串確實屬於該語言的證明——剖析這個問題，被自動回答了，而且在文法夠仁慈時，是以線性時間。