3.3 自底向上分析：LR、LALR 與 Yacc/Bison#

歷史脈絡#

1965 年，Donald Knuth 發表《On the Translation of Languages from Left to Right》，定義 LR( \(k\) ) 文法——理論上涵蓋所有「由下而上、一次預看 \(k\) 個符號、線性時間」可分析的語言，表達力嚴格強於 LL。但 Knuth 的原始構造需要龐大的狀態表，當年記憶體無法承受。1971 年，Frank DeRemer 提出簡化版 SLR 與 LALR(1)，將狀態數壓到與 LR(0) 相同而能力接近 LR(1)。同年 Stephen Johnson 在貝爾實驗室寫出 Yacc（Yet Another Compiler Compiler），以 LALR(1) 為核心，成為 UNIX 標配；GNU 版本為 Bison（1985 起）。

自底向上的兩個動作#

分析器維護一個狀態堆疊，對輸入只做兩件事：

• 移進（shift）：把輸入符號壓入堆疊，狀態轉移。
• 歸約（reduce）：當堆疊頂出現某產生式右部的句柄（handle），彈出之、壓入左部非終端。

歸約到底時即完成分析。句柄是最右推導中「最後一步被使用」的產生式實例——自底向上分析就是在反向重建最右推導。

範例：id + id 用 \(E \to E + E \mid id\) ：

堆疊            輸入         動作
$               id + id $    shift
$id             + id $       reduce E -> id
$E              + id $       shift
$E +            id $         shift
$E + id         $            reduce E -> id
$E + E          $            reduce E -> E + E
$E              $            accept

LR 分析表與 LR(0) 項目#

LR(0) 項目：產生式右部加一個位置點，如 \(E \to E + \cdot E\) ，表示「已看到 \(E+\) ，期待 \(E\) 」。項目集閉包（closure）把「點後是非終端 \(A\) 」的項目擴充為 \(A\) 所有產生式的點在開頭的項目。goto 函數則描述「看到符號 \(X\) 後點前進一格」的狀態轉移。

由項目集規範族建出 ACTION 與 GOTO 表：

對狀態 I，項目 A -> α · a β：
  shift: ACTION[I, a] = shift to goto(I, a)
對 A -> α ·：
  SLR : 對 FOLLOW(A) 中每個 a，ACTION[I,a] = reduce A -> α
  LR(1): 僅對 lookahead in 項目本身
  LALR(1): 合併 LR(1) 中核心相同的狀態
對 S' -> S ·：ACTION[I, $] = accept

四個層級的比較：

Yacc/Bison 實例#

%{
#include <stdio.h>
int yylex(void);
void yyerror(const char *s);
%}

%union { double val; }
%token <val> NUM
%type  <val> expr
%left '+' '-'
%left '*' '/'

%%

input : input line | ;
line  : '\n' | expr '\n' { printf("= %g\n", $1); } ;
expr  : NUM               { $$ = $1; }
      | expr '+' expr     { $$ = $1 + $3; }
      | expr '-' expr     { $$ = $1 - $3; }
      | expr '*' expr     { $$ = $1 * $3; }
      | expr '/' expr     { $$ = $1 / $3; }
      | '(' expr ')'      { $$ = $2; } ;
%%

void yyerror(const char *s) { fprintf(stderr, "%s\n", s); }
int main() { return yyparse(); }

要點：

• 優先與結合性宣告（%left、%right）解決算式歧義，這是 Yacc 對歧義文法的務實妥協。
• $$、$1 是語意值堆疊：歸約時把被彈出符號的語意值組合成左部值，可在歸約點直接建 AST 或求值。
• 衝突診斷：bison -v 產生 .output 檔列出 shift/reduce 與 reduce/reduce 衝突。shift/reduce 常見於 dangling else；reduce/reduce 幾乎總是文法錯誤。

LALR 與 GLR#

LALR(1) 將 LR(1) 中「核心（產生式與點相同）」相同的狀態合併，狀態數與 LR(0) 一致，但合併會把錯誤延遲到後續幾個符號才報出（不影響正確性）。若語言過於複雜（如 C++），Bison 提供 GLR（Generalized LR, Tomita 1984）：衝突時平行分裂堆疊，事後保留語意上可行的剖析，代價是最壞指數時間。

為何 LR 適合工具、LL 適合手寫#

• LR 表由機器生成最有效率，人類難以閱讀；錯誤訊息品質受限（傳統 Yacc）。
• 現代手寫編譯器回流 LL/Pratt，因為錯誤復原與 IDE 需求更重視可讀性。
• 兩者的分界在 2000 年後逐漸模糊：LALRPop、Tree-sitter（GitHub, 2018，用 GLR 驅動編輯器語法高亮）各自取捨。

小結#

• Knuth 1965 的 LR(k) 是自底向上分析的理論基石；DeRemer 1971 的 LALR 使其工程可行。
• shift/reduce 兩動作＋LR 項目集＋ACTION/GOTO 表是核心機制。
• Yacc/Bison 以 LALR(1) 提供聲明式語法＋語意動作，與 Lex 構成經典組合。