從一堆規則，到一段逐步的故事
在前一篇你認識了作為四元組 (V, Σ, R, S) 的上下文無關文法：變數集合 V、終端符號的字母表 Sigma（Σ，即真正的字母）、有限的一堆產生式規則 R，以及一個選定的起始符號 S。但一堆規則乾擺在那裡什麼也生不出來——你必須去使用它們。文法不像 DFA 那樣讀一個字串再回答接受與否；它是從種子 S 出發、一次重寫一個佔位符、直到只剩真正字母為止，藉此「建造」字串。本篇談的正是這個建造過程，以及我們如何把它記錄下來。
唯一的原子動作是推導步驟，寫成 u => v。它的意思是：取當前字串 u，在其中找到某個變數 A 的「一個」出現處，把那一個 A 替換成某條規則 A → α 的右側。A 周圍的一切都保持不動。所以若 u 形如 xAy（其中 x 與 y 是任意符號字串），而文法有規則 A → α，則一步之內 xAy => xαy。這就是整套機制——一條規則、一個變數、一次替換。文法的全部威力，不過是把許多這樣的微小替換串連起來。
把這些步驟從起始符號一路串接到一個全是終端符號的字串，你就得到一個推導：一串 S => w1 => w2 => ... => wn，其中 wn 已沒有任何變數可再展開。我們寫 S =>* w（讀作「S 經零步或多步推導出 w」）表示存在這樣一條鏈。帶星號的箭頭允許零步，所以顯然 S =>* S。一個字串 w 屬於文法的語言，恰當且唯當存在「某個」以純終端符號收尾的推導 S =>* w——這就是「文法生成什麼」的完整定義。
句型：途中的快照
推導進行到一半時，你手上握著一個半成品：一部分是真正的字母，一部分是仍等著被展開的佔位符——就像一個填空句子，有些空格填了、有些還空著。每個這樣的中間字串就是一個句型：形式上，任何滿足 S =>* w、由終端符號與變數組成的字串 w。最最開頭的句型是單獨的起始符號 S 本身（零步即達）。推導的每一行都是一個句型；推導不過是把它們列成一張清單。
當一個句型「只」含終端符號——不再剩任何變數——時，它有個特別的名字：句子，而它恰好是語言的一個成員。所以「句型」是一般概念（施工中，可能仍含變數），「句子」是完工的特例。一個常見的口誤是把含有殘留變數的半成品字串叫作句子；它不是——在最後一個變數都被重寫掉之前，它都只是個句型。文法所生成的語言，恰好就是它所有句子的集合：所有從 S 可達的、只含終端符號的字串。
以文法 S → A B、A → a A | a、B → b 為例，看著快照一張張閃過：S => A B => a A B => a a B => a a b。前四個字串（S，接著 A B、a A B、a a B）都是仍握有至少一個變數的句型；只有最後一個 a a b 全是終端符號——那一個才是句子，它證明了 S =>* aab，把「aab」放進了語言。順著這串快照往下讀，就是在讀推導；變數一耗盡的那一刻，你就降落在語言之中了。
下一個重寫哪個變數？最左與最右
推導步驟裡藏著一個自由：當一個句型握有「好幾個」變數時，你下一步要重寫哪一個？定義裡沒有任何東西強迫你怎麼選，所以同一個字串可以由許多不同的序列建造，它們只差在你以何種順序去攻擊那些變數。為了馴服這點，我們採取一條紀律。最左推導在每一步都重寫「最左邊」的變數——就像嚴格地由左到右讀寫，絕不在填完較前面的空格之前跳去填較後面的。我們有時把這些步驟標記為 =>lm。
它的鏡像是最右推導（標記為 =>rm），它總是先伸手去抓「最右邊」的變數。兩種紀律描述的是「同一個」推導概念——它們只固定了要攻擊「哪個」變數，去除這一個自由，只留下「要套用哪條規則」這個真正的選擇。以文法 S → A B、A → a、B → b B | b 為例。「abb」的一個最右推導會在碰 A 之前先把 B 完全展開：S =>rm A B =>rm A b B =>rm A b b =>rm a b b。同一字串的最左推導則先做 A：S =>lm A B =>lm a B =>lm a b B =>lm a b b。同一字串、同一結構——只是步驟順序不同。
剖析樹：為許多推導畫的一張圖
這裡是整篇指南的關鍵。推導是一段冗長、逐步的口述；剖析樹則是把同樣的資訊畫成一張圖，並悄悄丟棄了那從不重要的部分——獨立的選擇碰巧以何種順序作出的順序。樹的形狀顯示各片段如何彼此巢狀。它是字串的結構骨架，也是「這是怎麼組合起來的？」這個問題的誠實答案。
樹是怎麼建的？根標記為起始符號 S。每個內部節點都標記為一個變數，而標記為 A 的節點之子節點——由左到右讀出——恰好拼出某條用來展開那個 A 的規則 A → α 的右側。葉節點標記為終端符號（或當套用形如 A → ε 的規則時標記為 ε，它不貢獻任何字元）。所以每個內部節點是一次規則套用，而整棵樹一次記錄了整個推導，與規則觸發的順序無關。
把手指沿著葉節點由左到右滑過，把看到的寫下來：這串終端符號就是樹的果實（也稱為它的邊界）。果實只從「葉節點」讀出——標記內部節點的變數是結構的一部分，卻絕非果實的一部分。這給了語言第二個、完全等價的定義：一個字串 w 在文法的語言中，恰當且唯當存在一棵根為 S、果實為 w 的剖析樹。推導與樹描述的是同一組字串；樹只是保留結構、丟棄順序的雜訊。
Grammar: S -> A B, A -> a A | a, B -> b
Parse tree for 'aab':
S
/ \
A B
/ \ |
a A b
|
a
Reading the leaves left to right: a a b -> yield = "aab"樹對上推導，以及歧義的種子
現在來談那個深刻的關係，它值得背下來。「一」棵剖析樹對應「許多」推導（把獨立重寫排序的所有方式），但「恰好一個」最左推導與恰好一個最右推導。這個對應是一一對應的：每棵剖析樹給出唯一的最左推導，而每個最左推導也回給一棵唯一的剖析樹。這正是為何樹、而非原始的推導序列，才是結構的正確概念——只在記帳順序上不同的兩個推導，會塌縮成同一棵樹。
- 若兩個推導產生相同的剖析樹，它們就描述「相同」的結構——即使它們的步驟序列不同（最左與最右的通常就不同）。光是步驟順序不同，什麼也不代表。
- 所以「兩種結構」的誠實檢驗，是兩棵不同的剖析樹——等價地，兩個不同的「最左」推導（或兩個不同的最右推導），因為每棵樹各只有一個。
- 一個文法是「歧義的」，恰當且唯當其語言中的某個單一字串有兩棵真正不同的剖析樹。扁平文法 E → E + E | E * E | a 是經典慣犯：a + a * a 既剖析為 (a + a) * a，又剖析為 a + (a * a)——同一果實、兩棵樹、兩種不同的分組。
這條路要通往哪裡
你現在擁有了把一堆靜態規則變成活生生生成器的機械：推導步驟 u => v、串接的推導 S =>* w、沿途的句型、兩種有紀律的順序（最左與最右），以及最重要的、果實即所生成字串的剖析樹（其果實）。語言的兩個等價定義如今擺在你眼前：「滿足 S =>* w 且 w 為終端符號的 w」與「作為某棵根為 S 之樹的果實的 w」。兩者描述的都恰好是該文法的上下文無關語言。
下一篇把這從分析變成手藝：如何「設計」一個上下文無關文法，使它恰好生成你想要的語言——a^n b^n、平衡括號與算術表達式的遞迴模板，全藉遞迴思考建成（一個基底情形，加上一條把較小實例包進較大東西裡的規則）。而一旦你能生成正確的字串「集合」，第四篇就把標準提高到更難、也更誠實的目標：藉由消除歧義，給每個字串「正確的樹」。前進時請緊握一個念頭——承載意義的，永遠是剖析樹，而非推導順序。