从零开始的 JSON 库教程（二）：解析数字解答篇

  • Milo Yip
  • 2016/9/20

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

1. 重构合并

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

  1. static int lept_parse_literal(lept_context* c, lept_value* v, const char* literal, lept_type type) {
  2.     size_t i;
  3.     EXPECT(c, literal[0]);
  4.     for (i = 0; literal[i + 1]; i++)
  5.         if (c->json[i] != literal[i + 1])
  6.             return LEPT_PARSE_INVALID_VALUE;
  7.     c->json += i;
  8.     v->type = type;
  9.     return LEPT_PARSE_OK;
  10. }
  12. static int lept_parse_value(lept_context* c, lept_value* v) {
  13.     switch (*c->json) {
  14.         case 't':  return lept_parse_literal(c, v, "true", LEPT_TRUE);
  15.         case 'f':  return lept_parse_literal(c, v, "false", LEPT_FALSE);
  16.         case 'n':  return lept_parse_literal(c, v, "null", LEPT_NULL);
  17.         /* ... */
  18.     }
  19. }

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

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

2. 边界值测试

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

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

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

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

  1. int negative = 0;
  2. int64_t mantissa = 0;
  3. int exp = 0;
  5. /* 解析... 并存储 negative, mantissa, exp */
  6. 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。

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

我们把语法再看一遍：

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

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

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

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

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

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

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

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

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

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

  1.         p++;
  2.         while (ISDIGIT(*p))
  3.             p++;

4. 数字过大的处理

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

  1. #include <errno.h>   /* errno, ERANGE */
  2. #include <math.h>    /* HUGE_VAL */
  4. static int lept_parse_number(lept_context* c, lept_value* v) {
  5.     /* ... */
  6.     errno = 0;
  7.     v->n = strtod(c->json, NULL);
  8.     if (errno == ERANGE && v->n == HUGE_VAL) return LEPT_PARSE_NUMBER_TOO_BIG;
  9.     /* ... */
  10. }

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

5. 总结

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

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