用 Rust 从零实现 JSON 解析器:递归下降没那么难
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,有两个原因:
- 保持字段顺序是 JSON 的常见要求(很多接口靠字段顺序做 diff)
- 解析阶段不需要哈希,最后想转 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、配置文件——任何"有语法"的输入,都是同一套模板。 下一个轮子,我们就用它去造一个序列化框架。