写一个 JSON、XML 或 YAML 的 Parser 的思路是什么?

本人是做java开发的。依赖java大量现成的包或者框架,工作中甚至都遇不到要解析xml和json的情况。就算有业务需要定义业务相关的xml(比如自己写一个简单的flow引擎),也有大量的第三方包可以非常方便的处理xml。 我知道xml, json和yaml的parser实现都是按照他们的规范来的。 最近比较闲,就想自己实现一个yaml的parser。但是看完规范后,完全没有思路。 看过很多版本的源码,都感觉需要大量的代码才能实现。自己完全理不出流程。 …
关注者
1,071
被浏览
27,808
先占坑,说说JSON吧,因为自己写过。

前面的大神们提到了很多编译原理的东西,比如词法分析、EBNF乃至AST之类的名词。然而如果我们仅仅是要解析JSON这种数据结构的话,其实用不着那么多东西。要知道JSON的流行很大程度上就是因为它是一个轻量级的、简单易读的数据结构。说个无关的,要知道我第一次看编译原理的书,了解上下文无关文法这个概念的时候,很大程度上是靠了脑子里闪现出来的JSON官网 JSON 里描述的完整的JSON文法。
object = {}
       | { members }

members = pair
        | pair , members

pair = string : value

array = []
      | [ elements ]

elements = value 
         | value , elements

value = string
      | number
      | object
      | array
      | true
      | false
      | null

string = ""
       | " chars "

chars = char
      | char chars

char = any-Unicode-character-except-"-or-\-or- control-character
     | \"
     | \\
     | \/
     | \b
     | \f
     | \n
     | \r
     | \t
     | \u four-hex-digits

number = int
       | int frac
       | int exp
       | int frac exp

int = digit
    | digit1-9 digits 
    | - digit
    | - digit1-9 digits

frac = . digits

exp = e digits

digits = digit
       | digit digits

e = e
  | e+
  | e-
  | E
  | E+
  | E-
JSON的优势除了文法很简单之外,还有一个很重要的地方是,我们逐个字符地解析JSON,在不考虑错误处理的情况下,甚至都不需要前瞻!举个例子,在JSON解析的一开始,如果发现是字符'n',可以立马断定是null;是'{',就是对象。这给我们解析器的编写带来了很大的方便。

其实不管是JSON、XML还是YAML,其核心都是要描绘一种树状类型的结构。原因是生活中的大部分信息都是以这种形式保存的。有树,就会有结点。而不同的标记语言,这个结点里包含的东西也就不同。但是这种树状的结构是基本相同的。把源字符串转换成我们定义好的数据结构的过程,也就是所谓的解析。

那么解析的难点在哪里呢?如果一个JSON字符串里的内容仅仅是“true”四个字符,一次strcmp即可完成,你还觉得难吗?是任意数量的空格吗?貌似也不是。不知道题主初学编程时有没有写过那种“统计输入中空格的数量”的程序。如果有,其实排除空格的原理差不多。

而且请注意,我们写一个JSON解析器的目的是让杂乱的字符串变成C/Java/Python...等语言能够识别的数据结构。我们所做的工作仅仅是“保存”,没有“解释”,更不是“编译”。外加前面说的根本不需要前瞻一个字符的特性,我们编写JSON Parser其实连词法分析都不用。在这里,我们先定义好一个JSON数据结构的结点类型。
struct json_node {
    enum {
        NUMBER,
        STRING,
        ARRAY,
        OBJECT,
        TRUE,
        FALSE,
        NUL,
        UNKNOWN
    } type;
    char *name;
    union {
        double number;
        struct json_node *child_head;
        char *val_str;
    };
};
定义好了这个结构体,我们的工作其实就已经完成一半了。根据上面完整定义的文法,再来写解释基本类型的代码。
struct json_node *
parse_json(void)
{
    struct json_node *res = malloc(sizeof(struct json_node));
    char ch = getchar();
    switch (ch) {
    case 't':
        while (isalpha(ch)) {
            ch = getchar();
        }
        res->type = TRUE;
        break;
    /* 对于null和false也一样 */
    case '\"':
        res->type = STRING;
        /* 寻找到第一个不是转义字符的双引号 " */
        break;
    case '+':
    case '-':
    case '1':
    /* 1-9 */
        res->type = NUMBER;
        /* 缓冲区存储字符直到停止,然后用系统库函数转换 */
    default:
        res->type = UNKNOWN;
        break;
    }
    return res;
}
挺容易明白的。

那么为什么JSON解析对于一个之前从未写过的人来说会感觉很难呢?

因为它是递归的。

递归很强大,很直观,很简洁。但对于不懂递归的人来说,递归往往会使人手足无措。我解析一个true可以,但是我要是要解析未知层数的括号包着的内容呢?没关系,我们解析的函数也递归调用就行了。只要系统的输入流一直在向前走,这没关系。

解析object和array的过程类似,只不过我们把词法分析和语法分析弄到了一起,所以跳过空格的过程会比较麻烦:
struct json_node *
parse_json(void)
{
    /* 开头的声明 */
    switch (ch) {
    /* 数字和字符串等的解析 */
    case '{':
    {
        char *tmp_name = NULL;
        struct json_node *tmp_child = NULL;
        struct json_node *tmp_tail = NULL;
        res->type = OBJECT;
        res->child_head = NULL;
        while (ch != '}') {
            /* 跳过空格 */
            /* 向后解析字符串 */
            tmp_name = parse_string(ch);
            /* 跳过空格 */
            /* 冒号 */
            ch = getchar();
            current_child = parse_json();
            current_child->name = tmp_name;
            /* 跳过空格 */
            /* 逗号 */
            ch = getchar();
            /* 跳过空格 */
            if (res->child_head == NULL) {
                res->child_head = tmp_tail = tmp_child;
            } else {
                tmp_tail->next = tmp_child;
                tmp_tail = tmp_child;
            }
        }
        break;
    }
    case '[':
    {
        /*
         * 跟解析对象的过程类似
         * 只不过没有名字
         */
    }
    /* 未知情况 */
    }
    return res;
}