[博客翻译]用500行Rust解析JSON


原文地址:https://www.krish.gg/blog/json-parser-in-rust


用500行Rust代码解析JSON

背景

上学期在大学,我参加了一门叫“基于语法的工具与编译器”的课程。这门课主要学习为一种名为PL0的语言构建扫描器、解析器和编译器等内容。我们在课上使用了Python,但那时我对学习Rust非常感兴趣。

因此,我决定启动一个课外项目(没错,又一个!)。这次,我想尝试用Rust构建一个JSON解析器。我的目标是检验课程中学到的技能,并终于着手完成我一直拖延了三年的Rust项目。


计划

我发现学习编程的最佳方法就是直接动手实践。所以我打算按照这个思路来行动。我找到了JSON规范并开始阅读。这个规范中有许多清晰的图表,能够帮助我们理解JSON文档的结构。

构建“解析器”有多种方式,我可以进行验证、扫描、标记化,然后再最终解析JSON。但我希望保持简单,所以跳过了这些步骤,专注于从原始文本文件/字符串中解析JSON,并将其表示为一个Rust枚举类型,以反映JSON的结构。

还有一种工具可以根据语法规则自动生成自顶向下或自底向上的解析器,但我的实现是一种手写解析器。这种方法更加灵活,不严格受限于规则或实现细节,使我能够轻松修改代码。


实现

如何在Rust中表示JSON?

为了存储解析后的JSON,我需要一种方法来在Rust中表示数据。我首先创建了一个通用的枚举JSONValue,用于表示JSON文档的“树”结构。每个“节点”可以是多种类型之一:字符串、数字、对象、数组、布尔值或空值(null)。根节点是一个JSON对象。

最终,我设计了如下枚举:

#[derive(Debug, Clone, PartialEq)]
enum JSONValue {
  Null,
  True,
  False,
  Number(f64),
  String(String),
  Array(Vec<JSONValue>),
  Object(HashMap<String, JSONValue>),
}

错误处理怎么办?

需要注意的是,解析是一个可能会失败的过程——源文本可能存在语法错误,解析器应能够妥善处理这些问题。因此,我决定让解析器返回一个Result类型。如果解析成功,则返回解析后的JSON值;否则返回错误。

以下是用于表示解析过程中可能发生的不同错误类型的枚举:

enum JSONParseError {
  Error(usize),
  NotFound,
  UnexpectedChar(usize),
  MissingClosing(usize),
}

注意,某些错误带有usize值,表示发生错误时输入字符串剩余的长度。这有助于确定输入字符串被消耗了多少,从而打印更好的错误消息。NotFound错误更多是内部错误,用于指示解析器未能在输入字符串中找到预期元素。


JSON中的“值”

根据JSON规范,一切皆始于一个元素——它是由空白符包围的值。该值可以是以下类型之一:

  • 对象
  • 数组
  • 字符串
  • 数字
  • "true"
  • "false"
  • "null"

简单值

我希望从最简单的值开始,然后逐步扩展到更复杂的类型。所以,我先从null值开始。以下是处理null值的一个简单函数:

fn null(src: &str) -> Result<(&str, JSONValue), JSONParseError> {
  match src.strip_prefix("null") {
    Some(rest) => Ok((rest, JSONValue::Null)),
    None => Err(JSONParseError::NotFound),
  }
}

这段代码只是检查输入字符串是否以"null"开头。如果是,则返回剩余字符串和JSONValue::Null;否则返回错误,表明未找到预期值。

类似地,我也对truefalse值采取了相同的方法,只需将"null"替换为"true"或"false"。

字符串

乍一看,解析JSON中的字符串似乎很简单——只需要找到开始和结束引号之间的内容即可。但实际上并非如此。字符串可能包含转义序列,例如\"\\\n等,因此需要仔细处理以正确解析字符串。

下面是部分字符串解析代码:

fn string(mut src: &str) -> Result<(&str, JSONValue), JSONParseError> {
  // 确保以引号开头
  match src.strip_prefix("\"") {
    Some(rest) => src = rest,
    None => return Err(JSONParseError::NotFound),
  };
  let mut result: String = "".to_string();
  let mut escaping = false; // 标志位
  let mut chars = src.chars(); // 迭代器
  loop {
    let c = match chars.next() {
      Some(c) => c,
      None => return Err(JSONParseError::MissingClosing(src.len())),
    };
    if c == '\\' && !escaping {
      escaping = true;
    } else if c == '"' && !escaping {
      break;
    } else if escaping {
      match c {
        '"' => result.push('"'),
        ... // 其他转义序列
        _ => {
          return Err(JSONParseError::UnexpectedChar(chars.count()));
        }
      }
      escaping = false;
    } else {
      result.push(c);
    }
  }
  Ok((chars.as_str(), JSONValue::String(result)))
}

这段代码首先查找起始引号,然后逐字符读取,直到遇到结束引号为止。若遇到反斜杠(\),说明接下来的字符是转义字符,需要特殊处理。

数字

在普通编程语言中,我们通常使用多种数据类型来表示数字,如不同大小的整数、浮点数等。而在JSON中,只有一种数字类型——任意值,可以是整数、浮点数或科学计数法表示的数字。

在我的解析器中,每个数字都被表示为f64(浮点数)。这是在Rust中表示数字的一种简单方法,但它不支持JSON允许的完全任意精度。这是我的解析器的一个限制,但目前我愿意接受。

以下是数字解析的核心逻辑:

fn number(mut src: &str) -> Result<(&str, JSONValue), JSONParseError> {
  let mut result;
  let negative;
  match integer(src) {
    Ok((rest, num)) => {
      result = num.abs() as f64;
      negative = num.is_negative();
      src = rest;
    }
    Err(e) => return Err(e),
  };
  match fraction(src) {
    Ok((rest, frac)) => {
      result += frac;
      src = rest;
    }
    Err(JSONParseError::NotFound) => {}
    Err(e) => return Err(e),
  }
  match exponent(src) {
    Ok((rest, exponent)) => {
      src = rest;
      let multipier = 10_f64.powf(exponent as f64);
      result *= multipier;
    }
    Err(JSONParseError::NotFound) => {}
    Err(e) => return Err(e),
  }
  if negative {
    result *= -1.0;
  }
  Ok((src, JSONValue::Number(result)))
}

此代码分为三部分:整数部分、小数部分和指数部分。解析器逐一读取这些部分,并构造出一个f64值。

列表与对象

数组和对象都是值的集合。数组是有序值列表,而对象则是无序的键值对集合。解析器需要同时处理这两种类型。

从语法上看,这两者都是由逗号分隔的元素组成的集合。对于每种类型,解析器需要能够处理三种情况:

  • 没有元素
  • 一个元素
  • 多个元素

没有元素的情况很简单——只需找到一对括号,中间可能是空白符。对于后两种情况,可以通过循环不断读取元素,直到遇到逗号为止。这样可以简单地解析这些集合,但仍需注意不能跳过无效的JSON值,因此适当的错误处理至关重要。

以下是相关代码:

fn elements(mut src: &str) -> Result<(&str, Vec<JSONValue>), JSONParseError> {
  let mut values = ve