一直是阵雨

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

背景#

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

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

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

注意：

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

前提知識#

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

パーサー#

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

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

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

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

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

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

PEG#

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

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

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

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

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

次に、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 を使用して実現されたパーサージェネレーターは、特定の構文ルールを使用してパーサーを記述し、表現能力は構文ルールに制約されます。つまり、パーサージェネレーターのインターフェースを使用するだけでなく、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 型を提供しており、以下のように使用されます：

• どのルールがペアを生成したかを特定する
• ペアを元の & str として使用する
• ペアを生成した内部命名ルールを確認する

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::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 メソッド

派生した 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+      // 1つ以上の'0'から'9'の文字

// マッチプロセス
"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(
                                   │      パーサーが触れなかった内容,
                                   │      正規表現にマッチした内容
                                   │   )
             ┌─────────┐           │
 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