Markdown パーサを書きたい！～パーサコンビネータ編～

この記事は某企業2024年度新卒Advent Calender 2024 3 日目の記事です。

ある日突然パーサ書いてみたいなぁという脳の声が聞こえたので、 Markdown パーサを書いてみたいと思います。
しかし私はパーサを作ったことがなければ、知識もないので一旦調べてみました。
調べていくなかで、「パーサコンビネータ」というワードに目が止まります。

なにこれかっこええやん

ということでパーサコンビネータを使って Markdown パーサを書くことを目指します。
その第 1 回として本記事はパーサコンビネータを作ってみる記事となっています。

パーサコンビネータとは

パーサコンビネータとはなんぞやと調べてみると、英語 wikiにはこう書いてあります。

In computer programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output.

訳すと以下のようになります。

コンピュータプログラミングにおいて、パーサコンビネータはいくつかのパーサを入力として受け取り、新しいパーサを出力として返す高階関数です。

ほうほう、なるほどと。
じゃあパーサはどういったものなのかというと次の文章に書いてあります。

In this context, a parser is a function accepting strings as input and returning some structure as output, typically a parse tree or a set of indices representing locations in the string where parsing stopped successfully.

訳すと

この文脈では、パーサはある文字列を入力として受け取り、なんらかの構造を出力として返します。この構造は通常パースツリー（解析ツリー）または解析が正常に停止した文字列の位置を表すインデックスのセットです。

となります。
じゃあつまりパーサは

Parser: (text: String) -> Structure

ということで、パーサコンビネータは

ParserCombinator: (parser1: Parser, parser2: Parser, ...) -> Parser

ということですかね。
これは小さなパーサを組み合わせて大きなパーサを作るということのようです。
高階関数というワードも出てきているあたり、関数型プログラミングにも関わっていそうです。

wiki には理論的なことも色々書いてありますが、いったんよくわからないので上に書いた定義を元に作ってみたいと思います。

パーサコンビネータを作ってみる

今回使用する言語は、私が今勉強中の Rust で書いていこうと思います。
私は Rust についても初心者ではあるので、これも調べながらやっていこうと思います。

作るうえで色々知識が不足しているので、 Rust でパーサコンビネータを作ってみる (前編) こちらの記事をかなり参考にさせていただいています。

パーサを定義

ではまず、パーサがどいういったものなのかを定義します。
先ほどパーサは文字列を何かしらの構造に変換するものとありました。
これをコードに落とし込んでみます。

trait Parser<T>: Fn(&str) -> T {}

でしょうか。
ただ、パーサはパースに失敗する場合があります。
ですので

trait Parser<T>: Fn(&str) -> Option<T> {}

となります。
そしてパーサは先頭の文字列から順次解析していくので、解析が終わった位置を知る必要があります。
なので、パースが終わった残りの部分を返すとして

trait Parser<T>: Fn(&str) -> Option<(T, &str)> {}

これをパーサとして定義します。
ではこちらを使って少しパーサを作ってみます。

まずは特定の 1 文字とマッチするパーサを作る character を作ります。

fn character(c: char) -> impl Parser<()> {
    move |input: &str| {
        if input.starts_with(c) {
            Some((), &input[c.len_utf8()..])
        } else {
            None
        }
    }
}

#[test]
fn test_character() {
    let parser = character('a');
    let parser_utf8 = character('あ');

    assert_eq!(parser("abc"), Some(((), "bc")));
    assert_eq!(parser("def"), None);
    assert_eq!(parser_utf8("あいう"), Some((), "いう"));
    assert_eq!(parser_utf8("えおか"), None);
}

character('a')はaという文字にマッチするというパーサを生成する高階関数になっています。
生成したパーサはパースする文字列を入力して、ある構造（今回は生成するものがないので空となっています）とマッチした部分の残りを出力するようになっています。
これはテスト部分を見るとわかるかと思います。

こんな感じで特定の文字列にマッチするstringを作ってみます。

fn string<'a>(s: &'a str) -> impl Parser<()> + 'a {
    move |input: &str| {
        if input.starts_with(s) {
            Some(((), &input[s.len()..]))
        } else {
            None
        }
    }
}

#[test]
fn test_string() {
    let parser = string("abc");
    let parser_utf8 = string("あいう");

    assert_eq!(parser("abcdef"), Some(((), "def")));
    assert_eq!(parser("def"), None);
    assert_eq!(parser_utf8("あいう"), Some(((), "")));
    assert_eq!(parser_utf8("あいうえお"), Some(((), "えお")));
}

characterの場合と同じ感じですね。
これらのパーサがパーサコンビネータの部品となります。
ただ、これだけではMarkdownをパースできるパーサを作ることは難しいです。
これらを組み合わせることで複雑なパーサを作ります。

ですので次はパーサを組み合わせることをやっていきます。

パーサを組み合わせる

characterやstringはただ文字列にマッチするだけで、何も出力していません。
パーサでは最終的にパースした結果（構文木）を出力する必要があります。
ですので、ある文字列にマッチしたとき、何かを出力するという関数が必要になります。
この関数がmapです。

ではこのmapをParserのメソッドとして作ってみます。

trait Parser<T>: Fn(&str) -> Option<(T, &str)> {
    fn map<U>(self, f: impl Fn(T) -> U) -> impl Parser<U>;
}

impl<T, F> Parser<T> for F
where
    F: Fn(&str) -> Option<(T, &str)>
{
    fn map<U>(self, f: impl Fn(T) -> U) -> impl Parser<U> {
        move |input: &str| self(input).map(|(t, rest| (f(t), rest)))
    }
}

#[test]
fn test_map() {
        let parser = character('a').map(|_| 1);

        assert_eq!(parser("abc"), Some((1, "bc")));
        assert_eq!(parser("def"), None);
        assert_eq!(parser(""), None);
    }

mapは他の言語でもある配列なんかの要素を別の要素に変えるアレです。
今回はそのパーサバージョンと言う感じですね。
パーサバージョンでは前段のパーサがパースに成功したとき、mapの引数で受け取った関数を適用するといった感じになります。
内部実装ではOptionのmapを使っていますね。

テストをみると、'a'にマッチしたとき、1を出力するパーサを作れています。
ということでなにかの文字列にマッチしたとき任意の出力ができるようになりました。

まだこれだけではMarkdownのパーサを作ることは難しいので、次にパーサ同士を組み合わせるorとandを作っていきます。

trait Parser<T>: Fn(&str) -> Option<(T, &str)> {
    fn or(self, other: impl Parser<T>) -> impl Parser<T>;
    fn and<U>(self, other: impl Parser<U>) -> impl Parser<(T, U)>;
}

impl<T, F> Parser<T> for F
where
    F: Fn(&str) -> Option<(T, &str)>
{
    fn or(self, other: impl Parser<T>) -> impl Parser<T> {
        move |input: &str| self(input).or(other(input))
    }

    fn and<U>(self, other: impl Parser<U>) -> impl Parser<(T, U)> {
        move |input: &str| {
            self(input).and_then(|(t, rest)| other(rest).map(|(u, rest)| ((t, u), rest)))
        }
    }
}

#[test]
fn test_or() {
    let parser = character('a').or(character('b'));

    assert_eq!(parser("abc"), Some(((), "bc")));
    assert_eq!(parser("bcd"), Some(((), "cd")));
    assert_eq!(parser("def"), None);
    assert_eq!(parser(""), None);
}

#[test]
fn test_and() {
    let parser = character('a').and(character('b').map(|_| 1));

    assert_eq!(parser("abc"), Some((((), 1), "c")));
    assert_eq!(parser("def"), None);
    assert_eq!(parser(""), None);
}

orのテストを見ると、character('a')のパーサとcharacter('b')のパーサの2つを組み合わせて、'a'または'b'にマッチするようなパーサを作っています。
また、andのテストでは、character('a')のパーサとcharacter('b').map(|_| 1)のパーサの2つを組み合わせて、"ab"という文字が出てきたら((), 1)を出力するパーサを作っています。
（string("ab").map(|_| 1)でええやんと思ったあなた、正解です）

パーサコンビネータではこれらのor、and、mapを使って小さいパーサを組み合わせて、複雑なパーサを作っていくんですね。
あとは部品となるパーツやそれを手助けするヘルパー関数を作ります。

便利関数を作る

trim_ws

Markdownのパースをするとき、空白を読み飛ばしたいときがよくあります。
その関数を作ります。

fn trim_ws<T>(parser: impl Parser<T>) -> impl Parser<T> {
    move |input: &str| parser(input.trim_start())
}

これで先頭の空白を読み飛ばしてパーサに入力できます。

many, many1

パースにおいて繰り返しが必要になることがあります。
そのヘルパー関数を作ります。

fn many<T>(parser: impl Parser<T>) -> impl Parser<Vec<T>> {
    move |mut input: &str| {
        let mut result = Vec::new();
        while let Some((t, rest)) = parser(input) {
            result.push(t);
            input = rest;
        }
        Some((result, input))
    }
}

fn many1<T>(parser: impl Parser<T>) -> impl Parser<Vec<T>> {
    move |input: &str| {
        let (t, rest) = parser(input)?;
        let mut result = vec![t];
        let mut input = rest;
        while let Some((t, rest)) = parser(input) {
            result.push(t);
            input = rest;
        }
        Some((result, input))
    }
}

manyは0回以上の繰り返し、many1は1回以上の繰り返しで、パースに成功する限りパースを続ける関数となっています。
パースした結果はVecに保存されます。

regex

パースで正規表現が使えるとかなり便利になります。
この関数はRust でパーサコンビネータを作ってみる (前編)こちらで紹介されていたものです。

fn regex<'a, T>(pattern: &'a Regex, f: impl Fn(&str) -> Option<T> + 'a) -> impl Parser<T> + 'a {
    move |input| {
        pattern
            .find(input)
            .and_then(|m| f(m.as_str()).map(|t| (t, &input[m.end()..])))
    }
}

#[macro_export]
macro_rules! regex {
    ($pattern:expr, $f:expr) => {{
        use once_cell::sync::Lazy;
        use regex::Regex;
        static RE: Lazy<Regex> = Lazy::new(|| Regex::new($pattern).unwrap());
        $crate::parser_combinator::regex(&RE, $f)
    }};
}

まず、regex関数は正規表現のパターンと、正規表現にマッチしたとき適用する関数をとります。
マクロ版は正規表現のテンプレートを静的に定義することで、パースのたびにテンプレートを生成することを防いでいます。

おわりに

今回はMarkdownパーサを作るためのパーサコンビネータを作ってみました。
次回はこのパーサコンビネータを使って、実際にMarkdownパーサを構築してみます。

それでは。

参考文献