一、递归下降解析：解析器的“灵魂”所在

说到JSON和XML解析，很多人第一反应是“调库”。但你想过没有，这些解析器底层到底是怎么工作的？

我个人习惯把解析器分成两类：一类是自动生成的（比如用yacc/bison），另一类是手写的递归下降解析器。今天咱们聊的是后者——递归下降解析。说白了，就是用递归函数来模拟语法规则，一个函数对应一条语法规则。

我在项目中遇到过不少解析场景，比如自定义配置文件、网络协议报文解析。每次我都优先考虑递归下降法。为什么？因为它直观、好调试、代码量还少。

1.1 什么是递归下降解析？

递归下降解析是一种自顶向下的解析方法。它从最顶层的语法规则开始，逐层向下匹配。每个非终结符（语法元素）对应一个解析函数，函数内部根据当前输入决定走哪条分支。

举个例子，JSON的顶层结构是：

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

对应的解析函数就是：

parse_value() {
    if (当前字符是 '{') 调用 parse_object()
    else if (当前字符是 '[') 调用 parse_array()
    else if (当前字符是 '"') 调用 parse_string()
    else if (当前字符是数字或负号) 调用 parse_number()
    else if (匹配 "true") 返回 true
    else if (匹配 "false") 返回 false
    else if (匹配 "null") 返回 null
    else 报错
}

你看，每个分支都对应一个子解析函数。这些子函数内部可能又会调用其他函数，形成递归调用链。

核心思想：语法规则 = 函数调用链。每条规则就是一个函数，规则之间的引用就是函数调用。

1.2 为什么JSON和XML适合递归下降？

JSON和XML都是嵌套结构的语言。JSON里有对象套对象、数组套对象；XML里有元素套元素。这种嵌套天然适合递归处理。

我举个例子你就明白了：

// JSON嵌套示例
{
    "name": "张三",
    "address": {
        "city": "北京",
        "district": {
            "name": "海淀区",
            "code": 100000
        }
    }
}

解析这个JSON时，parse_object() 遇到 "address" 字段的值又是一个对象，于是它再次调用 parse_object()。这就是递归——同一个函数处理不同层级的相同结构。

XML也是同理：

<person>
    <name>张三</name>
    <address>
        <city>北京</city>
        <district>
            <name>海淀区</name>
            <code>100000</code>
        </district>
    </address>
</person>

parse_element() 遇到子元素，就递归调用自己。结构清晰，代码也干净。

二、递归下降解析的核心组件

一个完整的递归下降解析器，通常包含三个部分：词法分析器（Lexer）、语法分析器（Parser）和抽象语法树（AST）。不过对于JSON/XML这种简单场景，我们经常把词法和语法合并在一起做。

2.1 词法分析器（Lexer）

词法分析器的任务是把原始字符串拆成一个个Token。Token是最小的语法单元，比如左花括号、字符串、数字等。

我习惯用结构体来表示Token：

typedef enum {
    TOKEN_OBJECT_BEGIN,   // {
    TOKEN_OBJECT_END,     // }
    TOKEN_ARRAY_BEGIN,    // [
    TOKEN_ARRAY_END,      // ]
    TOKEN_STRING,         // "xxx"
    TOKEN_NUMBER,         // 123
    TOKEN_TRUE,           // true
    TOKEN_FALSE,          // false
    TOKEN_NULL,           // null
    TOKEN_COLON,          // :
    TOKEN_COMMA,          // ,
    TOKEN_EOF             // 文件结束
} TokenType;

typedef struct {
    TokenType type;
    char*     value;   // 仅字符串和数字有值
    int       line;    // 行号，用于报错
} Token;

词法分析器逐个字符读取，遇到引号就读字符串，遇到数字就读数字，遇到花括号就返回对应Token。嗯，这里要注意：词法分析器不关心语法结构，它只负责切分。

2.2 语法分析器（Parser）

语法分析器是核心。它从词法分析器拿Token，然后根据语法规则构建AST。

每个语法规则对应一个函数，函数签名通常长这样：

ASTNode* parse_object(Parser* parser);
ASTNode* parse_array(Parser* parser);
ASTNode* parse_string(Parser* parser);
ASTNode* parse_number(Parser* parser);
ASTNode* parse_value(Parser* parser);

每个函数内部会调用 next_token() 获取下一个Token，然后根据Token类型决定下一步动作。如果遇到嵌套结构，就递归调用对应的解析函数。

小技巧：我习惯在Parser结构体里保存一个“当前Token”和“下一个Token”。这样遇到需要“预读”的情况（比如判断是对象还是数组），就不用回退Token流了。

2.3 抽象语法树（AST）

AST是解析的结果。它把JSON/XML的嵌套结构变成一棵树，方便后续遍历和操作。

JSON的AST节点类型：

typedef enum {
    NODE_OBJECT,
    NODE_ARRAY,
    NODE_STRING,
    NODE_NUMBER,
    NODE_TRUE,
    NODE_FALSE,
    NODE_NULL
} NodeType;

typedef struct ASTNode {
    NodeType type;
    union {
        struct { 
            char** keys; 
            struct ASTNode** values; 
            int count; 
        } object;
        struct { 
            struct ASTNode** elements; 
            int count; 
        } array;
        char* string_value;
        double number_value;
    } data;
} ASTNode;

XML的AST类似，只是多了标签名和属性：

typedef struct XMLNode {
    char* tag_name;
    struct XMLAttribute* attrs;
    int attr_count;
    struct XMLNode** children;
    int child_count;
    char* text_content;  // 文本内容
} XMLNode;

三、递归下降解析的完整流程

咱们用一张图来展示整个流程：

递归下降解析器工作流程 原始字符串 词法分析器 (Lexer) Token 流 语法分析器 (Parser) - 递归下降 抽象语法树 (AST) 递归调用

流程很清晰：原始字符串 → 词法分析 → Token流 → 语法分析 → AST。其中语法分析阶段就是递归下降的核心，它会根据Token流递归调用各个解析函数。

四、实战：手写一个简易JSON解析器

光说不练假把式。咱们写一个简易的JSON解析器，只解析对象和字符串，但足以展示递归下降的精髓。

4.1 词法分析器实现

Token next_token(Parser* parser) {
    skip_whitespace(parser);
    
    char c = peek_char(parser);
    
    switch (c) {
        case '{': consume_char(parser); return (Token){TOKEN_OBJECT_BEGIN, NULL, parser->line};
        case '}': consume_char(parser); return (Token){TOKEN_OBJECT_END, NULL, parser->line};
        case '"': return read_string(parser);
        case '\0': return (Token){TOKEN_EOF, NULL, parser->line};
        default: 
            // 错误处理
            fprintf(stderr, "第%d行: 非法字符 '%c'\n", parser->line, c);
            exit(1);
    }
}

这里有个细节：skip_whitespace() 跳过空格、换行、制表符。JSON标准要求解析器必须忽略这些空白字符。

4.2 语法分析器实现

ASTNode* parse_value(Parser* parser) {
    Token token = peek_token(parser);
    
    switch (token.type) {
        case TOKEN_OBJECT_BEGIN:
            return parse_object(parser);
        case TOKEN_STRING:
            return parse_string(parser);
        // 其他类型省略...
        default:
            fprintf(stderr, "第%d行: 期望一个值\n", token.line);
            exit(1);
    }
}

ASTNode* parse_object(Parser* parser) {
    // 消费 '{'
    consume_token(parser, TOKEN_OBJECT_BEGIN);
    
    ASTNode* obj = create_node(NODE_OBJECT);
    
    // 如果是 '}'，空对象
    if (peek_token(parser).type == TOKEN_OBJECT_END) {
        consume_token(parser, TOKEN_OBJECT_END);
        return obj;
    }
    
    // 解析键值对
    while (1) {
        // 键必须是字符串
        ASTNode* key = parse_string(parser);
        
        // 消费 ':'
        consume_token(parser, TOKEN_COLON);
        
        // 值可以是任意类型
        ASTNode* value = parse_value(parser);
        
        // 添加到对象
        add_pair_to_object(obj, key->data.string_value, value);
        
        // 如果是 '}'，结束
        if (peek_token(parser).type == TOKEN_OBJECT_END) {
            consume_token(parser, TOKEN_OBJECT_END);
            break;
        }
        
        // 否则消费 ','
        consume_token(parser, TOKEN_COMMA);
    }
    
    return obj;
}

你看，parse_object() 内部调用了 parse_string() 和 parse_value()。而 parse_value() 又可能调用 parse_object()。这就是递归下降——函数之间互相调用，形成递归链。

曾经踩过的坑：我曾经在解析嵌套对象时忘了处理空对象（{}）的情况。结果遇到空对象就直接报错了。后来加了个判断：如果下一个Token是 '}'，直接返回空对象。这种边界情况一定要考虑周全。

五、递归下降解析的优缺点

优点 缺点
代码直观，语法规则和代码结构一一对应 对左递归语法不友好，需要改写
容易调试，每个函数职责单一 递归深度受限于栈空间
可以精确控制错误位置和错误信息 性能不如表驱动的解析器
适合手写，不需要生成工具 语法规则复杂时代码量较大

对于JSON和XML这种上下文无关文法，递归下降解析是最实用的选择。它不需要复杂的生成工具，一个C文件就能搞定。

六、避坑指南

我总结了几条实战中容易踩的坑：

  • 递归深度问题：JSON嵌套太深（比如超过1000层）会导致栈溢出。我建议设置一个最大深度限制，超过就报错。
  • 错误恢复：解析出错时，尽量给出有意义的错误信息，比如“第42行: 期望 '}'，但遇到 ']'”。不要只说“解析失败”。
  • 内存管理：AST节点用完后要记得释放。我习惯用引用计数或者arena分配器来管理内存。
  • Unicode处理：JSON字符串支持\uXXXX转义。解析时要把这些转义序列转换成实际字符。

个人习惯：我写解析器时，会先写一个简单的版本（只支持基本类型），然后逐步扩展。这样每个阶段都能测试，不会出现最后联调时一堆bug的情况。

七、总结

递归下降解析说白了就是用函数模拟语法规则。每个语法元素对应一个函数，函数内部根据当前输入决定走哪条分支。遇到嵌套结构就递归调用。

JSON和XML的嵌套特性，让它们成为递归下降解析的天然应用场景。你只要把语法规则写清楚，代码自然就出来了。

嗯，如果你现在去翻翻一些开源JSON库的源码（比如cJSON、Jansson），你会发现它们的核心解析函数就是递归下降的。看懂了今天的内容，你就能轻松读懂这些库的源码了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →