cJSON源码分析-实现

好了好了,这篇文章拖了真久啊,活活三个月。不过之前承诺要经常更新博客的,所以先把这个烂尾的坑给填了。

之前提到了cJSON这个C语言写成的JSON解析库的接口,也就是头文件里的内容。这一次我们来分析一下实现。上车吧。

还是按照源代码的逻辑走。我们发现cJSON最开始有一个全局的字符指针ep,以及一个用以返回ep的函数。可以看出,这个ep是用来存储错误信息的。这种实现是C语言的常用手法,即把一些状态用static的方式隐藏在单个文件中,并实现一些函数当作接口。

static const char *ep;
const char *cJSON_GetErrorPtr(void) {return ep;}

下面是一个大小写无关的字符串比较函数。看后面的源码可以发现这个函数用在了JSON对象名的查找当中。实现没有什么特别的难点,所以就不提了。顺便说一句,在C++里要实现这个大小写无关比较,可以用STL里的一个方法叫做lexicographical_compare,搭配lambda表达式可以轻松达到目的。

作者把负责动态内存分配和释放的函数直接「填」成了标准库的malloc和free,像C++的allocator一样。如果担心内存碎片的问题,可以自己再当个二道贩子,实现一个内存池,不过那有点背离本文的主题了。作者自己实现了一个版本的strdup,里面也是用这个用户可以更换的cJSON_malloc进行内存分配的。

新建JSON和释放JSON的工作不难,前者就是内存分配的问题,后者就判断一下JSON的type,如果是基本类型就直接释放,如果是数组或者对象就递归删除(类似二叉树)。

目前好戏来了。第一个函数是解析数的。写过词法分析器的就懂,这个用自动机很容易描述,不过这里实在是没有什么好的能在电脑上绘制自动机图的工具,所以用列表表示这个过程,看看应该能体会。

  1. 开头有负号吗?有就记下来,向前走。
  2. 第一个数字是0吗?是就前进,反正默认的结果都是0.
  3. 这是小数点以前的部分,一位一位地循环解析就好了,到第一个非数字的字符为止。
  4. 有点并且点后面有数字吗?有就把小数部分也解析了加上去。
  5. 有E或者e吗?有就算10的幂次方。

简单吧?我们接着往下走。看到一个…奇怪的函数。

static int pow2gt (int x)
{
    --x;
    x|=x>>1;
    x|=x>>2;
    x|=x>>4;
    x|=x>>8;
    x|=x>>16;
    return x+1;
}

看见这个函数心里大概会想——什么鬼?名字看不懂,内容也看不懂。唔,不过看在它参数和返回值都是简单的int类型,不妨写个小程序测试一下结果。(限于篇幅省略结果)跑完之后我们猜测,这个函数的目的大概是返回一个不小于x的2的整数次幂。(对2的整数次幂还不敏感吗?)那我们来根据代码验证一下。

先略过这个减1的过程,看看位运算。我们假设整数的二进制形式从右向左,最后一个值为1的位是第n位,那么运算的过程是:

  1. 首轮,第n位右移1位,经过按位或运算,第n和n-1位(n右边那一位)确保为1.
  2. 第二轮,类似地,n和n-1都右移2位,所以n-3到n都是1.
  3. 第三轮,同样,此时n-7到n位都可以确保为1.
  4. 第四第五轮后,从1到n位都是1了。右移到16截止是因为这里的整数只有32位。

最后往这n位连续的1上再加个1,就是1后n个0,即2^n了。起来这个过程有点故弄玄虚的意思,因为我们也可以用循环的方式来解决。不过这里作者巧妙利用了整数位数的限制,用五次位运算达成了对任意整数都有效的效果。为什么要减1呢?因为不减1再加回去的话,对一个已经是2^n的数进行运算会得到2^(n+1),不符合我们的预期。实际上,这样的位运算技巧在《高效算法的奥秘》和《深入理解计算机系统》中都有相关的阐述。

这个函数有什么用呢?搜索一下就会发现。它只用在了一个地方,就是下面这个ensure函数。继续追踪可以发现,这个函数包括下面的update以及printbuffer这个结构体,都是用来存储缓冲区的。在缓冲区里面空间成2倍地扩大。不过我们的重点在字符串解析和内部的数据结构。

到这里,我们回过头来整理一下思路。JSON的类型有6种,而操作又都有解析和输出两种。

  • null和bool,由于bool只有两种固定的值,所以对于这两者,输出和解析都是简单的strcmp、strcpy就可以。
  • string,解析本身难度不是太大,去掉两端引号中间的就是字符串内容。但是有两个(或者说就是一个)问题,一是要注意反斜杠’\’开头的转义字符,二是字符串涉及到utf16到utf8的转换。输出的话不是什么太大问题。
  • number的解析前面已经说过了,浮点数输出要考虑一下精度,IEEE754标准和utf8都是坑。
  • array和object都是递归解析。如果要按格式输出,缩进是一个问题。

唔,好尴尬,写到这里突然不知道怎么继续了。在这里贴一下主要的解析函数parse_value的代码。

/* Parser core - when encountering text, process appropriately. */
static const char *parse_value(cJSON *item,const char *value)
{
   if (!value)         return 0;   /* Fail on null. */
   if (!strncmp(value,"null",4))   { item->type=cJSON_NULL;  return value+4; }
   if (!strncmp(value,"false",5))  { item->type=cJSON_False; return value+5; }
   if (!strncmp(value,"true",4))   { item->type=cJSON_True; item->valueint=1;    return value+4; }
   if (*value=='\"')               { return parse_string(item,value); }
   if (*value=='-' || (*value>='0' && *value<='9')){ return parse_number(item,value); }
   if (*value=='[')                { return parse_array(item,value); }
   if (*value=='{')                { return parse_object(item,value); }
   ep=value;return 0;  /* failure. */
}

跟我前面的分类一样,很清楚了。至于空格,这个函数在每次被调用之前都会先调用一次skip函数,用来跳过空白的:

/* Utility to jump whitespace and cr/lf */
static const char *skip(const char *in)
{
    while (in && *in && (unsigned char)*in<=32)
        in++;
    return in;
}

查看ASCII码表就可以知道32之前的基本都是不可见的控制字符或者空白,这里的条件判断真是简单粗暴。

parse_array的过程已经说得比较清楚了,就是不断地跳过空格、读取逗号、再跳过空格、读取一个新的对象的循环……直到遇到反方括号。前面那个指针ep的用途也明白了,就是指向读取失败的地方。parse_object类似,只是每次循环还要插入一个读名字的过程。

输出部分没有什么特别值得提的地方(其实是懒),要注意的就是输出array和object的时候需要控制一下缩进。总的来说,cJSON的代码逻辑就是这个样子。阅读这样「接地气」的代码,好处在于能够快速学到很多这门语言的最佳实践,但是繁杂的工程细节也会让人厌烦。好在大一些的项目往往在抽象上做得更好,方便我们抽丝剥茧,寻得新知。

cJSON源码分析-接口

最近因为各种忙碌,博客一直没有更新。下半学期的ACM/ICPC报名已经过去了,我没有参加,因为觉得自己对这种比赛没有什么特别的兴趣。其实话说回来,要和人「当面比」的事情,我很多都不喜欢。大概是因为从小到大的不自信导致的。这边Rails的项目快要写完了,收获不少,会找个时候专门用一篇博文记述。喜欢编程,所以就总是停不下来,想找点事情做。大家都说,提升编程能力要做项目。这话不假。但是编程就像写作文,初中生洋洋洒洒写个小说,很可能只会被成年人看作是幼稚文章。编程作为一门手艺,阅读他人的源码也是很重要的。感谢自由软件运动让我们有大量的源码可以用来学习,也感谢GitHub这样的平台能让我们更加方便地获取和发布源代码。所以最近可能会陆陆续续地更新一些程序的分析,也借这个过程提高一下自己细粒度层面的编程水平。希望不会烂尾。(flag已立!)

要分析呢,就从最熟悉的语言开始吧,也就是C咯。然后找一个简单的开源项目。好啦,中央已经决定了,就是cJSON了。同济2014级软件学院的C语言期末作业就是要求写一个cJSON解析器,后来我才发现那个提供的头文件就是cJSON里的……

软件的第一要义就是,它创造出来必须有用。那cJSON,顾名思义,就是一个程序,它能够:

  1. 将文本化的JSON转化为C语言可以操作的数据结构(解析)
  2. 将内存里的数据结构输出为格式化的JSON字符串(序列化)

具体JSON是什么格式,不用我再多说了吧。在JavaScript流行的今天,JSON由于其简单的语法和支持嵌套的特点,得到了广泛应用。许多框架的配置文件什么的,都是用的JSON格式。也有许多人试图用JSON逐渐取代XML语言。

我们先来看源码的文件结构:

  • cJSON.c
  • cJSON.h
  • test.c
  • README.md
  • LICENSE
  • CMakeLists.txt
  • Makefile
  • cJSON_Utils.h
  • cJSON_Utils.c
  • test_utils.c
  • test/

其中末尾带util的都是针对JSON做的一些扩展(RFC6901和RFC6902),我们先略去不谈。其实作为库,核心部分就两个文件,一个cJSON.h声明,一个cJSON.c实现。那么我们就先来看看头文件,cJSON到底提供了哪些接口。

/* cJSON Types: */
#define cJSON_False  (1 << 0)
#define cJSON_True   (1 << 1)
#define cJSON_NULL   (1 << 2)
#define cJSON_Number (1 << 3)
#define cJSON_String (1 << 4)
#define cJSON_Array  (1 << 5)
#define cJSON_Object (1 << 6)

#define cJSON_IsReference 256
#define cJSON_StringIsConst 512

/* The cJSON structure: */
typedef struct cJSON {
    struct cJSON *next,*prev;   /* next/prev allow you to walk array/object chains. Alternatively, use GetArraySize/GetArrayItem/GetObjectItem */
    struct cJSON *child;        /* An array or object item will have a child pointer pointing to a chain of the items in the array/object. */

    int type;                   /* The type of the item, as above. */

    char *valuestring;          /* The item's string, if type==cJSON_String */
    int valueint;               /* The item's number, if type==cJSON_Number */
    double valuedouble;         /* The item's number, if type==cJSON_Number */

    char *string;               /* The item's name string, if this item is the child of, or is in the list of subitems of an object. */
} cJSON;

typedef struct cJSON_Hooks {
      void *(*malloc_fn)(size_t sz);
      void (*free_fn)(void *ptr);
} cJSON_Hooks;

整个分成三个部分,一个是标记Type的宏,包括了cJSON结构体里type成员的所有取值。它在这里额外增加了IsReference和StringIsConst两个类型标记。我们注意到作者表示cJSON的类型不是用的正常的自然数的顺序排布,而是利用位移运算构成了等比数列。为什么要这样呢?因为这样的话一个类型就可以和IsReference和StringIsConst叠加了。这是C语言里的常用技巧。

再往下,我们可以看到作者定义了一个叫做cJSON_Hooks的结构,包含了malloc_fn和free_fn两个函数指针作为成员。很容易看出来这两个函数指针的原型也刚好对应malloc和free的函数原型。虽然还没有开始阅读源代码,不过我们自信地猜想,这个结构的作用类似于C++ STL中的allocator,负责标准分配之外的分配方式。话说我一开始写maolang的容器的时候也用过这个方法,但是后来觉得太累赘而放弃了。

再看下面的代码。

/* Supply malloc, realloc and free functions to cJSON */
extern void cJSON_InitHooks(cJSON_Hooks* hooks);

/* Supply a block of JSON, and this returns a cJSON object you can interrogate. Call cJSON_Delete when finished. */
extern cJSON *cJSON_Parse(const char *value);
/* Render a cJSON entity to text for transfer/storage. Free the char* when finished. */
extern char  *cJSON_Print(cJSON *item);
/* ... */

/* Returns the number of items in an array (or object). */
extern int    cJSON_GetArraySize(cJSON *array);
/* ... */
/* For analysing failed parses. This returns a pointer to the parse error. You'll probably need to look a few chars back to make sense of it. Defined when cJSON_Parse() returns 0. 0 when cJSON_Parse() succeeds. */
extern const char *cJSON_GetErrorPtr(void);

限于篇幅,把更多的函数声明省略了。函数声明前面加上extern关键字是可选的,仅仅是标注它是一个外部链接的函数而已。然后是一堆用以创建、删除、插入、修改JSON结构的函数,更详细的内容在头文件里。

/* Duplicate a cJSON item */
extern cJSON *cJSON_Duplicate(cJSON *item,int recurse);
/* Duplicate will create a new, identical cJSON item to the one you pass, in new memory that will
need to be released. With recurse!=0, it will duplicate any children connected to the item.
The item->next and ->prev pointers are always zero on return from Duplicate. */

复制的函数有一个额外参数,表示是否选择递归复制(深拷贝)。这里还有一些函数,我们分析实现的时候再说。在头文件的最后还有一个有趣的宏:

/* Macro for iterating over an array */
#define cJSON_ArrayForEach(pos, head) \
    for(pos = (head)->child; pos != NULL; pos = pos->next)

虽然仅仅是简陋的宏替换,不过还真是搞出了现代语言的感觉呢。

看完头文件之后,我们发现,cJSON这个简单的解析器,名堂却不小,提供了不少实用的接口。至于这些接口内部实现的细节,我们下一篇文章再来讨论啦。

构建Mao语言运行器-语法树

好了,前面我们说到了词法分析的过程。如果你按照我的思路进行的话,现在你已经可以把源代码转换成一个一个的词法单元,也就是所谓的token了。接下来要做的就是按照我们人为设定好的语法规则把这些词法单元组织起来。我们前面说过,Mao语言的语法结构极其简单,只有声明变量、表达式和print输出三个部分。而表达式所包含的内容也只包括加减乘除和括号。更关键的是它是保证输入的代码不会出错的。(当然你要满足程序对于健壮性的要求那就是另一回事了)

首先从变量的声明开始讨论起。Mao语言里只有int和double两种类型。所以我们可以一句一句地读取,直至分号结束。

struct token tkindex;
while (!istokenend(tkindex = gettoken())) {
    /* 你要记住这是伪代码,不要问我这个函数怎么来的 */
    if (tkindex.type == TOKEN_INT) {
        while (!istokenend(tkindex = gettoken())) {
            if (tkindex.type == TOKEN_VARIABLE) {
                /* 把这个名字和类型加到变量列表里 */
            } else if (tkindex.type == TOKEN_COMMA) {
                /* 如果是逗号,继续前进 */
                continue;
            } else if (tkindex.type == TOKEN_SEMICOLON) {
                /* 遇见分号,声明语句结束,循环停止 */
                break;
            }
        }
    } else if (tkindex.type == TOKEN_DOUBLE) {
        /* 跟上面一样玩 */
    } else if (/* 其他类型 */) {
        /* 其他的处理代码 */
    }
}

为什么可以写得这么简单?因为变量声明的时候保证没有带等号的初始化语句哦。

变量定义还是很简单的事情,重头戏在于表达式的求值。就算是后面的print语句,你不能保证它不会给你来个print(a+b)或者直接print(1*3/2),所以要先把表达式求值做好才能实现输出语句。(注:有同学指出需求文件里只说了print不会输出表达式,只会输出变量,这样就更容易咯)

如何给表达式求值呢?参考文档里给的暗示方法,是把中缀表达式转换为后缀表达式(逆波兰表示法),其中要用到所谓的调度场算法。然后利用栈来求解。这个方法不难,不过我们这里为了程序的可扩展性和方便理解,决定采用树的方式来实现。并且这里的树还是最简单的一种情况,即二叉树。如图:

语法树例子

所以,你以为我会这样老老实实写个结构:

struct expr_node {
    int type;
    char * var_name;
    union {
        int ival;
        double dval;
    };
    struct expr_node * left_child;
    struct expr_node * right_child;
};

哼哼,想错了。在这个话题上,为了说明问题,我们用不着那么麻烦。

我在软件工程学生如何学好C语言?这个问题的回答里面说过,理解数据结构不要过分机械地非要做一堆结构体和指针来模拟。计算机科学的核心是抽象。把握好抽象然后再来特化到适合特定场合的结构。所以呢,还是用数组吧。

什么?数组不是顺序存储的结构吗?naive,我们可以这样定义:

  • 数组的第一个元素,可以看作整个树的头
  • 对于任意第n个元素,它的左子节点是第2n个元素,右子节点是第2n+1个元素
  • 类似地,对于任意第n(不论奇偶)个元素,它的父节点编号是n/2

对于这棵树,我们可以稍微分析一下。这棵二叉树每一“层”包含的元素数量是2^n个。所以我们给这个等比数列求一个和,结果就是2^n – 1次方。也就是说对于一个10层的二叉树,我们需要1023个空间的数组。其实也不是很大,而且我们也不太可能出现一个需要10层的表达式数……好吧,如果你实在不放心,C99标准支持以变量初始化数组,自己先感受一下再开数组吧。

好了,数据结构准备好了,我们可以开始构建这个树了。讲道理说语法树有点言过其实,我们这里构建树的过程连什么LL(1)都用不到。我们来思考一下,假如我是一台计算机,我要怎么计算公式k * (a+c) + (j=3)呢?

你也许会说,我们从k开始,k右边的第一个符号就作为树根。但是加减乘除是有优先级的,最后算的应该是加号。注意,我们给这个表达式树求值是自上而下递归求值的,我们把下层计算好之后再把结果返回给上层来计算。所以我们应该以哪个符号开始呢?嗯,第一个优先级最低的符号。在这里,我们的最低优先级的符号是等号,其次是加减,最后是乘除。

等等,貌似有点不对。对于上面的那个等式,如果我们要搜到第一个优先级最低的符号也就是等号,那逻辑不对啊。嗯,因为上面我们没有考虑到括号。所以修正一下上面的规则——第一个括号之外的优先级最低的符号。你需要定义一个变量来记录当前是否外面还有括号。唔,是“第一个”吗?我想应该是最后一个吧,因为在你搜索到最后一个优先级最低的符号之前,是不知道当前位置上的符号是不是最后一个的。像a=1+1这种当然好判断,有等号就行了,可是比如a*21/b+11我怎么知道后面还有没有更低的呢?所以,应该改成——最后一个(括号之外的(优先级最低的(符号)))。(打括号是为了好断句)

好了好了,我们已经把“寻找树根”的任务搞定了。任务已经完成了一半了。什么,你不相信?我们构造这个树是递归的喂!我们只要找到树根,然后正确分划,这个树就搞定了。这就是递归的力量。So,我们再来讨论分划的问题。其实分划挺简单的,我们已经找到了那个“树根”的token,然后parse它左边的部分和右边的部分。

空话说得太多没用,我们来讨论下具体的实现。根据上文的思考,我们可以总结出从token流产生语法树的若干规则:

  • 如果整个串中只有一个token,是数或者变量,那么这个表达式树的值就是这个数或者变量的值
  • 否则,当前表达式树的值是左子树的值同右子树的值经过计算的结果,计算的方式由树根类型决定
  • 树根定义为当前token流中不在任何括号内的最后一个优先级最低的符号,左子树是从token流开始一直到树根的所有内容,右子树同理
  • 如果有括号,把括号内内容当作一个整体

由于叙述需要严谨性,所以听起来很复杂。其实整个的实现过程非常的清晰明了,我们来举个例子说明:

对于表达式foo = sample * (3 + 5)而言,我们的搜索过程是这样:

  1. 从左至右找到最后一个不在括号内的最低优先级符号“=”,将其作为树根。
  2. 树根左边的子token流里只有一个变量foo,所以左子树的值就是foo,停止。
  3. 树根右边最后一个不在任何括号内优先级最低的运算符是“*”,将其作为子树的树根。
  4. 子树树根的左边的token流也只有一个内容,就是sample变量,所以同样停止搜索。
  5. “*”右边的括号是一个整体,我们在括号内部搜索不在任何“括号”(打引号是因为这里的“不在”是指不在这个括号内部的另外的括号里)内的最低优先级运算符,找到了,是“+”。
  6. “+”左右都各是一个数,所以这两个子树停止搜索。

如果把这棵二叉树表达为一个数组,我们的数组结构是这样(编号表示下标,C语言的话要全部减1):

  1. 符号 =
  2. 变量 foo
  3. 符号 *
  4. (空)
  5. (空)
  6. 变量 sample
  7. 符号 +
  8. (空)
  9. (空)
  10. (空)
  11. (空)
  12. (空)
  13. (空)
  14. 数值 3
  15. 数值 5

之所以会有那么多空位是因为数或变量是没有子节点的,而数组的话必须要把它们的空间留足。好了,我们解决了理论上生成树的问题,如何用代码来实现呢?首先要面对的一个问题是,不管我们如何递归处理这个表达式,它始终都是一个整体,比如上面,当我们在创建符号“*”的左右子树的时候,为什么不会搜索到“=”那里去呢?所以我们需要两个变量,来标记我们可以搜索的token范围。如果你觉得我说的话很晦涩的话,那是因为我没说清楚。想想子字符串吧,一样的道理。

struct expr_node tmp_tree[128];
struct token stream[1000];
/* stream数组假设已经经过了词法分析阶段的输入 */
/* 为了说明问题,我才使用的全局变量 */
void create_tree(size_t tkstart, size_t tkend, size_t tree_root)
{
    if (tkstart == tkend) {
    /* 如果整个流只有一个内容 */
        if (stream[tkstart].type == TOKEN_INTNUM) {
            tmp_tree[tree_root].type = TOKEN_INTNUM;
            tmp_tree[tree_root].var_name = NULL;
            tmp_tree[tree_root].ival = atoi(stream[tkstart]);
            /* 结构体中的匿名联合体是C11标准支持的新语法,可以直接访问它的内部成员 */
            /* 这里我们假设在词法分析阶段对于数保存的是它们的字符串形式 */
        } else if (stream[tkstart].type == TOKEN_DOUBLENUM) {
            /* 同样处理double的情况 */
        } else if (stream[tkstart].type == TOKEN_VARIABLE) {
            /* 变量的情况也是类似,只不过需要保存它们的名字 */
        }
    }

    int parentheses = 0;
    size_t lowest_token = tkstart;
    /* 在没有出问题的情况下,第一个token不可能是运算符,所以可以专门规定非运算符的运算符优先级最高 */

    for (size_t i = tkstart; i &lt;= tkend; ++i) {
        if (is_operator(stream[i])) {
            if (priority(stream[i]) &lt; priority(stream[lowest_token] &&
                !parentheses) {
                /* is_operator和priority都是自己定义的宏 */
                lowest_token = i;
            }
        } else if (stream[i].type == TOKEN_LPAREN) {
            /* 左括弧,标记变量加一 */
            ++parentheses;
        } else if (stream[i].type == TOKEN_RPAREN) {
            --parentheses;
        }
    }

    create_tree(tkstart, lowest_token - 1, tree_root * 2);
    create_tree(lowest_token + 1, tkend, tree_root * 2 + 1);
}

这段构造树的代码原理清晰,但是其实它是有问题的:

  • 如果一个表达式整个被括号包住,那么它是无法处理的,因为自始至终变量parentheses不为0
  • Mao语言的文档里有写y=(c+6)*-(1+1)这样的表达式,而我们的程序无法处理两个符号连在一起的情况

解决第一个问题,可以用一个简单粗暴但是很脏的办法。所有带括号的表达式,最后都会递归到一个括号从前往后包住的形式。所以如果我们发现第一个token是左括号,我们识别一下是不是从头到尾都被包住了,如果是,就再去掉括号往下识别。

第二个问题,要解决需要我们在识别lowest_token的时候修改一下算法。所谓’+’和’-‘,如果前面有其他非括号的符号,那必然是正负号,否则是加减号。所以,如果发现加减的上一个有运算符,那就把正负号连上作为子树。然后,如果开头是加减号,那就自动补0.

计算的话,很简单的。用一个switch…case语句分开判断当前是什么符号,default表示是数或变量。类型转换的事情交给编译器就好,你要负责的只是判断这个变量应该是什么类型。什么,一个函数不能返回多种类型的值?那可以返回struct嘛,哈哈哈……

构建Mao语言运行器-词法分析

这个世界的本质是无序的。所以编程最广泛也是最常被讨论的用途就是处理在计算机看来什么意义也没有的字符串。而处理编程语言的源代码在其中是很特殊的一种,因为编程语言包含的信息按照一定的规则聚合,解析起来比自然语言容易得多。而处理编程语言的源代码的时候该干什么,取决于软件的目的以及这门语言本身的特性。

好了,言归正传,说说这次的期末作业Mao语言吧。一开始很多同学估计还没反应过来是怎么一回事。以为做一个解释器只要用宏替换就可以了。另外一些人估计连解释器编译器的区别都没有分清楚。讲道理的话,大一的期末项目不太可能要求学生做编译器的,那么多数据结构都没学,汇编也不懂,没法弄。

那么什么是解释器呢?

解释器是能够执行用其他计算机语言编写的程序的系统软件,它是一种翻译程序。 它的执行方式是一边翻译一边执行,因此其执行效率一般偏低,但是解释器的实现较为简单,而且编写源程序的高级语言可以使用更加灵活和富于表现力的语法。

懂了没?一边翻译一边执行。读入输入然后处理的作业在之前也做过不少,所以有人想到一个一个“单词”地做。关键是,我们处理这些源代码的基本单位是什么?先来看看范例里的一段代码。

int a;
double x, y;
int b, c, d;
a=5.5;
x=y=(1+a)*6.44;
a+4;
a=a/2;
print(a);
y=(c+6)*-(1+1);
print(y);
d=a/(2/5);
print(d);

这段代码基本上涵盖了Mao语言所有能用到的符号。仔细观察可以发现,关键字只有int和double,如果把print写死进去那就是三个。程序中可以出现任意的空格,因此我们需要把这些空格要么去掉要么屏蔽掉。变量名可以是一个字母也可以是很多个字母和数字的组合,当作一个char来弄显然也不行。我们需要一个专门的过程来将源代码里的“多个字符”映射到一个单位里。我们理想的结果应该是生成一个更有结构的数据流,其中一个符号(int、变量名或者是运算符)是一个单位,没有空格的存在。这样的话,很多东西就方便很多了。

这个扫描源代码生成结构化数据流的过程就叫做词法分析。大多数编译器或者解释器接收到源代码做的第一件事就是词法分析。词法分析生成的东西叫做token,记号还是符文还是什么,随便翻译。显然,我们要做词法分析,就要把整个源代码字符串遍历一遍,并且扫描完之后就可以把它丢掉了,之后的处理是针对这个数据流而不是纯文本进行的。在整个编译或者解释执行的过程中,对源代码或者它对应的信息我们需要过不止一趟 (pass)。多趟的处理也许对效率有影响,但是实现更加简单。所谓one-pass的编译器,很多时候只是作者的炫技之举。当然,对语法极其简单的Mao语言,这不是不能做,只是写得太杂乱就会失去很多乐趣。

好了,如何定义我们的数据结构呢?比如:

struct token {
    int type;
    char * content;
};

这是最简单的形式。content表示什么自不必说,可以指变量名或者整数浮点数。而更多的固定形式的符号,我们直接用type表示,然后把content设为NULL即可。

#define TOKEN_INT       1
#define TOKEN_DOUBLE    2
#define TOKEN_PRINT     3
#define TOKEN_VARIABLE  4
#define TOKEN_INTNUM    5
#define TOKEN_DOUBLENUM 6
#define TOKEN_COMMA     7
#define TOKEN_SEMICOLON 8
#define TOKEN_ADD       9
#define TOKEN_SUB       10
#define TOKEN_MUL       11
#define TOKEN_DIV       12
#define TOKEN_ASSIGN    13
#define TOKEN_LPAREN    14
#define TOKEN_RPAREN    15

整个Mao语言的符号不超过这区区十五种。规定好了token的结构和type的取值,我们就可以开始扫描的过程了。

开始这个扫描的过程应该不算是什么难事。我们从输入的第一个字符开始判断,就像《C程序设计语言》里常用的那样:

char ch;
while ((ch = getchar()) != EOF) {
    /*
     * 对输入字符的类型进行判断
     * 如果是一个字符,我们进入处理字母集合(类型、print或变量名)的函数
     * 如果是加减乘除等符号,我们进入处理运算符的函数
     * 如果是数字或者点号,我们进入处理整数或浮点数的函数
     */
}

那么对此,我们可以声明这样的一堆函数:

void type_var(char ch);
void number(char ch);
void symbol(char ch);

这些函数内部是如何运作的呢?举个例子:

void type_var(char ch)
{
    char tmp[20];
    size_t index = 0;
    do {
        tmp[index++] = ch;
    } while ((ch = getchar()) != EOF && isalnum(ch));
    tmp[index++] = '\0';
    if (!strcmp(tmp, "int")) {
        /* 将当前流指向的token设置为TOKEN_INT */
    } else if (!strcmp(tmp, "double") {
        /* 将当前流指向的token设置为TOKEN_DOUBLE */
    } else if (/* 其他情况 */) {
        /* 对应的处理 */
    } else {
        /* 不是关键字,那么定义成变量名,TOKEN_VARIABLE */
    }
    ungetc(ch, stdin); /* 退回一个字符输入 */
    /* 流指针向前进 */
}

显然,这个词法分析程序会自动获取能够最大接收的token,并且不需要手动写,自动就排除掉了空格,并且将每个变量名与逗号分隔了开来。

由于Mao语言的符号数量很少,并且各个类型的token规则特意设置得很简单(浮点数甚至不包含科学计数法的形式)。写一个tokenizer还是非常容易的。不过又一个还没有提到的东西,就是词法分析整数或者浮点数的时候,前面的正负号会被识别成加减号。当然这个问题无关紧要,讲道理的话在后面的语法分析阶段也能解决。不过就当作一个练习吧。

词法分析就到这,下次来说说语法树的事情。

用C写的一个简易JSON Parser

初来乍到的一学期实在是无聊,于是在百团大战中加了计算机协会,就认识了几个计算机和软件专业的人。看见一软件同学在空间上转发的C语言期末项目,顿时生了兴趣。代码是春节期间写完的,可惜这个博客被搁置了太久,现在把代码贴上来,也不算过分吧。

作业的具体内容是:老师给定一个头文件 json.h ,包含了 json 数据结构的定义以及一些相关函数的声明,任务就是实现这些函数,最后提交通过学校的自动化测试。我不是软件的学生,自然没有这个权利,不过手工检验了一下,貌似还没有太大问题。只是最近写一个 web 项目的时候,把其间一个比较“庞大”的 json 文件(也才4KB!)当作测试材料,结果程序直接崩溃了;再截取一小部分,又能运行了。难道是字符串读写复制操作太多?可貌似连 fopen 函数都调用失败了,搞不懂。

老师们给的头文件想必是由 cJSON 的头文件修改而来的,json结构体的定义如下:

typedef struct JSON {
    int type;   /* The type of the item, as above. */

    char *valuestring;  /* The item's string, if type==JSON_STRING */
    int valueint;   /* The item's number, if type==JSON_TRUE||JSON_FLASE;
                      or quantity of members, if type==JSON_ARRAY||JSON_OBJECT */
    double valuedouble; /* The item's number, if type==JSON_NUMBER */

    // the following are created by me
    struct JSON *head; /* Head of array, if type==JSON_ARRAY||JSON_OBJECT */
    struct JSON *last; /* Previous member, if this belongs to an array or object */
    struct JSON *next; /* Next member, if this belongs to an array or object */
    char *name; /* Name of member, if this belongs to an object */
} JSON;

函数众多就不一一列举了,有几个实现起来相对复杂的:

void PrintJSON(JSON *item);
JSON *Duplicate(JSON *item, int recurse);
JSON *ParseJSON(const char *value);```

如果有朋友对 json 不熟悉的话,简单介绍一下:

{
    "name": "ecnelises",
    "school": {
        "primary": "Chenjiawan",
        "junior": "qinghua",
        "senior": "yucai",
        "university": "tongji"
    },
    "randomvalue": [
        1.5,
        18,
        true,
        null
    ]
}

json 的类型有 object、array、string、number、boolean(true、false)、null. array 用方括号 [] 括起来,object是“键值对”(类似C++中的 map),用花括号 {} 括起来。json 是一种简化版的数据结构(相比于庞杂的 xml),在 javascript 和其他地方广泛使用。

第一个要介绍的函数是 Print,顾名思义就是根据既有的 json 打印出规整的内容。这个函数本身的定义很简单:

void PrintJSON(JSON *item)
{
    if (item == NULL){
        return;
    }

    switch (item -> type) {
        case JSON_FALSE:
            printf("false");
            break;
        case JSON_TRUE:
            printf("true");
            break;
        case JSON_NULL:
            printf("null");
            break;
        case JSON_NUMBER:
            printf("%lf", item -> valuedouble);
            break;
        case JSON_STRING:
            printf("\"%s\"", item -> valuestring);
            break;
        case JSON_ARRAY:
            PrintArray(1, item, 1);
            break;
        case JSON_OBJECT:
            PrintObject(1, item, 1);
            break;
        default:
            break;
    }
}

关键在于调用的另外两个函数:PrintArray 和 PrintObject. 引入这两个函数的原因是方便递归。

void PrintArray(int layers, JSON *array, int newline)
{
    if (newline) {
        for (int i = 1; i < layers; ++i) {
            printf("    ");
        }
        printf("[\n");
    }

    JSON *find = array -> head;
    for (int c = 1; c <= array -> valueint; ++c) {
        if (find -> type == JSON_OBJECT) {
            PrintObject(layers + 1, find, 1);
        } else if (find -> type == JSON_ARRAY) {
            PrintArray(layers + 1, find, 1);
        } else {
            for (int i = 1; i < layers + 1; ++i) {
                printf("    ");
            }
            PrintJSON(find);
        }
        if (c < array -> valueint) {
            printf(",");
        }
        printf("\n");
        find = find -> next;
    }

    for (int c = 1; c < layers; ++c) {
        printf("    ");
    }
    printf("]");

    if (layers == 1) {
        printf("\n");
    }
}

void PrintObject(int layers, JSON *object, int newline)
{
    if (newline) {
        for (int i = 1; i < layers; ++i) { // Each calling executes all in the same layer
            printf("    ");
        }
        printf("{\n");
    }

    JSON *find = object -> head;
    for (int c = 1; c <= object -> valueint; ++c) {
        for (int i = 1; i < layers + 1; ++i) {
            printf("    ");
        }
        printf("\"%s\": ", find -> name);

        if (find -> type == JSON_OBJECT) {
            printf("{\n");
            PrintObject(layers + 1, find, 0); // '{' doesn't make a new line
        } else if (find -> type == JSON_ARRAY) {
            printf("[\n");
            PrintArray(layers + 1, find, 0);
        } else {
            PrintJSON(find);
        }
        if (c < object -> valueint) {
            printf(",");
        }
        printf("\n");
        find = find -> next;
    }

    for (int i = 1; i < layers; ++i) {
        printf("    ");
    }

    printf("}");

    if (layers == 1) {
        printf("\n");
    }
}

参数 layers 决定了当前要打印的东西在第几“层”,也就是说前面要有多少层缩进。newline 是为了处理冒号后 { 或 [ 不换行的情况。

下面的函数 Duplicate 是负责复制 json 的,recurse 参数决定是否“深度”复制,我想大概是递归的意思吧。

JSON *Duplicate(JSON *item, int recurse)
{
    JSON *source = item;
    JSON *target = NULL;
    JSON *last = NULL;
    JSON *count;

    while (source != NULL) {
        switch (source -> type) {
            case JSON_TRUE:
                target = CreateTrue();
                break;
            case JSON_FALSE:
                target = CreateFalse();
                break;
            case JSON_NUMBER:
                target = CreateNumber(source -> valuedouble);
                break;
            case JSON_NULL:
                target = CreateNULL();
                break;
            case JSON_STRING:
                target -> valuestring = CopyString(source -> valuestring);
                break;
            case JSON_ARRAY:
                target = CreateArray();

                if (source -> head != NULL && recurse) {
                    target -> head = Duplicate(source -> head, 1);
                } else if (source -> head != NULL && !recurse) {
                    target -> head = source -> head;
                }

                count = target -> head;
                while (count != NULL) {
                    target -> valueint += 1;
                    count = count -> next;
                }
                break;
            case JSON_OBJECT:
                target = CreateObject();
                target -> name = CopyString(source -> name);

                if (source -> head != NULL && recurse) {
                    target -> head = Duplicate(source -> head, 1);
                } else if (source -> head != NULL && !recurse) {
                    target -> head = source -> head;
                }

                count = target -> head;
                while (count != NULL) {
                    target -> valueint += 1;
                    count = count -> next;
                }
                break;
            default:
                break;
        }

        source = source -> next;
        target -> last = last;
        if (last != NULL) {
            last -> next = target;
        } else {
            item = target; // Give the begining position to item
        }
        last = target;
        target = target -> next;
    }

    return item;
}

函数思路简单,但是算不上太好写……用“同步跟踪”的方式从当前 json 的子节点开始,最后再把头补上。

相对而言最复杂的要数 ParseJSON 函数了。基本想法就是先搜索配对的括号,然后递归处理括号里边的内容,直到没括号的时候就根据冒号和逗号分隔开各个字符串然后进行解析。由于源字符串可以不是规整的,所以还得跳过其间的空白。没有学过编译原理,所以程序也不带出错功能,错误的输入结果是未知的。

JSON *ParseJSON(const char *value)
{
    /* We read the whole string char by char,
       and create a new function parse_object.
       We make two tables to record emergency of {} and [].
     */
    int blank_state = 1; // 是否空白
    int flayerl = 1;
    int flayers = 1;
    int lallb = 0, sallb = 0; // 记录所有出现的括号
    int lbrackets = 0, sbrackets = 0; // 记录“第一层”的括号
    unsigned long vallen = strlen(value);
    int *lbracket_table = NULL;
    int *sbracket_table = malloc(sizeof(int) * sbrackets);

    for (int i = 0; i < vallen; ++i) {
        if (value[i] == '{' && flayerl) {
            flayerl = 0;
            ++lbrackets;
            ++lallb;
        } else if (value[i] == '{' && !flayerl) {
            ++lallb;
        } else if (value[i] == '}' && (lallb != lbrackets)) {
            --lallb;
        } else if (value[i] == '}' && (lallb == lbrackets)) {
            flayerl = 1;
            lbracket_table = (int*)realloc(lbracket_table, sizeof(int) * lbrackets);
            lbracket_table[lbrackets - 1] = i;
        } else if (value[i] == '[' && flayers) {
            flayers = 0;
            ++sbrackets;
            ++sallb;
        } else if (value[i] == '[' && !flayers) {
            ++sallb;
        } else if (value[i] == ']' && (sallb != sbrackets)) {
            --sallb;
        } else if (value[i] == ']' && (sallb == sbrackets)) {
            flayers = 1;
            sbracket_table = (int*)realloc(sbracket_table, sizeof(int) * sbrackets);
            sbracket_table[sbrackets - 1] = i;
        }
    }
    lbrackets = 0;
    sbrackets = 0;
    // 在这里,由于函数是递归调用的关系,两个表只存储“第一层”括号的内容

    JSON *res = malloc(sizeof(JSON));
    JSON *pre = res;
    JSON *find = res -> next;
    char *middle;

    for (int i = 0; i < vallen; ++i) {
        if (blank_state && isspace(value[i])) {
            continue;
        } else if (blank_state && !isspace(value[i])) {
            switch (value[i]) {
                case '{':
                    find = parse_object(middle = substr(value + i, '{', '}'));
                    free(middle);
                    i = lbracket_table[lbrackets++] + 1;
                    pre -> next = find;
                    find -> last = pre;
                    pre = pre -> next;
                    find = find -> next;
                    break;
                case '[':
                    find = parse_array(middle = substr(value + i, '[', ']'));
                    free(middle);
                    i = sbracket_table[sbrackets++] + 1;
                    pre -> next = find;
                    find -> last = pre;
                    pre = pre -> next;
                    find = find -> next;
                    break;
                case '\"':
                    find = parse_string(value + i);
                    pre -> next = find;
                    find -> last = pre;
                    pre = pre -> next;
                    find = find -> next;
                    i += next_mark(value + i + 1, '\"'); // 返回出现第二个参数对应字符的下一个位置
                    break;
                case 'f':
                case 't':
                case 'n': // 猜测是否为 false、true 或者 null,在函数里验证
                    find = parse_bool_null(value + i);
                    pre -> next = find;
                    find -> last = pre;
                    pre = pre -> next;
                    find = find -> next;
                    blank_state = 0;
                    break;
                case '+':
                case '-':
                default:
                    find = parse_number(value + i);
                    pre -> next = find;
                    find -> last = pre;
                    pre = pre -> next;
                    find = find -> next;
                    blank_state = 0;
                    break;
            }
        } else {
            switch (value[i]) {
                case ',':
                    blank_state = 1;
                    continue;
                    break;
                default:
                    continue;
                    break;
            }
        }
    }
    pre = res -> next;
    free(res);
    res = pre;
    res -> last = NULL;

    free(lbracket_table);
    free(sbracket_table);

    return res;
}

附上 parse_object 和 parse_array 的代码:

JSON *parse_object(const char *value)
{
    JSON *res = CreateObject();
    JSON *tmp;
    int blank_state = 1;
    char *left;
    char *right;

    for (int i = 0; i < strlen(value); ++i) {
        if (blank_state && isspace(value[i])) {
            continue;
        } else if (blank_state && !isspace(value[i])) {
            left = divstr(value + i); // 返回第一个在所有括号之外的 “:” 或者 “,” 的位置
            i += next_mark(value + i, ':') + 1;
            AddItemToObject(res, (tmp = parse_string(left)) -> valuestring, ParseJSON(right = divstr(value + i)));
            free(left);
            free(right);
            free(tmp);
            i += next_mark(value + i, ','); // when this loop end, i will be added by 1
            blank_state = 1; // so here we don't have 1 as an addition
        }
    }
    return res;
}

JSON *parse_array(const char *value)
{
    JSON *res = CreateArray();
    char *middle;
    int blank_state = 1;

    for (int i = 0; i < strlen(value); ++i) {
        if (blank_state && isspace(value[i])) {
            continue;
        } else if (blank_state && !isspace(value[i])) {
            AddItemToArray(res, ParseJSON(middle = divstr(value + i)));
            free(middle);
            i += next_mark(value + i, ',');
            blank_state = 1;
        }
    }
    return res;
}

虽然自己接触C语言有些久了,但是真正写出一个达千行的程序,这还是第一次。寒假在家里反复改反复调试,看来自己代码能力还是很不行。虽然在高手们看来可能这个程序还很拙劣,不过成功运行之后还是很有成就感的。加油吧。