返回文章列表

用 Rust 从零实现 JSON 解析器:递归下降没那么难

477 字·4 分钟阅读
Rust从零造轮子解析器

serde_json 用起来太方便了,方便到大多数人从没想过 JSON 是怎么被解析的。

但 JSON 是所有"手写解析器"里最适合入门的:语法规范只有一页,没有运算符优先级,没有类型推导。把 JSON 解析器写一遍,你就拿到了写任何解析器的入场券。

这篇分两部分:词法分析(tokenize)和语法分析(递归下降)。


先看 JSON 的语法

用 BNF 写出来就这么几行:

value   = object | array | string | number | "true" | "false" | "null"
object  = "{" (pair ("," pair)*)? "}"
pair    = string ":" value
array   = "[" (value ("," value)*)? "]"
string  = '"' char* '"'
number  = "-"? digit+ ("." digit+)? (("e"|"E") ("+"|"-")? digit+)?

规范就这么多。没有优先级,就没有歧义,递归下降可以直接照着语法抄。

AST 设计:用枚举表达"和"

解析结果用什么表示?JSON 的值有六种形态,天然对应一个枚举:

#[derive(Debug, Clone, PartialEq)]
pub enum JsonValue {
    Null,
    Bool(bool),
    Number(f64),
    String(String),
    Array(Vec<JsonValue>),
    Object(Vec<(String, JsonValue)>),
}

Object 这里用 Vec<(String, JsonValue)> 而不是 HashMap,有两个原因:

  1. 保持字段顺序是 JSON 的常见要求(很多接口靠字段顺序做 diff)
  2. 解析阶段不需要哈希,最后想转 HashMap 再说

编号也顺便统一了:JSON 只有一种数字(f64),不像 JS 要区分整数和浮点。

第一步:词法分析

词法分析的任务是把字符流切成 token。token 是解析器的最小单位。

#[derive(Debug, Clone, PartialEq)]
pub enum Token {
    LBrace,     // {
    RBrace,     // }
    LBracket,   // [
    RBracket,   // ]
    Colon,      // :
    Comma,      // ,
    String(String),
    Number(f64),
    True,
    False,
    Null,
    Eof,
}

词法分析器本质上是一个带着游标的循环:

pub struct Lexer<'a> {
    chars: std::iter::Peekable<std::str::Chars<'a>>,
    pos: usize,
}
 
impl<'a> Lexer<'a> {
    pub fn new(input: &'a str) -> Self {
        Self {
            chars: input.chars().peekable(),
            pos: 0,
        }
    }
 
    fn bump(&mut self) -> Option<char> {
        self.pos += 1;
        self.chars.next()
    }
 
    fn peek(&mut self) -> Option<&char> {
        self.chars.peek()
    }
}

用 Peekable 的原因是:很多判断要看下一个字符但不能消费它(比如 - 后面跟数字才是一个 number 的开头)。

跳过空白,然后分派:

    pub fn next_token(&mut self) -> Result<Token, ParseError> {
        self.skip_whitespace();
 
        let c = match self.bump() {
            Some(c) => c,
            None => return Ok(Token::Eof),
        };
 
        match c {
            '{' => Ok(Token::LBrace),
            '}' => Ok(Token::RBrace),
            '[' => Ok(Token::LBracket),
            ']' => Ok(Token::RBracket),
            ':' => Ok(Token::Colon),
            ',' => Ok(Token::Comma),
            '"' => self.read_string(),
            't' => self.read_literal("rue", Token::True),
            'f' => self.read_literal("alse", Token::False),
            'n' => self.read_literal("ull", Token::Null),
            c if c == '-' || c.is_ascii_digit() => self.read_number(c),
            c => Err(ParseError::unexpected_char(c, self.pos)),
        }
    }

读取字符串:转义是关键

JSON 字符串里可以出现转义序列,最常见的坑是 \uXXXX,以及代理对(surrogate pair)。

    fn read_string(&mut self) -> Result<Token, ParseError> {
        let mut s = String::new();
 
        loop {
            let c = self.bump().ok_or_else(|| ParseError::unterminated_string(self.pos))?;
            match c {
                '"' => return Ok(Token::String(s)),
                '\\' => {
                    let esc = self.bump().ok_or_else(|| ParseError::unterminated_string(self.pos))?;
                    match esc {
                        '"' => s.push('"'),
                        '\\' => s.push('\\'),
                        '/' => s.push('/'),
                        'b' => s.push('\u{0008}'),
                        'f' => s.push('\u{000C}'),
                        'n' => s.push('\n'),
                        'r' => s.push('\r'),
                        't' => s.push('\t'),
                        'u' => {
                            let cp = self.read_hex4()?;
                            // 处理 UTF-16 代理对
                            if (0xD800..=0xDBFF).contains(&cp) {
                                let hi = cp;
                                // 期待 \uDC00-\uDFFF
                                if self.bump() != Some('\\') || self.bump() != Some('u') {
                                    return Err(ParseError::invalid_surrogate(self.pos));
                                }
                                let lo = self.read_hex4()?;
                                let combined =
                                    0x10000 + ((hi - 0xD800) << 10) + (lo - 0xDC00);
                                s.push(char::from_u32(combined).ok_or_else(|| ParseError::invalid_surrogate(self.pos))?);
                            } else {
                                s.push(char::from_u32(cp).ok_or_else(|| ParseError::invalid_unicode(cp, self.pos))?);
                            }
                        }
                        c => return Err(ParseError::invalid_escape(c, self.pos)),
                    }
                }
                c => s.push(c),
            }
        }
    }

代理对这段代码值得单独说。JSON 里 \uD83D\uDE00 表示 😀,但这两个码点单独看都是无效的 Unicode 字符。必须把它们合成一个码点再转成 char,否则会解析失败。

字符串转义是最容易被"看起来能用"骗过去的部分。日常的 ASCII 数据测不出代理对的问题。

读取数字:先收集,再转换

数字不适合边读边算,因为要处理 -、.、e、+ 各种组合。最简单可靠的写法是先把字符收集成一个字符串,再交给 f64::from_str:

    fn read_number(&mut self, first: char) -> Result<Token, ParseError> {
        let mut buf = String::new();
        buf.push(first);
 
        while let Some(&c) = self.peek() {
            if c.is_ascii_digit() || c == '.' || c == 'e' || c == 'E' || c == '+' || c == '-' {
                buf.push(c);
                self.bump();
            } else {
                break;
            }
        }
 
        buf.parse::<f64>()
            .map(Token::Number)
            .map_err(|_| ParseError::invalid_number(buf, self.pos))
    }

不要手写浮点数解析。 正确的浮点解析需要处理精度、舍入、1e400 溢出为 inf 之类的边界。标准库的实现经过大量测试,用它是明智的。

第二步:递归下降解析

有了 token 流,解析就很直白了。每个语法规则对应一个函数。

pub struct Parser {
    tokens: Vec<Token>,
    pos: usize,
}
 
impl Parser {
    pub fn parse(input: &str) -> Result<JsonValue, ParseError> {
        let tokens = Lexer::new(input).tokenize_all()?;
        let mut p = Parser { tokens, pos: 0 };
        let value = p.parse_value()?;
        p.expect(Token::Eof)?; // 不允许尾部有多余内容
        Ok(value)
    }
 
    fn peek(&self) -> &Token {
        self.tokens.get(self.pos).unwrap_or(&Token::Eof)
    }
 
    fn advance(&mut self) -> Token {
        let t = self.peek().clone();
        self.pos += 1;
        t
    }
}

parse_value 是分派中心,照着语法第一行写:

    fn parse_value(&mut self) -> Result<JsonValue, ParseError> {
        match self.peek() {
            Token::LBrace => self.parse_object(),
            Token::LBracket => self.parse_array(),
            Token::String(_) => {
                let Token::String(s) = self.advance() else { unreachable!() };
                Ok(JsonValue::String(s))
            }
            Token::Number(n) => {
                let Token::Number(n) = self.advance() else { unreachable!() };
                Ok(JsonValue::Number(n))
            }
            Token::True => { self.advance(); Ok(JsonValue::Bool(true)) }
            Token::False => { self.advance(); Ok(JsonValue::Bool(false)) }
            Token::Null => { self.advance(); Ok(JsonValue::Null) }
            t => Err(ParseError::unexpected_token(t.clone(), self.pos)),
        }
    }

数组:

    fn parse_array(&mut self) -> Result<JsonValue, ParseError> {
        self.expect(Token::LBracket)?;
        let mut items = Vec::new();
 
        if matches!(self.peek(), Token::RBracket) {
            self.advance();
            return Ok(JsonValue::Array(items));
        }
 
        loop {
            items.push(self.parse_value()?);
            match self.advance() {
                Token::Comma => continue,
                Token::RBracket => break,
                t => return Err(ParseError::expected("',' or ']'", t, self.pos)),
            }
        }
        Ok(JsonValue::Array(items))
    }

空数组要单独处理:如果上来就是 ],直接返回,不能进循环去 parse_value。

对象同理:

    fn parse_object(&mut self) -> Result<JsonValue, ParseError> {
        self.expect(Token::LBrace)?;
        let mut pairs = Vec::new();
 
        if matches!(self.peek(), Token::RBrace) {
            self.advance();
            return Ok(JsonValue::Object(pairs));
        }
 
        loop {
            let key = match self.advance() {
                Token::String(s) => s,
                t => return Err(ParseError::expected("string key", t, self.pos)),
            };
            self.expect(Token::Colon)?;
            let value = self.parse_value()?;
            pairs.push((key, value));
 
            match self.advance() {
                Token::Comma => continue,
                Token::RBrace => break,
                t => return Err(ParseError::expected("',' or '}'", t, self.pos)),
            }
        }
        Ok(JsonValue::Object(pairs))
    }

错误定位:好解析器和能用的解析器的分水岭

一个只返回 "parse error" 的解析器,在生产里几乎没法排查。必须带上位置。

#[derive(Debug)]
pub struct ParseError {
    pub kind: ErrorKind,
    pub pos: usize,
    pub line: usize,
    pub column: usize,
}

要算出行列号,就需要原始输入。有两种做法:

  • 把输入一起存进 Lexer,出错时用它反查
  • 记录每个 token 的起始偏移

第二种更干净:

#[derive(Debug, Clone)]
pub struct SpannedToken {
    pub token: Token,
    pub offset: usize,
}

有了 offset,报错时截取上下文,给用户看箭头:

解析失败: 第 3 行第 12 列,期望 ',' 或 '}'
  {"name": "king" "age": 30}
                 ^

这个箭头能省下的排查时间,远超实现它的成本。

为什么"先分词再解析"更好

也可以完全不分词,直接在字符流上递归下降(很多小解析器这么干)。两种方式各有取舍:

维度 直接扫字符 先分词
代码量 少一点 多一层
错误定位 手动维护位置 token 自带 offset
回溯/预读 麻烦 容易(token 已缓存)
性能 更快(无中间分配) 多一次分配
可测试性 难单测 lexer 可独立测

我偏向先分词,主要因为可测试性:词法分析器可以脱离语法单独测,边界情况(转义、数字格式)都能覆盖。拆分之后,每一层的输入输出都很明确。

生产级解析器(比如 serde_json)会用零拷贝和 SIMD 把性能压到极致,但架构上依然是"分词 + 状态机"的思路。

性能上的两个关键点

真要追求性能,有两个杠杆最有效:

1. 减少字符串分配。 上面的 read_string 每个 key 都 String::new()。零拷贝的做法是返回 &str 切片(只在有转义时才分配):

pub enum Token<'a> {
    String(std::borrow::Cow<'a, str>),
    // ...
}

没有转义的字符串直接借用原输入,这是 serde_json 快的重要原因。

2. 不要 build 中间 token 数组。 上面 tokenize_all 把全部 token 存进 Vec,是 O(n) 额外空间。流式解析(每次 next_token 现算)能省掉这块。

解析器的性能优化,90% 都在"少分配"和"少复制"上,而不是在算法上。

结论

手写 JSON 解析器,核心就这几步:

词法分析切成 token(注意转义和代理对);递归下降照着 BNF 抄;错误必须带位置和上下文;性能优化优先减少字符串分配。

这套流程可以直接迁移到 YAML、TOML、SQL、配置文件——任何"有语法"的输入,都是同一套模板。 下一个轮子,我们就用它去造一个序列化框架。