catwithtudou

一直是阵雨

🌦️一枚服务端菜狗/ 大部分时间都是 golang 🫖尝试记录和热爱生活/尝试交一些新朋友 📖目前最重要的事情是打破信息壁垒&重新拾起初心和兴趣&输出者
twitter
github

🔬用 Rust 建立解析器(上)

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

背景#

最近在跟著 mbrubeck 大佬寫的 Robinson 學習用 Rust 來編寫一個簡單的瀏覽器引擎(後續寫完我也會出一個文檔來介紹下),在其過程中因為需要解析 html、css 等格式文件,所以你需要編寫相關的解析器來完成。

而從 0 到 1 的手寫解析器是一件非常枯燥且容易出錯的行為,因為你不僅需要考慮其具體需要解析的協議規則,還需要考慮解析器的錯誤處理、擴展性、解析性能等,所以在文章中大佬也提到,建議後續可通過目前已有的類似 pest 等解析器三方庫來優化。

回想在我日常的開發工作中,遇到需要構造解析器的場景較少,往往是,如果出現對解析某格式或協議的信息,如 Json、Csv 等,為了追求效率,直接使用找針對解析該格式或協議的三方庫。但實際上並不是所有協議或格式都有別人寫好的解析器,特別是對於各種網絡通信協議等,且寫好的解析器也很難針對其定制化,所以借助這個契機,正好學習了解下解析器,及構造解析器的相關實踐,方便後續有類似場景的使用。

注意:

  • 此篇文檔不會重點深挖解析器和解析器庫的相關原理,更多是對於「解析器入門的了解及其實踐」
  • 此系列文檔分為上下兩篇,上篇主要講述解析器的了解和三方庫的使用,下篇主要講述具體的實踐
  • 此系列文檔出現的源碼可在 https://github.com/catwithtudou/parser_toy 查看

前置知識#

下面會介紹一些關於解析器相關的前置背景知識,幫助了解後面的理解。

Parser#

這裡提到的解析器(Parser)實際是更廣泛的定義,通常是指把某種格式的信息轉換成某種數據結構的組件。

就好比將某種某種格式的信息進行 “解碼”,抽象成有組織的數據結構信息,方便對信息的理解和處理加工。

舉個🌰:此時有一段算數表達式的文本 "1 + 2",期望通過程序能夠計算出結果。

為了讓程序能夠識別算術表達式,可通過針對算法表達式的解析器,轉換成 (left,op,right) 的結構體進行計算。

對於計算機領域來說,在處理數據的過程中解析器必不可少,能夠應用各種數據處理場景中,比如較為常見的:

  • 在底層編譯器或解釋器中的解析器,其主要作用就是將源碼進行詞法和語法的分析,提取出抽象語法樹 AST
  • 對於 Web 應用較多的數據交換格式 Json 的文本,可通過對應的解析器序列化需要的數據結構進行處理加工
  • 其他如通過解析器解析網絡通信協議、腳本語言、數據庫語言等

PEG#

在介紹 PEG (解析表達文法)之前,我們這裡可通過(假設)更為常見的正則表達式來進行方便理解。

正則表達式和 PEG 聯繫主要是都可在處理字符文本時通過特定的語法對字符文本進行匹配和解析,而不同點在於:

  • 【語法方面】前者是使用一種特定語法來描述字符串的模式,通常用於處理簡單的字符串匹配和搜索。而後者使用一種更複雜的語法來描述語言結構,通常用於處理複雜的語言解析和分析需求。
  • 【應用領域】前者主要用於處理簡單的文本處理需求,例如查找特定模式的文本或驗證輸入的格式。而後者主要用於處理複雜的語言結構,例如編程語言的語法分析和解釋器的構建。

通過介紹,相信大家對於 PEG 有了簡單的理解。

而為什麼介紹 PEG,其原因就是因為可通過 PEG 實現的工具(稱為 Parser Generator)來實現定制的 Parser。

接下來我們來簡單正式介紹下 PEG 即 解析表達文法:

  1. PEG(解析表達文法)簡介

解析表達文法,簡稱PEG(英語:Parsing Expression Grammar):

  • 是一種分析型 **** 形式文法。在 04 年由 Bryan Ford 推出,與 20 世紀 70 年代引入的自頂向下的語法分析語言家族相關
  • 作為描述語言結構的語法,相較於正則表達式可以處理更複雜的語言結構,因遞歸性特點可描述無限嵌套的結構
  • 使用一種簡單而靈活的方式來定義語法規則,該規則可以被用來解析輸入字符串並生成語法樹
  • 易用性、正確性和性能的優勢且提供錯誤報告、可重用規則模板等功能,因此在解析和分析文本時被廣泛使用
  1. PEG 應用簡介

PEG 的語法類似於編程語言,使用操作符規則來描述語言結構:

  • 操作符包括 “|”(或)、“&”(與)、“?”(可選)等,規則則用於描述語言的具體結構

  • 例如下面是一個簡單的 PEG 規則,它描述了一個整數的語法:

    int := [0-9]+
    

因為可以直接轉換為高效的解析器代碼,目前已有許多底層使用 PEG 實現的解析器,如 ANTLR、PEG.js 等。

Parser Combinator#

通過前對 Parser 的了解,理解 Parser Combinator(解析器組合器)就比較容易了。

  1. Parser Combinator 的定義及思想

簡單來說 Parser Combinator 就是組合各種解析器組件而構建的組件。

Parser Combinator 的思路就比較符合軟件工程,它是一種基於函數組合的方式來構建解析器的技術,通過組合小的、可復用的、可測試的解析器組件來構建複雜的解析器,這種方式可以使得解析器的構建更加靈活和可擴展,且大大提升了開發的效率和方便了後續的維護。

  1. Parser Combinator 和 Parser Generator

Parser Combinator 實際上和前面提到的 Parser Generator 是平行的概念,這裡舉個例子:

  • 如果我們把想要實現的解析器(如 Json Parser)看成一幢大樓的話
  • 用 Parser Generator 構建則每次都幾乎從零開始構建該大樓,大樓和大樓之間相似的部分(如門窗)無法復用
  • 而用 Parser Combinator ** 就像搭樂高積木即不斷構建小的,可復用 **** 的、**可測試的組件,然後用這些組件來構建大樓,如果我們要構建新的大樓時,之前創建的組件可以拿來使用,非常方便。同時當解析器出現問題時,可容易地定位到某個具體的組件,也方便後續的維護
  1. Parser Combinator 和基於 PEG 實現的 Parser Generator

【表達方面】Parser Combinator 在表達能力上更加靈活,可以直接使用編程語言的特性來組合和定義解析器。而 PEG 實現的 Parser Generator 則是通過特定的語法規則來描述解析器,表達能力受到語法規則的限制,即你需要學會使用其 Parser Generator 本身接口外還必須要掌握 PEG 的語法規則

【性能方面】Parser Combinator 和 Parser Generator 的性能對比取決於具體的實現和使用場景。但是一般從底層原理來說,Parser Generator 通常會生成高效的解析器代碼,因此在處理大型語法和複雜輸入時可能具有更好的性能。另一方面,Parser Combinator 通常會有一定的性能開銷,因為它們是在運行時動態組合解析器的

但目前在 Rust 中,基於 Parser Combinator 實現的 nom 和基於 PEG 實現的 pest,前者性能更高一些。

Rust Praser Library#

下面會介紹在 Rust 中用於實現解析器的經典三方庫,分別是基於 PEG 的 Pest 和 Paser Combinator 的 Nom。

pest#

簡介#

Pest 是一個使用 Rust 編寫的通用解析器,注重可訪問性、正確性和性能。它使用前面提到的 PEG 作为输入,提供了解析複雜語言所需的增強表達能力,同時也以一種簡潔、優雅的方式來定義和生成解析器方便構造自定義解析器。

其中還具有自動生成錯誤報告、通過 derive 屬性自動生成實現解析器 trait、單個文件中可定義多個解析器等特性。

使用示例#

  1. 在 cargo.toml 引入 pest 依賴
[dependencies]
pest = "2.6"
pest_derive = "2.6"
  1. 新建**src/grammar.pest**文件編寫解析表達式語法

這裡語法表示 field 字段的解析規則,即每個字符都是 ASCII 數字且包含小數點和負號,+表示該模式可出現多次。

field = { (ASCII_DIGIT | "." | "-")+ }
  1. 新建**src/parser.rs**文件定義解析器

下面代碼通過定義一個結構體 Parser,通過派生宏綁定,(每次編譯)自動實現滿足語法文件中模式的解析器。

use pest_derive::Parser;

#[derive(Parser)] 
#[grammar = "grammer.pest"]
pub struct Parser;

// 每當你編譯這個文件時,pest 會自動使用 grammar 文件生成這樣的項
#[cfg(test)]
mod test {
    use std::fs;

    use pest::Parser;
    
    use crate::{Parser, Rule};

    #[test]
    pub fn test_parse() {
        let successful_parse = Parser::parse(Rule::field, "-273.15");
        println!("{:?}", successful_parse);

        let unsuccessful_parse = Parser::parse(Rule::field, "China");
        println!("{:?}", unsuccessful_parse);
    }
}    

具體使用#

官方文檔

Parser API#

pest 提供了多種訪問成功解析結果的方法。下面按照以下語法示例來介紹其方法:

number = { ASCII_DIGIT+ }                // one or more decimal digits
enclosed = { "(.." ~ number ~ "..)" }    // for instance, "(..1024..)"
sum = { number ~ " + " ~ number }        // for instance, "1024 + 12"
  1. Tokens

pest 使用 tokens 表示成功,每當規則匹配時,會生成兩個 tokens,分別表示匹配的開頭 start 和結尾 start,如:

"3130 abc"
 |   ^ end(number)
 ^ start(number)

目前 rustrover 有支持 pest 格式的插件,能夠校驗規則和查看 tokens 等功能。

  1. 嵌套規則

如果一個命名規則包含另一個命名規則,則均會為兩者生成 tokens 生成如下將為兩者,如:

"(..6472..)"
 |  |   |  ^ end(enclosed)
 |  |   ^ end(number)
 |  ^ start(number)
 ^ start(enclosed)

同時某些場景下,標記可能會出現在不同的字符位置:

"1773 + 1362"
 |   |  |   ^ end(sum)
 |   |  |   ^ end(number)
 |   |  ^ start(number)
 |   ^ end(number)
 ^ start(number)
 ^ start(sum)
  1. interface

token 會以 Token enum 形式暴露,該 enum 具有 Start 和 End 變體,可在解析結果上調用 tokens 來獲取迭代器:

let parse_result = DemoParser::parse(Rule::sum, "1773 + 1362").unwrap();
let tokens = parse_result.tokens();

for token in tokens {
    println!("{:?}", token);
}

img

  1. Pairs

若考慮匹配的標記對來探索解析樹,則 pest 提供 Pair 類型來表示一對匹配的 tokens,使用方式主要如下:

  • 確定哪個規則產生了 Pair
  • 使用 Pair 作為原始 &str
  • 檢查生成 Pair 的內部命名規則
let pair = DemoParser::parse(Rule::enclosed, "(..6472..) and more text")
    .unwrap().next().unwrap();

assert_eq!(pair.as_rule(), Rule::enclosed);
assert_eq!(pair.as_str(), "(..6472..)");

let inner_rules = pair.into_inner();
println!("{}", inner_rules); // --> [number(3, 7)]

Pair 可能有任意數量的內部規則,可通過 Pair::into_inner () 返回 Pairs 即每一對的迭代器:

let pairs = DemoParser::parse(Rule::sum, "1773 + 1362")
    .unwrap().next().unwrap()
    .into_inner();

let numbers = pairs
    .clone()
    .map(|pair| str::parse(pair.as_str()).unwrap())
    .collect::<Vec<i32>>();
assert_eq!(vec![1773, 1362], numbers);

for (found, expected) in pairs.zip(vec!["1773", "1362"]) {
    assert_eq!(Rule::number, found.as_rule());
    assert_eq!(expected, found.as_str());
}
  1. Parse method

派生的 Parser 提供了會返回 Result<Paris,Error> parse 方法,若要訪問底層解析樹則需要 match 或 unwrap 結果:

// check whether parse was successful
match Parser::parse(Rule::enclosed, "(..6472..)") {
    Ok(mut pairs) => {
        let enclosed = pairs.next().unwrap();
        // ...
    }
    Err(error) => {
        // ...
    }
}

解析表達式語法#

PEG 語法的基本邏輯實際上是非常簡單和直接的,可以概括為三步:

  • 嘗試匹配規則
  • 如果成功,就嘗試下一步
  • 如果失敗,就嘗試另外規則

其語法的特點主要有以下四點:

  1. Eagerness

當在輸入字符串上運行重複的 PEG 表達式時,它會貪婪地(盡可能多次)運行表達式,其結果有以下:

  • 若匹配成功,則會消耗它所匹配的任何內容,並將剩余的輸入傳遞到解析器的下一步
  • 若匹配失敗,則不消耗什麼字符,且若該失敗就會向上傳播,最終導致解析失敗,除非失敗被傳播中被捕獲
// 表達式
ASCII_DIGIT+      // one or more characters from '0' to '9'

// 匹配過程
"42 boxes"
 ^ Running ASCII_DIGIT+

"42 boxes"
   ^ Successfully took one or more digits!

" boxes"
 ^ Remaining unparsed input.
  1. Ordered choice

語法中存在有序的選擇操作符|,比如one|two則表示先嘗試前者 one,若失敗則嘗試後者 two。

若有順序的要求,則需要注意規則放置在表達式中的位置,比如:

  • 表達式"a"|"ab",在匹配字符串 "abc" 時,命中前面的規則"a"後,則不會解析後面的 "bc" 了

所以通常當編寫一個有選擇的解析器時,把最長或最具體的選擇放在前面,而把最短或最一般的選擇放在最後。

  1. Non-backtracking

在解析過程中,表達式要麼成功,要麼失敗。

若成功則進行下一步,若失敗了,則表達式會失敗,且引擎不會後退再試即回溯,這與具有回溯的正則表達式不同。

比如下面這個例子(其中~表示該表達式中前面規則匹配成功後會進行的下一步):

word = {     // to recognize a word...
    ANY*     //   take any character, zero or more times...
    ~ ANY    //   followed by any character
}

"frumious"

匹配字符串 "frumious" 時,ANY*首先會消耗掉整個字符串,而下一步ANY則不會匹配任何內容,導致它解析失敗

"frumious"
 ^ (word)

"frumious"
         ^ (ANY*) Success! Continue to ANY with remaining input "".
 
""
 ^ (ANY) Failure! Expected one character, but found end of string.

而上面這種場景,對於具有回溯功能的系統(如正則表達式),則會後退一步,“吐出 " 一個字符,然後再試。

  1. Unambiguous

PEG 的每個規則都會在輸入字符串的剩余部分上運行,消耗盡可能多的輸入。一旦一個規則完成,剩下的輸入就會被傳遞給解析器的其他部分,比如表達式ASCII_DIGIT+表示匹配一個或多個數字,始終會匹配可能的最大的連續數字序列。而不存在意外地,讓後面的規則回溯,且以一種不直觀和非局部的方式竊取一些數字等可能的危險情況。

這與其他解析工具形成了鮮明對比,如正則表達式和 CFG,在這些工具中,規則的結果往往取決於一些距離的代碼。

解析器語法 & 內置規則#

  1. 重要語法

pest 的語法數量相較於正則表達式來說少很多,下面簡單展示主要的語法及含義,關於語法的詳情可自行搜索:

語法含義語法含義
foo = { ... }regular rulebaz = @{ ... }atomic
bar = _{ ... }silentqux = ${ ... }compound-atomic
#tag = ...tagsplugh = !{ ... }non-atomic
"abc"exact string^"abc"case insensitive
'a'..'z'character rangeANYany character
foo ~ barsequence`bazqux`
foo*zero or morebar+one or more
baz?optionalqux{n}exactly n
qux{m, n}between m and n (inclusive)
&foopositive predicate
PUSH(baz)match and push!barnegative predicate
POPmatch and pop
DROPpop without matchingPEEKmatch without pop
PEEK_ALLmatch entire stack
  1. 內置規則

除了ANY外,pest 還提供非常多的內置規則,讓解析文本更加方便,這裡主要展示幾個常用的,詳情可自行查閱

內置規則等價於內置規則等價於
ASCII_DIGIT'0'..'9'ASCII_ALPHANUMERICany digit or letter `ASCII_DIGIT
UPPERCASE_LETTER大寫字母NEWLINEany line feed format`"\n"
LOWERCASE_LETTER小寫字母SPACE_SEPARATOR空格分隔符
MATH_SYMBOL數學符號EMOJIEmoji 表情

nom#

簡介#

nom 是使用 Rust 編寫的前面提到的解析器組合器(Parser Combinator)庫,它具有以下特性:

  • 在不影響速度或內存消耗的情況下構建安全的解析器
  • 依靠 Rust 強大的類型系統和內存安全來生成既正確又高效的解析器
  • 提供函數、宏和特徵來抽象大部分容易出錯的管道,同時也能輕鬆組合和重用解析器來構建複雜解析器

nom 能支持的應用場景非常廣泛,比如以下常見場景:

  • 二進制格式解析器:nom 的性能與用 C 語言手寫的解析器一樣快,且不受緩衝區溢出漏洞,並內置常見處理模式
  • 文本格式解析器:能夠處理類似 csv 和更複雜的嵌套格式 Json 等,不僅可以管理數據,並內置多個有用的工具
  • 編程語言解析器:nom 可作為語言的原型解析器,支持自定義錯誤類型和報告、自動處理空格、就地構造 AST 等
  • 除了以上場景還有 streaming formats(如 HTTP 網絡處理)、更符合軟件工程的解析器組合器等

使用示例#

這裡以 nom repo README 提供的 “十六進制顏色解析器” 例子來進行介紹:

這裡簡單講述下十六進制顏色的具體格式是:

  • 以 "#" 開頭,後面跟著六個字符,每兩個字符代表紅、綠、藍三種顏色通道的數值

比如 "#2F14DF" 則 "2F" 代表紅色通道的數值,"14" 代表綠色通道的數值,"DF" 代表藍色通道的數值。

  1. 在 cargo.toml 引入 nom 依賴
[dependencies]
nom = "7.1.3"
  1. 新建**src/nom/hex_color.rs, 引入 nom 來構造十六進制顏色的解析方法hex_color**
  • tag會匹配開頭的字符模式,tag("#")返回的是一個函數,其返回值為IResult<Input,Input,Error>
    • 其中Input為函數輸入參數類型,第一个值為去掉匹配模式后的輸入值,第二個為匹配內容,最後是錯誤值
  • nom 提供的take_while_m_n方法前兩個參數為最少和最多的匹配數量,最後參數為匹配規則,返回與上類似
  • nom 提供的map_res方法則可將第一個參數得到的結果進行根據第二參數的模式進行轉換
  • nom 提供的tuple方法接受一組組合子,將組合子按順序應用到輸入上,然後按順序以元組形式返回解析結果
use nom::{AsChar, IResult};
use nom::bytes::complete::tag;
use nom::bytes::complete::take_while_m_n;
use nom::combinator::map_res;
use nom::sequence::tuple;

#[derive(Debug, PartialEq)]
pub struct Color {
    pub red: u8,
    pub green: u8,
    pub blue: u8,
}


// 是否為16進制數字
pub fn is_hex_digit(c: char) -> bool {
    c.is_hex_digit()
}

// 將字符串轉換為十進制結果
pub fn to_num(input: &str) -> Result<u8, std::num::ParseIntError> {
    u8::from_str_radix(input, 16)
}

// 按 is_hex_digit 規則對輸入按兩位進行匹配,並將結果按 to_hex_num 轉換十進制結果
pub fn hex_primary(input: &str) -> IResult<&str, u8> {
    map_res(
        take_while_m_n(2, 2, is_hex_digit),
        to_num,
    )(input)
}

// 十六進制顏色的解析器
pub fn hex_color(input: &str) -> IResult<&str, Color> {
    let (input, _) = tag("#")(input)?;
    let (input, (red, green, blue)) = tuple((hex_primary, hex_primary, hex_primary))(input)?;

    Ok((input, Color { red, green, blue }))
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_hex_color() {
        assert_eq!(hex_color("#2F14DF"), Ok(("", Color {
            red: 47,
            green: 20,
            blue: 223,
        })))
    }
}

具體使用#

parser result#

在前面示例中看到的 nom 解析方法的返回IResult,這是 nom 的核心結構之一,表示 nom 解析的返回結果。

首先 nom 構造的解析器,將解析后的結果定義為以下:

  • Ok(...)表示解析成功后找到的內容,Err(...)表示解析沒有查到對應內容
  • 若解析成功后,將返回一個元組,第一个會包含解析器未匹配的所有內容,第二個會包含解析器匹配的所有內容
  • 若解析失敗,則可能會返回多個錯誤
                                   ┌─► Ok(
                                   │      what the parser didn't touch,
                                   │      what matched the regex
                                   │   )
             ┌─────────┐           │
 my input───►│my parser├──►either──┤
             └─────────┘           └─► Err(...)

所以為表示該模型,nom 定義了結構體IResult<Input,Output,Error>

  • 可看出實際上 Input 和 Output 可定義為不同的類型,Error 則為任何實現 ParseError trait 的類型

tag & character classes#

  1. tag 字節集合標籤

nom 將簡單的字節集合稱為標籤。因為這些十分常見,所以也內置了tag()函數,返回給定字符串的解析器。

比如想要解析字符串 "abc",則可使用tag("abc")

需要注意的是 nom 中存在多個不同的 tag 定義,若不特別說明則通常使用以下定義,避免出現意外的錯誤:

pub use nom::bytes::complete::tag;

tag函數的簽名如下,可看到其tag返回了一個函數,且該函數是一個解析器,獲取 &str 并返回 IResult

同時這裡的,創建解析器的函數返回其解析器函數,使用時輸入其參數,是 nom 中的常見模式。

pub fn tag<T, Input, Error: ParseError<Input>>(
    tag: T
) -> impl Fn(Input) -> IResult<Input, Input, Error> where
    Input: InputTake + Compare<T>,
    T: InputLength + Clone, 

這裡以一個實現使用tag的函數來進行舉例:

use nom::bytes::complete::tag;
use nom::IResult;

pub fn parse_input(input: &str) -> IResult<&str, &str> {
    tag("abc")(input)
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test_parse_input() {
        let (leftover_input, output) = parse_input("abcWorld!").unwrap();
        assert_eq!(leftover_input, "World!");
        assert_eq!(output, "abc");
        assert!(parse_input("defWorld").is_err());
    }
}
  1. character classes

考慮到 tag 僅能用於開頭序列中的字符,nom 提供了另外的預先編寫的解析器即被稱為 character classes,其允許接受一組字符中的任何一個。下面展示一些使用較多的內置解析器:

解析器作用解析器作用
alpha0/alpha1識別零個或多個小寫和大寫字母字符後者類似,但要求至少返回一個字符multispace0/multispace1識別零個或多個空格、制表符、回車符和換行符後者類似,但要求至少返回一個字符
alphanumeric0/alphanumeric1識別零個或多個數字字符或字母字符後者類似,但要求至少返回一個字符space0/space1識別零個或多個空格和制表符後者類似,但要求至少返回一個字符
digit0/digit1識別零個或多個數字字符後者類似,但要求至少返回一個字符newline識別換行符

這裡舉一個簡單的例子來看看是如何使用的:

use nom::character::complete::alpha0;
use nom::IResult;

fn parse_alpha(input: &str) -> IResult<&str, &str> {
    alpha0(input)
}

#[test]
fn test_parse_alpha() {
    let (remaining, letters) = parse_alpha("abc123").unwrap();
    assert_eq!(remaining, "123");
    assert_eq!(letters, "abc");
}

alternatives & composition#

  1. alternatives

nom 提供了alt()組合器來滿足多個解析器的選擇,它將執行元組中的每個解析器,直至找到解析成功的解析器

若元組中的所有解析器都解析失敗,那麼才會收到相應的報錯。

下面舉一個簡單的例子來進行說明:

use nom::branch::alt;
use nom::bytes::complete::tag;
use nom::IResult;

fn parse_abc_or_def(input: &str) -> IResult<&str, &str> {
    alt((
        tag("abc"),
        tag("def"),
    ))(input)
}

#[test]
fn test_parse_abc_or_def() {
    let (leftover_input, output) = parse_abc_or_def("abcWorld").unwrap();
    assert_eq!(leftover_input, "World");
    assert_eq!(output, "abc");
    let (_, output) = parse_abc_or_def("defWorld").unwrap();
    assert_eq!(output, "def");
    assert!(parse_abc_or_def("ghiWorld").is_err());
}
  1. composition

除了多個解析器的選擇之外,組合解析器也是一項非常常見的要求,所以 nom 提供了內置的組合器

比如tuple(),其采用解析器的元組,且返回Ok以及所有成功解析的元組,或返回第一個失敗的 Err解析器。

use nom::branch::alt;
use nom::bytes::complete::tag_no_case;
use nom::IResult;
use nom::sequence::tuple;

fn parse_base(input: &str) -> IResult<&str, &str> {
    alt((
        tag_no_case("a"), // 與 tag 相比不區分大小寫的標籤
        tag_no_case("t"),
        tag_no_case("c"),
        tag_no_case("g"),
    ))(input)
}

fn parse_pair(input: &str) -> IResult<&str, (&str, &str)> {
    tuple((
        parse_base, parse_base
    ))(input)
}

#[test]
fn test_parse_pair() {
    let (remaining, parsed) = parse_pair("aTcG").unwrap();
    assert_eq!(parsed, ("a", "T"));
    assert_eq!(remaining, "cG");
    assert!(parse_pair("Dct").is_err());
}

除了上面提到的,實際上 rust 還支持下面具有類似操作的解析器

combinatorusageinputoutput
delimiteddelimited(char('('), take(2), char(')'))"(ab)cd"Ok(("cd", "ab"))
precededpreceded(tag("ab"), tag("XY"))"abXYZ"Ok(("Z", "XY"))
terminatedterminated(tag("ab"), tag("XY"))"abXYZ"Ok(("Z", "ab"))
pairpair(tag("ab"), tag("XY"))"abXYZ"Ok(("Z", ("ab", "XY")))
separated_pairseparated_pair(tag("hello"), char(','), tag("world"))"hello,world!"Ok(("!", ("hello", "world")))

Parsers With Custom Return Types#

就像提到的IResult中的 Input 和 Output 實際上可以為不同的類型,如果我們想要對標籤的結果進行類型轉換,那麼就可以使用 nom 提供的**value**組合器來將解析成功的結果轉換為特定值。比如下面這個例子:

use nom::branch::alt;
use nom::bytes::complete::tag;
use nom::combinator::value;
use nom::IResult;

fn parse_bool(input: &str) -> IResult<&str, bool> {
    alt((
        value(true, tag("true")),    // 轉換為 bool 類型
        value(false, tag("false")),
    ))(input)
}

#[test]
fn test_parse_bool() {
    let (remaining, parsed) = parse_bool("true|false").unwrap();
    assert_eq!(parsed, true);
    assert_eq!(remaining, "|false");
    assert!(parse_bool(remaining).is_err());
}

Repeating Predicates and Parsers#

  1. Repeating With Predicates

這裡的 Predicates 實際上就像是我們之前接觸到的 while 循環,為了滿足包含特定條件而重複的解析器處理的功能,nom 提供了幾個不同類別的謂詞解析器,主要分別是take_tilltake_untiltake_while三種類別:

组合器作用用法输入输出
take_till持續消耗輸入,直到其輸入滿足謂詞take_while(is_alphabetic)"abc123"Ok(("123", "abc"))
take_while持續消耗輸入,直到其輸入不滿足謂詞take_till(is_alphabetic)"123abc"Ok(("abc", "123"))
take_until消耗直到滿足謂詞的第一次出現take_until("world")"Hello World"Ok(("World", "Hello "))

這裡可以再補充一些:

  • 上述組合器實際上都有一個 “双胞胎”,即名稱末尾帶有1,區別在於需要至少返回一個匹配字符,不然就會報錯
  • 前面用到的take_while_m_n,實際類似於 take_while,是作為一種特殊情況,其保證消耗[m,n]字節
  1. Repeating Parsers

除了重複謂詞的單個解析器,nom 還提供了重複解析器的組合器,比如many0能盡可能多次地應用解析器,並返回這些解析結果的向量,比如下面這個例子:

use nom::bytes::complete::tag;
use nom::IResult;
use nom::multi::many0;

fn repeat_parser(s: &str) -> IResult<&str, Vec<&str>> {
    many0(tag("abc"))(s)
}

#[test]
fn test_repeat_parser() {
    assert_eq!(repeat_parser("abcabc"), Ok(("", vec!["abc", "abc"])));
    assert_eq!(repeat_parser("abc123"), Ok(("123", vec!["abc"])));
    assert_eq!(repeat_parser("123123"), Ok(("123123", vec![])));
    assert_eq!(repeat_parser(""), Ok(("", vec![])));
}

下面也列出一些常用的組合器:

组合器用法输入输出
countcount(take(2), 3)"abcdefgh"Ok(("gh", vec!["ab", "cd", "ef"]))
many0many0(tag("ab"))"abababc"Ok(("c", vec!["ab", "ab", "ab"]))
many_m_nmany_m_n(1, 3, tag("ab"))"ababc"Ok(("c", vec!["ab", "ab"]))
many_tillmany_till(tag( "ab" ), tag( "ef" ))"ababefg"Ok(("g", (vec!["ab", "ab"], "ef")))
separated_list0separated_list0(tag(","), tag("ab"))"ab,ab,ab."Ok((".", vec!["ab", "ab", "ab"]))
fold_many0fold_many0(be_u8, || 0, |acc, item| acc + item)[1, 2, 3]Ok(([], 6))
fold_many_m_nfold_many_m_n(1, 2, be_u8, || 0, |acc, item| acc + item)[1, 2, 3]Ok(([3], 3))
length_countlength_count(number, tag("ab"))"2ababab"Ok(("ab", vec!["ab", "ab"]))

Error management#

nom 的錯誤在設計時考慮到了多種需求:

  • 指示哪個解析器失敗以及輸入數據中的位置
  • 當錯誤沿著解析器鏈向上時,積累更多的上下文
  • 開銷非常低,因為調用解析器通常會丟棄錯誤
  • 可以根據用戶的需要進行修改,因為有些語言需要更多的信息

為了滿足以上需求, nom 解析器的結果類型設計如下:

pub type IResult<I, O, E=nom::error::Error<I>> = Result<(I, O), nom::Err<E>>;

pub enum Err<E> {
    Incomplete(Needed),    // 表示解析器沒有足夠的數據來做出決定,通常在 streaming 場景會遇到
    Error(E),              // 正常的解析器錯誤,比如 alt 組合器的子解析器返回 Error ,它將嘗試另一個子解析器
    Failure(E),            // 無法恢復的錯誤,比如子解析器返回 Failure ,則 alt 組合器將不會嘗試其他分支
}
  1. **nom::Err<E>**中常見的錯誤類型
  • 默認錯誤類型nom::error::Error,它會返回具體是哪些解析器的錯誤及錯誤的輸入位置

      #[derive(Debug, PartialEq)]
      pub struct Error<I> {
        /// position of the error in the input data
        pub input: I,
        /// nom error code
        pub code: ErrorKind,
      }
    
    • 這種錯誤類型速度快且開銷較低,適合重複調用的解析器,但它的功能也是有限的,比如不會返回調用鏈信息
  • 獲取更多信息nom::error::VerboseError,它會返回遇到錯誤的解析器鏈的更多信息,如解析器類型等

      #[derive(Clone, Debug, PartialEq)]
      pub struct VerboseError<I> {
        /// List of errors accumulated by `VerboseError`, containing the affected
        /// part of input data, and some context
        pub errors: crate::lib::std::vec::Vec<(I, VerboseErrorKind)>,
      }
      
      #[derive(Clone, Debug, PartialEq)]
      /// Error context for `VerboseError`
      pub enum VerboseErrorKind {
        /// Static string added by the `context` function
        Context(&'static str),
        /// Indicates which character was expected by the `char` function
        Char(char),
        /// Error kind given by various nom parsers
        Nom(ErrorKind),
      }
    
    • 通過查看原始輸入和錯誤鏈,可以構建更加用戶友好的錯誤消息,可通過nom::error::convert_error 函數可以構建這樣的消息
  1. ParseError tait 自定義錯誤類型

可通過實現 ParseError<I> 特徵來定義自己的錯誤類型

因為所有 nom 組合器對於其錯誤都是通用的,因此只需要在解析器結果類型中定義它,並且它將在任何地方使用。

pub trait ParseError<I>: Sized {
    // 根據輸入位置和 ErrorKind 枚舉來指示在哪個解析器中遇到錯誤
    fn from_error_kind(input: I, kind: ErrorKind) -> Self;
    // 允許在回溯解析器樹時創建一系列錯誤(各種組合器將添加更多上下文)
    fn append(input: I, kind: ErrorKind, other: Self) -> Self;
    // 創建一個錯誤,指示期望哪個字符
    fn from_char(input: I, _: char) -> Self {
        Self::from_error_kind(input, ErrorKind::Char)
    }
    // 在像 alt 這樣的組合器中,允許在來自各個分支的錯誤之間進行選擇(或累積它們)
    fn or(self, other: Self) -> Self {
        other
    }
}

也可以實現ContextError特徵來支持 VerboseError<I> 使用的 context() 组合器。

下面通過一個簡單的例子來介紹其用法,這裡會定義一個調試錯誤類型,做到每次生成錯誤時打印額外信息:

use nom::error::{ContextError, ErrorKind, ParseError};

#[derive(Debug)]
struct DebugError {
    message: String,
}

impl ParseError<&str> for DebugError {
    // 打印出具體錯誤的解析器類型
    fn from_error_kind(input: &str, kind: ErrorKind) -> Self {
        let message = format!("【{:?}】:\t{:?}\n", kind, input);
        println!("{}", message);
        DebugError { message }
    }

    // 若遇到組合器的多個錯誤則打印出其他上下文信息
    fn append(input: &str, kind: ErrorKind, other: Self) -> Self {
        let message = format!("【{}{:?}】:\t{:?}\n", other.message, kind, input);
        println!("{}", message);
        DebugError { message }
    }

    // 打印出具體期望的字符
    fn from_char(input: &str, c: char) -> Self {
        let message = format!("【{}】:\t{:?}\n", c, input);
        print!("{}", message);
        DebugError { message }
    }

    fn or(self, other: Self) -> Self {
        let message = format!("{}\tOR\n{}\n", self.message, other.message);
        println!("{}", message);
        DebugError { message }
    }
}

impl ContextError<&str> for DebugError {
    fn add_context(_input: &str, _ctx: &'static str, other: Self) -> Self {
        let message = format!("【{}「{}」】:\t{:?}\n", other.message, _ctx, _input);
        print!("{}", message);
        DebugError { message }
    }
}
  1. 調試解析器

編寫解析器的過程中,若需要跟踪解析器的執行過程信息,可通過dbg_dmp函數來打印出解析器的輸入和輸出:

fn f(i: &[u8]) -> IResult<&[u8], &[u8]> {
    dbg_dmp(tag("abcd"), "tag")(i)
}

let a = &b"efghijkl"[..];

// Will print the following message:
// tag: Error(Error(Error { input: [101, 102, 103, 104, 105, 106, 107, 108], code: Tag })) at:
// 00000000        65 66 67 68 69 6a 6b 6c         efghijkl
f(a);

總結#

通過這篇文章我們基本了解了解析器的前置知識(Parser、PEG 和 Parser Combinator)和如何使用 Rust 實現解析器需要的三方庫( pest 和 nom)。而無論是基於 PEG 實現的 pest 還是基於 Parser Combinator 實現的 nom,都能滿足實現自定義解析器的通用場景,都不需要再從零到一的手寫解析器了,這使自定義解析器的實現成本大大降低。若考慮更加複雜的情況(如性能、實現成本、使用文檔等因素),就需要根據具體的場景來選擇相應的三方庫進行實現。

下篇文章我們就會分別用到 pest 和 nom 來實現幾個常見的解析器,以此來更好地掌握解析器的視線。

參考#

https://zhuanlan.zhihu.com/p/427767002

https://zh.wikipedia.org/wiki/%E8%A7%A3%E6%9E%90%E8%A1%A8%E8%BE%BE%E6%96%87%E6%B3%95

https://zhuanlan.zhihu.com/p/355364928

https://ohmyweekly.github.io/notes/2021-01-20-pest-grammars/#

https://pest.rs/book/parser_api.html

https://rustmagazine.github.io/rust_magazine_2021/chapter_4/nom_url.html

https://tfpk.github.io/nominomicon/chapter_1.html

載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。