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();