頭條：兩種描述，同一類語言
到目前為止，你已認識了兩種非常不同、用來描述上下文無關語言的方式。一種是上下文無關文法，一個生成器：它待在那裡，靠改寫變數來產出字串，正如你在文法那一階梯所見。另一種是本階梯第一、二篇中的下推自動機，一個辨認器：它由左至右讀入一個字串，推入又彈出一個堆疊，最後接受或拒絕。本階梯的核心定理是：這兩種描述涵蓋恰好相同的語言。一個語言有上下文無關文法，當且僅當有某台下推自動機辨認它。這就是下推自動機與上下文無關文法的等價。
為什麼要在意一個說「兩樣東西相等」的定理？因為各邊都擅長對方笨拙之處。當你想指定一個語言——比方說，描述一門程式語言合法的巢狀結構——文法是順手的筆。當你想靠掃過字串一次來判定成員資格，一台帶堆疊的自動機則是順手的機器。這份等價，讓你能在兩者間自由翻轉：用文法設計，再轉一轉曲柄，就免費得到一個辨認器，而那正是剖析器的本質。下一整階關於剖析的內容，全都倚靠這座橋。
文法變下推自動機：讓堆疊跑推導
較容易的方向，是把文法變成下推自動機，而點子優美得直接：建一台機器，讓它的堆疊執行文法的一條最左推導。回想文法那一階梯：最左推導永遠先改寫最左邊的變數。在任一時刻，推導中尚未「完成」的部分，是一串終端符號與變數混成的字串——一個句型。下推自動機把那個句型中尚未配對的尾段放在它的堆疊上，最左邊的符號在頂端，然後一路把它處理下去：用輸入去比對終端符號，並用規則去展開變數。
- 佈置。這台下推自動機本質上只有一個工作狀態。把文法的起始符號推上堆疊（在底端標記之上），於是堆疊一開始就恰好握著「整條還沒做完的推導」。
- 展開一個變數。若堆疊頂端是變數 A，就把它彈出，再推上某條規則 A -> alpha 的右側，最左符號在頂端。這個走法不讀任何輸入——它是個 epsilon 走法——而這正是下推自動機猜測要套用哪條規則的所在。
- 比對一個終端符號。若堆疊頂端是終端符號 a，而下一個輸入符號也是 a，就彈出那個 a 並讓輸入前進。若頂端的終端符號與輸入不合，這條分支就卡住、死掉。
- 接受。當輸入完全用盡，且堆疊空回到底端標記，每一次猜測都被證明是相符的——以空堆疊接受。若沒有任何一條執行抵達那個狀態，就拒絕。
第二步，正是非確定性掙得它薪水的地方。當變數 A 有好幾條規則，下推自動機並不知道這個特定字串需要哪一條，於是它分支、平行地全試一遍——用 NFA 的圖像來說，就是把自己複製出來。一個字串被接受，恰恰當某一串規則猜測，拼出了一條真正的、同時也與輸入相符的最左推導之時。所以下推自動機的接受執行，與文法中的最左推導是一一對應的。這份對應就是這個方向的全部證明：機器接受一個字串，當且僅當文法能推導出它。空堆疊接受在這裡是天然的契合，因為堆疊正好在推導完成之時清空。
Grammar: S -> a S b | epsilon (the language a^n b^n)
PDA built from it (single state q, accept by empty stack):
push S to start
delta(q, epsilon, S) = { push 'aSb' , push '' } <- guess a rule
delta(q, a, a) = pop <- match terminal a
delta(q, b, b) = pop <- match terminal b
Run on input a a b b (top of stack on the LEFT):
input left stack move
---------- ----------- -------------------------------
a a b b S expand S -> a S b
a a b b a S b match a (pop a, read a)
a b b S b expand S -> a S b
a b b a S b b match a
b b S b b expand S -> epsilon
b b b b match b
b b match b
(empty) (empty) ACCEPT下推自動機變文法：較難、較巧的方向
反方向——每台下推自動機都有等價的文法——乍看不可能，卻會回報一個細膩的點子。麻煩在於下推自動機的行為是糾纏的：它能做什麼，同時取決於它當前的狀態以及堆疊上正擺著什麼，而堆疊還能無限制地長大。我們馴服它的辦法，是替每一段自成一體的堆疊片段發明一個變數：寫成 A(p, X, q) 的變數，它的承諾是「能讓下推自動機從狀態 p、X 在堆疊頂端出發，走到狀態 q，並在過程中把那個確切的 X 彈掉、其間從不掉到它底下的那些字串」。把它讀成「一次『推入再相配地彈出』、從 p 到 q 的淨效果」。
把那個承諾固定下來後，文法規則幾乎是靠映照下推自動機的走法而自己寫出來的。若某個單一走法彈掉 X（讀入 a、從 p 走到 q），那是個基底情形：A(p, X, q) -> a。若某個走法推入符號——比方說它讀入 a、從 p 走到 r，並把 X 換成兩個符號 Y Z——那麼清掉 X 就意味著先清掉 Y（在某個中間狀態 s 結束），再清掉 Z（在 q 結束）。這化成規則 A(p, X, q) -> a A(r, Y, s) A(s, Z, q)，機器在此猜測中間狀態 s。起始符號則對每個接受狀態 f 展開為 A(start, bottom, f)。如今文法的推導，會一步一步地追蹤下推自動機的接受執行。
別去背那些索引上的體操——要背的是這個點子的形狀。一個文法變數，代表一段完整的、被括起來的堆疊生命片段：有東西被推入，稍後又被它自己的彈出所相配，開頭的狀態與收尾的狀態記在這變數的名字裡。一個被推入、稍後又被彈出的符號，正是這台自動機版本的「一對相配括號」，而文法的巢狀變數，就是這台自動機的巢狀堆疊。這就是兩個模型重合的深層原因：堆疊做的是後進先出的相配，文法遞迴做的是巢狀的相配，而那是同一個動作從兩側看去的樣子。
確定性：有限自動機與下推自動機分道揚鑣之處
這裡有個讓這座階梯值得攀爬的轉折，而如果你記得有限自動機的故事，它確實出人意料。對有限自動機而言，子集構造證明了非確定性買不到任何能力：每台 NFA 都有等價的 DFA，而一台確定性有限自動機，辨認的正是相同的正規語言。你也許會以為這裡也一樣。這是錯的。確定性下推自動機嚴格較弱於非確定性的那台。有些上下文無關語言，是沒有任何確定性下推自動機能辨認的。
差別何在？一台 DFA 能一次跑完 NFA 所有的平行猜測，靠的是追蹤它可能身處的狀態集合——子集有限多個，所以一台更大、卻仍有限的機器，就模擬了那份猜測。下推自動機沒辦法玩同一招，因為它的「組態」包含了整個堆疊，而堆疊內容沒有上限可摺進有限多個狀態裡。需要這份猜測的經典語言例子，是 {a, b} 上的偶數長度回文——正讀與反讀相同的字串。一台非確定性下推自動機把前半推入，再用它去配對後半並彈出，但它必須猜測中點在哪裡。一台確定性的機器，由左至右讀、毫無前瞻，無從得知何時該從推入切換到彈出。