跟着做一个JSON解析器（二）

跟着github上的项目json-tutorial完成一个json解析器。本文对应该项目的第二单元，重点在于解析 JSON number 类型。

👉原项目地址

一、JSON 数字语法

1
2
3
4
number = [ "-" ] int [ frac ] [ exp ]
int = "0" / digit1-9 *digit
frac = "." 1*digit
exp = ("e" / "E") ["-" / "+"] 1*digit

number 是以十进制表示，它主要由 4 部分顺序组成：负号、整数、小数、指数。只有整数是必需部分。注意和直觉可能不同的是，正号是不合法的。

整数部分如果是 0 开始，只能是单个 0；而由 1-9 开始的话，可以加任意数量的数字（0-9）。也就是说，0123 不是一个合法的 JSON 数字。

小数部分比较直观，就是小数点后是一或多个数字（0-9）。

JSON 可使用科学记数法，指数部分由大写 E 或小写 e 开始，然后可有正负号，之后是一或多个数字（0-9）。

JSON 标准 ECMA-404 采用图的形式表示语法，也可以更直观地看到解析时可能经过的路径：

number

上一单元的 null、false、true 在解析后，我们只需把它们存储为类型。但对于数字，我们要考虑怎么存储解析后的结果。

二、数字表示方式

从 JSON 数字的语法，我们可能直观地会认为它应该表示为一个浮点数（floating point number），因为它带有小数和指数部分。然而，标准中并没有限制数字的范围或精度。为简单起见，leptjson 选择以双精度浮点数（C 中的 double 类型）来存储 JSON 数字。

为 lept_value 添加成员：

1
2
3
4
typedef struct {
    double n;
    lept_type type;
}lept_value;

仅当 type == LEPT_NUMBER 时，n 才表示 JSON 数字的数值。所以获取该值的 API 是这么实现的：

1
2
3
4
double lept_get_number(const lept_value* v) {
    assert(v != NULL && v->type == LEPT_NUMBER);
    return v->n;
}

使用者应确保类型正确，才调用此 API。我们继续使用断言来保证。

三、单元测试

我们定义了 API 之后，按照 TDD，我们可以先写一些单元测试。这次我们使用多行的宏来减少重复代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define TEST_NUMBER(expect, json)\
    do {\
        lept_value 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));\
    } while(0)

static void test_parse_number() {
    TEST_NUMBER(0.0, "0");
    TEST_NUMBER(0.0, "-0");
    TEST_NUMBER(0.0, "-0.0");
    TEST_NUMBER(1.0, "1");
    TEST_NUMBER(-1.0, "-1");
    TEST_NUMBER(1.5, "1.5");
    TEST_NUMBER(-1.5, "-1.5");
    TEST_NUMBER(3.1416, "3.1416");
    TEST_NUMBER(1E10, "1E10");
    TEST_NUMBER(1e10, "1e10");
    TEST_NUMBER(1E+10, "1E+10");
    TEST_NUMBER(1E-10, "1E-10");
    TEST_NUMBER(-1E10, "-1E10");
    TEST_NUMBER(-1e10, "-1e10");
    TEST_NUMBER(-1E+10, "-1E+10");
    TEST_NUMBER(-1E-10, "-1E-10");
    TEST_NUMBER(1.234E+10, "1.234E+10");
    TEST_NUMBER(1.234E-10, "1.234E-10");
    TEST_NUMBER(0.0, "1e-10000"); /* must underflow */
}

以上这些都是很基本的测试用例，也可供调试用。大部分情况下，测试案例不能穷举所有可能性。因此，除了加入一些典型的用例，我们也常会使用一些边界值，例如最大值等。

除了这些合法的 JSON，我们也要写一些不合语法的用例：

1
2
3
4
5
6
7
8
9
10
11
12
static void test_parse_invalid_value() {
    /* ... */
    /* invalid number */
    TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "+0");
    TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "+1");
    TEST_ERROR(LEPT_PARSE_INVALID_VALUE, ".123"); /* at least one digit before '.' */
    TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "1.");   /* at least one digit after '.' */
    TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "INF");
    TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "inf");
    TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "NAN");
    TEST_ERROR(LEPT_PARSE_INVALID_VALUE, "nan");
}

四、十进制转换至二进制

我们需要把十进制的数字转换成二进制的 double。这并不是容易的事情。为了简单起见，leptjson 使用标准库的 strtod() 来进行转换。strtod() 可转换 JSON 所要求的格式，但问题是，一些 JSON 不容许的格式，strtod() 也可转换，所以我们需要自行做格式校验。

函数 strtod() 用来将字符串转换成双精度浮点数(double)，其原型为：
double strtod (const char* str, char** endptr);

https://en.cppreference.com/w/c/string/byte/strtof

【参数说明】str 为要转换的字符串，endstr 为第一个不能转换的字符的指针。

【函数说明】strtod() 函数会扫描参数str字符串，跳过前面的空白字符（例如空格，tab缩进等，可以通过 isspace() 函数来检测），直到遇上数字或正负符号才开始做转换，到出现非数字或字符串结束时(‘\0’)才结束转换，并将结果返回。参数 str 字符串可包含正负号、小数点或E(e)来表示指数部分。如123. 456 或123e-2。

若endptr 不为NULL，则会将遇到的不符合条件而终止的字符指针由 endptr 传回；若 endptr 为 NULL，则表示该参数无效，或不使用该参数。

【返回值】返回转换后的浮点型数；若不能转换或字符串为空，则返回 0.0。

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdlib.h>  /* NULL, strtod() */

static int lept_parse_number(lept_context* c, lept_value* v) {
    char* end;
    /* TODO validate number */
    v->n = strtod(c->json, &end);
    if (c->json == end)
        return LEPT_PARSE_INVALID_VALUE;
    c->json = end;
    v->type = LEPT_NUMBER;
    return LEPT_PARSE_OK;
}

c->json == end说明json字符串开头就不符合double的语法，没有开始转换。

加入了 number 后，value 的语法变成：

1
value = null / false / true / number

记得在第一单元中，我们说可以用一个字符就能得知 value 是什么类型，有 11 个字符可判断 number：

  • 0-9/- ➔ number

但是，由于我们在 lept_parse_number() 内部将会校验输入是否正确的值，我们可以简单地把余下的情况都交给 lept_parse_number()：

1
2
3
4
5
6
7
8
9
static int lept_parse_value(lept_context* c, lept_value* v) {
    switch (*c->json) {
        case 't':  return lept_parse_true(c, v);
        case 'f':  return lept_parse_false(c, v);
        case 'n':  return lept_parse_null(c, v);
        default:   return lept_parse_number(c, v);
        case '\0': return LEPT_PARSE_EXPECT_VALUE;
    }
}

五、总结与练习答案

本单元讲述了 JSON 数字类型的语法，以及 leptjson 所采用的自行校验＋strtod()转换为 double 的方案。实际上一些 JSON 库会采用更复杂的方案，例如支持 64 位带符号／无符号整数，自行实现转换。解析／生成数字类型可以说是 RapidJSON 中最难实现的部分，也是 RapidJSON 高效性能的原因。

  1. 重构合并 lept_parse_null()、lept_parse_false()、lept_parse_true 为 lept_parse_literal()。

由于 true / false / null 的字符数量不一样，这个答案以 for 循环作比较，直至 '\0'。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static int lept_parse_literal(lept_context* c, lept_value* v, const char* literal, lept_type type) {
    size_t i;
    EXPECT(c, literal[0]);
    for (i = 0; literal[i + 1]; i++)
        if (c->json[i] != literal[i + 1])
            return LEPT_PARSE_INVALID_VALUE;
    c->json += i;
    v->type = type;
    return LEPT_PARSE_OK;
}

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);
        /* ... */
    }
}

注意在 C 语言中，数组长度、索引值最好使用 size_t 类型，而不是 int 或 unsigned。

你也可以直接传送长度参数 4、5、4，只要能通过测试就行了。

  1. 加入 维基百科双精度浮点数 的一些边界值至单元测试，如 min subnormal positive double、max double 等。

这问题其实涉及一些浮点数类型的细节，例如 IEEE-754 浮点数中，有所谓的 normal 和 subnormal 值，这里暂时不展开讨论了。

1
2
3
4
5
6
7
8
9
TEST_NUMBER(1.0000000000000002, "1.0000000000000002"); /* the smallest number > 1 */
TEST_NUMBER( 4.9406564584124654e-324, "4.9406564584124654e-324"); /* minimum positive denormal */
TEST_NUMBER(-4.9406564584124654e-324, "-4.9406564584124654e-324");
TEST_NUMBER( 2.2250738585072009e-308, "2.2250738585072009e-308");  /* Max subnormal double */
TEST_NUMBER(-2.2250738585072009e-308, "-2.2250738585072009e-308");
TEST_NUMBER( 2.2250738585072014e-308, "2.2250738585072014e-308");  /* Min normal positive double */
TEST_NUMBER(-2.2250738585072014e-308, "-2.2250738585072014e-308");
TEST_NUMBER( 1.7976931348623157e+308, "1.7976931348623157e+308");  /* Max double */
TEST_NUMBER(-1.7976931348623157e+308, "-1.7976931348623157e+308");

另外，这些加入的测试用例，正常的 strtod() 都能通过。所以不能做到测试失败、修改实现、测试成功的 TDD 步骤。

有一些 JSON 解析器不使用 strtod() 而自行转换，例如在校验的同时，记录负号、尾数（整数和小数）和指数，然后 naive 地计算：

1
2
3
4
5
6
int negative = 0;
int64_t mantissa = 0;
int exp = 0;

/* 解析... 并存储 negative, mantissa, exp */
v->n = (negative ? -mantissa : mantissa) * pow(10.0, exp);

这种做法会有精度问题。实现正确的答案是很复杂的，RapidJSON 的初期版本也是 naive 的，后来 RapidJSON 就内部实现了三种算法（使用 kParseFullPrecision 选项开启），最后一种算法用到了大整数（高精度计算）。有兴趣的同学也可以先尝试做一个 naive 版本，不使用 strtod()。之后可再参考 Google 的 double-conversion 开源项目及相关论文。

  1. *去掉 test_parse_invalid_value() 和 test_parse_root_not_singular 中的 #if 0 ... #endif，执行测试，证实测试失败。按 JSON number 的语法在 lept_parse_number() 校验，不符合标准的情况返回 LEPT_PARSE_INVALID_VALUE 错误码，即要排除掉那些strtod能够转换但在json中不合法的数字形式。

（提示：要校验 JSON 的数字语法。建议可使用以下两个宏去简化一下代码：

1
2
#define ISDIGIT(ch)         ((ch) >= '0' && (ch) <= '9')
#define ISDIGIT1TO9(ch)     ((ch) >= '1' && (ch) <= '9')

另一提示：在校验成功以后，我们不再使用 end 指针去检测 strtod() 的正确性，第二个参数可传入 NULL。）

首先，如同 lept_parse_whitespace()，我们使用一个指针 p 来表示当前的解析字符位置。这样做有两个好处，一是代码更简单，二是在某些编译器下性能更好（因为不能确定 c 会否被改变，从而每次更改 c->json 都要做一次间接访问）。如果校验成功，才把 p 赋值至 c->json。

1
2
3
4
5
6
7
8
9
10
11
static int lept_parse_number(lept_context* c, lept_value* v) {
    const char* p = c->json;
    /* 负号 ... */
    /* 整数 ... */
    /* 小数 ... */
    /* 指数 ... */
    v->n = strtod(c->json, NULL);
    v->type = LEPT_NUMBER;
    c->json = p;
    return LEPT_PARSE_OK;
}

我们把语法再看一遍：

1
2
3
4
number = [ "-" ] int [ frac ] [ exp ]
int = "0" / digit1-9 *digit
frac = "." 1*digit
exp = ("e" / "E") ["-" / "+"] 1*digit

负号最简单，有的话跳过便行：

1
if (*p == '-') p++;

整数部分有两种合法情况，一是单个 0，否则是一个 1-9 再加上任意数量的 digit。对于第一种情况，我们像负号般跳过便行。对于第二种情况，第一个字符必须为 1-9，如果否定的就是不合法的，可立即返回错误码。然后，有多少个 digit 就跳过多少个。

1
2
3
4
5
if (*p == '0') p++;
else {
    if (!ISDIGIT1TO9(*p)) return LEPT_PARSE_INVALID_VALUE;
    for (p++; ISDIGIT(*p); p++);
}

如果出现小数点，我们跳过该小数点，然后检查它至少应有一个 digit，不是 digit 就返回错误码。跳过首个 digit，我们再检查有没有 digit，有多少个跳过多少个。这里用了 for 循环技巧来做这件事。

1
2
3
4
5
if (*p == '.') {
    p++;
    if (!ISDIGIT(*p)) return LEPT_PARSE_INVALID_VALUE;
    for (p++; ISDIGIT(*p); p++);
}

最后，如果出现大小写 e，就表示有指数部分。跳过那个 e 之后，可以有一个正或负号，有的话就跳过。然后和小数的逻辑是一样的。

1
2
3
4
5
6
if (*p == 'e' || *p == 'E') {
    p++;
    if (*p == '+' || *p == '-') p++;
    if (!ISDIGIT(*p)) return LEPT_PARSE_INVALID_VALUE;
    for (p++; ISDIGIT(*p); p++);
}

这里用了 18 行代码去做这个校验。当中把一些 if 用一行来排版，而没用采用传统两行缩进风格，我个人认为在不影响阅读时可以这样弹性处理。当然那些 for 也可分拆成三行：

1
2
3
p++;
while (ISDIGIT(*p))
    p++;
  1. 去掉 test_parse_number_too_big 中的 #if 0 ... #endif，执行测试，证实测试失败。仔细阅读 strtod()，看看怎样从返回值得知数值是否过大，以返回 LEPT_PARSE_NUMBER_TOO_BIG 错误码。（提示：这里需要 #include 额外两个标准库头文件。）
1
2
3
4
5
6
7
8
9
10
#include <errno.h>   /* errno, ERANGE */
#include <math.h>    /* HUGE_VAL */

static int lept_parse_number(lept_context* c, lept_value* v) {
    /* ... */
    errno = 0;
    v->n = strtod(c->json, NULL);
    if (errno == ERANGE && v->n == HUGE_VAL) return LEPT_PARSE_NUMBER_TOO_BIG;
    /* ... */
}

许多时候课本／书籍也不会把每个标准库功能说得很仔细，我想藉此提醒同学要好好看参考文档，学会读文档编程就简单得多！cppreference.com 是 C/C++ 程序员的宝库。

strtod()：

“If the converted value falls out of range of corresponding return type, range error occurs and HUGE_VAL, HUGE_VALF or HUGE_VALL is returned. “

errno.h：

errno macro which expands to POSIX-compatible thread-local error number variable (macro variable)

ERANGE Result too large (macro constant)

math.h：

HUGE_VAL Expands to positive double expression that indicates overflow, not necessarily representable as a float

六、Q & A

  1. 为什么要把一些测试代码以 #if 0 ... #endif 禁用？

    因为在做第 1 个练习题时，我希望能 100% 通过测试，方便做重构。另外，使用 #if 0 ... #endif 而不使用 /* ... */，是因为 C 的注释不支持嵌套（nested），而 #if ... #endif 是支持嵌套的。代码中已有注释时，用 #if 0 ... #endif 去禁用代码是一个常用技巧，而且可以把 0 改为 1 去恢复。

  2. 科学计数法的指数部分没有对前导零作限制吗？1E012 也是合法的吗？

    是的，这是合法的。JSON 源自于 JavaScript（[ECMA-262, 3rd edition](https://www.ecma-international.org/publications/files/ECMA-ST-ARCH/ECMA-262, 3rd edition, December 1999.pdf)），数字语法取自 JavaScript 的十进位数字的语法（§7.8.3 Numeric Literals）。整数不容许前导零（leading zero），是因为更久的 JavaScript 版本容许以前导零来表示八进位数字，如 052 == 42，这种八进位常数表示方式来自于 C 语言。禁止前导零避免了可能出现的歧义。但是在指数里就不会出现这个问题。

留言

⬆︎TOP