把推導倒著讀
在第二篇你打造了一台由上而下的剖析器：它從起始符號出發，朝著輸入一路往下猜——挑一條規則，再試著比對那條規則所預測的東西。由下而上剖析則把同一套機制反方向跑。它從原始輸入——也就是葉子——出發，朝著起始符號往上做，而且在還沒親眼看見整條右側擺在面前之前，絕不去猜任何規則。由上而下問的是「我接下來該展開哪條規則？」，由下而上問的卻是「我是不是剛好把某條規則的右側拼完了？若是，我能不能把它折回左側去？」把完工的零件折回去，就是全部的點子。
用最乾淨的方式來想像它。一條推導從起始符號開始，一步步把某個變數換成某規則的右側，直到只剩終端符號為止——這是由上而下的視角。一台由下而上的剖析器產出的，恰恰是這樣一條推導，但它倒著發現其步驟：最後一步反而最先被發現。剖析器做的每一次折疊——把一條右側換回它的左側——就是把一個推導步驟撤銷掉。當整段輸入一路折回到起始符號，剖析器實際上就藉由倒讀，重建出了一條推導。這正是為什麼由下而上剖析有時被稱作「歸約式」剖析：每一步都把字串向起始符號歸約。
兩個動作與一個堆疊
整套機制靠的是一個堆疊和恰恰兩個動作，這正是它叫做移入-歸約剖析的原因。這個堆疊，就是你在下推自動機那裡見過的那疊盤子：你永遠只碰最上面那一個。堆疊的右邊，擺著還沒讀的輸入。一次移入（shift）把下一個輸入詞元從輸入端拿走、推上堆疊——簡直就是再往那疊盤子上放一個。一次歸約（reduce）則做折疊：當堆疊頂端的那些符號恰好對上某條規則的右側時，你就把它們彈掉，換上那條規則的單一左側變數。就這樣：移入、移入、歸約、移入、歸約……直到堆疊只剩起始符號、輸入也空了為止。
我們拿 CFG 那一階梯第一篇的運算式文法來具體跑一遍：E -> E + T | T、T -> T * F | F、F -> ( E ) | id。我們要剖析 `id + id * id`。一列一列地讀下面這份追蹤。注意那股節奏：剖析器一直移入詞元，直到堆疊頂端對上某條右側，才歸約。真正的深層魔法，在於選擇何時歸約、而非再多移入一個詞元——而這份追蹤每一次都悄悄地做了正確的選擇，好讓 `*` 結合得比 `+` 更緊。
Shift-reduce parse of id + id * id (rules: E->E+T | T , T->T*F | F , F->(E) | id) STACK INPUT ACTION (empty) id + id * id $ shift id id + id * id $ reduce F -> id F + id * id $ reduce T -> F T + id * id $ reduce E -> T E + id * id $ shift + E + id * id $ shift id E + id * id $ reduce F -> id E + F * id $ reduce T -> F E + T * id $ shift * <-- do NOT reduce E+T yet! E + T * id $ shift id E + T * id $ reduce F -> id E + T * F $ reduce T -> T * F E + T $ reduce E -> E + T E $ ACCEPT The held-back reduce at the marked line is exactly what makes * bind tighter than +. Reading the ACTION column bottom to top spells out a rightmost derivation, run in reverse.
把手：該在哪裡折，又為何那麼難
回頭看那份追蹤，問那個唯一要緊的問題：每一步，我該移入還是歸約？若要歸約，該用哪條規則、哪些符號？任一時刻該折的那段正確子字串，有個名字——它叫做把手。嚴格地說，把手是某條規則的右側，恰好坐在對的位置上，使得把它歸約能讓你沿著一條最右推導往回退一步。每一步都正確找出把手，剖析就一路直奔起始符號。挑錯了子字串——把某個看起來像右側、卻不是真正把手的東西歸約掉——你就會岔進一條死胡同。
那個定義裡藏著兩個微妙的警告。第一，把手不只是「任何等於某條右側的子字串」。在追蹤裡，當 `E + T` 出現在堆疊上、而 `* id` 還在等著時，`E + T` 這幾個符號的確構成 E -> E + T 的右側——可是在那裡歸約卻是錯的，因為真正的把手還在更右邊。一段子字串可以對上某條規則，卻仍不是把手；把手取決於整個脈絡，不只取決於形狀。第二，在一次正確的移入-歸約剖析裡，把手永遠坐在堆疊頂端——這正是為什麼堆疊在這裡是對的資料結構的深層理由。你永遠不必往下挖。
於是由下而上剖析的全部困難，就坍縮成一個問題：剖析器要怎麼知道——只看堆疊頂端、外加頂多一個即將到來的詞元——它此刻是不是正盯著一個把手？一台天真的剖析器只好回溯：試著歸約、失敗、撤銷、改試移入。回溯雖正確卻緩慢。LR 家族的勝利，在於確定性地回答把手問題，完全不必回溯——靠的是預先算好一張有限狀態的表，由它讀取堆疊頂端的脈絡、發號施令決定動作。那張表，就是下一節的主題。
LR 家族，與那張作決定的表
LR 剖析就是被弄成確定性的移入-歸約剖析。「L」指的是由左到右（Left）讀輸入；「R」指的是建一條最右（Rightmost）推導（如我們所見，是倒著建的）。訣竅在於：一台正確剖析器所能抵達的全部堆疊內容，其本身構成一個正規語言——而正規語言可由一台有限自動機辨識。於是 LR 剖析器會預先、一次性地建出一台DFA，它的每個狀態都概括了「關於堆疊、凡是對決定下一步要緊的一切」。剖析時，剖析器只要把堆疊餵進這台 DFA，落在某個狀態裡，那個狀態就毫不含糊地說：『移入』或『用規則 R 歸約』。
LR 有一整道強度階梯，全都共用這副骨架，差別只在表用多少前瞻。LR(0) 完全不看前瞻詞元。SLR 與 LALR(1) 看一個前瞻詞元，用的是你在第二篇遇過的 FIRST 與 FOLLOW 集合來計算；LALR(1) 是真實工具會生成的甜蜜點，因為它的表保持得小。標準 LR(1) 是看一個詞元的版本裡最強的，代價是大得多的表。別去背這鍋字母湯——重點是它們全都在回答同一個把手問題，而更強的變體不過是在宣告衝突之前，多分辨出幾種情境罷了。
為什麼 LR 嚴格強過第二篇的 LL 剖析？因為 LR 能晚得多才作決定。一台 LL(1) 剖析器，必須在看見規則內容之前，就承諾它要展開哪條規則——它從第一個詞元就在預測。一台 LR 剖析器，卻可以把整條右側都移入堆疊，然後才決定是哪條規則生出了它。在承諾之前看見整條產生式，是個天大的優勢：凡是 LL(1) 剖析器處理得了的文法，LR(1) 剖析器也處理得了，反過來卻不成立。尤其，LR 剖析器並不要求你移除左遞迴——它其實偏好左遞迴，因為那能讓堆疊保持淺。
衝突，與誠實的界限
有時候表沒辦法決定。當某個狀態對同一個前瞻、會同時叫剖析器『移入』又『歸約』時，那就是一次移入-歸約衝突；當它會同時用兩條不同規則歸約時，那就是歸約-歸約衝突。一次衝突，意味著這個特定文法在所選的前瞻量下並非 LR——表確實沒辦法從它被允許看見的東西，判斷堆疊頂端是不是把手。日常裡最經典的例子是「懸置 else」：在 `if C then if C then S else S` 裡，那個 `else` 該接到內層還是外層的 `if`？文法兩者都允許，所以表同時看見了一次移入與一次歸約。
真實的剖析器生成器不會一遇衝突就放棄——它們用宣告的優先序與結合性來化解衝突。你告訴工具『`*` 結合得比 `+` 緊』、『else 接到最近的 if』（這是標準規則），它就用這些宣告，在每個起衝突的狀態挑選移入或歸約。這恰恰是 CFG 設計那篇的分層變數技巧，只是被搬出文法、移進了一張表達偏好的旁表裡。它讓文法保持小而可讀，同時仍迫使出你心裡那一棵樹。下一篇談剖析器生成器，會展示這些宣告的具體語法。
最後一道誠實的界限。LR 剖析器固然強大，卻仍只應付得了確定性的上下文無關語言——也就是確定性下推自動機所接受的那一類。並非每個上下文無關文法在任何固定前瞻下都是 LR，而有些上下文無關語言根本不是確定性的，因此根本不存在它們的 LR 表。當你真的需要剖析這樣的文法時——包含歧義文法，或自然語言——你就會去動用下一篇的通用演算法 CYK 與 Earley，它們用速度去換「能應付任何上下文無關文法」的本事。