手把手寫 C 語言編譯器（五）：用 Bison 實現四則運算解析器

編輯：關於C語言

前言

系列第五篇，使用 **Bison (GNU yacc)** 定義文法，生成 LALR(1) 解析器，實現一個支持浮點數、四則運算、一元負號的迷你計算器。完整 `.y` 文件與編譯運行步驟均已包含。

Bison 文法文件 `calc.y`

%{
#define YYSTYPE double
#include 
#include 
int yylex(void);
void yyerror(const char *);
%}

%token NUM

%%
input:  /* empty */
      | input line
      ;

line: '\n'
    | exp '\n'   { printf("\t%.10g\n", $1); }
    ;

exp: NUM                 { $$ = $1; }
   | exp exp '+'         { $$ = $1 + $2; }
   | exp exp '-'         { $$ = $1 - $2; }
   | exp exp '*'         { $$ = $1 * $2; }
   | exp exp '/'         { $$ = $1 / $2; }
   | exp 'n'             { $$ = -$1; }   /* 一元負號，lexer 返回 'n' */
   ;
%%

/* 詞法分析器 */
int yylex(void) {
    int c;
    while ((c = getchar()) == ' ' || c == '\t'); // 跳過空白
    if (c == '.' || isdigit(c)) {
        ungetc(c, stdin);
        scanf("%lf", &yylval);
        return NUM;
    }
    if (c == EOF) return 0;
    if (c == '-') { /* 區分減號與負號：簡單策略，上一 token 為數字或 ')' 視為減號，否則負號 */
        int next = getchar();
        if (next == ' ' || next == '\t' || next == '\n' || next == EOF) return 'n'; // 簡化處理
        ungetc(next, stdin);
    }
    return c; // 返回單字符 token (+ - * / \n)
}

void yyerror(const char *msg) {
    fprintf(stderr, "Error: %s\n", msg);
}

int main() {
    return yyparse();
}

編譯與運行步驟 (Ubuntu/Linux)

# 1. 安裝工具
sudo apt-get install bison flex gcc

# 2. 生成解析器 C 代碼
bison -d calc.y        # 生成 calc.tab.c 和 calc.tab.h

# 3. 編譯鏈接
gcc -o calc calc.tab.c -lfl  # -lfl 鏈接 flex 庫 (若 yylex 用 flex 生成則需)，純手寫 yylex 可省略

# 4. 運行測試
./calc
# 輸入 (後綴/逆波蘭表達式，因文法為 exp exp op)：
1 4 +     → 輸出 5
3 10 *    → 輸出 30
5 2 -     → 輸出 3
6 2 /     → 輸出 3
4 n       → 輸出 -4   (一元負號)
Ctrl+D 退出

關鍵點解析

項目	說明
`%define YYSTYPE double`	語義值類型為 double，支持浮點運算
`%token NUM`	聲明終結符 NUM，對應浮點數
文法 `exp exp '+'`	後綴表達式 (逆波蘭)，天然無歧義、無需優先級聲明
`exp 'n'`	一元負號，lexer 中將負號映射為字符 `'n'`
`yyerror`	語法錯誤回調，這裡僅打印
`$$ = $1 + $2`	語義動作：$1/$2 為左右子節點值，$$ 為本節點值