土法炼钢兴趣小组的算法知识备份

手把手教你用 C++ 写一个简单的 JSON 解析器

#cpp #json #parser #state-machine #compiler

目录

引言

JSON (JavaScript Object Notation) 是现代互联网最通用的数据交换格式。虽然市面上有无数成熟的 JSON 库（如 RapidJSON, nlohmann/json），但自己动手写一个解析器是学习编译原理、状态机和C++ 字符串处理的绝佳练习。

本文将带你从零开始，用 C++ 实现一个简单的 JSON 解析器。我们将采用经典的 词法分析 (Lexer) + 语法分析 (Parser) 架构。

一、 JSON 语法简介

JSON 的结构非常简单，主要包含以下几种类型： - 对象 (Object): { "key": value, ... } - 数组 (Array): [ value1, value2, ... ] - 字符串 (String): "hello" - 数字 (Number): 123, -3.14, 1e5 - 布尔值 (Boolean): true, false - 空值 (Null): null

二、 架构设计

我们的解析器分为两步： 1. Tokenizer (Lexer): 将原始字符串分解成一个个 Token（标记）。 - 输入: {"a": 1} - 输出: L_BRACE, STRING("a"), COLON, NUMBER(1), R_BRACE 2. Parser: 根据 Token 序列构建数据结构（DOM 树）。

三、 数据结构定义

首先，我们需要一个类来表示 JSON 的值。

#include <string>
#include <vector>
#include <map>
#include <variant>
#include <iostream>

enum class JsonType { Null, Bool, Number, String, Array, Object };

struct JsonValue; // Forward declaration

using JsonList = std::vector<JsonValue>;
using JsonObject = std::map<std::string, JsonValue>;

struct JsonValue {
    JsonType type;
    // 使用 std::variant 存储多种可能的值 (C++17)
    std::variant<std::monostate, bool, double, std::string, JsonList, JsonObject> value;

    JsonValue() : type(JsonType::Null), value(std::monostate{}) {}
    JsonValue(bool b) : type(JsonType::Bool), value(b) {}
    JsonValue(double d) : type(JsonType::Number), value(d) {}
    JsonValue(std::string s) : type(JsonType::String), value(s) {}
    // ... 其他构造函数
};

四、 词法分析 (Tokenizer)

Tokenizer 的核心是一个状态机，或者更简单点，一个大循环加 switch-case。

enum class TokenType {
    L_BRACE, R_BRACE, // { }
    L_BRACKET, R_BRACKET, // [ ]
    COLON, COMMA, // : ,
    STRING, NUMBER,
    TRUE, FALSE, NULL_TOKEN,
    END
};

struct Token {
    TokenType type;
    std::string strValue;
    double numValue;
};

class Lexer {
    std::string_view src;
    size_t pos = 0;

public:
    Lexer(std::string_view s) : src(s) {}

    Token next() {
        skipWhitespace();
        if (pos >= src.size()) return {TokenType::END};

        char c = src[pos];
        switch (c) {
            case '{': pos++; return {TokenType::L_BRACE};
            case '}': pos++; return {TokenType::R_BRACE};
            case '[': pos++; return {TokenType::L_BRACKET};
            case ']': pos++; return {TokenType::R_BRACKET};
            case ':': pos++; return {TokenType::COLON};
            case ',': pos++; return {TokenType::COMMA};
            case '"': return parseString();
            default:
                if (isdigit(c) || c == '-') return parseNumber();
                if (isalpha(c)) return parseLiteral(); // true, false, null
                throw std::runtime_error("Unexpected character");
        }
    }
    
    // ... skipWhitespace, parseString, parseNumber 的实现
};

细节提示：parseString 需要处理转义字符（如 \n, \"），parseNumber 需要处理科学计数法。

五、 语法分析 (Parser)

我们使用递归下降 (Recursive Descent) 算法。这是一种非常直观的解析方法，每个非终结符对应一个函数。

class Parser {
    Lexer lexer;
    Token currentToken;

    void eat(TokenType type) {
        if (currentToken.type == type) {
            currentToken = lexer.next();
        } else {
            throw std::runtime_error("Unexpected token");
        }
    }

public:
    Parser(std::string_view src) : lexer(src) {
        currentToken = lexer.next();
    }

    JsonValue parse() {
        return parseValue();
    }

    JsonValue parseValue() {
        switch (currentToken.type) {
            case TokenType::L_BRACE: return parseObject();
            case TokenType::L_BRACKET: return parseArray();
            case TokenType::STRING: {
                std::string s = currentToken.strValue;
                eat(TokenType::STRING);
                return JsonValue(s);
            }
            // ... 处理 Number, True, False, Null
            default: throw std::runtime_error("Invalid value");
        }
    }

    JsonValue parseArray() {
        JsonList list;
        eat(TokenType::L_BRACKET);
        if (currentToken.type != TokenType::R_BRACKET) {
            while (true) {
                list.push_back(parseValue());
                if (currentToken.type == TokenType::COMMA) {
                    eat(TokenType::COMMA);
                } else {
                    break;
                }
            }
        }
        eat(TokenType::R_BRACKET);
        // 构造 JsonValue 返回...
    }

    JsonValue parseObject() {
        JsonObject obj;
        eat(TokenType::L_BRACE);
        if (currentToken.type != TokenType::R_BRACE) {
            while (true) {
                if (currentToken.type != TokenType::STRING) throw std::runtime_error("Key must be string");
                std::string key = currentToken.strValue;
                eat(TokenType::STRING);
                eat(TokenType::COLON);
                obj[key] = parseValue();
                
                if (currentToken.type == TokenType::COMMA) {
                    eat(TokenType::COMMA);
                } else {
                    break;
                }
            }
        }
        eat(TokenType::R_BRACE);
        // 构造 JsonValue 返回...
    }
};

六、 总结与扩展

通过不到 300 行代码，我们就可以实现一个基本的 JSON 解析器。 这个过程让我们学到了： 1. 状态机在词法分析中的应用。 2. 递归下降在处理嵌套结构（对象套对象）时的威力。 3. std::variant 在 C++ 中处理多态数据的便利性。

扩展思考： - 如何优化性能？（避免 std::string 拷贝，使用 string_view，内存池） - 如何处理更复杂的 Unicode 转义？ - 如何实现序列化（将 JsonValue 转回字符串）？

动手写一遍，比看十遍文档都要理解得深刻！

By .