我們究竟為何需要通用剖析器
前幾篇給了你兩個快速的剖析器家族。LL(1) 由上而下讀取，憑一個前瞻符記決定每條規則；LR 由下而上讀取，辨認出一個句柄再進行歸約。兩者都是線性時間，這很美妙——但兩者都要求一個行為良好的文法。LL(1) 被左遞迴與重疊的 FIRST 集合卡住；LR 則拒絕任何帶有無法消解的移入－歸約或歸約－歸約衝突的文法。要用它們，你得先把文法重塑成貼合剖析器的樣子，而有些文法根本無法被重塑。
現在把需求翻轉過來。假設有人交給你一個任意的上下文無關文法——也許是一個亂糟糟、滿是歧義的英語語法文法，也許是一個帶著深層左遞迴、而你又無權改寫的文法——你必須回答：這個字串屬於這個語言嗎？若屬於，它的結構又是什麼？你要的是一個對每一個上下文無關文法都管用、毫無前提條件的剖析器。這就是通用剖析器，而理論早已保證它能存在：上下文無關語言的成員資格是可判定的。CYK 與 Earley 正是真正做到這件事的兩種經典途徑。
CYK：填滿一個三角形的格子
CYK 演算法（Cocke–Younger–Kasami）有一個前提：文法必須是 喬姆斯基範式（CNF），這你在範式那一階梯見過。在 CNF 中，每條規則要嘛是 A → B C（一個變數重寫成恰好兩個變數），要嘛是 A → a（一個變數重寫成單一終端符號），而 epsilon 只允許用於起始符號。「右側兩個變數」這個形狀正是 CYK 之所以行得通的全部原因：每次你建造字串的一塊時，它都乾淨地裂成左半與右半，而 CYK 只是試遍所有能切的位置。
把它想成對子字串做動態規劃。對一個長度 n 的字串，CYK 填一張三角形表格，其格子 (i, 長度) 裝著所有能推導出「從位置 i 開始、延伸該長度」之子字串的變數。它是按跨度由下而上，而不是按樹形：先解所有長度 1 的跨度（單一終端符號——很簡單，查一下哪些變數有規則 A → a），再長度 2、再長度 3，依此類推一路到整個字串。一個變數 A 會進入較長的格子，若某條規則 A → B C 讓你把那段跨度切成「B 能覆蓋的左半」與「C 能覆蓋的右半」。
- 長度 1 那一列：對位置 i 上的每個單一字元，把所有「具有與該字元相符之規則 A → a」的變數 A 放進格子 (i,1)。這是基底情況，直接從終端規則讀出。
- 對每個較長的跨度（長度 2、再 3、…一直到 n），試遍把它切成「非空左半」與「非空右半」的每一種切法。切點至多有 n−1 個。
- 對某個固定切法，看看「已對左半證明出的變數」與「已對右半證明出的變數」。若某條規則 A → B C 的 B 在左集合裡、C 在右集合裡，那麼 A 就能推導整段跨度——把 A 加進這個格子。
- 填完最頂端的格子（整個字串，位置 1、長度 n）後，當且唯當起始符號 S 出現在其中，就接受。那個格子回答了成員資格；你在每次切分時存下的反向指標則重建出剖析樹。
Grammar (Chomsky normal form): Parse the string: b a a b
S -> A B | B C positions: 1 2 3 4
A -> B A | a
B -> C C | b CYK table (cell shows variables; rows = span length)
C -> A B | a
len4: [ S, A, C ] <- S here => ACCEPT
Terminals: len3: [ - ] [ B ]
a is derived by A and C len2: [ S,A ] [ B ] [ B ]
b is derived by B len1: [ B ] [ A,C ] [ A,C ] [ B ]
b a a b
How len2 cell over 'b a' got S,A:
split b | a -> left has B, right has A,C
rule S -> B C? need B then C : B(left)+C(right) = yes -> S
rule A -> B A? B(left)+A(right) = yes -> A為什麼 CYK 老實說是立方時間，以及它真正判定了什麼
把工作量數一數，立方成本就毫無神祕之處。格子大約有 n^2/2 個（每個 (起點, 長度) 配對一個）。填一個格子要試至多 n 個切點，而每個切點做的規則配對量是有界的（有界，是因為文法固定、不是輸入的一部分）。所以總量大約是（格子數）乘以（每格切點數）= O(n^2) · O(n) = O(n^3)。這是貨真價實的最壞情況，不是寬鬆的估計：確實存在文法與字串，真的逼你去考慮那麼多切法。
要精確說明一張填好的表格給了你什麼。頂端格子回答成員資格問題——字串在語言中嗎？——給出乾淨的是或否。但 CYK 做的更多：因為格子裡的每個變數都記得哪條規則與哪個切法把它放進來，你可以從 S 沿反向指標往下走，還原出一棵真正的剖析樹。若文法歧義，單一格子可能透過好幾種不同的切法持有同一個變數，而那些選項正好就是一個歧義字串的多棵剖析樹。CYK 面對歧義不會慌張；它把所有剖析緊湊地一次表示出來。
Earley：照文法原樣剖析
CYK 雖優雅，卻逼你先轉成喬姆斯基範式，這會膨脹文法、模糊它的自然形狀。Earley 剖析器免去了這道苦差事：它對任何上下文無關文法都照原樣執行——左遞迴、epsilon 規則、任意右側、歧義，一概沒問題，無需轉換。它的構想是由左到右追蹤剖析器可能正進行到一半的每一條規則，並用一個點狀標記記下它已經走到哪裡。
記帳的單位是一個 Earley 項目：一條規則，配一個點，標示「已配對的部分」與「尚待配對的部分」之間的界線，再加上「這條規則的配對是從哪個輸入位置開始的」。寫成 A → α · β @ k，意思是「我們正在產生一個 A 的途中；我們已配對 α，還需要 β，而這次嘗試是從位置 k 起的」。剖析器在每個輸入位置維護一組這樣的項目，並由左到右反覆套用三種運算來填滿這些組，直到沒有新項目出現為止。
- 預測（PREDICT）：若點正好落在某個變數 B 之前（A → α · B β），那麼 B 可能就在此處開始，於是為 B 的每條規則加入新項目 B → · γ @（此處）。這是由上而下的猜測——像遞迴下降在展開一個非終端符號，但它把 B 的「所有」規則平行展開。
- 掃描（SCAN）：若點正好落在某個終端符號 a 之前（A → α · a β），且下一個輸入符號確實是 a，就把點推過它，並把該項目帶進下一個位置的組裡。這是唯一會消耗輸入的運算。
- 完成（COMPLETE）：若一個項目走完了（B → γ · @ k，點在最末），那麼 B 在「從 k 到此處」這段跨度上已被完整配對。回到位置 k，把當時每個正在等待一個 B 的項目的點往前推。這是由下而上的歸約——像 LR 辨認出一個句柄。
- 當且唯當在最末位置的組裡，你找到 S → γ · @ 0——一個「從位置 0 開始、橫跨整個輸入」且已完成的起始符號項目——就接受。存下的完成連結重建剖析樹；每當字串歧義時，每個格子會有數條連結。
注意這個優美的融合：PREDICT 是由上而下的猜測（遞迴下降的精神），而 COMPLETE 是由下而上的歸約（LR 的精神）。Earley 同時跑這兩者，而 @k 起點指標把它們縫合起來，使得只有「彼此一致的局部剖析」能存活下來。這也是為什麼左遞迴無害：一個左遞迴的 PREDICT 只是加入一個項目，一旦完成就立刻餵給 COMPLETE——不會無限迴圈，因為項目存在組裡，重複的項目永不被再次加入。
選擇剖析器，以及程式碼以外的剖析
那麼你該伸手拿哪個？對於一個由你掌控的程式語言，就用 LR（或 LL）剖析器：它是線性的，而你大可設計一個無衝突的文法去餵它。當你無法把文法遷就工具時——當文法是給定的、歧義的、深層左遞迴的，或正在實驗性地演變——才伸手拿通用剖析器。在兩個通用剖析器之間，Earley 通常是較友善的選擇：它照文法原樣剖析，在人們實際使用的文法上往往跑得比立方更好（在許多無歧義文法上是線性），而且退化得很平緩。CYK 則作為「乾淨、易於證明正確」的演算法而出色——用於教學、用於理論，以及當你手上已經有一個 CNF 文法時。
通用性的價值就在這裡兌現。自然語言剖析是它的殺手級應用：人類的文法（英語、中文）無可避免地歧義——「我用望遠鏡看見那個人」有兩種真實讀法——而且它們充滿了 LR 消化不了的那種結構。Earley 正是在計算語言學中長大的，在那裡你希望每一個合法剖析都被回傳，好讓後續階段依機率為它們排序。通用剖析器也服務於動態或使用者提供的文法：資料格式、查詢語言，以及即時的文法原型工具，在那些情境下你無法事先要求使用者交出一個無衝突的文法。
退後一步，看清這整個階梯貫穿始終的主線。掃描器用正規語言的機制把字元變成符記；文法給了那些符記巢狀結構；由上而下與由下而上的剖析器在受限文法上快速地讀出那個結構；而現在 CYK 與 Earley 為所有文法讀出它，代價是立方時間。無論你用哪個剖析器，產出都是同一份獎賞：一棵結構化的樹（通常蒸餾成一棵抽象語法樹），讓編譯器的其餘部分——或語言學家、或資料工具——終於能夠對它進行推理。最後一篇將轉向實務機制：像 yacc 與 bison 這樣的剖析器產生器、真實世界的文法衝突，以及優先級宣告如何消解它們。