從零打造 C 語言 JSON 解析引擎：遞歸下降分析實作詳解

編輯：關於C語言

從零打造 C 語言 JSON 解析引擎：遞歸下降分析實作詳解

前言與設計動機

作者先前曾為統計實驗專案撰寫輕量 JSON 解析器，後深入研究知名開源專案 cJSON。雖 cJSON 僅 700 行左右，但程式碼緊湊難讀；作者決定重構一套結構更清晰、效能更優、介面更友善的 cjson_t 引擎，採用遞歸下降分析處理 JSON 語法。

核心資料結構

struct cjson {
    struct cjson *next, *prev;  // 同層節點雙向鏈表
    struct cjson *child;        // 子節點（陣列/物件）
    int type;                   // 型別：NULL/TRUE/FALSE/NUMBER/STRING/ARRAY/OBJECT
    char *key;                  // 物件鍵名
    char *vs;                   // 字串值
    double vd;                  // 數值/布林值
};
typedef struct cjson* cjson_t;

此設計以雙向鏈表串連同層節點，child 指向巢狀結構，極易遍歷與操作。

關鍵解析函數：遞歸下降入口

static const char* __parse_value(cjson_t item, const char* value) {
    char c;
    if (value && (c = *value)) {
        switch (c) {
            case 'n': return item->type = _CJSON_NULL, value + 4;
            case 'f': return item->type = _CJSON_FALSE, value + 5;
            case 't': return item->type = _CJSON_TRUE, item->vd = 1.0, value + 4;
            case '\"': return __parse_string(item, value);
            case '0': case '1': case '2': case '3': case '4':
            case '5': case '6': case '7': case '8': case '9': case '+': case '-':
                return __parse_number(item, value);
            case '[': return __parse_array(item, value);
            case '{': return __parse_object(item, value);
        }
    }
    SL_WARNING("params value = %s!", value);
    return NULL;
}

陣列解析範例

static const char* __parse_array(cjson_t item, const char* str) {
    cjson_t child;
    if (*str != '[') return NULL;
    item->type = _CJSON_ARRAY;
    str = __skip(str + 1);
    if (*str == ']') return str + 1; // 空陣列

    item->child = child = __cjson_new();
    str = __skip(__parse_value(child, str));
    if (!str) return NULL;

    while (*str == ',') {
        cjson_t nitem = __cjson_new();
        child->next = nitem; nitem->prev = child; child = nitem;
        str = __skip(__parse_value(child, __skip(str + 1)));
        if (!str) return NULL;
    }
    if (*str != ']') return NULL;
    return str + 1;
}

數值解析支援科學標記法

static const char* __parse_number(cjson_t item, const char* str) {
    double n = 0.0, ns = 1.0, nd = 0.0;
    int e = 0, es = 1;
    char c;
    if ((c = *str) == '-' || c == '+') { ns = (c == '-') ? -1.0 : 1.0; ++str; }
    for (c = *str; c >= '0' && c <= '9'; c = *++str) n = n * 10 + c - '0';
    if (c == '.') for (; (c = *++str) >= '0' && c <= '9'; --nd) n = n * 10 + c - '0';
    if (c == 'e' || c == 'E') {
        if ((c = *++str) == '+') ++str;
        else if (c == '-') { es = -1; ++str; }
        for (; (c = *str) >= '0' && c <= '9'; ++str) e = e * 10 + c - '0';
    }
    n = ns * n * pow(10.0, nd + es * e);
    item->vd = n; item->type = _CJSON_NUMBER;
    return str;
}