設計上下文無關文法

從讀規則到寫規則

在這一階梯到目前為止，你一直是文法的讀者：給你一個上下文無關文法和一個字串，你描出一條推導、畫出剖析樹。設計則是反過來的手藝。你從一個目標出發——一個你想生成的語言，裡頭的每個字串都要生得出，外頭的一個字串也不能生——而你必須發明出恰好命中那個目標的變數、產生規則與起始符號。並沒有什麼機械化的演算法，能憑一句語言描述就把文法交到你手上；設計確實是創造性的。但它也不是瞎猜。一小套反覆出現的套路，就涵蓋了你這輩子會遇到的絕大部分語言。

最有用的一個習慣，是把每個變數讀成一個關於子語言的承諾。挑一個名字，然後用白話把你打算讓那個變數生成的字串集合，一字一句地寫下來。比方說，「S 生成每一個配對括號字串」，或「E 生成每一個格式正確的算術運算式」。一旦某個變數有了這樣的契約，每一條左邊是該變數的規則，就都必須守住這個承諾：右邊只能提到那些本身也與各自契約相符的零件。於是設計就變成了「填入一些尊重一小組承諾的規則」——而扛起重活的，是遞迴。

第一招：能對上計數的遞迴

回想正規語言那一階梯的金絲雀：a^n b^n，也就是「若干個 a，後接恰好同樣多個 b」的字串。幫浦引理證明了有限記憶沒辦法這樣計數，所以沒有任何正規文法搆得著它。上下文無關文法卻可以，而訣竅正是那個讓文法比有限自動機更強大的招式：一條同時往兩端添上相配零件的規則。把一個 a 和一個 b 包在同一結構的較小副本外頭，再讓基底情形在空字串處停住遞迴。

整個文法就兩條規則：S -> a S b | epsilon。第一條是包覆，第二條是在空字串（epsilon）處停住的基底情形。看著 aabb 的一條最左推導自然掉出來：S => a S b（套用包覆）、=> a a S b b（再包一層）、=> a a b b（套用 S -> epsilon）。對應的剖析樹根部是一個 S，子節點為 a、S、b；那個內層的 S 又有子節點 a、S、b；最內層的 S 走向 epsilon。把葉子由左讀到右，產出物恰好是 aabb。每一次規則套用都貢獻了一個 a 與一個 b，所以就構造而言，這兩個計數絕不可能有差。

為什麼這在有限記憶失敗之處卻行得通？這個遞迴不是用一個數字在計數——它是用結構在配對。某條規則生出的每一個 a，都在同一次規則套用裡與它自己的 b 一同誕生，所以無論巢狀有多深，它們都不會失衡。這正是你稍後在這座階梯會遇見的下推自動機的種子：同一份平衡，也可以用一疊盤子來執行，每讀一個 a 就推一個、每讀一個 b 就彈一個。文法與堆疊，是同一份「比有限自動機多出來的力量」的兩張臉。

第二招：巢狀，與配對括號的語言

現在從一對相配，推廣到任意的巢狀。配對括號的語言，包含空字串、`()`、`(())`、`()()`、`(()())`，以及每一個正確地開啟與閉合的括號字串——但不含 `)(` 或 `(()`。這裡有兩招合在一起。第一，先前那招包覆：一個配對字串，可以是一個較小的配對字串、外頭再圍上一對新括號。第二，一招串接：兩個配對字串並排黏在一起，仍然是配對的。給變數 S 這個承諾——「S 恰好生成那些配對括號字串」——這兩招就都化成了規則。

結果是三條規則：S -> ( S ) | S S | epsilon。第一條在一個配對的內部外頭包上一對括號；第二條把兩個配對字串並排擺放；第三條在空字串處停住。要看它們生成 (())()，就推導 S => S S（拆成兩個配對的半邊）、=> ( S ) S（包覆左半）、=> ( ( S ) ) S（往內再包一層）、=> ( ( ) ) S（用 epsilon 收掉那個內層）、=> ( ( ) ) ( S )（包覆右半）、=> ( ( ) ) ( )（epsilon）。每個 `(` 都由同一次包覆引入的 `)` 來閉合，所以這字串永遠不會失衡。

看著這套工具運作。單一的遞迴變數 S，加上一個基底情形，再加上自我串接，是一個你會不斷重用的樣式：它正是巢狀串列、相配的 HTML 或 XML 標籤、區塊結構程式碼，以及 JSON 的骨架。不過要誠實地警告一句：文法 S -> ( S ) | S S | epsilon 雖然正確，卻是歧義的——空字串、甚至 `SS`，都容許不只一棵剖析樹，因為 S S 可以往左或往右結合。語言的正確性，與剖析的唯一性，是兩個不同的目標；下一招以及整篇下一份指南，談的就是怎麼補上第二道缺口。

第三招：把優先序內建進去的算術運算式

現在來談把玩具文法變成真正編譯器前端的那一招：像 `a + b * c` 這樣的算術運算式。天真的文法 E -> E + E | E * E | ( E ) | a 把語言寫對了，卻歧義得無可救藥——`a + b * c` 可以剖析成 `(a + b) * c` 或 `a + (b * c)`，而只有一個符合數學的本意。修法不是把規則扔掉，而是把優先序編碼進變數的分層裡。我們替每個優先序層級發明一個變數，並讓層級由結合最鬆、降到結合最緊。

把運算子依優先序排名。最低的結合最鬆（+ 與 -），再來是乘法與除法，最後是結合最緊的零件：數字、名稱，以及任何放在括號裡的東西。每個排名配一個變數：E 代表運算式、T 代表項、F 代表因子。
讓每一層都用「更緊的下一層」搭建出來。E 是若干個 T 相加；T 是若干個 F 相乘；F 是原子的東西。因為 `+` 只活在 E 這一層、`*` 只活在 T 這一層，所以在樹上，`*` 絕不會不小心坐到 `+` 的上頭。
用「哪一側遞迴」來編碼結合性。寫成 E -> E + T（遞迴在左側）會迫使左結合的分組，於是 `a - b - c` 剖析成 `(a - b) - c`——這正是減法實際運作的方式。
讓括號在最底層重新進場：F -> ( E )。這使得一個帶括號的運算式能當成單一的緊密因子，而這恰恰是括號在真實算術裡覆寫優先序的方式。

Unambiguous expression grammar (precedence + associativity built in)

    E  ->  E + T  |  E - T  |  T
    T  ->  T * F  |  T / F  |  F
    F  ->  ( E )  |  id

Parse of  a + b * c  is now FORCED:

            E
          / | \
         E  +  T
         |    /|\
         T   T * F
         |   |   |
         F   F   c
         |   |
         a   b

The '*' node sits BELOW the '+' node, so b * c is grouped
first -- i.e. a + (b * c), the mathematically correct reading.

每個優先序層級配一個變數（E、T、F），使得那棵唯一正確的剖析樹成為唯一可能的一棵。乘法之所以結合得更緊，是因為它在文法中被生成得更深。

停下來體會一下剛剛發生的事，因為這正是實用文法設計的關鍵。我們並沒有更動語言——新文法生成的字串集合，與那個天真版本一模一樣。改變的是樹的形狀，而既然編譯器是靠走訪這棵樹來計算意義的，塑造樹形也就是塑造語義。優先序與結合性，並不是事後另外拴上去的功能；它們是「你如何分層變數、又在哪一側遞迴」的後果。每當你為一門程式語言寫文法，這個單一技巧就會再度現身。

設計搆不著的地方，與誠實的界限

兩個誠實重點，能把你的期待校準。第一，從一個文法裡移除歧義，往往是你做得到的手藝——但有些語言是本質歧義的：為它們寫的每一個上下文無關文法都歧義，沒有任何改寫能修好。標準的例子，是「a^i b^j c^k 字串中，i = j 或 j = k」的語言。本質歧義是語言本身的性質，不是你不夠聰明的失敗，所以別花上好幾個鐘頭，去獵捕一個可以被證明不存在的無歧義文法。

第二，上下文無關文法強大，卻不是萬能。包覆這招配對一組計數，巢狀則能應付任意深度——但文法沒辦法同時執行兩組互不相干的相配計數。語言 a^n b^n c^n（三者個數都相等）不是上下文無關的；你稍後會用上下文無關語言的幫浦引理證明這件事。一個概略的法則是：文法擅長一層的巢狀或配對，卻沒辦法讓兩筆毫不相干的帳目保持同步。那道界線，恰恰就是喬姆斯基層級中、上下文無關之上的那一階，在那裡你需要一台更強的機器。