開源項目cJSON具體實作3（字元串的解析）

3. JSON 字元串解析

文章目錄

- - 3. JSON 字元串解析
  - - 3.1 JSON字元串的文法規則及解釋
    - 3.2 設計頭檔案
    - 3.3 測試代碼
    - 3.4 實作解析器
    - 3.5 拓展，關于記憶體洩漏的檢測方法。

3.1 JSON字元串的文法規則及解釋

/*
JSON 字元串是由前後兩個雙引号(quotation-mark)夾着零至多個字元組成。
字元分為 無轉義字元 或 轉義字元。
轉義序列有 9 種，都是以反斜線開始，如常見的 \n 代表換行符，比較特殊的是 \uXXXX
*/
JSON-text = ws value ws
value = string
string = quotation-mark *char quotation-mark
char = unescaped /
   escape (
       %x22 /          ; "    quotation mark  U+0022
       %x5C /          ; \    reverse solidus U+005C
       %x2F /          ; /    solidus         U+002F
       %x62 /          ; b    backspace       U+0008
       %x66 /          ; f    form feed       U+000C
       %x6E /          ; n    line feed       U+000A
       %x72 /          ; r    carriage return U+000D
       %x74 /          ; t    tab             U+0009
       %x75 4HEXDIG )  ; uXXXX                U+XXXX
escape = %x5C          ; \
quotation-mark = %x22  ; "
unescaped = %x20-21 / %x23-5B / %x5D-10FFFF

3.2 設計頭檔案

在 C 語言中，字元串一般表示為空結尾字元串（’\0’）代表字元串的結束。然而，JSON 字元串是允許含有空字元的。是以如果純粹使用空結尾字元來表示 JSON 解析後的結果，就沒法處理空字元；為此，我們的解決方法是即儲存解析後的字元，也記錄字元的長度。由于大部分 C 程式都假設字元串是空結尾字元串，我們還是在最後加上一個空字元。

是以我們這個結構就變成了：

typedef struct {
    char* s;   //string
    size_t len;   //string len
    double n;  //number
    lept_type type;   //類型
}lept_value;

注意：一個值不可能同時為數字和字元串，是以我們可使用 C 語言的 union 來節省記憶體：

typedef struct {
    union {
        struct { char* s; size_t len; }s;  /* string */
        double n;                          /* number */
    }u;
    lept_type type;
}lept_value;

拓展，關于聯合：

union維護足夠的空間來放置多個資料成員中的一種，而不是每一個資料成員配置空間。在union中所有的資料成員共用一個空間，同一時間隻能存儲一個資料成員。

API設計

const char* lept_get_string(const lept_value* v);
size_t lept_get_string_length(const lept_value* v);

在前兩個部分，我們隻提供讀取值的 API，沒有寫入的 API，是因為寫入時我們還要考慮釋放記憶體。我們在這裡把它們補全：

#define lept_init(v) do { (v)->type = LEPT_NULL; } while (0)     //用上 do { ... } while(0) 是為了把表達式轉為語句，模仿無傳回值的函數。

#define lept_set_null(v) lept_free(v);//由于 lept_free() 實際上也會把 v 變成 null 值，我們隻用一個宏來提供 lept_set_null() 這個 API。

int lept_parse(lept_value* v, const char* json);  

void lept_free(lept_value* v);

lept_type lept_get_type(const lept_value* v); 

int lept_get_boolean(const lept_value* v);
void lept_set_boolean(lept_value* v, int b);

double lept_get_number(const lept_value* v);
void lept_set_number(lept_value* v, double n);

const char* lept_get_string(const lept_value* v);
size_t lept_get_string_length(const lept_value* v);
void lept_set_string(lept_value* v, const char* s, size_t len);

關于 lept_init; lept_free; lept_set_null 這三個函數？

因為現在在lept_value中加入了字元串的儲存，并且由于這個字元串它的長度不是固定的，是以我們使用動态配置設定記憶體來完成存儲，即我們使用了指針；API 設計中我們加入了許多的set函數，在使用set時得對傳入的參數 lept_value* v 進行清空可能配置設定到的記憶體，是以設計了 lept_free 函數。

我們在解析JSON-text時，會對存儲樹形結構的 lept_value v 的類型進行改變，是以在調用這些函數之前，得進行初始化，又因為初始化函數的實作非常簡單，是以我們用宏實作。

至于 lept_set_null 函數的作用與 lept_free() 相同，是以用一個宏來實作 lept_set_null()

API函數的實作

int lept_parse(lept_value* v, const char* json) {
    /*  */
    lept_init(v);
    lept_parse_whitespace(&c);
    /*  */
}

void lept_free(lept_value* v) {
    assert(v != NULL);
    if (v->type == LEPT_STRING)//僅當值是字元串類型，我們才要處理
        free(v->u.s.s);//對數組的釋放
    v->type = LEPT_NULL;//對對象的釋放
 }

lept_type lept_get_type(const lept_value* v) {
    assert(v != NULL);
    return v->type;
}

int lept_get_boolean(const lept_value* v) {
    assert(v != NULL && (v->type == LEPT_TRUE || v->type == LEPT_FALSE));
    return v->type == LEPT_TRUE;
}

void lept_set_boolean(lept_value* v, int b) {
    lept_free(v);
    v->type = b ? LEPT_TRUE : LEPT_FALSE;
}

double lept_get_number(const lept_value* v) {
    assert(v != NULL && v->type == LEPT_NUMBER);
    return v->u.n;
}

void lept_set_number(lept_value* v, double n) {
    lept_free(v);
    v->u.n = n;
    v->type = LEPT_NUMBER;
}

const char* lept_get_string(const lept_value* v) {
    assert(v != NULL && v->type == LEPT_STRING);
    return v->u.s.s;
}

size_t lept_get_string_length(const lept_value* v) {
    assert(v != NULL && v->type == LEPT_STRING);
    return v->u.s.len;
}

/*  我們來實作lept_set_string函數，即把參數中的字元串複制一份  */
void lept_set_string(lept_value* v, const char* s, size_t len) {
    assert(v != NULL && (s != NULL || len == 0));//非空指針（有具體的字元串）或是零長度的字元串都是合法的。
    lept_free(v);
    v->u.s.s = (char*)malloc(len + 1);//+ 1 是因為結尾空字元
    memcpy(v->u.s.s, s, len);
    v->u.s.s[len] = '\0';//補上結尾空字元
    v->u.s.len = len;
    v->type = LEPT_STRING;
}

3.3 測試代碼

先捋個邏輯：首先因為現在的lept_value結構體裡面包含了一個字元指針，是以代碼在調用 lept_parse() 之後，最終也應該調用 lept_free() 去釋放記憶體。如果不使用 lept_parse()，我們需要初始化值lept_init()，最後 lept_free()。是以之前的單元測試要加入此調用。（lept_parse中已經初始化過就不用了）

static void test_parse_null() {
    lept_value v;
    lept_init(&v);  //相當于之前的 v.type = LEPT_FALSE; 作用
    lept_set_boolean(&v, 0);
    EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, "null"));
    EXPECT_EQ_INT(LEPT_NULL, lept_get_type(&v));
    lept_free(&v);
}

static void test_parse_true() {
    lept_value v;
    lept_init(&v);
    lept_set_boolean(&v, 0);
    EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, "true"));
    EXPECT_EQ_INT(LEPT_TRUE, lept_get_type(&v));
    lept_free(&v);
}

static void test_parse_false() {
    lept_value v;
    lept_init(&v);
    lept_set_boolean(&v, 1);
    EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, "false"));
    EXPECT_EQ_INT(LEPT_FALSE, lept_get_type(&v));
    lept_free(&v);
}

#define TEST_NUMBER(expect, json)\
    do {\
        lept_value v;\
        lept_init(&v);\  //注意得加上初始化
        EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, json));\
        EXPECT_EQ_INT(LEPT_NUMBER, lept_get_type(&v));\
        EXPECT_EQ_DOUBLE(expect, lept_get_number(&v));\
        lept_free(&v);\
    } while(0)


#define TEST_ERROR(error, json)\
    do {\
        lept_value v;\
        lept_init(&v);\  //注意得加上初始化
        EXPECT_EQ_INT(error, lept_parse(&v, json));\
        EXPECT_EQ_INT(LEPT_NULL, lept_get_type(&v));\
        lept_free(&v);\
    } while(0)

接下來是字元串的測試代碼

#define EXPECT_EQ_STRING(expect, actual, alength) \
    EXPECT_EQ_BASE(sizeof(expect) - 1 == alength && memcmp(expect, actual, alength) == 0, expect, actual, "%s")

#define TEST_STRING(expect, json)\
    do {\
        lept_value v;\
        lept_init(&v);\
        EXPECT_EQ_INT(LEPT_PARSE_OK, lept_parse(&v, json));\
        EXPECT_EQ_INT(LEPT_STRING, lept_get_type(&v));\
        EXPECT_EQ_STRING(expect, lept_get_string(&v), lept_get_string_length(&v));\
        lept_free(&v);\
    } while(0)

static void test_parse_string() {
    TEST_STRING("", "\"\"");
    TEST_STRING("Hello", "\"Hello\"");
    
     TEST_STRING("Hello\nWorld", "\"Hello\\nWorld\"");
    TEST_STRING("\" \\ / \b \f \n \r \t", "\"\\\" \\\\ \\/ \\b \\f \\n \\r \\t\"");
}

//錯誤的測試案例
/*引号不全*/
static void test_parse_missing_quotation_mark() {
    TEST_ERROR(LEPT_PARSE_MISS_QUOTATION_MARK, "\"");
    TEST_ERROR(LEPT_PARSE_MISS_QUOTATION_MARK, "\"abc");
}

/*不合法的字元轉義*/
static void test_parse_invalid_string_escape() {
   TEST_ERROR(LEPT_PARSE_INVALID_STRING_ESCAPE, "\"\\v\""); TEST_ERROR(LEPT_PARSE_INVALID_STRING_ESCAPE, "\"\\'\"");
    TEST_ERROR(LEPT_PARSE_INVALID_STRING_ESCAPE, "\"\\0\"");
    TEST_ERROR(LEPT_PARSE_INVALID_STRING_ESCAPE, "\"\\x12\"");

}

/*不合法的字元*/
static void test_parse_invalid_string_char() {
    TEST_ERROR(LEPT_PARSE_INVALID_STRING_CHAR, "\"\x01\"");
    TEST_ERROR(LEPT_PARSE_INVALID_STRING_CHAR, "\"\x1F\"");

}

static void test_parse() {
    /*  */
    test_parse_string();
    test_parse_missing_quotation_mark();
    test_parse_invalid_string_escape();
    test_parse_invalid_string_char();
}

注意：因為現在我們在頭檔案裡提供了API通路函數：lept_set_boolean、lept_set_numbe、lept_set_string、lept_set_null，是以這些也是要測試的。

#define EXPECT_TRUE(actual) EXPECT_EQ_BASE((actual) != 0, "true", "false", "%s")

#define EXPECT_FALSE(actual) EXPECT_EQ_BASE((actual) == 0, "false", "true", "%s")

static void test_access_null() {
    lept_value v;
    lept_init(&v);
    lept_set_string(&v, "a", 1);//為什麼先設成字元串？可以測試設定為其他類型時，有沒有調用 lept_free() 去釋放記憶體，因為先設定成 string類型一定改變了記憶體

    lept_set_null(&v);
    EXPECT_EQ_INT(LEPT_NULL, lept_get_type(&v));
    lept_free(&v);
}

static void test_access_boolean() {
        lept_value v;
        lept_init(&v);
        lept_set_string(&v, "a", 1);
        lept_set_boolean(&v, 1);
        EXPECT_TRUE(lept_get_boolean(&v));
        lept_set_boolean(&v, 0);
        EXPECT_FALSE(lept_get_boolean(&v));
        lept_free(&v);
}


static void test_access_number() {
    lept_value v;
        lept_init(&v);
        lept_set_string(&v, "a", 1);
        lept_set_number(&v,1234.5);
        EXPECT_EQ_DOUBLE(1234.5, lept_get_number(&v));
        lept_free(&v);
}


static void test_access_string() {
    lept_value v;
    lept_init(&v);
    lept_set_string(&v, "", 0);
    EXPECT_EQ_STRING("", lept_get_string(&v), lept_get_string_length(&v));
    lept_set_string(&v, "Hello", 5);
    EXPECT_EQ_STRING("Hello", lept_get_string(&v), lept_get_string_length(&v));
    lept_free(&v);
}

static void test_parse() {
    /*  */
    test_parse_string();
    test_parse_missing_quotation_mark();
    test_parse_invalid_string_escape();
    test_parse_invalid_string_char();

    test_access_null();
    test_access_boolean();
    test_access_number();
    test_access_string();
}

3.4 實作解析器

注意：我們解析字元串（以及之後的數組、對象）時，需要把每一個字元解析後的結果先儲存在一個臨時的緩沖區，最後再用 lept_set_string() 把緩沖區的結果放入 lept_value 中。在完成解析一個字元串之前，這個緩沖區的大小是不能預知的。是以，我們可以采用動态數組（dynamic array）這種資料結構。

如果每次解析字元串時，都重建立一個動态數組，那麼是比較耗時的。是以我們希望可以重用這個動态數組，在每次解析 JSON 時就隻需要建立一個。而且我們将會發現，無論是解析字元串、數組或對象，我們也隻需要以先進後出的方式通路這個動态數組。換句話說，我們需要一個動态的堆棧資料結構。是以可以在 lept_context 裡放入一個動态堆棧。

typedef struct {
    const char* json;
    char* stack;
    size_t size, top;// size 是目前的堆棧容量，top 是棧頂的位置，由于我們會擴充 stack，是以不要把 top 用指針形式存儲
}lept_context;

注意：既然現在lept_context 裡面包含了一個動态堆棧，就要記得一個原理：使用前先初始化，使用完後記得free。

還是先在lept_parse中添加字元串類型。

static int lept_parse_value(lept_context* c, lept_value* v) {
    switch (*c->json) {
        case 't':  return lept_parse_literal(c, v, "true", LEPT_TRUE);
        case 'f':  return lept_parse_literal(c, v, "false", LEPT_FALSE);
        case 'n':  return lept_parse_literal(c, v, "null", LEPT_NULL);
        default:   return lept_parse_number(c, v);
        case '"':  return lept_parse_string(c, v);  //string
        case '\0': return LEPT_PARSE_EXPECT_VALUE;
    }
}

int lept_parse(lept_value* v, const char* json) {
    int ret;
     assert(v != NULL);
    
    //建立c并初始化stack
    lept_context c;   
   	c.json = json;
    c.stack = NULL;
    c.size = c.top = 0;
    
    lept_init(v);
    lept_parse_whitespace(&c);
    if ((ret = lept_parse_value(&c, v)) == LEPT_PARSE_OK) {
        lept_parse_whitespace(&c);
        if (*c.json != '\0') {
            v->type = LEPT_NULL;
            ret = LEPT_PARSE_ROOT_NOT_SINGULAR;

        }
    }

    assert(c.top == 0);//釋放前加入斷言確定所有資料都被彈出。
    free(c.stack);//記得free
    return ret;
}

實作堆棧的壓入及彈出操作。和普通的堆棧不一樣，我們這個堆棧是以位元組儲存的。每次可要求壓入任意大小的資料，它會傳回資料起始的指針。

#ifndef LEPT_PARSE_STACK_INIT_SIZE
#define LEPT_PARSE_STACK_INIT_SIZE 256
#endif

static void* lept_context_push(lept_context* c, size_t size) {
    void* ret;
    assert(size > 0);
    if (c->top + size >= c->size) {
        if (c->size == 0)
            c->size = LEPT_PARSE_STACK_INIT_SIZE;
        while (c->top + size >= c->size)
            c->size += c->size >> 1;  /* c->size * 1.5 */
        c->stack = (char*)realloc(c->stack, c->size);
    }
    ret = c->stack + c->top;
    c->top += size;
    return ret;
}

static void* lept_context_pop(lept_context* c, size_t size) {
    assert(c->top >= size);
    return c->stack + (c->top -= size);
 }

lept_parse_string 函數的實作

#define PUTC(c, ch) do { *(char*)lept_context_push(c, sizeof(char)) = (ch); } while(0)

/*
函數目的：解析字元串
參數：1. lept_context* c :要被解析的value
     2. lept_value* v :解析後要被儲存的位置
     3. 
解析思路：隻需要先備份棧頂，然後把解析到的字元壓棧，最後計算出長度并一次性把所有字元彈出，再設定到值裡便可以。

注意：
1. 對于不合法的轉義字元傳回 LEPT_PARSE_INVALID_STRING_ESCAPE
2. 對于不合法字元，首先由`unescaped = %x20-21 / %x23-5B / %x5D-10FFFF`可知。當中空缺的 %x22 是雙引号，%x5C 是反斜線，都已經處理。是以不合法的字元是 %x00 至 %x1F。
*/
static int lept_parse_string(lept_context* c, lept_value* v) {
        size_t head = c->top;//備份棧頂
        size_t len;
	    EXPECT(c, '\"');//判斷c是否為string類型
        const char* p = c->json;//p指向的是字元串開始的字元

	    for (;;) {
       		char ch = *p++;
        	switch (ch) {
                       case '\\':             //轉義字元的處理
                              switch (*p++){
                              case '\"': PUTC(c, '\"'); break;
                              case '\\': PUTC(c, '\\'); break;
                              case '/':  PUTC(c, '/'); break;
                              case 'b':  PUTC(c, '\b'); break;
                              case 'f':  PUTC(c, '\f'); break;
                              case 'n':  PUTC(c, '\n'); break;
                              case 'r':  PUTC(c, '\r'); break;
                              case 't':  PUTC(c, '\t'); break;
                              default:
                                      c->top = head;
                                      return LEPT_PARSE_INVALID_STRING_ESCAPE;
                              }
                              break;
            case '\"':
                len = c->top - head; 
                lept_set_string(v, (const char*)lept_context_pop(c, len), len);//将所有字元一次性彈出
                c->json = p;
                return LEPT_PARSE_OK;
            case '\0':
                c->top = head;
                return LEPT_PARSE_MISS_QUOTATION_MARK;
            default:
                              if ((unsigned char)ch < 0x20){  //剩餘的情況下有不合法字元串的情況：%x00 至 %x1F
                                      c->top = head;
                                      return LEPT_PARSE_INVALID_STRING_CHAR;//不合法的字元串
                              }
                PUTC(c, ch); //把解析的字元串壓棧
        }
    }
}

3.5 拓展，關于記憶體洩漏的檢測方法。

Windows下的記憶體洩漏檢測方法

在 Windows 下，可使用 Visual C++ 的 C Runtime Library（CRT）檢測記憶體洩漏。

首先，我們在 .c 檔案首行插入這一段代碼：

#ifdef _WINDOWS
#define _CRTDBG_MAP_ALLOC
#include <crtdbg.h>
#endif

并在 main() 函數開始位置插入：

#ifdef _WINDOWS
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

就可以在調試的輸出視窗看到。

如果檢測不到記憶體洩漏的話（前提是要有記憶體洩漏），可以試試：

在代碼最上面多加上一條：#define _WINDOWS
在main退出前加上一句：_CrtDumpMemoryLeaks();

開源項目cJSON具體實作3（字元串的解析）

3. JSON 字元串解析

文章目錄

3.1 JSON字元串的文法規則及解釋

3.2 設計頭檔案

3.3 測試代碼

3.4 實作解析器

3.5 拓展，關于記憶體洩漏的檢測方法。

繼續閱讀

C語言——指針與數組名的差別一：指針二：數組名三.分析四：差別

C語言程式注釋風格

【C語言】Simple Sorting（結構）

C語言：記憶體四區C語言之記憶體四區

【C語言】指針進階實踐（指針數組和建立單連結清單）

C語言小遊戲：和電腦玩21點遊戲

C 語言添加列印資訊

穩住别被驚豔了哦！！！IT行業計算機專業——必備100個網站

C語言——運算符優先級一：引言二：優先級表

資料結構：線性表資料結構：線性表

C語言學習筆記3--輸入輸出C語言學習筆記3–輸入輸出

線性插值_c語言實作

資料結構（4）連結清單的介紹與代碼實作（c語言)單連結清單的實作代碼雙連結清單的實作代碼

strlen實作的對比學習

C指針之指針帶來的一些符号的了解

模拟A卷二、6 unix系統中tail指令實作