第60章实战

课程目录第60章实战

实战：JSON解析器（状态机+递归下降）

JSON解析，听起来是不是有点唬人？其实说白了，就是把一段像 {"name":"张三","age":18} 这样的文本，变成程序能理解的数据结构。我当年第一次写解析器时，也觉得这东西高深莫测，后来发现核心就两个东西：状态机和递归下降。今天咱们就把这层窗户纸捅破。

为什么需要两种技术？

你想想看，JSON的结构其实分两层：

词法层面：识别出花括号、冒号、引号、数字这些“单词”
语法层面：把这些单词组合成对象、数组、键值对

状态机擅长做第一件事——它像流水线上的分拣员，一个个字符读进来，判断当前该进哪个状态。递归下降则擅长第二件事——它像俄罗斯套娃，一个函数调用另一个函数，层层嵌套地解析复杂结构。

核心思路：先用状态机做词法分析（Tokenizer），再用递归下降做语法分析（Parser）。两阶段分离，代码清晰到爆。

第一步：状态机实现词法分析

我个人习惯把词法分析器写成一个迭代器，每次返回一个Token。Token就是最小的语义单元，比如左花括号、字符串、数字等。

enum class TokenType {
    LBRACE, RBRACE,      // { }
    LBRACKET, RBRACKET,  // [ ]
    COLON, COMMA,        // : ,
    STRING, NUMBER,      // 字符串和数字
    TRUE, FALSE, NULL,   // 字面量
    END                  // 结束
};

struct Token {
    TokenType type;
    std::string value;
};

class JsonTokenizer {
public:
    explicit JsonTokenizer(const std::string& input) 
        : input_(input), pos_(0) {}

    Token nextToken() {
        skipWhitespace();
        if (pos_ >= input_.size()) return {TokenType::END, ""};

        char c = input_[pos_];
        switch (c) {
            case '{': pos_++; return {TokenType::LBRACE, "{"};
            case '}': pos_++; return {TokenType::RBRACE, "}"};
            case '[': pos_++; return {TokenType::LBRACKET, "["};
            case ']': pos_++; return {TokenType::RBRACKET, "]"};
            case ':': pos_++; return {TokenType::COLON, ":"};
            case ',': pos_++; return {TokenType::COMMA, ","};
            case '"': return readString();
            case 't': return readLiteral("true", TokenType::TRUE);
            case 'f': return readLiteral("false", TokenType::FALSE);
            case 'n': return readLiteral("null", TokenType::NULL);
            default:
                if (isdigit(c) || c == '-') return readNumber();
                throw std::runtime_error("Unexpected character");
        }
    }

private:
    const std::string& input_;
    size_t pos_;

    void skipWhitespace() {
        while (pos_ < input_.size() && isspace(input_[pos_])) pos_++;
    }

    Token readString() {
        pos_++; // 跳过开头的引号
        std::string value;
        while (pos_ < input_.size() && input_[pos_] != '"') {
            if (input_[pos_] == '\\') {
                pos_++;
                switch (input_[pos_]) {
                    case '"': value += '"'; break;
                    case '\\': value += '\\'; break;
                    case 'n': value += '\n'; break;
                    case 't': value += '\t'; break;
                    default: throw std::runtime_error("Invalid escape");
                }
            } else {
                value += input_[pos_];
            }
            pos_++;
        }
        if (pos_ >= input_.size()) throw std::runtime_error("Unterminated string");
        pos_++; // 跳过结尾的引号
        return {TokenType::STRING, value};
    }

    Token readNumber() {
        size_t start = pos_;
        if (input_[pos_] == '-') pos_++;
        while (pos_ < input_.size() && isdigit(input_[pos_])) pos_++;
        if (pos_ < input_.size() && input_[pos_] == '.') {
            pos_++;
            while (pos_ < input_.size() && isdigit(input_[pos_])) pos_++;
        }
        return {TokenType::NUMBER, input_.substr(start, pos_ - start)};
    }

    Token readLiteral(const std::string& expected, TokenType type) {
        if (input_.substr(pos_, expected.size()) != expected) {
            throw std::runtime_error("Invalid literal");
        }
        pos_ += expected.size();
        return {type, expected};
    }
};

避坑指南：我曾经在解析字符串时忘了处理转义字符，结果线上服务收到一个带反斜杠的JSON直接崩溃。记住，\"、\\、\n 这些都得老老实实处理。

第二步：递归下降实现语法分析

有了Token流，解析就变成了“看下一个Token是什么，然后决定怎么走”。递归下降的核心就是：每个语法规则对应一个函数，函数里可以调用其他函数。

class JsonParser {
public:
    explicit JsonParser(JsonTokenizer& tokenizer) 
        : tokenizer_(tokenizer), current_(tokenizer.nextToken()) {}

    JsonValue parse() {
        return parseValue();
    }

private:
    JsonTokenizer& tokenizer_;
    Token current_;

    void consume(TokenType expected) {
        if (current_.type != expected) {
            throw std::runtime_error("Unexpected token");
        }
        current_ = tokenizer_.nextToken();
    }

    JsonValue parseValue() {
        switch (current_.type) {
            case TokenType::LBRACE:  return parseObject();
            case TokenType::LBRACKET: return parseArray();
            case TokenType::STRING: {
                std::string val = current_.value;
                consume(TokenType::STRING);
                return JsonValue(val);
            }
            case TokenType::NUMBER: {
                double val = std::stod(current_.value);
                consume(TokenType::NUMBER);
                return JsonValue(val);
            }
            case TokenType::TRUE:
                consume(TokenType::TRUE);
                return JsonValue(true);
            case TokenType::FALSE:
                consume(TokenType::FALSE);
                return JsonValue(false);
            case TokenType::NULL:
                consume(TokenType::NULL);
                return JsonValue(nullptr);
            default:
                throw std::runtime_error("Invalid value");
        }
    }

    JsonValue parseObject() {
        consume(TokenType::LBRACE);
        std::map<std::string, JsonValue> members;
        if (current_.type != TokenType::RBRACE) {
            do {
                if (current_.type != TokenType::STRING) {
                    throw std::runtime_error("Expected string key");
                }
                std::string key = current_.value;
                consume(TokenType::STRING);
                consume(TokenType::COLON);
                members[key] = parseValue();
            } while (current_.type == TokenType::COMMA && (consume(TokenType::COMMA), true));
        }
        consume(TokenType::RBRACE);
        return JsonValue(members);
    }

    JsonValue parseArray() {
        consume(TokenType::LBRACKET);
        std::vector<JsonValue> elements;
        if (current_.type != TokenType::RBRACKET) {
            do {
                elements.push_back(parseValue());
            } while (current_.type == TokenType::COMMA && (consume(TokenType::COMMA), true));
        }
        consume(TokenType::RBRACKET);
        return JsonValue(elements);
    }
};

注意：递归下降解析器对递归深度有限制。如果JSON嵌套超过1000层，可能会栈溢出。我在项目中遇到过这种情况——一个配置文件的数组嵌套了2000层，直接导致程序崩溃。解决方案是改用迭代式解析，或者增大栈空间。

整体架构图

下面这张图展示了整个解析器的数据流。我建议你把它打印出来贴在工位上，写代码时对照着看。

JsonValue的设计

解析出来的结果需要一种统一的数据结构来承载。我推荐用 std::variant，C++17之后这东西太好用了。

class JsonValue {
public:
    using Object = std::map<std::string, JsonValue>;
    using Array = std::vector<JsonValue>;

    // 各种构造函数
    JsonValue() : data_(nullptr) {}
    JsonValue(std::nullptr_t) : data_(nullptr) {}
    JsonValue(bool b) : data_(b) {}
    JsonValue(double n) : data_(n) {}
    JsonValue(const std::string& s) : data_(s) {}
    JsonValue(const char* s) : data_(std::string(s)) {}
    JsonValue(const Object& obj) : data_(obj) {}
    JsonValue(const Array& arr) : data_(arr) {}

    // 类型判断
    bool isNull() const { return std::holds_alternative<std::nullptr_t>(data_); }
    bool isBool() const { return std::holds_alternative<bool>(data_); }
    bool isNumber() const { return std::holds_alternative<double>(data_); }
    bool isString() const { return std::holds_alternative<std::string>(data_); }
    bool isObject() const { return std::holds_alternative<Object>(data_); }
    bool isArray() const { return std::holds_alternative<Array>(data_); }

    // 取值方法（带安全检查）
    double asNumber() const {
        if (!isNumber()) throw std::runtime_error("Not a number");
        return std::get<double>(data_);
    }
    std::string asString() const {
        if (!isString()) throw std::runtime_error("Not a string");
        return std::get<std::string>(data_);
    }
    const Object& asObject() const {
        if (!isObject()) throw std::runtime_error("Not an object");
        return std::get<Object>(data_);
    }
    const Array& asArray() const {
        if (!isArray()) throw std::runtime_error("Not an array");
        return std::get<Array>(data_);
    }

private:
    std::variant<std::nullptr_t, bool, double, std::string, Object, Array> data_;
};

小技巧：用 std::variant 比用 union 安全得多。我以前用union写过一个JSON库，结果因为忘记调用析构函数导致内存泄漏，排查了两天才找到问题。variant自动管理生命周期，省心不少。

完整使用示例

int main() {
    std::string json = R"({
        "name": "张三",
        "age": 28,
        "skills": ["C++", "Python", "Rust"],
        "address": {
            "city": "北京",
            "zip": "100000"
        },
        "active": true,
        "salary": null
    })";

    try {
        JsonTokenizer tokenizer(json);
        JsonParser parser(tokenizer);
        JsonValue result = parser.parse();

        // 访问数据
        auto& obj = result.asObject();
        std::cout << "姓名: " << obj.at("name").asString() << std::endl;
        std::cout << "年龄: " << obj.at("age").asNumber() << std::endl;

        auto& skills = obj.at("skills").asArray();
        std::cout << "技能: ";
        for (const auto& skill : skills) {
            std::cout << skill.asString() << " ";
        }
        std::cout << std::endl;

    } catch (const std::exception& e) {
        std::cerr << "解析失败: " << e.what() << std::endl;
    }

    return 0;
}

性能对比

解析方式	代码量	可读性	性能	适用场景
状态机 + 递归下降	中等（约300行）	高	良好	通用JSON解析
纯状态机	大（约500行）	低	优秀	嵌入式/高性能场景
第三方库（nlohmann/json）	极小	极高	优秀	生产环境首选

我的建议：如果是学习目的，自己手写一遍状态机和递归下降，绝对能让你对编译原理的理解上一个台阶。如果是生产环境，直接用 nlohmann/json 或者 rapidjson，别重复造轮子。我自己在项目里就吃过这个亏——花了一周写的解析器，性能还不如人家成熟库的一半。

嗯，到这里JSON解析器的核心内容就讲完了。你可能会问：为什么不用正则表达式？正则处理简单JSON还行，一旦遇到嵌套结构就抓瞎了。状态机+递归下降的组合，才是处理结构化文本的正道。

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

📚 课程目录

实战：JSON解析器（状态机+递归下降）

为什么需要两种技术？

第一步：状态机实现词法分析

第二步：递归下降实现语法分析

整体架构图

JsonValue的设计

完整使用示例

性能对比