Bison 相關函數的調用時機及數據結構詳解

1. 核心函數調用流程

1.1 `yyparse()` 的完整執行流程

初始化階段：

分配初始棧空間：初始化狀態棧 yyss 和值棧 yyvs，默認大小為 YYINITDEPTH（通常為 200）。
設置初始狀態：壓入初始狀態 0 到狀態棧。

yyss = yyssa;       // 靜態初始棧空間
yyvs = yyvsa;       // 靜態值棧空間
yystacksize = YYINITDEPTH;
yyssp = yyss;       // 棧頂指針
yyvsp = yyvs;       // 值棧指針
*yyssp = 0;         // 初始狀態

主循環（狀態機驅動）：
- 循環步驟：
  1. 獲取當前狀態：yystate = *yyssp。
  2. 查詢 ACTION 表：根據當前狀態和輸入 token（通過 yylex() 獲取），決定下一步動作。
  3. 執行動作：
    - 移進（Shift）：壓入新狀態和語義值。
    - 歸約（Reduce）：彈出右端符號，執行語義動作，壓入左端符號。
    - 接受（Accept）：返回成功。
    - 錯誤（Error）：調用錯誤恢復。

棧擴展策略：

當棧空間不足時，以 2 倍 當前大小擴容：

new_stacksize = yystacksize * 2;
yyss = (yytype_int16 *) realloc (yyss, new_stacksize * sizeof (yytype_int16));
yyvs = (YYSTYPE *) realloc (yyvs, new_stacksize * sizeof (YYSTYPE));

終止條件：
- 接受狀態：返回 0。
- 不可恢復錯誤：返回 1。

1.2 `yylex()` 的觸發時機

每次需要新 Token 時：在 yyparse() 主循環中，通過以下代碼觸發：

yychar = yylex();  // 調用詞法分析器
if (yychar < 0) yychar = YYEOF; // 處理 EOF

緩存機制：Bison 可能預讀取一個 token（Lookahead Token），導致 yylex() 在歸約前被調用。

1.3 `yyerror()` 的錯誤處理流程

錯誤觸發：當 ACTION 表返回 YY_ERROR_ACTION 時，調用 yyerror("syntax error")。
錯誤恢復：
1. 彈出棧狀態，直到找到包含 error 符號的狀態。
2. 丟棄輸入 Token，直到找到同步符號（如分號、換行符）。
3. 恢復解析：壓入 error 符號，繼續執行。

2. 主要數據結構的實現細節

2.1 LALR(1) 狀態機表

ACTION 表結構：
- 編碼方式：使用壓縮的一維數組存儲，通過宏 YY_ACTTAB 定義。
- 動作類型：
  - 正數：移進到對應狀態（如 5 表示移進到狀態 5）。
  - 負數：歸約規則編號（如 -3 表示按第 3 條規則歸約）。
  - YY_ACCEPT：接受輸入。
  - YY_ERROR_ACTION：語法錯誤。
```
static const yytype_int8 yyaction[] = {
    YY_ACCEPT,            /* 狀態 0 的默認動作 */
    YY_ERROR_ACTION,       /* 狀態 1 的默認動作 */
    // ...
};
```

GOTO 表結構：

存儲非終結符的轉移目標狀態：

static const yytype_int8 yygoto[] = {
    2,    /* 狀態 0 遇到非終結符 expr 跳轉到狀態 2 */
    // ...
};

2.2 語法分析棧的底層實現

狀態棧和值棧的同步更新：

// 移進操作示例
*++yyssp = yystate;     // 壓入新狀態
*++yyvsp = yyval;       // 壓入語義值

歸約操作示例：

// 彈出右端符號
yyssp -= yylen;         // 彈出狀態
yyvsp -= yylen;         // 彈出值
// 執行語義動作
yyval = yyaction(yyvsp); 
// 壓入左端符號
*++yyssp = yygoto[/* 根據左端符號查詢 GOTO 表 */];
*++yyvsp = yyval;

2.3 符號編號的生成規則

終結符（Tokens）：
- 用戶定義的 Token（如 NUMBER、ID）從 258 開始編號（避免與 ASCII 沖突）。
- YYEOF 固定為 0，YYerror 為 256，YYUNDEF 為 257。
非終結符（Non-terminals）：
- 編號從 用戶定義的 Token 數量 + 1 開始。

編號映射表：

#define NUMBER 258
#define ID 259
#define expr 260

2.4 語義值（`YYSTYPE`）和位置信息（`YYLTYPE`）

YYSTYPE 的生成規則：

// 用戶定義的 %union
%union { int ival; char *sval; }
// 生成的代碼
typedef union YYSTYPE {
    int ival;
    char *sval;
} YYSTYPE;

YYLTYPE 的擴展：

// 用戶啟用 %locations
%locations
// 生成的代碼
typedef struct YYLTYPE {
    int first_line;  int first_column;
    int last_line;   int last_column;
} YYLTYPE;

3. 關鍵代碼片段解析

3.1 Bison 生成的解析器主循環

int yyparse() {
    // 初始化棧
    yyssp = yyss;
    yyvsp = yyvs;
    *yyssp = 0; // 初始狀態

    while (1) {
        // 獲取當前狀態
        yystate = *yyssp;

        // 查詢 ACTION 表
        yyact = yy_action[yystate];
        if (yyact == YY_ERROR_ACTION) {
            // 處理錯誤
            yyerror("syntax error");
            // 錯誤恢復邏輯
            // ...
        }

        // 移進或歸約
        if (yyact < YYNSTATE) {
            // 移進操作
            *++yyssp = yyact; // 新狀態
            *++yyvsp = yylval; // 語義值
            yychar = yylex();  // 讀取下一個 Token
        } else {
            // 歸約操作
            yylen = yyr2[yyact];
            // 彈出右端符號
            yyssp -= yylen;
            yyvsp -= yylen;
            // 執行語義動作
            yyval = yyaction(yyvsp);
            // 壓入左端符號
            *++yyssp = yygoto[/* 查詢 GOTO 表 */];
            *++yyvsp = yyval;
        }
    }
}

3.2 用戶定義的語義動作示例

expr: expr '+' expr {
    // 語義動作：$$ = $1 + $3
    YYSTYPE val1 = yyvsp[-2].ival; // $1
    YYSTYPE val2 = yyvsp[0].ival;  // $3
    yylval.ival = val1 + val2;
    // 合并位置信息
    yylloc.first_line = yylsp[-2].first_line;
    yylloc.last_line = yylsp[0].last_line;
}

4. 調試與分析工具

4.1 生成狀態機報告

使用 bison -v 生成 .output 文件，查看所有狀態和沖突：

bison -d -v parser.y

輸出示例：

State 5:
    expr -> expr . '+' expr
    '+' shift 6
    '+' [reduce using rule 2 (expr)]
    $default reduce using rule 2 (expr)

4.2 啟用調試模式

在 Bison 文件中添加 %debug，或在編譯時定義 YYDEBUG=1：

%debug // 在 .y 文件中啟用調試

bison -t parser.y     // 生成帶調試符號的代碼
gcc -DYYDEBUG=1 ...   // 啟用調試宏

運行時通過 YYDEBUG=1 環境變量控制輸出：

YYDEBUG=1 ./parser input.txt

5. 實戰示例：解析算術表達式

5.1 詞法分析器（Flex）

%{
#include "parser.tab.h"
%}

%option noyywrap

%%
[0-9]+      { yylval.ival = atoi(yytext); return NUMBER; }
"+"         { return PLUS; }
"*"         { return STAR; }
[ \t\n]     { /* 忽略空白符 */ }
.           { yyerror("Invalid character"); return YYUNDEF; }
%%

5.2 語法分析器（Bison）

%{
#include <stdio.h>
%}

%token NUMBER
%token PLUS STAR
%left PLUS
%left STAR

%%

input: expr { printf("Result: %d\n", $1); }
     ;

expr: expr PLUS expr { $$ = $1 + $3; }
    | expr STAR expr { $$ = $1 * $3; }
    | NUMBER         { $$ = $1; }
    ;

%%

int main() {
    yyparse();
    return 0;
}

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

5.3 解析流程跟蹤

輸入 3 + 5 * 2 時，解析器狀態變化如下：

移進 3：狀態棧 [0] → [0, 5]（假設狀態 5 對應 NUMBER）。
歸約 expr → NUMBER：彈出 5，壓入 expr 對應的狀態。
移進 +：狀態棧 [0, expr] → [0, expr, 6]。
移進 5：狀態棧 [0, expr, 6, 5]。
移進 *：狀態棧 [0, expr, 6, 5, 7]。
移進 2：狀態棧 [0, expr, 6, 5, 7, 5]。
歸約 expr → NUMBER：彈出 5，壓入 expr。
歸約 expr → expr * expr：計算 5 * 2 = 10，壓入 expr。
歸約 expr → expr + expr：計算 3 + 10 = 13，輸出結果。

6. 總結與進階

性能優化：通過調整棧初始大小（%define initial-action）或使用更高效的內存分配器減少 realloc 調用。
錯誤恢復增強：自定義 yyerror() 和同步符號集合，提升錯誤恢復能力。
多文件解析：通過 yyrestart() 函數重置解析器狀態，支持連續解析多個輸入文件。
符號表集成：在語義動作中管理符號表，支持變量聲明和作用域。

通過深入理解 Bison 的函數調用機制和數據結構，開發者可以高效構建復雜的語法分析器，并解決實際工程中的性能、內存和錯誤處理問題。

posted on 2025-03-10 15:29 哈哈哈119 閱讀(87) 評論(0) 收藏舉報

刷新頁面返回頂部