🔬用 Rust 建立解析器（下）

此文檔內容為飛書文檔複製過來作為搜索，存在內容格式不兼容情況，建議看原飛書文檔

背景#

通過上文（Build A Parser By Rust（上））我們已經基本了解了解析器的相關概念及其 Rust 中解析器庫的相關使用等，所以這篇文章我們將上文學到的東西實踐到具體的 case 中，幫助大家更好地理解其概念和掌握其實際的應用，同時也能了解到部分解析器實現的相關設計，為後續實現自定義的解析器提供思路。

下面將會帶領大家，分別通過 nom 和 pest 來簡單實現較為常見且協議較為簡單的 Json 解析器。

注意：

下面使用到的 nom 或者 pest 的依賴版本為最新版本
[dependencies]
pest = "2.6"
pest_derive = "2.6"
nom = "7.1.3"
下面在實踐過程中，只會解釋部分重要或上文沒有提到的 API 的具體含義，若想了解可查閱上文或庫文檔

此篇文檔構造的解析器只驗證了解析的正確性，並沒有進行相關的性能壓測，感興趣的同學可自行嘗試

具體源碼可查看：

catwithtudou/parser_toy

build parser by rust

Rust20

Json 標準#

Json（JavaScript Object Notation）是一種輕量級的數據交換格式。它採用易於閱讀的文本形式表示數據，對人類來說易於閱讀和編寫。Json 格式由鍵值對組成，使用了類似於 JavaScript 對象的語法，因此得名 JavaScript Object Notation。Json 格式通常用於在網絡傳輸數據、存儲配置信息、以及在不同系統之間交換數據。它在 Web 開發中非常常見，例如用於 API 的數據傳輸、前後端數據交互等。Json 也被廣泛應用於移動應用開發、大數據處理等領域。由於 Json 格式簡單易用且易於閱讀，因此它非常常見，並且成為了許多應用程序中數據交換的標準格式之一。

若我們想要實現 Json 解析器，我們首先需要了解 Json 標準協議，可看到標準中主要拆分為以下 6 個部分：

Json 標註	描述	具體定義
空白 whitespace	空白（whitespace）可以插入在任何一對標記之間
數值 number	數值（number）非常類似於 C 或 Java 數字，只是不使用八進制和十六進制格式
字符串 string	一個字符串（string）是由用雙引號括起來的零個或多個 Unicode 字符組成的序列，使用反斜杠轉義。一個字符（character）即一個單獨的字符串（character string）
值 value	值（value）可以是雙引號括起來的字符串（string）、數值 (number)、true、false、 null、對象（object）或者數組（array）。並且這些結構可以嵌套
數組 array	數組（array）是值（value）的有序集合。一個數組以左中括號`[`開始且以右中括號`]`結束，值之間使用逗號`,`分隔
對象 object	對象（object）是一個無序的名稱 / 值對集合。一個對象以左括號`{`開始，右括號`}`結束。每個名稱後跟一個冒號`:` ，且名稱 / 值對之間使用逗號`,`分隔

可以看到在 Json 標準協議中，其數據類型的定義和具體解析情況都非常清晰和較為簡單。

下面會根據其標準，分別通過前面了解到的 nom 和 pest 簡單實現，具體代碼路徑在 nom/json 和 pest/json 中。

基於 nom 實現#

Json Model#

這裡我們使用一個枚舉來代表除空白外的 Json Value：

#[derive(Debug, PartialEq)]
pub enum JsonValue {
    Str(String),
    Boolean(bool),
    Num(f64),
    Array(Vec<JsonValue>),
    Object(HashMap<String, JsonValue>),
    Null,
}

具體類型解析#

空白

從前面中可看到空白元素分為以下情況的任意一個，處理時會消耗輸入直至遇到其他元素，最終得到 whitespace：

space->" "
linefeed->"\n"
carriage return->"\r"
horizontal tab->"\t"

這裡 nom 有兩種實現方式，一種可直接使用內置函數multispace0，一種是利用take_while構建解析函數：

前文可了解到take_while作為謂詞解析器持續消耗輸入，直到其輸入不滿足謂詞。

// whitespace Json 空格解析（等價於 nom 內置函數 multispace0）
fn whitespace(i: &str) -> IResult<&str, &str> {
    let chars = " \t\r\n";
    take_while(move |c| chars.contains(c))(i)
}

數值

從前面可以看到對於數值，Json 是支持正負數、小數和科學計數法，雖然我們可以通過alt和be_f64等解析器子組合進行解析，但是考慮到此場景更常用的是使用 nom 提供的內置函數 double，其使用方式可參考示例：

use nom::number::complete::double;

let parser = |s| {
  double(s)
};

assert_eq!(parser("1.1"), Ok(("", 1.1)));
assert_eq!(parser("123E-02"), Ok(("", 1.23)));
assert_eq!(parser("123K-01"), Ok(("K-01", 123.0)));
assert_eq!(parser("abc"), Err(Err::Error(("abc", ErrorKind::Float))));

字符串

這裡我們需要分別討論字符串和兩邊引號中的字符串的情況：

首先可看到在字符串中，在左引號右邊有三種情況，除了引號之間為空白的空字符情況外，其餘情況可通過組合器來去掉兩邊引號，獲取到兩邊引號中的字符串的內容，其中組合器的使用方式有很多種，這裡列舉出常見的兩種使用思路：
- alt+delimited：按字符整體結構的思路去解析
- preceded+cut+terminated：按字符順序的思路去解析

// string 整個字符串解析
fn string(i: &str) -> IResult<&str, &str> {
    context(
        "string",
        preceded(char('\"'), cut(terminated(parse_str, char('\"')))))(i)
        // parse_str 後續會描述其實現
}
fn string(i: &str) -> IResult<&str, &str> {
    context(
        "string",
        alt((tag("\"\""), delimited(tag("\""), parse_str, tag("\"")))),
    )(i)
}

其中cut組合器的的作用是阻止回溯（backtracking），它會在解析失敗時立即停止解析，而不會嘗試其他可能的解析路徑。這對於避免不必要的性能開銷和解析錯誤非常有用。這裡給出官方的示例方便理解：
use nom::combinator::cut;

fn parser(input: &str) -> IResult<&str, &str> {
  alt((
    preceded(one_of("+-"), cut(digit1)),
    rest
  ))(input)
}

assert_eq!(parser("+10 ab"), Ok((" ab", "10")));
assert_eq!(parser("ab"), Ok(("", "ab")));
assert_eq!(parser("+"), Err(Err::Failure(Error { input: "", code: ErrorKind::Digit })));

然後獲取到引號中的字符串後，我們需要處理轉義字符才能獲取到實際內容，目前 nom 內置提供了專門處理轉義字符的 escaped 函數，該函數入參為 escaped(normal, control, escapable)，其參數分別表示：
- normal ：用於匹配普通字符解析器，但無法接受含有控制符的字符
- control：控制字符（例如在大多數語言中使用的\）
- escapable：可匹配的轉義字符

// 官方示例
use nom::bytes::complete::escaped;
use nom::character::complete::one_of;

fn esc(s: &str) -> IResult<&str, &str> {
  // digit1:即內置解析器函數，表示匹配至少一個數字
  // '\\':表示反斜杠字符'\'
  // r#""n\"#:通過「r#"{構造原始字符串字面量的字符串內容}"#」，這裡表示可匹配的轉義字符有 "、n、\
  escaped(digit1, '\\', one_of(r#""n\"#))(s)
}

assert_eq!(esc("123;"), Ok((";", "123")));
assert_eq!(esc(r#"12\"34;"#), Ok((";", r#"12\"34"#)));

最後根據escaped函數和 Json 標準構造parse_str函數，其中在此場景填寫的三個參數的意思分別為：
- normal：匹配 "Any codepoint except" or \ or control characters"
- '\\'：Json 中的轉義字符同樣也是反斜杠字符
- escapable：匹配標準描述中的",\,/,b等，需要注意十六進制數字也需要單獨處理
  - 這裡特別說明一下十六進制處理使用到的peek內置函數即解析後不消耗輸入，使後面解析正常

// parse_str 單獨字符串解析
fn parse_str(i: &str) -> IResult<&str, &str> {
    escaped(normal, '\\', escapable)(i)
}

// normal 普通字符解析
fn normal(i: &str) -> IResult<&str, &str> {
    take_till1(|c: char| c == '\\' || c == '"' || c.is_ascii_control())(i)
}

// escapable 轉義字符解析
fn escapable(i: &str) -> IResult<&str, &str> {
    context(
        "escaped",
        alt((
            tag("\""),
            tag("\\"),
            tag("/"),
            tag("b"),
            tag("f"),
            tag("n"),
            tag("r"),
            tag("t"),
            hex
        )))(i)
}

// hex  十六進制字符解析
fn hex(i: &str) -> IResult<&str, &str> {
    context(
        "hex",
        preceded(
            peek(tag("u")),
            take_while_m_n(5, 5, |c: char| c.is_ascii_hexdigit() || c == 'u'),
        ))(i)
}

前面已經實現了空白、數字、字符串的解析器，下面我們先完成基本類型 boolean 和 null：

// boolean 布爾數據類型解析
fn boolean(i: &str) -> IResult<&str, bool> {
    alt((
        value(true, tag("true")),
        value(false, tag("false"))
    ))(i)
}

// null Null解析
fn null(i: &str) -> IResult<&str, JsonValue> {
    map(tag("null"), |_| JsonValue::Null)(i)
}

目前根據實現好的類型解析器，我們可以構造出值的解析器（複合類型後面實現）：

下面實現中有一個可能比較難理解的語法，這裡簡單說明下：

map函數的入參類型分別是 nom parser trait 和閉包函數 *FnMut*(O1) -> O2

這裡我們可以利用枚舉類型的元素的構造函數本身就是如上的匿名函數，所以可直接使用

// json_value JsonValue 解析
fn json_value(i: &str) -> IResult<&str, JsonValue> {
    context(
        "json value",
        delimited(
            whitespace,
            alt((
                map(string, |s| JsonValue::Str(String::from(s))),
                map(double, JsonValue::Num),
                map(boolean, JsonValue::Boolean),
                null,
                map(array, JsonValue::Array),
                map(object, JsonValue::Object)
            )),
            whitespace,
        ),
    )(i)
}

數組

根據數組的標準描述：

首先使用delimited來去掉左右方括號後，方便解析之間的內容
利用內置函數 separated_list0 來解析括號包含內容得到數組 Vec<JsonValue>：

// array 數組解析
fn array(i: &str) -> IResult<&str, Vec<JsonValue>> {
    context(
        "array",
        delimited(
            tag("["),
            separated_list0(tag(","), delimited(whitespace, json_value, whitespace)),
            tag("]"),
        ),
    )(i)
}

對象

對於像對象這樣複雜的解析器，通過組合器解析器的思想，我們可通過拆分子解析器的方式來分別實現：

首先針對對象中的名稱 / 值對的格式進行解析，使用separated_pair+preceded的組合：

// key_value kv格式解析
fn key_value(i: &str) -> IResult<&str, (&str, JsonValue)> {
    separated_pair(preceded(whitespace, string), cut(preceded(whitespace, char(':'))), json_value)(i)
}

然後針對對象的整體結構，其解析思路為：
- 左括號 -> 括號中內容 -> 按（前面已實現的）鍵值對格式解析構造數組 -> 數組轉換為 HashMap 的類型 -> 右括號

// object 對象格式解析
fn object(i: &str) -> IResult<&str, HashMap<String, JsonValue>> {
    context(
        "object",
        preceded(
            char('{'),
            cut(terminated(
                map(
                    separated_list0(preceded(whitespace, char(',')), key_value),
                    |tuple_vec| {
                        tuple_vec.into_iter().map(|(k, v)| (String::from(k), v)).collect()
                    },
                ),
                preceded(whitespace, char('}')),
            )),
        ),
    )(i)
}

頂層解析函數#

前面我們已實現 Json 標準中所有的標註類型，最後我們只需要構造頂層的函數來使用該解析器。

這裡 Json 的最外層結果允許要麼是對象，要麼是數組，所以我們的頂層函數為：

fn root(i: &str) -> IResult<&str, JsonValue> {
    delimited(
        whitespace,
        alt((
            map(object, JsonValue::Object),
            map(array, JsonValue::Array),
        )),
        opt(whitespace),
    )(i)
}

最後你可運行下面測試函數來看看最終的返回結果是否正常：

#[cfg(test)]
mod test_json {
    use crate::nom::json::json::root;

    #[test]
    fn test_parse_json() {
        let data = "  { \"a\"\t: 42,
  \"b\": [ \"x\", \"y\", 12 ] ,
  \"c\": { \"hello\" : \"world\"}
  } ";
        println!("will try to parse valid JSON data:\n\n**********\n{}\n**********\n", data);
        //
        // will try to parse valid JSON data:
        //
        //     **********
        // { "a" : 42,
        //     "b": [ "x", "y", 12 ] ,
        //     "c": { "hello" : "world"}
        // }
        // **********


        println!(
            "parsing a valid file:\n{:#?}\n",
            root(data)
        );
        // parsing a valid file:
        //     Ok(
        //         (
        // "",
        // Object(
        //     {
        //         "c": Object(
        //         {
        //             "hello": Str(
        //             "world",
        //             ),
        //         },
        //         ),
        //         "b": Array(
        //             [
        //                 Str(
        //         "x",
        //         ),
        //         Str(
        //             "y",
        //         ),
        //         Num(
        //             12.0,
        //         ),
        //         ],
        //         ),
        //         "a": Num(
        //         42.0,
        //         ),
        //     },
        // ),
        // ),
        // )
    }
}

至此通過 nom 實現的 Json 解析器就完成了。這裡沒有進行具體的性能測試，感興趣的同學可以壓測一下。

基於 pest 實現#

Json Model#

與 nom 前面的實現類似，這裡用一個枚舉來構建除空白外的 Json Value

#[derive(Debug, PartialEq)]
pub enum JsonValue<'a> {  
    Number(f64),
    String(&'a str),
    Boolean(bool),
    Array(Vec<JsonValue<'a>>),
    Object(Vec<(&'a str, JsonValue<'a>)>),
    Null,
}

實際上也不一定要聲明生命週期，可直接使用 String，聲明的原因是引入了&str，這樣可省去後面類型轉換處理。

考慮到後面 Json 解析後得到的 JsonValue 更好地展示和處理，這裡增加一個針對 JsonValue 的序列化器：

pub fn serialize_json_value(val: &JsonValue) -> String {
    use JsonValue::*; // 方便後續枚舉

    match val {
        Number(n) => format!("{}", n),
        String(s) => format!("\"{}\"", s),
        Boolean(b) => format!("{}", b),
        Array(a) => {
            let contents: Vec<_> = a.iter().map(serialize_json_value).collect();
            format!("[{}]", contents.join(","))
        }
        Object(o) => {
            let contents: Vec<_> = o
                .iter()
                .map(|(key, value)| format!("\"{}\":{}", key, serialize_json_value(value)))
                .collect();
            format!("{{{}}}", contents.join(","))
        }
        Null => "null".to_string(),
    }
}

其中需要注意，在處理數組和對象複合類型時，需要進行遞歸才能拿到複合類型下的具體值。

Pest Grammar 解析#

這裡我們新建json.pest來用 Pest Grammar 來編寫我們需要解析的 Json 標準。

空白

根據標準提到的描述，通過可選操作符|實現：

WHITESPACE = _{ " " | "\t" | "\r" | "\n" }

這裡有幾個的語法特殊處理需要前置說明下：

若規則加上前綴_則代表創建了一個靜默規則，與普通規則不同的是，在解析過程中不會產生 token pairs 同時也不會上報錯誤，最終只會獲取到最外層的一對 token pair
在 pest 中若單獨定義WHITESPACE，則它會被隱式地插入到每個 sequence 或 repetition 之間（除原子規則）
- 這裡的提到的 “除原子規則外” 需要注意，後面會有規則關聯到這個信息
- 類似的隱式約定還有COMMENT規則，都是 pest 對於字符內容中隱含空白場景的考慮處理

綜上可知，後續文件中除原子規則外的所有 sequence 或 repetition 之間解析時都會忽略空白

數值

根據標準描述，通過序列運算符~來加入表達式不同的解析條件，且可利用 pest 中對數字相關的內置規則：

// 2. number
number = @{
    "-"?
    ~ ("0" | ASCII_NONZERO_DIGIT ~ ASCII_DIGIT*)
    ~ ("." ~ ASCII_DIGIT*)?
    ~ (^"e" ~ ("+"|"-")? ~ ASCII_DIGIT+)?
}

這裡同樣存在語法的特殊處理需要解釋下，方便大家理解為什麼要這麼寫：

若規則加上前綴@則代表創建了一個原子規則，其具有以下特性：
- 不會生效前面提到的WHITESPACE處理，即不會隱藏內部空白，與~構造的 sequence 之間不會忽略字符
- 在原子規則中，調用的其他規則也會被視為原子規則
- 在原子規則中，內部匹配的所有規則會被視為靜默的，即只能獲取到最外層的整個規則的解析結果
在規則後綴加上運算符?、*、+，則分別表示可匹配至多一個，匹配所有，匹配至少一個字符
在規則前綴加上運算符^，則說明不區分大小寫

字符串

根據標準描述，我們這裡將字符串的解析結合三個規則來更清晰地說明：

// 3. string
string = ${ "\"" ~ inner ~ "\"" }
inner = @{ char* }
char = {
    !( "\"" | "\\") ~ ANY
    | "\\" ~ ("\"" | "\\" | "/" | "b" | "f" | "n" | "r" | "t")
    | "\\" ~ ("u" ~ ASCII_HEX_DIGIT{4})
}

pest 沒有像 nom 一樣提供了內置針對轉義字符的處理函數，所以我們需要在解析時需要手動帶上轉義符號。

這裡解釋下其中用到的語法特殊處理：

若規則加上前綴$則代表創建了一個複合原子規則，與前面原子規則類似但也有區別需注意，其具有以下特性：
- 同樣不會生效前面提到的WHITESPACE處理
- 在複合原子規則中，不存在將其他規則視為原子規則和內部匹配規則視為靜默的處理，其他均與普通規則類似
!(...) ~ ANY代表匹配除了括號中給出的字符之外的任何字符

與之前實現值類似，我們先完成基本類型 boolean 和 null

// 4. boolean
boolean = {"true" | "false"}
// 5. null
null = {"null"}

結合各數據類型的解析規則構造值，考慮到後續不關心值中不同規則的解析過程，所以標記 _ 靜默規則減少嵌套：

value = _{ number | string | boolean | array | object | null}

其中數組和對象我們下面描述。

數組

根據標準描述，這裡將空數組和有值數組分開，通過 ~ 和 \* 來表示可能會存在的多個值：

// 6. array
array = {
    "[" ~ "]"|
    "[" ~ value ~ ("," ~ value)* ~ "]"
}

對象

這裡單獨將對象值拆分成 pair 規則，利用前面的字符串和值規則，後面與數組類似處理，區分空對象和有值對象：

// 7. object
object = {
    "{" ~ "}"|
    "{" ~ pair ~ ("," ~ pair)* ~ "}"
}
pair = { string ~ ":" ~ value }

最終規則

最後我們需要一個最終規則來表示整個 Json，而 Json 內容唯一合法的是一個對象或數組。

同時考慮到後續我們只需要解析後的值本身，以及 EOI 規則兩個 token pairs，所以我們將規則標記為靜默：

// 9. json
json = _{ SOI ~ (object | array) ~ EOI}

至此我們需要編寫的 pest 規則已經完成，下面就是根據規則生成的解析結構來生成 AST。

AST 生成和解析#

定義 Pest 規則綁定的構造體

pest 需要通過 grammar 宏來標記到 Rust 的構造體上：

use pest::Parser;
use pest_derive::Parser;

#[derive(Parser)]
#[grammar = "pest/json/json.pest"] // 根據自己項目文件所定
pub struct JsonParser;

構建 AST 生成函數

通過綁定 pest 規則的 JsonParser，使用pest::Parser 的 parse 方法來得到前面的 json 規則生成的 AST 結果：

pub fn root(content: &str) -> Result<JsonValue, Error<Rule>> {
    let json = JsonParser::parse(Rule::json, content)?.next().unwrap();
    // ......
}

由於 json 為靜默規則只有最終生成的 token pair 即 Pair<Rule> 類型，所以只需要next()一次就可以了。

我們的目標是將 AST 解析得到最終的 JsonValue，所以我們還需要一個方法來解析這個Pair<Rule>。

解析 AST 函數

新增parse_json_value函數：

使用得到的 AST 結果，來對 JsonValue 中的各個類型，根據前面 pest 的規則進行解析賦值
其中對數組和對象複合類型的處理，需要通過遞歸函數來搜索嵌套的值
若匹配的 Rule 不是 JsonValue 中的類型，則直接報錯退出

pub fn parse_json_value(pair: Pair<Rule>) -> JsonValue {
    match pair.as_rule() {
        Rule::number => JsonValue::Number(pair.as_str().parse().unwrap()),
        Rule::string => JsonValue::String(pair.into_inner().next().unwrap().as_str()),
        Rule::boolean => JsonValue::Boolean(pair.as_str().parse().unwrap()),
        Rule::null => JsonValue::Null,
        Rule::array => JsonValue::Array(pair.into_inner().map(parse_json_value).collect()),
        Rule::object => JsonValue::Object(
            pair.into_inner()
                .map(|pair| {
                    let mut inner_rules = pair.into_inner();
                    let key = inner_rules
                        .next() // 得到 pair 規則
                        .unwrap()
                        .into_inner()
                        .next() // 得到 pair 規則的第一個 token pair 即 key
                        .unwrap()
                        .as_str();
                    let value = parse_json_value(inner_rules.next().unwrap());
                    (key, value)
                })
                .collect()
        ),
        _ => unreachable!()
    }
}

最終頂層函數及函數測試

根據上一步的解析函數，我們來完善前面的頂層函數 root，得到最終的解析結果：

pub fn root(content: &str) -> Result<JsonValue, Error<Rule>> {
    let json = JsonParser::parse(Rule::json, content)?.next().unwrap();
    Ok(parse_json_value(json))
}

最後可運行下面測試函數來驗證解析的結果：

#[cfg(test)]
mod test {
    use crate::pest::json::json::{JsonValue, root, serialize_json_value};

    #[test]
    fn test_parse_json_by_pest() {
        let data = "  { \"a\"\t: 42,
  \"b\": [ \"x\", \"y\", 12 ] ,
  \"c\": { \"hello\" : \"world\"}
  } ";
        println!("will try to parse valid JSON data:\n\n** ********\n{}\n**********\n", data);

        // will try to parse valid JSON data:
        //
        //     **********
        // { "a" : 42,
        //     "b": [ "x", "y", 12 ] ,
        //     "c": { "hello" : "world"}
        // }
        // **********


        let json_result: JsonValue = root(data).expect("unsuccessful JSON");

        println!("{}", serialize_json_value(&json_result))
        // {"a":42,"b":["x","y",12],"c":{"hello":"world"}}
    }
}