有限自動機撞上的那道牆
到現在你已經能建造並信任一台 DFA：一台像旋轉閘門的機器，只記得目前的狀態，由左到右讀一個字串，最後說接受或拒絕。你也知道你用幫浦引理證出的那個痛苦極限：語言 a^n b^n——先若干個 a、再同樣數量的 b——不是正規語言。直覺很直白。一台 DFA 有固定且有限的狀態集合，所以它只能記住有限多件事之一；要檢查 a^n b^n，它得記住自己看過多少個 a，而 n 可以無上限地增大。有限的記憶體就是無法無界地計數。
這不是玩具例子才有的怪癖。真實的程式充滿了巢狀：括號裡套括號、區塊裡套區塊、一個 `if` 的主體又含另一個 `if`。最簡單而誠實的巢狀版本就是配對括號——像 (()) 與 ()() 這樣的字串是平衡的，但 ()) 與 )( 不是。要辨識配對括號，你實際上必須把每個左括號和後面某個右括號配起來，同時追蹤你目前嵌得多深。那個深度沒有上限，所以再一次，沒有任何正規語言能捕捉它。我們撞到了有限自動機世界的天花板。
翻轉問題：從讀取到建造
你到目前為止遇到的每一台機器都是讀者：把字串交給它，它判斷是或否。文法則把望遠鏡掉轉過來。文法不是讀一個完成的字串再評判它，而是從零建造字串。你從單一個佔位符開始，依照一份固定的規則清單，反覆把佔位符替換成其他片段，直到剩下的全是真正的字母為止。用這種方式所能建造出的所有字串，所成的集合就是這個文法描述的語言。問題從辨識移到了生成。
文法有四項材料。有變數（又稱非終端符號）：寫成大寫字母的特殊佔位符號，代表「仍在施工中的片段」。有終端符號：寫成小寫的真正字母表字母，會存活到完成的字串裡，且永不被重寫。有一個起始符號，一個你總是從之開始的選定變數。還有一份有限的產生式清單，每條形如 A → α，讀作「A 可重寫為 α」，其中左側是單一變數，右側是任意由變數與終端符號組成的字串。「左側單一變數」這條限制，正是讓文法成為上下文無關文法的關鍵。
為什麼叫上下文無關？因為每條規則的左側都只是一個變數，你不管它周圍有什麼都可以重寫它——它的「上下文」無關緊要。這是對規則形式的限制，並非宣稱意義被丟棄了。形式上我們把上下文無關文法打包成一個四元組 (V, Σ, R, S)：V 是變數，Σ（Sigma，字母表）是終端符號，R 是規則，S 是起始符號，且 V 與 Σ 互不相交。
遞迴就是全部的訣竅
這裡就是那個打破有限自動機天花板的招式：一個變數被允許出現在它自己的右側裡。規則 S → ( S ) 說「一個 S 可以是一對括號包住另一個 S」。套用一次你得到 ( S )；對裡面那個 S 再套用一次你得到 ( ( S ) )；如此繼續，你想嵌多深就多深。一份有限的規則清單生成無界深的巢狀，因為每次使用規則都能再生出一份新的變數副本，留待稍後展開。這就是遞迴，正是 DFA 所欠缺的那股力量。
我們來真正解掉那兩個擊敗 DFA 的語言。對 a^n b^n，文法是一條遞迴規則加一個基底情況：S → a S b 與 S → epsilon，其中 epsilon 是空字串。每次使用 S → a S b 都在左邊加恰好一個 a、在右邊加恰好一個 b，成對同步，所以兩者的數量永遠不會漂移分離；S → epsilon 則在中間停止遞迴。對配對括號，文法 S → S S | ( S ) | epsilon 就能勝任：( S ) 包住一個巢狀群組，S S 把兩個平衡字串並排，而 epsilon 是空的（仍然平衡的）字串。
Grammar for a^n b^n: Grammar for balanced brackets:
S -> a S b S -> S S | ( S ) | epsilon
S -> epsilon
Build aabb step by step: Build (()) step by step:
S S
=> a S b (S -> a S b) => ( S ) (S -> ( S ))
=> a a S b b (S -> a S b) => ( S S ) (S -> S S)
=> a a b b (S -> epsilon) => ( ( S ) S ) (S -> ( S ))
=> ( ( ) S ) (S -> epsilon)
yields aabb => ( ( ) ) (S -> epsilon)
yields (())從規則上讀出一次建造
上面那段逐步的故事——S => a S b => a a S b b => a a b b——稱為一次推導：一串字串，其中每一個都由前一個套用單一規則而來，從起始符號開始，以一個純終端符號的字串結束。我們寫 S =>* aabb 表示「S 經零步或多步推導出 aabb」。一個字串屬於文法所生成的語言，恰當且唯當存在它從 S 出發的某個推導。（你會在下一篇深入研究推導，以及把推導畫出來的剖析樹；這裡只要注意「它在語言中嗎？」已經變成了「文法能建造出它嗎？」）
有一個乾淨的方式能看出這個設計模式：把每條規則讀成一句關於結構的話。S → a S b 讀作「一個東西是一個 a、接著一個較小的東西、再接著一個 b」。E → E + E 讀作「一個表達式可以是一個表達式加上一個表達式」。設計文法在很大程度上就是發明對的變數的手藝——每個變數命名一種連貫的子結構種類——再寫出規則，說明每種如何由終端符號以及其他（或相同）種類建造而成。變數之間的遞迴，正是讓寥寥幾條規則得以描述無限的字串家族的關鍵。
當結構並不唯一：歧義
現在來看一個真正微妙的地方，也是這些文法對程式設計之所以重要的原因。考慮算術：E → E + E | E * E | a。試著建造 a + a * a。你可以用兩種真正不同的方式建造它——一種把它分組成 a + (a * a)，另一種把它分組成 (a + a) * a。同一個字串，卻有兩種不同的結構。一個文法若其中某個字串能以兩種不同結構建造，就稱為歧義文法，而歧義對編譯器來說是毒藥：如果 * 究竟先於還是後於 + 結合得看擲硬幣，那麼你程式的意義就沒有定義。
解藥是把優先級與結合性編進規則本身——把文法分層，逼出唯一的結構。為各層引入不同的變數：一個表達式是若干項之和，一個項是若干因子之積，一個因子是一個原子或一個括起來的表達式。於是 E → E + T | T、T → T * F | F、F → ( E ) | a。因為 + 住在比 * 更高的一層，每個 * 都必須在任何 + 觸及它之前先結合，所以 a + a * a 只能建造成 a + (a * a)。分組現在被烤進了規則的形狀裡。
文法的位置，以及這條路要通往哪裡
退後一步，把這件事放上地圖。正規語言——下方那幾階的 DFA／NFA／regex 世界——是最底層；上下文無關語言，也就是文法所生成的那些，高一階，並嚴格包含正規語言（每個正規語言都有文法，但 a^n b^n 有文法卻沒有 DFA）。本階梯稍後你會遇到那台在原始能力上與文法匹敵的機器：下推自動機，一台帶著一疊盤子的有限狀態控制器，而你永遠只能碰最上面那個盤子。那疊堆疊正是普通 DFA 所欠缺的無界記憶，而它恰好足夠——不多不少——去辨識上下文無關語言。
本階梯接下來四篇都建立在今天的圖像上。第二篇把推導與剖析樹講精確，並說明為什麼是剖析樹——而不是你恰好套用規則的順序——才是字串結構的誠實概念。第三篇把文法設計變成一門可教的技能，以 a^n b^n、配對括號與算術作為演練範式。第四篇正面進攻歧義。第五篇把這一切連到 BNF 與 EBNF 記號，那正是真實程式語言手冊實際用來發布語法的記法。你進來時能讀字串；離開這一階梯時，你能生成並建構它們。