一直是阵雨

この文書の内容は、検索用に Feishu 文書からコピーされたもので、内容のフォーマットが互換性がない場合があります。元のFeishu 文書を参照することをお勧めします。

背景#

最近、mbrubeckさんが書いたRobinsonに従って、Rust を使ってシンプルなブラウザエンジンを作成することを学んでいます（後で書き終えたら、文書を作成して紹介します）。その過程で、HTML、CSS などのフォーマットファイルを解析する必要があるため、関連するパーサーを作成する必要があります。

0 から 1 の手書きパーサーは非常に退屈で間違いやすい作業です。なぜなら、具体的に解析する必要があるプロトコルのルールを考慮するだけでなく、パーサーのエラーハンドリング、拡張性、解析性能なども考慮する必要があるからです。そのため、記事の中でも、現在存在する pest などのサードパーティライブラリを使用して最適化することをお勧めします。

私の日常の開発作業を振り返ると、パーサーを構築する必要があるシーンは少なく、通常、JSON、CSV などのフォーマットやプロトコルの情報を解析する必要がある場合、効率を追求して、そのフォーマットやプロトコルに特化したサードパーティライブラリを直接使用します。しかし、実際にはすべてのプロトコルやフォーマットに他の人が書いたパーサーがあるわけではありません。特にさまざまなネットワーク通信プロトコルなどに関しては、書かれたパーサーもカスタマイズが非常に難しいため、この機会を利用して、パーサーを学び、パーサーを構築する関連実践を理解し、今後似たようなシーンでの使用を便利にすることができます。

注意：

• この文書では、パーサーやパーサーライブラリの関連原理を深く掘り下げることはありません。主に「パーサー入門の理解と実践」についてです。
• このシリーズの文書は上下 2 篇に分かれており、上篇ではパーサーの理解とサードパーティライブラリの使用について、下篇では具体的な実践について説明します。
• このシリーズの文書に登場するソースコードは、https://github.com/catwithtudou/parser_toy で確認できます。

前提知識#

以下では、パーサーに関連する前提知識をいくつか紹介し、後の理解を助けます。

パーサー#

ここで言うパーサー（Parser）は、実際にはより広い定義であり、通常は特定のフォーマットの情報を特定のデータ構造に変換するコンポーネントを指します。

あるフォーマットの情報を「デコード」し、整理されたデータ構造情報に抽象化して、情報の理解と処理を容易にすることに似ています。

例を挙げると、算数の表現式のテキスト "1 + 2" があり、プログラムを通じて結果を計算できることを期待しています。

プログラムが算術表現を認識できるようにするために、算術表現のパーサーを通じて (left,op,right) の構造体に変換して計算します。

コンピュータ分野において、データ処理の過程でパーサーは不可欠であり、さまざまなデータ処理シーンで応用できます。例えば、一般的なものとして：

• 低レベルのコンパイラやインタプリタのパーサーは、主にソースコードを構文解析し、抽象構文木 AST を抽出する役割を果たします。
• Web アプリケーションでよく使用されるデータ交換フォーマット JSON のテキストは、対応するパーサーを通じて必要なデータ構造をシリアライズして処理します。
• その他、ネットワーク通信プロトコル、スクリプト言語、データベース言語などを解析するためのパーサーを使用します。

PEG#

PEG（Parsing Expression Grammar）を紹介する前に、（仮定として）より一般的な正規表現を使って理解を深めることができます。

正規表現と PEG の関係は、文字テキストを処理する際に特定の構文を使用して文字テキストをマッチングおよび解析する点で共通していますが、異なる点は以下の通りです：

• 【構文面】前者は文字列のパターンを記述するための特定の構文を使用し、通常は単純な文字列マッチングや検索に使用されます。一方、後者はより複雑な構文を使用して言語構造を記述し、通常は複雑な言語解析や分析のニーズに使用されます。
• 【応用分野】前者は主に単純なテキスト処理のニーズに使用され、特定のパターンのテキストを検索したり、入力フォーマットを検証したりします。一方、後者は複雑な言語構造を処理するために使用され、プログラミング言語の構文解析やインタプリタの構築に使用されます。

紹介を通じて、皆さんは PEG について簡単に理解できたと思います。

なぜ PEG を紹介するかというと、PEG を使用して実現できるツール（Parser Generator と呼ばれる）を通じてカスタマイズされたパーサーを実現できるからです。

次に、PEG（Parsing Expression Grammar）について簡単に正式に紹介します：

1. PEG（Parsing Expression Grammar）概要

Parsing Expression Grammarの略称はPEG（英語：Parsing Expression Grammar）：

• 解析型の形式文法です。2004 年に Bryan Ford によって提案され、1970 年代に導入されたトップダウン構文解析言語のファミリーに関連しています。
• 言語構造を記述するための構文として、正規表現よりもより複雑な言語構造を処理でき、再帰的な特徴により無限にネストされた構造を記述できます。
• シンプルで柔軟な方法で構文ルールを定義し、そのルールを使用して入力文字列を解析し、構文木を生成できます。
• 使いやすさ、正確性、性能の利点があり、エラーレポート、再利用可能なルールテンプレートなどの機能を提供するため、テキストの解析や分析に広く使用されています。

1. PEG の応用概要

PEG の構文はプログラミング言語に似ており、演算子とルールを使用して言語構造を記述します：

• 演算子には「|」（または）、「&」（および）、「？」（オプション）などが含まれ、ルールは言語の具体的な構造を記述するために使用されます。

• 例えば、以下は整数の構文を記述したシンプルな PEG ルールです：

  Copy

  int := [0-9]+
  

効率的なパーサーコードに直接変換できるため、現在では多くの低レベルで PEG を使用して実現されたパーサーが存在します。例えば、ANTLR、PEG.js などです。

パーサーコンビネーター#

前述のパーサーについての理解を通じて、パーサーコンビネーター（Parser Combinator）を理解するのは比較的容易です。

1. パーサーコンビネーターの定義と思想

簡単に言うと、パーサーコンビネーターはさまざまなパーサーコンポーネントを組み合わせて構築されたコンポーネントです。

パーサーコンビネーターの考え方はソフトウェア工学に非常に適しており、関数の組み合わせに基づいてパーサーを構築する技術です。小さく、再利用可能で、テスト可能なパーサーコンポーネントを組み合わせて複雑なパーサーを構築することで、パーサーの構築をより柔軟で拡張可能にし、開発の効率を大幅に向上させ、後のメンテナンスを容易にします。

1. パーサーコンビネーターとパーサージェネレーター

パーサーコンビネーターは、前述のパーサージェネレーターと平行の概念です。ここで例を挙げます：

• 実現したいパーサー（例えば JSON パーサー）を大きなビルと見なすとします。
• パーサージェネレーターを使用して構築すると、ほぼ毎回ゼロからそのビルを構築することになります。ビルとビルの間の類似部分（ドアや窓など）は再利用できません。
• 一方、パーサーコンビネーターを使用すると、レゴブロックを組み立てるように小さく、再利用可能で、テスト可能なコンポーネントを構築し、それらのコンポーネントを使用してビルを構築します。新しいビルを構築する際には、以前に作成したコンポーネントを使用することができ、非常に便利です。また、パーサーに問題が発生した場合、特定のコンポーネントに容易に特定でき、後のメンテナンスも便利です。

1. パーサーコンビネーターと PEG を使用して実現されたパーサージェネレーター

【表現面】パーサーコンビネーターは、表現能力がより柔軟で、プログラミング言語の特性を直接使用してパーサーを組み合わせて定義できます。一方、PEG を使用して実現されたパーサージェネレーターは、特定の構文ルールを使用してパーサーを記述し、表現能力は構文ルールに制約されます。つまり、Parser Generator 自体のインターフェースを使用する方法を学ぶ必要があり、PEG の構文ルールも習得する必要があります。

【性能面】パーサーコンビネーターとパーサージェネレーターの性能比較は、具体的な実装や使用シーンによって異なります。しかし、一般的に言えば、パーサージェネレーターは通常効率的なパーサーコードを生成します。そのため、大規模な構文や複雑な入力を処理する際には、より良い性能を持つ可能性があります。一方、パーサーコンビネーターは通常、実行時に動的にパーサーを組み合わせるため、一定の性能オーバーヘッドがあります。

ただし、現在 Rust では、パーサーコンビネーターを使用して実現された nom と、PEG を使用して実現された pest の間で、前者の方が性能が高いです。

Rust パーサーライブラリ#

以下では、Rust でパーサーを実現するための古典的なサードパーティライブラリ、PEG ベースの Pest とパーサーコンビネーターの Nomを紹介します。

pest#

概要#

Pest は、Rust で書かれた汎用パーサーであり、可用性、正確性、性能に重点を置いています。前述のPEG を入力として使用し、複雑な言語を解析するために必要な強化された表現能力を提供し、カスタムパーサーを構築するために簡潔で優雅な方法で定義および生成します。

自動生成エラーレポート、derive 属性を通じてパーサートレイトの実装を自動生成する機能、単一ファイル内で複数のパーサーを定義する機能なども備えています。

使用例#

1. cargo.toml に pest 依存関係を追加

[dependencies]
pest = "2.6"
pest_derive = "2.6"

1. 新しくsrc/grammar.pestファイルを作成し、解析表現の構文を記述

ここでの構文は、フィールドの解析ルールを示しており、各文字が 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);
    }
}    

具体的な使用#

公式文書

パーサー API#

pest は、成功した解析結果にアクセスするためのさまざまな方法を提供しています。以下の構文例に従ってその方法を紹介します：

number = { ASCII_DIGIT+ }                // 1つ以上の10進数字
enclosed = { "(.." ~ number ~ "..)" }    // 例えば、"(..1024..)"
sum = { number ~ " + " ~ number }        // 例えば、"1024 + 12"

1. トークン

pest は、成功を表すトークンを使用します。ルールがマッチすると、マッチした開始位置と終了位置を表す 2 つのトークンが生成されます。例えば：

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

現在、rustrover には pest フォーマットをサポートするプラグインがあり、ルールを検証したり、トークンを表示したりする機能があります。

1. ネストされたルール

ある命名ルールが別の命名ルールを含む場合、両者のトークンが生成されます。以下のように両者を示します：

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

同時に、特定のシーンでは、マークが異なる文字位置に現れない場合があります：

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

1. インターフェース

トークンは 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);
}

1. ペア

マッチしたトークン対を考慮して解析ツリーを探索する場合、pest は Pair 型を提供しており、以下のように使用されます：

• どのルールが 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. 解析メソッド

派生した Parser は、Result<Paris,Error> を返す parse メソッドを提供し、底層の解析ツリーにアクセスするには、結果を match または unwrap する必要があります：

// 解析が成功したかどうかを確認
match Parser::parse(Rule::enclosed, "(..6472..)") {
    Ok(mut pairs) => {
        let enclosed = pairs.next().unwrap();
        // ...
    }
    Err(error) => {
        // ...
    }
}

解析表現の構文#

PEG の基本的な論理は非常にシンプルで直接的であり、以下の 3 つのステップに要約できます：

• ルールのマッチを試みる
• 成功した場合、次のステップを試みる
• 失敗した場合、別のルールを試みる

その構文の特徴は以下の 4 点です：

1. 貪欲性

入力文字列上で繰り返し PEG 表現を実行すると、貪欲に（できるだけ多く）実行され、その結果は以下のようになります：

• マッチが成功した場合、マッチした内容を消費し、残りの入力を解析器の次のステップに渡します。
• マッチが失敗した場合、何の文字も消費せず、その失敗が伝播し、最終的に解析が失敗します。失敗が伝播中に捕捉されない限り。

// 表現
ASCII_DIGIT+      // '0'から'9'の1つ以上の文字

// マッチプロセス
"42 boxes"
 ^ Running ASCII_DIGIT+

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

" boxes"
 ^ Remaining unparsed input.

1. 順序付き選択

構文には順序付き選択演算子|が存在し、例えばone|twoは、最初に前者 one を試み、失敗した場合に後者 two を試みます。

順序が要求される場合、ルールを表現内の位置に配置する必要があります。例えば：

• 表現"a"|"ab"では、文字列 "abc" をマッチする際、前のルール"a"にヒットすると、後の "bc" を解析しなくなります。

そのため、選択的なパーサーを作成する際には、最も長いまたは具体的な選択を前に置き、最も短いまたは一般的な選択を最後に置くことが一般的です。

1. 非バックトラッキング

解析プロセス中、表現は成功するか失敗するかのいずれかです。

成功した場合は次のステップに進み、失敗した場合は表現が失敗し、エンジンは後退して再試行しません。これは、バックトラッキングを持つ正規表現とは異なります。

以下の例を見てみましょう（ここで~は、前のルールがマッチした後に実行される次のステップを示します）：

word = {     // 単語を認識するために...
    ANY*     //   任意の文字を0回以上取得...
    ~ ANY    //   任意の文字の後
}

"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 文字を後退して再試行します。

1. 明確性

PEG の各ルールは、入力文字列の残りの部分で実行され、できるだけ多くの入力を消費します。一度ルールが完了すると、残りの入力は解析器の他の部分に渡されます。例えば、表現ASCII_DIGIT+は 1 つ以上の数字をマッチすることを示し、常に可能な最大の連続数字のシーケンスをマッチします。意図しない形で後のルールがバックトラックすることはなく、直感的で非局所的な方法で数字を盗むような危険な状況はありません。

これは、他の解析ツール（正規表現や CFG など）とは対照的であり、これらのツールでは、ルールの結果はしばしば距離のあるコードに依存します。

パーサー構文と内蔵ルール#

1. 重要な構文

pest の構文は正規表現に比べて少ないですが、以下に主要な構文とその意味を簡単に示します。詳細については自分で検索してください：

1. 内蔵ルール

ANYの他に、pest は非常に多くの内蔵ルールを提供し、テキストの解析をより便利にします。ここでは主にいくつかの一般的なルールを示します。詳細は自分で調べてください：

nom#

概要#

nom は、前述のパーサーコンビネーター（Parser Combinator）ライブラリで、Rust で書かれています。以下の特徴があります：

• スピードやメモリ消費に影響を与えずに安全なパーサーを構築します。
• Rust の強力な型システムとメモリ安全性を活用して、正確で効率的なパーサーを生成します。
• 関数、マクロ、特徴を提供して、エラーが発生しやすいパイプラインの大部分を抽象化し、同時にパーサーを簡単に組み合わせて再利用して複雑なパーサーを構築できます。

nom は、非常に広範なアプリケーションシーンをサポートしており、以下の一般的なシーンが含まれます：

• バイナリフォーマットパーサー：nom の性能は、C 言語で手書きされたパーサーと同じくらい速く、バッファオーバーフローの脆弱性の影響を受けず、一般的な処理パターンが組み込まれています。
• テキストフォーマットパーサー：CSV やより複雑なネストされたフォーマット JSON などを処理でき、データを管理できるだけでなく、複数の便利なツールが組み込まれています。
• プログラミング言語パーサー：nom は言語のプロトタイプパーサーとして機能し、カスタムエラータイプとレポートをサポートし、空白を自動的に処理し、AST をその場で構築します。
• 上記のシーンの他にも、ストリーミングフォーマット（HTTP ネットワーク処理など）、ソフトウェア工学により適したパーサーコンビネーターなどがあります。

使用例#

ここでは、nom リポジトリの README に提供されている「16 進数カラー解析器」の例を紹介します：

ここで説明する 16 進数カラーの具体的なフォーマットは：

• "#" で始まり、その後に 6 文字が続き、各 2 文字が赤、緑、青の 3 つの色チャネルの値を表します。

例えば、"#2F14DF" では、"2F" が赤色チャネルの値、"14" が緑色チャネルの値、"DF" が青色チャネルの値を表します。

1. cargo.toml に nom 依存関係を追加

[dependencies]
nom = "7.1.3"

1. 新しくsrc/nom/hex_color.rsを作成し、nom をインポートして 16 進数カラーの解析メソッドhex_colorを構築

• tagは先頭の文字パターンをマッチし、tag("#")は関数を返し、その戻り値はIResult<Input,Input,Error>です。
  • ここでInputは関数の入力パラメータタイプであり、最初の値はマッチパターンを除いた入力値、2 番目はマッチ内容、最後はエラー値です。
• nom が提供するtake_while_m_nメソッドは、最小と最大のマッチ数を前の 2 つのパラメータとして受け取り、最後のパラメータはマッチルールであり、上記と似たような戻り値を返します。
• nom が提供するmap_resメソッドは、最初のパラメータから得られた結果を、2 番目のパラメータのパターンに従って変換できます。
• 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()
}

// 文字列を10進数の結果に変換
pub fn to_num(input: &str) -> Result<u8, std::num::ParseIntError> {
    u8::from_str_radix(input, 16)
}

// is_hex_digitルールに従って入力を2文字ごとにマッチし、結果をto_hex_numで10進数に変換
pub fn hex_primary(input: &str) -> IResult<&str, u8> {
    map_res(
        take_while_m_n(2, 2, is_hex_digit),
        to_num,
    )(input)
}

// 16進数カラーのパーサー
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,
        })))
    }
}

具体的な使用#

パーサー結果#

前述の例で見た nom 解析メソッドの戻り値IResultは、nom のコア構造の 1 つであり、nom 解析の戻り結果を表します。

まず、nom が構築したパーサーは、解析された結果を以下のように定義します：

• Ok(...)は解析が成功した後に見つかった内容を示し、Err(...)は解析が対応する内容を見つけられなかったことを示します。
• 解析が成功した場合、戻り値はタプルで、最初の値は解析器がマッチしなかったすべての内容を含み、2 番目の値は解析器がマッチしたすべての内容を含みます。
• 解析が失敗した場合、複数のエラーが返される可能性があります。

                                   ┌─► 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 トレイトを実装した任意のタイプです。

タグと文字クラス#

1. タグバイト集合タグ

nom は、単純なバイト集合をタグと呼びます。これらは非常に一般的であるため、tag()関数が内蔵されており、指定された文字列のパーサーを返します。

例えば、文字列 "abc" を解析したい場合、tag("abc")を使用できます。

注意が必要なのは、nom には異なるタグ定義が複数存在し、特に説明がない限り、通常は以下の定義を使用して、意図しないエラーを避けるべきです：

Copy

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

tag関数のシグネチャは以下のようになります。tagは関数を返し、その関数はパーサーであり、&strを取得し、IResultを返します：

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. 文字クラス

タグは先頭のシーケンスの文字にのみ使用できるため、nom は事前に書かれた解析器、すなわち文字クラスと呼ばれるものを提供しています。これにより、任意の文字のセットのいずれかを受け入れることができます。以下は、よく使用される内蔵解析器のいくつかを示します：

以下は、どのように使用するかを示す簡単な例です：

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");
}

選択肢と構成#

1. 選択肢

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. 構成

複数の解析器の選択に加えて、解析器を組み合わせることも非常に一般的な要求であるため、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_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 は以下のような類似の操作を持つ解析器をサポートしています。

カスタム戻り値を持つパーサー#

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());
}

繰り返し述語とパーサー#

1. 述語による繰り返し

ここでの述語は、特定の条件を満たすために繰り返し解析器を処理する機能を満たすために、nom はいくつかの異なるカテゴリの述語解析器を提供しています。主にtake_till、take_until、take_whileの 3 つのカテゴリがあります：

ここで補足として、上記のコンビネーターには「双子」が存在し、名前の末尾に1が付いています。これは、少なくとも 1 つのマッチ文字を返す必要があることを示し、そうでない場合はエラーが発生します。
前述のtake_while_m_nは、実際にはtake_whileに似ており、特定の[m,n]バイトを消費することを保証します。

1. 繰り返しパーサー

単一の解析器の繰り返しに加えて、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![])));
}

以下に、一般的に使用されるコンビネーターをいくつか示します：

エラーマネジメント#

nom のエラーは、さまざまなニーズを考慮して設計されています：

• どの解析器が失敗したか、入力データ内の位置を示す
• エラーが解析器チェーンを上に伝播する際に、より多くのコンテキストを蓄積する
• 通常、解析器を呼び出す際にエラーを破棄するため、非常に低いオーバーヘッド
• ユーザーのニーズに応じて変更可能で、特定の言語ではより多くの情報が必要です

これらのニーズを満たすために、nom 解析器の結果タイプは以下のように設計されています：

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

pub enum Err<E> {
    Incomplete(Needed),    // 解析器が決定を下すのに十分なデータがないことを示す。通常、ストリーミングシーンで遭遇します。
    Error(E),              // 通常の解析器エラー。例えば、altコンビネーターの子解析器がErrorを返すと、他の子解析器を試みます。
    Failure(E),            // 回復不可能なエラー。例えば、子解析器がFailureを返すと、altコンビネーターは他の分岐を試みません。
}

1. nom::Err<E>の中で一般的なエラータイプ

• デフォルトのエラータイプnom::error::Errorは、具体的にどの解析器のエラーであるか、エラーの入力位置を返します。

  Copy

    #[derive(Debug, PartialEq)]
    pub struct Error<I> {
      /// 入力データ内のエラーの位置
      pub input: I,
      /// nomエラーコード
      pub code: ErrorKind,
    }
  

  • このエラータイプは速度が速く、オーバーヘッドが低いため、繰り返し呼び出される解析器に適していますが、機能は限られています。例えば、呼び出しチェーン情報は返されません。

• より多くの情報を取得するためにnom::error::VerboseErrorを使用すると、エラーが発生した解析器チェーンのより多くの情報（解析器のタイプなど）を返します。

  Copy

    #[derive(Clone, Debug, PartialEq)]
    pub struct VerboseError<I> {
      /// `VerboseError`によって蓄積されたエラーのリスト。影響を受けた入力データの部分といくつかのコンテキストを含む
      pub errors: crate::lib::std::vec::Vec<(I, VerboseErrorKind)>,
    }
    
    #[derive(Clone, Debug, PartialEq)]
    /// `VerboseError`のエラーコンテキスト
    pub enum VerboseErrorKind {
      /// `context`関数によって追加された静的文字列
      Context(&'static str),
      /// `char`関数によって期待される文字を示す
      Char(char),
      /// 様々なnomパーサーによって与えられたエラーの種類
      Nom(ErrorKind),
    }
  

  • 元の入力とエラーのチェーンを確認することで、よりユーザーフレンドリーなエラーメッセージを構築できます。nom::error::convert_error関数を使用すると、このようなメッセージを構築できます。

1. ParseError トレイトによるカスタムエラータイプ

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"[..];

// 次のメッセージが印刷されます：
// 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);

まとめ#

この記事を通じて、私たちは基本的にパーサーの前提知識（パーサー、PEG、パーサーコンビネーター）と、Rust でパーサーを実現するために必要なサードパーティライブラリ（pest と nom）の使用方法を理解しました。PEG を使用して実現された pest でも、パーサーコンビネーターを使用して実現された 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