1965-LR解析#

案件摘要#

1965 年，Stanford 的年輕學者 Donald Knuth 發表 "On the Translation of Languages from Left to Right"，提出 LR(k) 文法理論。他在紙上完成了一件驚人的偵探工作：從左到右掃描、反向重建最右推導、只靠向前看 k 個符號，就能判定「所有確定性的上下文無關語言」。這是理論上的完美破案——但 Knuth 自己卻宣判了它「不實用」。十五年後，DeRemer 的簡化版理論讓這個「太完美的理論」真正上了街頭，成為今日每個編譯器的心臟。

前因 -- 為什麼會有這個案子#

• 遞迴下降的天花板：1960 年代主流的自頂向下（top-down）解析法，從起始符號往輸入展開。它只容得下 LL 類文法——而 LL 文法禁止左遞迴：

但人類寫算術運算式、寫程式語言，左遞迴文法最自然。強迫改寫成右遞迴會破壞結合律的語意，案子懸而未決。 - 回溯的代價：不加限制的自頂向下解析需要回溯（backtracking），最壞情況是指數時間——對編譯器這種「必須一次掃完、線性時間」的工具而言，不可接受。 - 既有的線索：1960 年代已有 bottom-up 解析的雛形（如 Irone Irons 的 precedence 技術、Floyd 的運算子優先法），但都只是「經驗法則」，沒有人能回答：到底哪一類語言，可以被一台確定性的下推自動機線性時間解析？

線索與推理 -- 數學式、程式、理論#

Knuth 的關鍵洞察：反向偵查#

自頂向下是「偵探沿著嫌犯的行蹤往前追」；Knuth 反過來想——解析器在掃描時做的其實是最左規約（leftmost reduction），而它恰好是最右推導（rightmost derivation）的反向。LR 的命名就是偵查路線圖：

• L（Left to right）：從左到右掃描輸入。
• R（Rightmost derivation in reverse）：重建最右推導的反向。
• k：向前看 k 個符號（lookahead），用來在分岔路口做決定。

Knuth 證明：一個語言能被確定性下推自動機線性時間解析，若且唯若它是某個 LR(k) 文法的語言。這是完整的刻畫（characterization）——案子的答案就是 LR(k)。

LR(0) 項目集：偵探的辦案筆記#

把文法規則 \(A \to XY\) 拆成「項目」(item)，中間的點 \(\bullet\) 代表偵查進度：

把所有「點在同一位置、且互相可達」的項目收進同一個項目集（狀態），建構演算法：

CLOSURE(I):
    重複直到不再變化:
        對 I 中每個項目 A -> α • B β:
            對每條規則 B -> γ:
                將 B -> • γ 加入 I

GOTO(I, X):
    J = { A -> α X • β | A -> α • X β ∈ I }
    回傳 CLOSURE(J)

建表:
    狀態 0 = CLOSURE({S' -> • S})
    反覆對每個狀態、每個符號 X 做 GOTO，直到不動點

ACTION/GOTO 表與 shift/reduce 衝突#

每個狀態一行，每個終端符號一個 ACTION 欄、每個非終端符號一個 GOTO 欄：

衝突偵測：若同一格同時可 shift 又可 reduce，稱 shift/reduce 衝突（懸案，如懸垂 else）；兩條規則都可規約稱 reduce/reduce 衝突。無衝突即為 LR(0)。Knuth 的 k 就是把「向前看符號」預先編進項目裡（LR(k) 項目 \([A\to\alpha\bullet\beta, u]\) ），消除分岔——但狀態數隨 k 指數膨脹。

Knuth 的自我宣判#

Knuth 估算 LR(k) 表的大小約為 \(\mathcal{O}(e^{ck})\) 量級的狀態數，且建表演算法複雜。他在論文中評論：對實際的程式語言，這個方法「需要過多的記憶體」，理論價值大於實用價值。完美破案，卻無人執行——懸案再度掛起。

Python 模擬：迷你 LR parser 跑算術運算式#

以下用手寫死的一小張 LR 表（文法：E -> E+T | T, T -> T*F | F, F -> (E) | id），模擬 shift/reduce 解析 id+id*id：

# 文法: 0:E->E+T  1:E->T  2:T->T*F  3:T->F  4:F->(E)  5:F->id
grammar = {0: ('E', 'E+T'), 1: ('E', 'T'), 2: ('T', 'T*F'),
           3: ('T', 'F'), 4: ('F', '(E)'), 5: ('F', 'id')}

# 迷你 LR(0) 表（手工建好的 canonical 集合，行號=狀態）
# ACTION[s][token] = ('s',next) | ('r',rule) | ('acc',) ; GOTO[s][nt] = next
ACTION = {
    0: {'id': ('s', 5), '(': ('s', 4)},
    1: {'+': ('s', 6), '$': ('acc',)},
    2: {'+': ('r', 1), '*': ('s', 7), '$': ('r', 1)},   # E->T •
    3: {'+': ('r', 3), '*': ('r', 3), '$': ('r', 3)},   # T->F •
    4: {'id': ('s', 5), '(': ('s', 4)},
    5: {'+': ('r', 5), '*': ('r', 5), '$': ('r', 5)},   # F->id •
    6: {'id': ('s', 5), '(': ('s', 4)},
    7: {'id': ('s', 5), '(': ('s', 4)},
    8: {'+': ('s', 6), ')': ('s', 11), '$': None},
    9: {'+': ('r', 0), '*': ('s', 7), '$': ('r', 0)},   # E->E+T •
   10: {'+': ('r', 2), '*': ('r', 2), '$': ('r', 2)},   # T->T*F •
   11: {'+': ('r', 4), '*': ('r', 4), '$': ('r', 4)},   # F->(E) •
}
GOTO = {0: {'E': 1, 'T': 2, 'F': 3}, 4: {'E': 8, 'T': 2, 'F': 3},
        6: {'T': 9, 'F': 3}, 7: {'F': 10}}

def parse(tokens):
    tokens = tokens + ['$']
    stack, i = [0], 0
    while True:
        s, tok = stack[-1], tokens[i]
        act = ACTION[s][tok]
        if act is None:
            return "語法錯誤（無此轉移）"
        kind, v = act
        if kind == 's':                      # shift：推符號與新狀態
            print(f"shift {tok} -> 狀態 {v}"); stack += [tok, v]; i += 1
        elif kind == 'r':                    # reduce：反推一條最右推導
            lhs, rhs = grammar[v]
            print(f"reduce {lhs} -> {rhs}")
            for _ in rhs: stack.pop(); stack.pop()
            goto = GOTO[stack[-1]][lhs]; stack += [lhs, goto]
        else:
            return "接受：id+id*id 是合法運算式 ✔"

parse(['id', '+', 'id', '*', 'id'])

注意狀態 2：遇到 + 時 reduce（E->T，因為 + 的左結合優先），遇到 * 時 shift（乘號優先綁定）——優先級就藏在表裡。堆疊上的每一步 reduce，正是最右推導 \(E \Rightarrow E+T \Rightarrow E+T*F \Rightarrow \dots\) 的反向重播。

結案 -- 後果與影響#

• 理論封頂：LR(k) 完整刻畫了確定性上下文無關語言，成為形式語言理論的里程碑，Knuth 後續的《The Art of Computer Programming》也建立在這套嚴謹分析之上。
• DeRemer 拯救實用性（1969/1971）：Frank DeRemer 在 MIT 的博士論文提出 SLR、LALR 與簡化的 LR(1)：不在項目裡編入完整 lookahead，而是用 FOLLOW 集合（SLR）或局部合併（LALR）近似之，狀態數從數千壓到數百——「太大的完美」變成「剛好的夠用」。
• 工具化：1975 年 Johnson 的 Yacc 把 LALR 表建構自動化（見 1975-Yacc與Lex），LR 解析從理論走進每一台 Unix 機器。
• 今日：GCC、Bison、Rust 的項目集解析、Go 的 yacc——Knuth 1965 年在紙上的偵查路線，至今仍是編譯器前端的主流幹道。

關鍵人物與文獻#

• Donald Knuth（Stanford）：1965 "On the Translation of Languages from Left to Right," Information and Control 8(6), 607–639.
• Frank DeRemer：1969 博士論文 "Practical Translators for LR(k) Languages"（SLR/LALR/LR(1)）。
• 文獻：
• A. V. Aho, J. D. Ullman, The Theory of Parsing, Translation, and Compiling (1972).
• D. E. Knuth, TAOCP Vol. 5 的解析章節（手稿）。