從「辨認」到「建造」
到目前為止，你已經見過兩種讀字串的機器。有限自動機像一座旋轉閘門：它只記得當前狀態，回答唯一一個是非題——這個字串在語言裡嗎？下推自動機多了一疊只能碰最上面那盤的盤子，這正是配對巢狀結構（例如成對括號或 a^n b^n）所需要的記憶。前幾個階梯證明了上下文無關文法與下推自動機描述同一類語言。但真正的編譯器要的不只是是非。它要的是結構：哪個符號是運算子、哪個子運算式是它的左運算元、一條敘述在哪裡結束、下一條從哪裡開始。
這就是本階梯要跨出的一步：從辨認一個字串，走到剖析它。剖析就是把一段扁平的符號序列拿來，還原出文法用來生成它的剖析樹——把推導倒著跑。辨認器只說「是」；剖析器說「是，而且這裡正是原因，畫成一棵樹」。編譯器後續的一切——型別檢查、最佳化、產生程式碼——都作用在那棵樹上，而非作用在原始字元上。所以剖析是磁碟上的位元組流與程式能推理的結構化物件之間的橋樑。
先是掃描器：正規語言負責詞法分析
在建出任何一棵樹之前，編譯器前端會先跑一個更便宜的階段。把單個字元直接餵進剖析器是浪費的：剖析器得耗力氣去判斷 'w'、'h'、'i'、'l'、'e' 拼出關鍵字 'while'，'1'、'2'、'3' 組成一個數字，而它們之間的三個空格只是雜訊。於是前端分成兩趟。第一趟是掃描器（又叫詞法分析器或 tokenizer），而精妙之處在於——它完全活在你早已精通的正規語言世界裡。
每一種 符記——識別字、數字、運算子、關鍵字——都用一個正規表示式描述，例如數字寫成 `[0-9]+`、識別字寫成一個字母後面接字母與數字。根據Kleene 定理，每個這樣的正規表示式都能編譯成一台有限自動機，所以掃描器不過是一台在輸入上飛快奔跑的 DFA，把字元流切成一串乾淨、帶標籤的符記。這正是掃描便宜的原因：一台旋轉閘門式、沒有堆疊的機器，線性時間、常數記憶體。一個獨立掃描器之所以可能存在，正是你早先學到的那條界線——一個語言的詞法結構（它的「字」）是正規的，即使它的文法結構（它的「句子」）不是。
Source text: while (n123 >= 0) Scanner (a DFA) emits a token stream: KEYWORD(while) LPAREN IDENT(n123) GE(>=) NUM(0) RPAREN - whitespace is recognized and discarded - 'n123' is ONE identifier token, not 4 characters - '>=' is ONE operator token, not '>' then '=' The parser never sees raw characters -- only this tidy stream.
接著是剖析器：一棵文法本會長出的樹
現在剖析器拿著符記流和語言的上下文無關文法，重建出一棵剖析樹——它的根是起始符號，內部節點是觸發過的規則，而它的葉子從左讀到右恰好拼出那串符記。建造這棵樹就是把推導倒著跑：推導從起始符號出發、套用產生規則、長出字串；剖析器則拿到完成品字串，必須重新找出哪些規則被套用過、以什麼順序。因為文法是上下文無關而不只是正規，這需要下推自動機提供的那個堆疊——那種遞迴、巢狀的配對，是單靠 DFA 辦不到的。
做這件事有兩大哲學，本階梯接下來兩篇各取其一。由上而下剖析從根——起始符號——出發，一路向著符記猜下去，邊問：「我正想建一個運算式；既然下一個符記是數字，我該展開哪條規則？」它對應一個最左推導。由下而上剖析從葉子——也就是真正的符記——出發，往上做，把完成的片段組成更大的片段，直到整體塌縮回起始符號為止，對應一個倒著跑的最右推導。由上而下是較直覺的「預測並展開」；由下而上是較強大的「等待、累積、然後歸約」。
並非每個文法都對每種方法友善，也並非每個字串都有唯一的樹。一個歧義文法能為同一串符記長出兩棵不同的剖析樹——經典例子是 `a - b - c`，一個粗心的文法會讓你把它讀成 `(a - b) - c` 或 `a - (b - c)`，兩種不同的意思。真正的剖析器用優先順序與結合性規則來打破這種平手，這是第五篇要回頭談的主題。誠實的提醒：歧義是文法的性質，而某些上下文無關語言是本質歧義的——沒有任何文法能為它們避開歧義。更糟的是，一般地問一個給定文法是否歧義，本身就是不可判定的，所以沒有演算法能替你篩查每一個文法。
當文法跟你作對：通用剖析器
兩種主流方法都附帶條件。由上而下只對 LL(1) 這類受限類別的文法順暢運作，在那裡下一個單一符記總能告訴你該展開哪條規則；由下而上的 LR 家族較寬容，但仍無法應付每一個上下文無關文法。那麼當一個文法既不肯套進這個模子、也不肯套進那個模子時——例如一套自然語言文法，或一套為了清楚而非為了剖析器而寫的文法——你該怎麼辦？你會搬出通用剖析器，它能處理任何上下文無關文法，含歧義在內，代價是花更多時間。
第四篇談兩種。CYK 演算法先把文法改寫成喬姆斯基正規形（每條規則不是 A -> B C 就是 A -> a），再由下而上填一張三角形的表：每一格記下哪些非終端符號能推導出輸入的某一段連續切片，從單個符記一路建到整串。對長度 n 的輸入，它是一個整齊的動態規劃，跑 O(n^3) 時間。Earley 剖析器走另一條路，從左掃到右時同時拋接一組組部分完成的規則；它最壞情況也是 O(n^3)，但在無歧義文法上加速到 O(n^2)，在性質好的文法上甚至是線性時間。取捨很清楚：以速度換通用性。一台專用的 LL(1) 或 LR 剖析器跑線性時間；通用剖析器為了接受那些快方法拒收的文法，付出一筆多項式的溢價。
產出：抽象語法樹，而不是剖析樹
還有最後一個容易被忽略的步驟。字面上的剖析樹忠實卻雜亂：每條觸發過的文法規則都有一個節點，包括各種記帳項目，例如你寫的括號、結束敘述的分號，以及文法為了編碼優先順序所需的那一長串單子節點規則。一旦結構確定，這些就都無關緊要了。於是前端把剖析樹蒸餾成一棵抽象語法樹（AST），只保留有意義的骨架。
拿 `a + b * c` 來說。完整的剖析樹會把它穿過像 Expr -> Term -> Factor 這樣的鏈，以強制 `*` 比 `+` 結合得更緊；AST 把那一切鷹架全丟掉，只留一個 `+` 節點，它的右子節點是一個 `*` 節點——只留意思，別無其他。括號也消失了，因為樹一旦存在，它們唯一的工作（分組）就已完成。AST 正是編譯器其餘部分所走訪的東西：型別檢查器拜訪每個節點問「這些型別合得來嗎？」，程式碼產生器為每個節點吐出一道指令。讀原始文字的階段結束了；從此程式就是一棵樹。
最後，這一切都不是程式語言的怪癖。同一條流水線——用正規掃描器斷詞、用上下文無關文法剖析、蒸餾成一棵樹——也是自然語言剖析的底層，語言學家在那裡為句子指派文法結構；同樣的流水線也撐起協定剖析器、查詢語言、組態檔，以及化學式判讀器。只要一段符號流承載著巢狀的意義，這套前端就是那件工具。依這些原理親手寫一台剖析器是第二、三篇的主題；最後一篇示範像 yacc 或 bison 這樣的剖析器產生器如何從一份文法替你建出剖析器，以及它如何回報那些衝突，警告你文法歧義或超出類別之外。