3.2 自頂向下分析：LL 與遞迴下降#

核心思想#

自頂向下分析從起始符號 $S$ 出發，模仿最左推導：在每一步選擇一條產生式，使推導出的字首與輸入一致。它本質上是對剖析樹做前序遍歷，由根往葉建構。

範例：輸入 id + id * id，文法 $E \to T E' \;|\; \ldots$ （見下），分析器先猜 $E \to T E'$ ，匹配 $T$ 為 $id$ ，再處理 $E'$ ……

LL(1) 的定義與判定#

LL( $k$ )：Left-to-right scan, Leftmost derivation, 使用 $k$ 個預看符號。LL(1) 是最實用的子集，判定條件：

對每對候選產生式 $A \to \alpha \mid \beta$ ：

$\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \emptyset$
若 $\beta \Rightarrow^* \epsilon$ ，則 $\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \emptyset$

亦即：預看一個符號即可唯一決定選哪條產生式。

LL(1) 分析表：列為非終端、行為終端（含 `$），格中填產生式：

	id	+	*	(	)	$
E	E→TE'			E→TE'
E'		E'→+TE'			E'→ε	E'→ε
T	T→FT'			T→FT'
T'		T'→ε	T'→*FT'		T'→ε	T'→ε
F	F→id			F→(E)

驅動程式以一個堆疊模擬：終端匹配輸入後彈出；非終端查表、展開、倒序壓入。

左遞迴消除與左因子提取#

遞迴下降不能處理左遞迴（ $`E \to E + T$ 會無限呼叫自己），需先改寫：

\[ E \to E + T \mid T \quad\Longrightarrow\quad E \to T E',\quad E' \to +\, T\, E' \mid \epsilon \]

公共前綴同理： $S \to if\ E\ then\ S\ else\ S \mid if\ E\ then\ S$ 改為

\[ S \to if\ E\ then\ S\ S', \quad S' \to else\ S \mid \epsilon \]

（著名的 dangling else 歧義由「else 總是跟最近的 if」的貪心策略解決。）

遞迴下降：手寫的主流#

每個非終端對應一個函式，堆疊由呼叫棧隱式提供：

// E -> T E'
void parse_E() {
    parse_T();
    parse_Ep();
}

// E' -> + T E' | - T E' | ε
void parse_Ep() {
    if (peek() == TK_PLUS) { advance(); parse_T(); parse_Ep(); }
    else if (peek() == TK_MINUS) { advance(); parse_T(); parse_Ep(); }
    // ε：直接返回
}

// F -> ( E ) | id | num
void parse_F() {
    if (accept(TK_LPAREN)) { parse_E(); expect(TK_RPAREN); }
    else if (accept(TK_ID) || accept(TK_NUM)) { /* 建節點 */ }
    else error("expected factor");
}

優點：

錯誤訊息精準：在明確的函式與位置上報錯。
可讀、可擴充：文法即程式碼，Clang、Rustc、Go、V8 皆採用。
語意動作自然：直接在函式裡建 AST。

缺點與解法#

LL(1) 表達力弱：無法處理左遞迴文法，也不適合天然左遞迴的語言（如 C 的宣告文法）。解法：改寫文法，或在函式裡用迴圈吸收左遞迴（while (peek()==PLUS) { ... } 即把右遞迴改為迭代）。
回溯成本：LL(k) 若不限制文法，可能需要試錯。工程上常用 LL(*)／PEG（解析表達文法, Bryan Ford, 2004）：以有序選擇與無限預看替代嚴格 LL，但 PEG 的「選了就不再回頭」會讓歧義被靜默地按順序吞掉。
運算子優先：寫成多層非終端（expr → term → factor）可行但繁瑣。運算子優先爬升法（Pratt parsing / precedence climbing, Vaughan Pratt, 1973） 用一個迴圈＋優先序表處理所有二元運算子，是現代手寫編譯器最愛的技巧：

Node* parse_expr(int min_prec) {
    Node* lhs = parse_unary();
    while (is_binop(peek()) && prec(peek()) >= min_prec) {
        Token op = advance();
        int next = prec(op) + (left_assoc(op) ? 1 : 0);
        Node* rhs = parse_expr(next);
        lhs = make_binop(op, lhs, rhs);
    }
    return lhs;
}

錯誤恢復#

遞迴下降常用 panic mode：出錯時跳過輸入直到遇見目前非終端的 FOLLOW 集合符號（如 ;、}），然後假裝該語法單元完成，繼續分析。良好的恢復使一次編譯回報多個錯誤。

小結#

LL(1) 以 FIRST/FOLLOW 判定，遞迴下降是其自然實作，也是現代主流編譯器的選擇。
左遞迴消除、左因子提取、Pratt parsing 是手寫實用的三大利器。
自頂向下的弱點（左遞迴、表達力）正是自底向上方法（3.3）的強項。