C語言實現 SGF 圍棋棋譜解析器：基於事件的 SAX 風格 API 設計與 EBNF 遞歸下降解析

編輯：關於C語言

前言

SGF (Smart Game Format) 是圍棋棋譜最通用的文本格式，基於樹結構、純文本、易解析。本文介紹一個純 C 實現的 **事件驅動（SAX 風格）解析器**，核心採用 **遞歸下降** 直接對應 EBNF 文法，代碼清晰、零依賴、記憶體佔用極低，適合嵌入式/移動端/網頁 WASM 移植。

SGF 核心 EBNF 文法（簡化）


Collection   = GameTree { GameTree }
GameTree     = "(" Sequence { GameTree } ")"
Sequence     = Node { Node }
Node         = ";" { Property }
Property     = PropIdent PropValue { PropValue }
PropIdent    = UcLetter { UcLetter }
PropValue    = "[" CValueType "]"
CValueType   = ValueType | Compose
ValueType    = None | Number | Real | Double | Color | SimpleText | Text | Point | Move | Stone

解析器架構設計

1. 上下文結構體


typedef struct {
    void* userData;           // 用戶自定義數據
    int treeIndex;            // 當前樹索引

    // 回調函數指針（用戶實現）
    void (*onTreeStart)  (void* ud, int idx);
    void (*onTreeEnd)    (void* ud, int idx);
    void (*onNodeStart)  (void* ud);
    void (*onNodeEnd)    (void* ud);
    void (*onProperty)   (void* ud, const char* ident, const char* value);

    // 內部緩衝區
    char identBuf[16];
    char* valueBuf;
    int valueBufSize;
} SGFParseContext;

2. 核心解析流程（偽碼）


parseCollection() {
    while (peekChar() == '(') parseGameTree();
}

parseGameTree() {
    expect('(');
    ctx->onTreeStart(ctx->userData, ctx->treeIndex++);
    parseSequence();
    while (peekChar() == '(') parseGameTree();  // 子樹（變化圖）
    expect(')');
    ctx->onTreeEnd(ctx->userData, ctx->treeIndex);
}

parseSequence() {
    while (peekChar() == ';') parseNode();
}

parseNode() {
    expect(';');
    ctx->onNodeStart(ctx->userData);
    while (isUpper(peekChar())) parseProperty();
    ctx->onNodeEnd(ctx->userData);
}

parseProperty() {
    readIdent();          // 大寫字母序列
    while (peekChar() == '[') {
        readValue();      // 處理轉義、換行、括號嵌套
        ctx->onProperty(ctx->userData, ctx->identBuf, ctx->valueBuf);
    }
}

關鍵實現細節

挑戰	解決方案
屬性值轉義 `\]` `\[` `\\`	讀值時逐字符處理，遇 `\` 檢查下一字符決定輸出
屬性值跨行	`[` 後遇換行符繼續讀取，直到配對 `]`
組合值	`CValueType` 允許同一屬性多個 `[]`，回調多次傳遞同 ident 不同 value
大文件流式處理	僅需緩衝當前屬性值，無需載入整棵樹，記憶體 O(1)
錯誤恢復	遇非法字符跳過至下一 `;` 或 `)`，回調錯誤碼供用戶決定是否中止

用戶端使用範例


// 回調實現：構建內存樹 / 存入資料庫 / 即時顯示
void onProperty(void* ud, const char* ident, const char* value) {
    SGFGame* game = (SGFGame*)ud;
    if (strcmp(ident, "B") == 0) addMove(game, BLACK, value);
    else if (strcmp(ident, "W") == 0) addMove(game, WHITE, value);
    else if (strcmp(ident, "SZ") == 0) game->boardSize = atoi(value);
    // ... 其他屬性
}

int main() {
    SGFParseContext ctx = {0};
    ctx.userData = &game;
    ctx.onProperty = onProperty;
    // ... 設定其他回調

    FILE* fp = fopen("game.sgf", "r");
    sgf_parse_file(&ctx, fp);
    fclose(fp);
    // game 現包含完整棋譜
}

效能與優化

時間複雜度：O(N) 單遍掃描，N 為文件字符數。
空間複雜度：O(1) 額外空間（不計用戶回調構建的數據結構）。
優化點：
- 識別符查表優化（`static const char* propNames[]` + 完美雜湊）。
- 值緩衝區複用，避免頻繁 `malloc`/`free`。
- SIMD 加速空白字符跳過（大文件明顯提速）。

對比：SAX vs DOM 風格

維度	SAX (事件驅動)	DOM (樹模型)
記憶體	極低	O(N) 載入整樹
隨機訪問	需用戶自建索引	原生支援
實現複雜度	低（遞歸下降）	高（需構建節點池）
適用場景	流式、嵌入式、大文件	編輯器、複雜查詢、多次遍歷