Skip to content

Latest commit

 

History

History
166 lines (126 loc) · 6.99 KB

tutorial02_answer.md

File metadata and controls

166 lines (126 loc) · 6.99 KB

从零开始的 JSON 库教程(二):解析数字解答篇

  • Milo Yip
  • 2016/9/20

本文是《从零开始的 JSON 库教程》的第二个单元解答篇。解答代码位于 json-tutorial/tutorial02_answer

1. 重构合并

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

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 类型,而不是 intunsigned

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

2. 边界值测试

这问题其实涉及一些浮点数类型的细节,例如 IEEE-754 浮点数中,有所谓的 normal 和 subnormal 值,这里暂时不展开讨论了。以下是我加入的一些边界值,可能和同学的不完全一样。

TEST_NUMBER(1.0000000000000002, "1.0000000000000002"); /* the smallest number > 1 */
TEST_NUMBER( 4.9406564584124654e-324, "4.9406564584124654e-324"); /* minimum 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 地计算:

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 开源项目及相关论文。

3. 校验数字

这条题目是本单元的重点,考验同学是否能把语法手写为校验规则。我详细说明。

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

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;
}

我们把语法再看一遍:

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

负号最简单,有的话跳过便行:

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

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

    if (*p == '0') p++;
    else {
        if (!ISDIGIT1TO9(*p)) return LEPT_PARSE_INVALID_VALUE;
        for (p++; ISDIGIT(*p); p++);
    }

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

    if (*p == '.') {
        p++;
        if (!ISDIGIT(*p)) return LEPT_PARSE_INVALID_VALUE;
        for (p++; ISDIGIT(*p); p++);
    }

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

    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 也可分拆成三行:

        p++;
        while (ISDIGIT(*p))
            p++;

4. 数字过大的处理

最后这题纯粹是阅读理解题。

#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++ 程序员的宝库。

5. 总结

本单元的习题比上个单元较有挑战性一些,所以我花了多一些篇幅在解答篇。纯以语法来说,数字类型已经是 JSON 中最复杂的类型。如果同学能完成本单元的练习(特别是第 3 条),之后的字符串、数组和对象的语法一定难不到你。然而,接下来也会有一些新挑战,例如内存管理、数据结构、编码等,希望你能满载而归。

如果你遇到问题,有不理解的地方,或是有建议,都欢迎在评论或 issue 中提出,让所有人一起讨论。