开源项目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命令实现