解析器生成器 Yacc 詳解：從文法規格到編譯器前端構建

1. 什麼是解析器生成器？

解析器生成器（Parser Generator）讀取**文法規格**（Grammar Specification），自動產生語法分析器（Parser）原始碼。開發者專注於文法描述，而非手寫遞歸下降或移進歸約邏輯。

2. Yacc：經典 LALR(1) 解析器生成器

• 全名：Yet Another Compiler-Compiler
• 作者：S. C. Johnson (1970s, AT&T Bell Labs)
• 算法：LALR(1) — Look-Ahead LR(1)，兼具 LR(1) 強大與 SLR(1) 簡練。
• 地位：UNIX 標準工具，構建無數生產級編譯器（C、Pascal、SQL、Script 語言等）。
• 現代替代：Bison (GNU 相容 Yacc)、ANTLR (LL(*)、支援多語言)、Menhir (OCaml)。

3. Yacc 工作流程

+----------------+     yacc      +----------------+     C編譯器      +----------------+
| translate.y    |  ──────────►  | y.tab.c        |  ────────────►  | translate      |
| (文法規格+動作) |               | (生成的Parser) |                  | (可執行檔)     |
+----------------+               +----------------+                  +----------------+
        ▲                                                               ▲
        │                                                               │
        │                      +----------------+                       │
        └───────────────────── | 詞法分析器    | ◄─────────────────────┘
                               | (lex/flex)   |
                               +----------------+

1. 編寫 translate.y：包含 **Token 宣告**、**文法規則**、**語義動作 (C 代碼)**。
2. 執行 yacc translate.y 產生 y.tab.c（含 yyparse()）。
3. 編寫/生成詞法分析器 lex.yy.c (flex)，提供 yylex()。
4. 編譯鏈接：cc y.tab.c lex.yy.c -ly -ll -o translate。

4. Yacc 規格檔結構

%{
/* C 宣告區：#include、全域變數、函數原型 */
#include <stdio.h>
#include "ast.h"
%}

/* Token 宣告區 */
%token NUMBER IDENTIFIER
%token IF ELSE WHILE RETURN
%left '+' '-'
%left '*' '/'
%right UMINUS  /* 一元負號優先級最高 */

/* 文法規則區 */
%%
program: declaration_list { $$ = make_program($1); }
       ;

declaration_list: declaration
                | declaration_list declaration { $$ = append_decl($1, $2); }
                ;

declaration: var_decl
           | fun_decl
           ;

var_decl: type_specifier IDENTIFIER ';' { $$ = make_var_decl($1, $2); }
        ;

type_specifier: 'int' { $$ = TYPE_INT; }
              | 'float' { $$ = TYPE_FLOAT; }
              ;

/* ... 更多規則 ... */
%%

/* 輔助函數區 */
int yyerror(const char *msg) { fprintf(stderr, "Line %d: %s\n", yylineno, msg); return 0; }
int main() { return yyparse(); }

5. 核心概念詳解

5.1 Token 與語義值

• %token 宣告終結符，可關聯型別：%token <int_val> NUMBER。
• 語義值透過 $$ (左邊)、$1 $2... (右邊符號) 存取。
• 預設型別 int；複雜型別用 %union 定義：

%union {
    int int_val;
    float float_val;
    char *str_val;
    ASTNode *node;
}
%token <int_val> NUMBER
%token <str_val> IDENTIFIER
%type <node> program declaration_list

5.2 優先級與結合性

• %left：左結合（+ - * /）
• %right：右結合（= ^ 一元運算子）
• %nonassoc：不結合（比較運算子 a < b < c 非法）
• 規則出現越晚優先級越高；同組同優先級。

5.3 衝突處理

6. 實戰技巧

1. 錯誤恢復：在關鍵規則加入 error 符號：
   stmt: error ';' { yyerrok; } — 遇錯跳到分號同步點。
2. 抽象語法樹 (AST) 建構：語義動作中分配節點、串聯子樹，$$ 回傳根節點。
3. 符號表管理：在聲明規則插入符號，作用域進出時推入/彈出符號表棧。
4. 除錯：yacc -v 產生 y.output 狀態機報告；運行時設定 yydebug=1 追蹤移進/歸約。

7. 從 Yacc 到現代工具

8. 總結

Yacc 確立了「聲明式文法 + 語義動作」的編譯器前端開發範式。雖然現代專案傾向 ANTLR 或手寫遞歸下降（更易除錯、錯誤訊息更好），但理解 Yacc/LALR 原理對掌握靜態分析、語言設計、工具鏈開發仍具核心價值。