Rust 製パーサーコンビネータライブラリの Chumsky (v0.9.3) を使用して、自作のミニ言語を作成し、インタプリタを作ってみましょう。

GitHub - zesterer/chumsky: Write expressive, high-performance parsers with ease.

Write expressive, high-performance parsers with ease. - zesterer/chumsky

github.com

私は過去に TypeScript を使用してパーサーコンビネータをゼロから作る記事を書いています。パーサーコンビネータを自作しながら原理を詳しく知りたい方はこちらの記事もどうぞ。

TypeScript でゼロから作るパーサコンビネータ - blog.livewing.net

プログラミング言語などのコンピュータ言語を構文解析するパーサコンビネータを TypeScript で作ってみようと思います。既存のパーサライブラリは使用せず、すべて自作します。パーサコンビネータを実装した後、四則演算の式パーサや JSON パーサを作ってみます。 書いてみると、意外と簡単です。「関数型言語」という言葉に謎にビビっている人もレッツトライ。 パーサコンビネータとは 小さなパーサ関数を組...

blog.livewing.net

Chumsky の名前の由来は言語学の権威 Noam Chomsky から取っていると思いますが、 1 文字 typo しているみたいです。このことについてライブラリの作者は「こんな馬鹿げた名前をつけて Noam 氏に申し訳ない」と言っています。

My apologies to Noam for choosing such an absurd name.

chumsky/README2.md at main · zesterer/chumsky · GitHub

プロジェクトの準備

早速 cargo new でプロジェクトを作成していきましょう。

$ cargo new my-lang-runtime
$ cd my-lang-runtime

cargo add で chumsky (バージョン 0.9.3) をプロジェクトに追加します。 Cargo.toml に直接書いても OK です。現在は 0.9.3 が最新版ですが、 1.0.0 が開発進行中で、 API がかなり変わる予定です。

$ cargo add chumsky@0.9.3

Parser トレイトと Error トレイト

Chumsky において軸となる Parser トレイトから見ていきましょう。定義は以下の通りです。

pub trait Parser<I: Clone, O> {
    // 実装必須の Associated Type
    type Error: chumsky::error::Error<I>;

    // 35 個の Provided Methods

    // fn parse(...) -> ... { ... }

    // fn map(...) -> ... { ... }
    // fn foldl(...) -> ... { ... }
    // fn foldr(...) -> ... { ... }
    // fn then(...) -> ... { ... }
    // fn or(...) -> ... { ... }
    // ...
}

このトレイトは、入力 I を受けとり、出力 O を出す関数を表すトレイトです。パーサー用途に特殊化された Fn トレイトのようなものと思ってください。入力が不正な値でエラーの場合は Error 型の値が出力のかわりに送出されます。

I はパーサーの入力の型であり、文字列をパースするパーサーの場合は char となります。 O は出力の型であり、これはパーサーによって異なります。例えば、数字をパースするパーサーなら i32 になったり、論理値をパースするパーサーなら bool になったり、たくさんのフィールドをまとめてパースするパーサーなら構造体になったりと、パーサーとコンビネータの組合せ次第で色々変化します。

Parser の Error には、パーサーのエラー型を指定します。 Chumsky 組み込みで Simple<T> と Cheap<T> がエラー型としてあらかじめ用意されています。 Simple<T> が標準的なエラー型で、 Cheap<T> が最軽量のエラー型となっています。 T が Hash + Eq を実装していて、独自のエラー型を実装しないのであれば Simple<T> を使うのが十分だと思います。

Provided Methods として、実際にパースを行う parse() 関数や、コンビネータである map() や foldl() などの関数が生えています。

ライブラリのユーザーがこの Parser トレイトを実装することはありません。 Chumsky で用意されているパーサー関数すべての戻り値が Parser トレイトを実装しているので、ユーザーは Provided Methods をコネコネするだけです。 I と O と Error はユーザーが指定する機会が多いので、これだけ覚えておきましょう。

このトレイトを頭の片隅に入れておきながら、実際にパーサーの使用方法を見ていきましょう。使ってみればトレイトの扱い方も分かるはず。

パーサーとコンビネータ

src/main.rs に Chumsky の prelude を use しましょう。

use chumsky::prelude::*;

any() プリミティブ

any() は任意の 1 文字を消費し、その文字を返すパーサー関数です。一番簡単な使用例を見てみましょう。

fn parser() -> impl Parser<char, char, Error = Simple<char>> {
    any()
}

fn main() {
    let source = "hello";
    let parsed: Result<char, Vec<Simple<char>>> = parser().parse(source);
    println!("{:?}", parsed);
    // => Ok('h')
}

まず parser() 関数の定義を見てみます。この関数は、引数を取らず、 Parser を実装する impl Trait を返す関数です。

型パラメータの最初の char は入力ストリームの要素の型で、今回の例だと文字型である char となります。 Rust の文字列を扱うパーサーであれば、ここは char となります。例えばバイナリを 1 バイトずつ扱うパーサーの場合、ここは u8 となります。

2 番目の型パラメータは出力を表しています。 parser() 関数はちょうど 1 文字パースする関数なので、 char となります。パース結果を変換するコンビネータを噛ませるなどすれば、自由自在に出力は変えられるので、ここの型指定は自由に指定できます。結果の変換については後述します。

3 番目の型パラメータ Error はエラーを表しています。 Chumsky 組み込みの Simple<char> を使いましょう。 Simple<char> で指定している型パラメータは入力の型です。よってここは char を指定します。

parser() 関数本体で Chumsky の any::<I, E>() 関数を呼んでいます。これで 1 文字をパースする関数が完成します。 any() 関数の戻り値は、 Parser<I, I> を実装する構造体です。型推論が効くので、 any::<I, E>() 関数の型パラメータを指定しなくても impl Parser<char, char, Error = Simple<char>> へ推論されます。

main() 関数内で parser() を呼び、 parse() 関数で実際にパースしています。パースが成功すれば、 Result::Ok がパース結果とともに返され、パースが失敗すれば Result::Err でエラーの Vec が返ります。

cargo run で実行しましょう。

$ cargo run

今回の例では Ok('h') が出力されます。シンプル。入力 source を変更して出力の変化を色々試してみてください。

「おい、 parse() 関数で 5 文字の "hello" って文字列渡してるじゃねーか！ 1 文字しかパースしないのにこれはエラーにならないのか？」という声が聞こえてきそうですが、 Chumsky は lazy なパーサーなので、残った他の文字列に関しては無視される仕様です。もちろん、「最後までパースしないとエラーになるパーサー」は end() パーサーを使用して定義できるので安心してください。後ほど紹介します。

当然、 any() だけではパーサーとして使い物にならないので、もっと他のプリミティブやコンビネータを見ていきましょう。

just() プリミティブ

just() は指定した文字や文字列のみパース成功するパーサーを定義します。例えば、文字列 "true" をパースするには以下のようにします。

fn parser() -> impl Parser<char, &'static str, Error = Simple<char>> {
    just("true")
}

fn main() {
    let source = "true";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

リテラル "true" の型は &'static str なので、 Parser の出力の型は &'static str となります。

これを実行すると Ok("true") が返ってきます。

さて、 "true" とくれば当然 "false" もパースしたくなりますよね。ここで or() コンビネータを使います。

or() コンビネータ

Chumsky の一部のコンビネータは Parser の Provided Methods として使用します。

fn parser() -> impl Parser<char, &'static str, Error = Simple<char>> {
    let true_literal = just("true");
    let false_literal = just("false");
    true_literal.or(false_literal)
}

fn main() {
    let source = "false";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

just() で作ったリテラルパーサーを let でバインドします。小さいパーサーはこのように名前を付けておきましょう。

パーサーに生えている or() を呼び出して、 true_literal と false_literal と繋ぎます。こうすると、 true_literal がパース成功した場合はその結果が、 true_literal がパース失敗した場合は false_literal の結果が返ります。

or() の呼び出し結果もまた Parser なので、さらに a.or(b).or(c) のようにメソッドチェーンを繋げて、 3 つ以上でも対応できます。

「"true" や "false" をパースするなら、結果を &'static str じゃなくて bool で寄越せや」という声がします。分かります。出力の変換、やりましょう。

to() コンビネータ

to() コンビネータを使うと、パースが成功したとき、出力を任意の定数値に変更することができます。

fn parser() -> impl Parser<char, bool, Error = Simple<char>> {
    let true_literal = just("true").to(true);
    let false_literal = just("false").to(false);
    true_literal.or(false_literal)
}

fn main() {
    let source = "false";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

to() を使用すると、パースが成功した場合、元の値に関わらず、出力を問答無用で指定した値に変えてしまします。今回は bool 型の値を指定したので、全体のパーサーの型は Parser<char, bool> となります。

類似のコンビネータとして map() があります。これは Iterator::map() と同じ感じで、パース結果を使用して値を変換することができます。後ほど紹介します。

ignored() コンビネータ

ignored() は to(()) と等価です。構文上は必要な文字だけどパース後のデータとしては必要ない場合に使用します。

filter() プリミティブ

最初に紹介した any() は任意の 1 文字をパースしますが、数字のみをパースしたかったり、小文字アルファベットのみをパースしたかったりする場面は当然あります。そんな時は filter() を使用して、特定の文字のみパースが成功するパーサーを作ることができます。

filter() を使用して、数字 1 文字をパースするパーサーを作ってみましょう。

fn parser() -> impl Parser<char, char, Error = Simple<char>> {
    filter(|c: &char| c.is_ascii_digit())
}

fn main() {
    let source = "5";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

filter() の引数に、パース成功する条件を書くことができます。ここでは標準ライブラリの char::is_ascii_digit() を使用して、 ASCII の数字のみパースが成功するようにしています。

今回は説明のために filter() の引数をクロージャを使用して冗長に書いていますが、もちろん以下のように書いても OK です。

fn parser() -> impl Parser<char, char, Error = Simple<char>> {
    filter(char::is_ascii_digit)
}

filter() は any() と同じく 1 文字しかパースしません。そのため単体では 2 桁以上の値はパースできません。当然解決策があり、 repeated() コンビネータを使えば、パーサーを任意の回数繰り返すことができます。使いましょう。

repeated() コンビネータ

repeated() を使うと、パーサー 0 回以上繰り返すパーサーを新しく作ることができます。出力は Vec<T> となります(ここで T は元のパーサーの出力型)。「0 回以上」なので、 0 回でも成功します。

fn parser() -> impl Parser<char, Vec<char>, Error = Simple<char>> {
    filter(char::is_ascii_digit).repeated()
}

fn main() {
    let source = "53位 ユウナのガード ワッカ";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

これを実行すると Ok(['5', '3']) となります。

「0 じゃなくて 1 回以上成功じゃないと困る」「ちょうど 3 文字じゃないとなぁ」

あります。 repeated() の返り値は Parser であるだけでなく、回数の制約を加えられる at_least() や at_most() や exactly() が追加で実装されているので、これを使いましょう。

fn parser() -> impl Parser<char, Vec<char>, Error = Simple<char>> {
    filter(char::is_ascii_digit).repeated().at_least(1)
}

「出力が String だったらなぁー Vec<char> じゃ嫌だなー」そんな時は collect() の出番です。

collect() コンビネータ

Iterator::collect() と同様、 FromIterator を実装するコンテナ型への変換は collect() コンビネータでできます。標準ライブラリに impl FromIterator<char> for String があるので、 collect() を呼び出せば一発で変換できます。 Turbofish ::<> で変換先の型を明示しておきます。もちろん、型推論が効くところは Turbofish が省略可能です。

fn parser() -> impl Parser<char, String, Error = Simple<char>> {
    filter(char::is_ascii_digit)
        .repeated()
        .at_least(1)
        .collect::<String>()
}

fn main() {
    let source = "53位 ユウナのガード ワッカ";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

結果は Ok("53") となります。

「String じゃなくて i32 でくれよ」となるので、先ほどチラっと紹介した map() で変換しましょう。

map() コンビネータ

map() を使用すると、パース結果を元に値を変換することができます。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    filter(char::is_ascii_digit)
        .repeated()
        .at_least(1)
        .collect::<String>()
        .map(|s: String| s.parse::<i32>().unwrap())
}

fn main() {
    let source = "53位 ユウナのガード ワッカ";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

結果は Ok(53) となります。

to() との違いは、元パーサーのパース結果を利用するか否かです。パース結果を利用するなら map() 、利用しないなら to() を使うのが分かりやすいと思います。

map() で、引数を無視しているなら to() と同じことになります。以下の 2 つのコードは等価です。

/* Parser... */.to(42)

/* Parser... */.map(|_| 42)

int() パーサー

数字を扱うことは非常によくあるので、標準で text::int() パーサーが定義されています。これは負でない数字をパースしてコンテナ型にしてくれます。基数も指定できます。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    text::int(10).map(|s: String| s.parse::<i32>().unwrap())
}

fn main() {
    let source = "53位 ユウナのガード ワッカ";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

この例では 10 進数の数字をパースしています。 text::int() は String などのコンテナ型で出力してくれるので、必要に応じて map() などを用いて値を変換します。

実際には、 text::int() が出力するのは chumsky::text::Character 型の Associated Type である Collection 型で、これは FromIterator などを実装している型です。なので collect() コンビネータの出力結果と同じように扱えます。

from_str() unwrapped() コンビネータ

i32 など FromStr を実装している型へ変換する場合は、 from_str() コンビネータで簡単に変換できます。出力は Result となります。また、 Result を unwrap 場合は unwrapped() コンビネータでどうぞ。

先程の int() パーサーの例は以下のように書けます。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    text::int(10).from_str::<i32>().unwrapped()
}

もちろん省略できる Turbofish は省略できます。ここまでコンパクトに書けます。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    text::int(10).from_str().unwrapped()
}

padded_by() padded() コンビネータ

padded_by() を使うと、両側にくっついた不必要な文字列を無視するパーサーを定義できます。よくある例として、数字の両端のスペースやタブ文字、改行などを無視するパーサーです。やってみましょう。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    let number = text::int(10).from_str().unwrapped();
    let whitespace = filter(|c: &char| c.is_whitespace()).repeated();
    number.padded_by(whitespace)
}

fn main() {
    let source = "  \t  42  \r\n  ";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

2 つのパーサーを定義しています。 number は先程の int() パーサー使用例と全く同じです。 whitespace は空白文字の繰り返しをパースします。

Parser に生えている padded_by() に whitespace を渡すことで、 number の両端にくっついている whitespace を無視するパーサーができました。実行すると Ok(42) が出力されます。

今回は whitespace を自分で定義しましたが、これもよく使うので chumsky::text::whitespace() が既に定義されています。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    text::int(10)
        .from_str()
        .unwrapped()
        .padded_by(text::whitespace())
}

また、 .padded_by(text::whitespace()) も頻出パターンですので、 padded() コンビネータが定義されています。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    text::int(10).from_str().unwrapped().padded()
}

delimited_by() コンビネータ

padded_by() では無視する両端のパーサーは共通でした。これを前後で独立して指定できるのが delimited_by() コンビネータです。例えば、 "(" と ")" で囲まれた値をパースする際に使用できます。後述の then_ignore() や ignore_then() を組み合せて使用するより楽です。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    let number = text::int(10).from_str().unwrapped();
    let leading = just('(');
    let trailing = just(')');
    number.delimited_by(leading, trailing)
}

fn main() {
    let source = "(42)";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

then() then_ignore() ignore_then() コンビネータ

then() then_ignore() ignore_then() これら 3 つのコンビネータを使うと、異なるパーサーを繋げて順番にパースすることができます。

あるパーサー 2 つ a b を考えます。 a の出力型が A 、 b の出力型が B とすると、コンビネータ適用後の出力型は以下のようになります。

呼び出し	出力
a.then(b)	(A, B)
a.then_ignore(b)	A
a.ignore_then(b)	B

簡単な例として、スペース 1 つで区切られた数字 2 つをパースしてみましょう。

fn parser() -> impl Parser<char, (i32, i32), Error = Simple<char>> {
    let number = text::int(10).from_str().unwrapped();
    let space = just(' ');
    number.then_ignore(space).then(number)
}

fn main() {
    let source = "1234 5678";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

number の出力型は i32 で、 space の出力型は &'static str です。

number.then_ignore(space) の時点で space 側が無視されるので、出力は i32 となります。ここから更に .then(number) と繋げることで、出力が (i32, i32) となります。

実行すると、 Ok((1234, 5678)) となります。

then() はタプルが出力となるので、異なる型を混在させることができます。もちろん、 then() は繰り返し呼び出すことでどんどん繋げていくことができます。ただし、 then() 呼び出しの度にタプルがネストされていくことに注意してください。例えば、パーサー a b c の出力がそれぞれ A, B, C だとすると、 a.then(b).then(c) の出力は ((A, B), C) となります。

fn parser() -> impl Parser<char, ((i32, i32), i32), Error = Simple<char>> {
    let number = text::int(10).from_str().unwrapped();
    let space = just(' ');
    number
        .then_ignore(space)
        .then(number)
        .then_ignore(space)
        .then(number)
}

もちろん map() でフラットなタプルにすることができます。その際は、パターンマッチングでバラして整形しましょう。

fn parser() -> impl Parser<char, (i32, i32, i32), Error = Simple<char>> {
    let number = text::int(10).from_str().unwrapped();
    let space = just(' ');
    number
        .then_ignore(space)
        .then(number)
        .then_ignore(space)
        .then(number)
        .map(|((a, b), c)| (a, b, c))
}

or_not() コンビネータ

パースしてもしなくても良いパーサーは or_not() コンビネータで作ることができます。単項プラス演算子を書いてみましょう。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    let plus = just('+').or_not();
    let number = text::int(10).from_str().unwrapped();
    plus.then(number).map(|(_plus, num)| num)
}

fn main() {
    let source = "+123";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

or_not() を適用すると、パーサーの出力型が Option でラップされます。 repeated().at_most(1) と書いても同じことができますが、面倒なので or_not() を使いましょう。

end() プリミティブ

end() は入力がもう残っていないときに成功し、それ以外の場合は失敗するパーサーです。これを使用すると、入力を最後までパースしきれないと失敗するパーサーを組めます。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    let number = text::int(10).from_str().unwrapped().padded();
    number.then_ignore(end())
}

fn main() {
    let source = " 42 ";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);  // => Ok(42)

    let source = " 42 hoge";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);  // => Err(...)
}

最後に余計な文字が書かれているとエラーとなります。 Chumsky は lazy なパーサーなので、余計な文字が最後に存在するべきでない場合は end() で指定してあげる必要があります。

ちなみに end() の出力型は () です。

foldl() foldr() コンビネータ

foldl() と foldr() はリストの要素に順番に関数を適用し、畳み込みを行います。畳み込みは各言語で色々な呼び方がある処理です。 Rust だと fold ですが、他の言語だと reduce や aggregate などと言われている処理です。

出力が (A, B) であるパーサーに foldl() を適用すると、 A を初期値、 B を処理対象の配列として畳み込みを行います。 B は IntoIterator を実装している必要があります。最終的な出力型は A となります。

出力が (A, B) であるパーサーに foldr() を適用すると、 B を初期値、 A を処理対象の配列として畳み込みを行います。 foldr() では配列 A は逆順に処理されます。そのため A::IntoIter は DoubleEndedIterator を実装している必要があります。最終的な出力型は B となります。

符号 - がついた数字を foldr() を使用してパースしてみましょう。 - は何個でもつけられるものとします。

fn parser() -> impl Parser<char, i32, Error = Simple<char>> {
    let negatives = just('-').to(-1).repeated();
    let number = text::int(10).from_str().unwrapped();
    negatives.then(number).foldr(|cur, acc| cur * acc)
}

fn main() {
    let source = "---42";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

negatives の出力が要素 -1 のみで構成される配列、 number の出力が i32 です。これらを then() で繋いで foldr() で畳み込みしています。 number の出力を初期値とし、 negatives の出力の配列を逆順に cur に格納しながら集計値 acc に集計します。

この例のように "---42" をパースする場合、 foldr() の計算の過程は以下のようになります。

回数	引数 cur	引数 acc	cur * acc
1	-1	42	-42
2	-1	-42	42
3	-1	42	-42

初期値 42 に * -1 が 3 回適用されて -42 が出力となりました。

recursive() パーサー

最後に、こってりした recursive() の紹介です。再帰的な構文をパースするのに使います。

一番単純な再帰的構文の例として、 LISP の連結リストを考えてみましょう。 Cons セルの構文は簡単に (car cdr) とし、 car は i32 の値、 cdr は nil もしくは Cons セル (再帰) であるとします。実際のリストの例は以下のようになります。

(123 (456 (789 nil)))

これをパースしてみようと思います。 enum で Cons セルを以下のように定義します。これは TRPL (The Rust Programming Language) に出てくるものと同じです。追加で Clone と Debug を derive しておきます。

#[derive(Clone, Debug)]
enum Cons {
    Nil,
    Value(i32, Box<Self>),
}

Value(i32, Box<Self>) に Self が出てくる再帰的な型です。 Box にくるむ必要があるのは Cons のサイズが確定しないからです (TRPL で学びましたよね) 。

Rust は後方参照ができない言語なので、 let で定義したものをそれより前で使用できません。 recursive() を使用することによってパーサー 1 つを巻き上げ、再帰的なパーサーを組むことができます。

少し大きめですが、パーサーの実装はこのようになります。

fn parser() -> impl Parser<char, Cons, Error = Simple<char>> {
    recursive(|cons| {
        let number = text::int(10).from_str().unwrapped().padded();

        let nil = just("nil").padded().to(Cons::Nil);
        let value = number
            .then(cons)
            .delimited_by(just('('), just(')'))
            .padded()
            .map(|(car, cdr)| Cons::Value(car, Box::new(cdr)));

        nil.or(value)
    })
    .then_ignore(end())
}

fn main() {
    let source = "(123 (456 (789 nil)))";
    let parsed = parser().parse(source);
    println!("{:?}", parsed);
}

recursive() 自体は一旦置いといて、 クロージャの中身から 1 つずつ見ていきましょう。

number は数字のパーサーです。

nil は nil のパーサーです。これは Cons::Nil に変換されます。

value は "(" と ")" で囲まれた、数字と Cons セルのペアをパースします。ここでクロージャ引数の cons が登場しています。これは再帰部分で、クロージャの戻り値のパーサーをここで再利用し、再帰となっています。 map() を使用して Cons::Value() に変換しています。

クロージャの戻り値として、 nil.or(value) を返しています。ここのパーサーはクロージャ引数 cons として再利用でき、これが recursive() 自体のパーサーにもなります。

最後に then_ignore(end()) で最後までパースするようにします。

これで Cons パーサーの完成です。これを実行すると Ok(Value(123, Value(456, Value(789, Nil)))) となります。少し書きかたにクセがありますが、無事に再帰パーサーを書くことができました。

四則演算パーサーの作成

パーサーと言えばお馴染み (?) の四則演算を Chumsky でパースしましょう。 Chumsky の Tutorial をアレンジして紹介します。

今回は四則演算を表す式から抽象構文木 (AST: Abstract Syntax Tree) を作るパーサーを組みます。足し算や引き算などの式をデータとして表現します。

解析結果の型である AST を enum で表現しましょう。

#[derive(Clone, Debug)]
enum Expr {
    Value(f64),
    Neg(Box<Self>),
    Add(Box<Self>, Box<Self>),
    Sub(Box<Self>, Box<Self>),
    Mul(Box<Self>, Box<Self>),
    Div(Box<Self>, Box<Self>),
}

Value は正の f64 値、 Neg は単項マイナス演算、 Add Sub Mul Div はそれぞれ加算、減算、乗算、除算の二項演算を表します。

出力型が Expr である parser() 関数を用意します。

fn parser() -> impl Parser<char, Expr, Error = Simple<char>> {
    todo!()
}

数値

数値をパースして Expr::Value にするパーサーです。今回は簡単のため、正の整数のみ対応とします。負の数については次節でパースします。チャレンジングな方は小数にも対応させてみてください。小数の表現方法については impl FromStr for f64 のドキュメント に記載されている EBNF (Extended Backus-Naur Form) 文法が参考になるかと思います。

fn parser() -> impl Parser<char, Expr, Error = Simple<char>> {
    let number = text::int(10)
        .map(|s: String| Expr::Value(s.parse().unwrap()))
        .padded();

    let atom = number;

    atom.then_ignore(end())
}

number はいつものですね。 map() で String からの parse() と Expr::Value へのラップを同時に行なっています。

number を atom に束縛しています。 atom は現状ただの数値ですが、今後 or() を使用して数値だけでなく括弧にも対応させます。

最後に then_ignore(end()) で最後までパースするようにします。これで正の数値をパースする関数ができました。正直今までやってきたことと何も変わりません。

main() 関数で文字列をパースし AST を表示してみましょう。

fn main() {
    let source = "123";
    let parsed = parser().parse(source);
    println!("{:#?}", parsed);
}

println!() のフォーマット文字列に "{:#?}" と指定しているので、出力がインデントされて出てきます。 cargo run で実行すると以下のようになります。

Ok(
    Value(
        123.0,
    ),
)

単項マイナス演算

atom に対して前置する単項マイナス演算子 '-' をパースし、 atom の出力である Expr を Expr::Neg でラップします。 '-' は連続で何個でも書けるものとします。 ('-' の繰り返し, Expr) というタプルなので、 repeated() と foldr() で書けます。

fn parser() -> impl Parser<char, Expr, Error = Simple<char>> {
    let number = text::int(10)
        .map(|s: String| Expr::Value(s.parse().unwrap()))
        .padded();

    let atom = number;

    let signed = just('-')
        .padded()
        .repeated()
        .then(atom)
        .foldr(|_op, rhs| Expr::Neg(Box::new(rhs)));

    signed.then_ignore(end())
}

foldr() のクロージャは '-' の個数回呼ばれるので、そこで Expr::Neg でラップしています。 repeated() は 0 回でも OK なので、 '-' が無い場合は foldr() のクロージャが呼ばれず Expr が素通りします。

"---123" をパースすると以下のようになります。

Ok(
    Neg(
        Neg(
            Neg(
                Value(
                    123.0,
                ),
            ),
        ),
    ),
)

この例のように "---123" をパースする場合、 foldr() の計算の過程は以下のようになります。

回数	引数 _op	引数 rhs	Expr::Neg(Box::new(rhs))
1	'-'	Value(123.0)	Neg(Value(123.0))
2	'-'	Neg(Value(123.0))	Neg(Neg(Value(123.0)))
3	'-'	Neg(Neg(Value(123.0)))	Neg(Neg(Neg(Value(123.0))))

次節から二項演算をパースしますが、ここで一つ下準備をしておきます。演算子のパースで just('-').padded() のように just() と padded() の組合せが大量に出て読みづらくてアレなので、自分で関数を作ってしまいます。

fn parser() -> impl Parser<char, Expr, Error = Simple<char>> {
    let number = text::int(10)
        .map(|s: String| Expr::Value(s.parse().unwrap()))
        .padded();

    let atom = number;

    let op = |c| just(c).padded();

    let signed = op('-')
        .repeated()
        .then(atom)
        .foldr(|_op, rhs| Expr::Neg(Box::new(rhs)));

    signed.then_ignore(end())
}

just('-').padded() の部分を op('-') として切り出しました。

乗除算

3 * 5 や 8 / 2 などの二項演算をパースしましょう。加減算より乗除算の方が優先されるので、乗除算をパースして Expr とし、その Expr 間での加減算をさらにパースするといった順序です。

まずは乗除算から。

fn parser() -> impl Parser<char, Expr, Error = Simple<char>> {
    let number = text::int(10)
        .map(|s: String| Expr::Value(s.parse().unwrap()))
        .padded();

    let atom = number;

    let op = |c| just(c).padded();

    let signed = op('-')
        .repeated()
        .then(atom)
        .foldr(|_op, rhs| Expr::Neg(Box::new(rhs)));

    let product = signed
        .then(op('*').or(op('/')).then(signed).repeated())
        .foldl(|lhs, (op, rhs)| match op {
            '*' => Expr::Mul(Box::new(lhs), Box::new(rhs)),
            '/' => Expr::Div(Box::new(lhs), Box::new(rhs)),
            _ => unreachable!(),
        });

    product.then_ignore(end())
}

product に乗除算が定義されています。

then() で数値、演算子、数値と繋いでいきます。乗除算の演算子は '*' か '/' なので or() で。

二項演算は 数値 演算子 数値 という順番で書きますが、 数値 演算子 数値 演算子 数値 といういう風に最後の 演算子 数値 の部分は繰り返すことができるので repeated() で繰り返します。 BNF (Backus-Naur Form) で表すと 数値 (演算子 数値)* となります。

数値 と 演算子 数値 の配列を、 foldl() で Expr::Mul もしくは Expr::Div にします。

"123 * 456 / 789" をパースすると以下のようになります。

Ok(
    Div(
        Mul(
            Value(
                123.0,
            ),
            Value(
                456.0,
            ),
        ),
        Value(
            789.0,
        ),
    ),
)

この例のように "123 * 456 / 789" をパースする場合、 foldl() の計算の過程は以下のようになります。

回数	引数 lhs	引数 op	引数 rhs	match op { ... }
1	Value(123.0)	'*'	Value(456.0)	Mul(Value(123.0), Value(456.0))
2	Mul(Value(123.0), Value(456.0))	'/'	Value(789.0)	Div(Mul(Value(123.0), Value(456.0)), Value(789.0))

うまく乗除算をパースできましたが、 match 内で unreachable!() が使われているのがイケてないです。そこで、 product をちょっと書きかえて match を消してみましょう。

fn parser() -> impl Parser<char, Expr, Error = Simple<char>> {
    // ...

    let mul_op = op('*').to(Expr::Mul as fn(_, _) -> _);
    let div_op = op('/').to(Expr::Div as fn(_, _) -> _);
    let product = signed
        .then(mul_op.or(div_op).then(signed).repeated())
        .foldl(|lhs, (op, rhs)| op(Box::new(lhs), Box::new(rhs)));

    product.then_ignore(end())
}

mul_op と div_op に注目です。演算子をパースし Expr::Mul や Expr::Div に変換しています。 Expr::Mul や Expr::Div は enum の variant ですが、同時に Expr 値のコンストラクタ関数でもあります (Haskell の data constructor のような感じです。この言語仕様、意外と知られていない?) 。 as を使って関数であることを明示しています。 Expr::Mul Expr::Div は 2 つの引数を取り、 Expr 値を返す関数です。実際の引数や戻り値の型は _ で推論してもらいましょう。

こうすると、 foldl() のクロージャ引数 op が Expr のコンストラクタ関数になるので、あとは op(Box::new(lhs), Box::new(rhs)) と呼び出してやれば Expr 値になります。

加減算

乗除算が定義できたので、それを用いて加減算を定義します。

fn parser() -> impl Parser<char, Expr, Error = Simple<char>> {
    let number = text::int(10)
        .map(|s: String| Expr::Value(s.parse().unwrap()))
        .padded();

    let atom = number;

    let op = |c| just(c).padded();

    let signed = op('-')
        .repeated()
        .then(atom)
        .foldr(|_op, rhs| Expr::Neg(Box::new(rhs)));

    let mul_op = op('*').to(Expr::Mul as fn(_, _) -> _);
    let div_op = op('/').to(Expr::Div as fn(_, _) -> _);
    let product = signed
        .then(mul_op.or(div_op).then(signed).repeated())
        .foldl(|lhs, (op, rhs)| op(Box::new(lhs), Box::new(rhs)));

    let add_op = op('+').to(Expr::Add as fn(_, _) -> _);
    let sub_op = op('-').to(Expr::Sub as fn(_, _) -> _);
    let sum = product
        .then(add_op.or(sub_op).then(product).repeated())
        .foldl(|lhs, (op, rhs)| op(Box::new(lhs), Box::new(rhs)));

    sum.then_ignore(end())
}

やっていることは乗除算と同じです。変わったのは演算子と、両辺に product が使われているくらいでしょうか。

"12 * 34 + 56 / 78" をパースすると以下のようになります。

Ok(
    Add(
        Mul(
            Value(
                12.0,
            ),
            Value(
                34.0,
            ),
        ),
        Div(
            Value(
                56.0,
            ),
            Value(
                78.0,
            ),
        ),
    ),
)

乗除算が優先的に計算されている AST となっています。

括弧

(1 + 2) * 3 のように括弧を使えば、演算子の優先順位を変えることができます。

パーサーの atom は数値のみでしたが、これを括弧つきの sum もパースできるようにすることで、優先度を乗除算よりも高くすることができます。しかし、 sum が宣言されているのは atom よりも下。宣言を巻き上げるためには、そうです。 recursive() を使います。

fn parser() -> impl Parser<char, Expr, Error = Simple<char>> {
    recursive(|expr| {
        let number = text::int(10)
            .map(|s: String| Expr::Value(s.parse().unwrap()))
            .padded();
        let parentheses = expr.delimited_by(just('('), just(')'));

        let atom = number.or(parentheses).padded();

        let op = |c| just(c).padded();

        let signed = op('-')
            .repeated()
            .then(atom)
            .foldr(|_op, rhs| Expr::Neg(Box::new(rhs)));

        let mul_op = op('*').to(Expr::Mul as fn(_, _) -> _);
        let div_op = op('/').to(Expr::Div as fn(_, _) -> _);
        let product = signed
            .clone()  // 追加!
            .then(mul_op.or(div_op).then(signed).repeated())
            .foldl(|lhs, (op, rhs)| op(Box::new(lhs), Box::new(rhs)));

        let add_op = op('+').to(Expr::Add as fn(_, _) -> _);
        let sub_op = op('-').to(Expr::Sub as fn(_, _) -> _);
        let sum = product
            .clone()  // 追加!
            .then(add_op.or(sub_op).then(product).repeated())
            .foldl(|lhs, (op, rhs)| op(Box::new(lhs), Box::new(rhs)));

        sum
    })
    .then_ignore(end())
}

recursive() で sum の宣言を巻き上げ、 expr としています。 parentheses を定義し atom で or() を使用して、括弧に対応させています。

recursive() を使うことによって signed と product にライフタイムの問題が起こるので、 clone() を追加しています。 Chumsky で実装している Parser は Clone トレイトが実装されています。

then_ignore(end()) の位置が変わっていることに注意してください。 end() は一番大枠のパーサーで使いましょう。

"12 * (34 + 56) / 78" をパースすると以下のようになります。

Ok(
    Div(
        Mul(
            Value(
                12.0,
            ),
            Add(
                Value(
                    34.0,
                ),
                Value(
                    56.0,
                ),
            ),
        ),
        Value(
            78.0,
        ),
    ),
)

括弧書きの加算が優先されるようになりました。

AST の評価

AST を組み上げられたので、この式を計算してみたいと思います。と言っても簡単です。再帰的に Expr を評価すればおしまいです。

fn eval(expr: &Expr) -> f64 {
    match expr {
        Expr::Value(value) => *value,
        Expr::Neg(expr) => -eval(expr),
        Expr::Add(lhs, rhs) => eval(lhs) + eval(rhs),
        Expr::Sub(lhs, rhs) => eval(lhs) - eval(rhs),
        Expr::Mul(lhs, rhs) => eval(lhs) * eval(rhs),
        Expr::Div(lhs, rhs) => eval(lhs) / eval(rhs),
    }
}

あとは呼び出すだけです。

fn main() {
    let source = "12 * (34 + 56) / 78";
    let parsed = parser().parse(source);
    let evaluated = parsed.as_ref().map(eval);
    println!("{:#?} = {:?}", parsed, evaluated);
}

実行結果は以下の通りです。

Ok(
    Div(
        Mul(
            Value(
                12.0,
            ),
            Add(
                Value(
                    34.0,
                ),
                Value(
                    56.0,
                ),
            ),
        ),
        Value(
            78.0,
        ),
    ),
) = Ok(13.846153846153847)

自作ミニ言語の作成

最後のプロジェクトとして、ごく小さいプログラミング言語を作って動かしてみようと思います。以下のような関数型言語っぽいものを考えてみました。

let
    myfunc a b = a + b,
    myvalue = 42,
    x = 123,
    y = x + 333,
in
    (myfunc -(x + 1) y) * myvalue

四則演算、 let 〜 in 式による関数の定義、関数の呼び出しといった機能を持った、式を評価することができる言語です。扱える型は数値のみで、値リテラルは整数のみとします。

この言語の構文は以下の EBNF 形式で表されます。

atom ::= number | expr | call | let
number ::= 0 | [1-9][0-9]*
expr ::= term (("+" | "-") term)*
term ::= factor (("*" | "/") factor)*
factor ::= number | "(" atom ")"
call ::= ident atom*
ident ::= [A-Za-z_][0-9A-Za-z_]*
let ::= "let" decl ("," decl)* ","? "in" atom
decl ::= ident ident* "=" atom

構文解析の流れ

今までは、文字列から直接 AST を作っていました。今回もその戦略で実装できなくもないですが、文字を対象に構文を組み立てるのは粒度が細かすぎますし、 .padded() の呼び出しの頻出によりコードの見通しが悪くなるので、まずは文字列を字句(トークン)の列にしてから、そのトークン列に対してパースして AST を作るという戦略で行こうと思います。

文字列を言語的に意味のある最小単位(トークン)に分解する処理を字句解析といいます。文字列をトークン列にただバラすだけです。木構造のようなものは持ちません。

例として以下のコードを考えます。

let func a b = a + b, in func 1 2

これを字句解析すると以下のようになるイメージです。

[
    Let,
    Ident("func"),
    Ident("a"),
    Ident("b"),
    Equal,
    Ident("a"),
    Plus,
    Ident("b"),
    Comma,
    In,
    Ident("func"),
    Number(1),
    Number(2),
]

Token の定義

まずは、トークンを enum で定義しましょう。新しくファイル src/parser.rs を作ります。

#[derive(Clone, Debug, PartialEq)]
enum Token {
    Let,
    In,
    Comma,
    LParen,
    RParen,
    Equal,
    Plus,
    Minus,
    Asterisk,
    Slash,
    Number(f64),
    Ident(String),
}

キーワードや記号をそのまま variant として定義し、リテラルや識別子はその値を持つようにします。簡単ですね。

Tokenizer の作成

実際に字句解析を行う tokenizer() を Chumsky で書きましょう。

fn tokenizer() -> impl Parser<char, Vec<Token>, Error = Simple<char>> {
    choice((
        text::keyword("let").to(Token::Let),
        text::keyword("in").to(Token::In),
        just(',').to(Token::Comma),
        just('(').to(Token::LParen),
        just(')').to(Token::RParen),
        just('=').to(Token::Equal),
        just('+').to(Token::Plus),
        just('-').to(Token::Minus),
        just('*').to(Token::Asterisk),
        just('/').to(Token::Slash),
        text::int(10).from_str().unwrapped().map(Token::Number),
        text::ident().map(Token::Ident),
    ))
    .padded()
    .repeated()
    .then_ignore(end())
}

ここで新登場のパーサーがいくつか出てきたので紹介します。まずは text::ident() です。これは C 言語スタイルの識別子パーサーで、正規表現 /[A-Za-z_][0-9A-Za-z_]*/ にマッチする文字列をパースします。

text::keyword() は text::ident() にマッチし、かつ指定の文字列のみをパースするパーサーです。

choice() はタプル内のパーサーを順番にテストし、最初に成功した結果を返すパーサーです。 or() と同じ役割をしますが、たくさんのパーサーを or() で繋げるより choice() の方がコンパイル時間が短いという特徴があります。 a.or(b).or(c) は choice((a, b, c)) と等価です。

あとはそれぞれのトークンパーサーを choice() でまとめて、空白無視して、繰り返して終わりです。ここまで読んできた人なら楽勝かと思います。

Expr の定義

AST を src/parser.rs に定義します。

#[derive(Clone, Debug)]
pub enum Expr {
    Number(f64),
    Call(String, Vec<Expr>),
    Let(Vec<(String, Vec<String>, Self)>, Box<Self>),
    Neg(Box<Self>),
    Add(Box<Self>, Box<Self>),
    Sub(Box<Self>, Box<Self>),
    Mul(Box<Self>, Box<Self>),
    Div(Box<Self>, Box<Self>),
}

先ほどの四則演算での AST に加えて、 Call と Let が登場です。

Call は関数呼び出しで、呼び出す関数名と引数の配列を保持します。例えば、 foo 123 456 という関数呼び出しは以下のように表現されます。

Call("foo", [Number(123), Number(456)])

また、 foo 単体のような引数なしの関数呼び出しは Call("foo", []) と表現されます。

Let は let 〜 in 式で、関数名・仮引数・関数本体のタプルの配列と、 in 直後の式を保持します。 let foo a b = a + b in foo 123 456 は以下のように表現されます。

Let(
    [(
        "foo",
        ["a", "b"],
        Add(
            Call("a", []),
            Call("b", [])
        )
    )],
    Call("foo", [Number(123), Number(456)])
)

パーサーの作成

さて、トークンの配列から AST を作るパーサーを src/parser.rs に作りましょう。ここが一番大変です。

まずは四則演算のみのパーサーを書いてみましょう。

use chumsky::error::Cheap;

fn parser() -> impl Parser<Token, Expr, Error = Cheap<Token>> {
    recursive(|expr| {
        let number = select! { Token::Number(x) => Expr::Number(x) };
        let parenthesis = expr
            .clone()
            .delimited_by(just(Token::LParen), just(Token::RParen));

        let atom = choice((number, parenthesis));

        let signed = just(Token::Minus)
            .repeated()
            .then(atom)
            .foldr(|_op, rhs| Expr::Neg(Box::new(rhs)));

        let mul_op = just(Token::Asterisk).to(Expr::Mul as fn(_, _) -> _);
        let div_op = just(Token::Slash).to(Expr::Div as fn(_, _) -> _);
        let product = signed
            .clone()
            .then(mul_op.or(div_op).then(signed).repeated())
            .foldl(|lhs, (op, rhs)| op(Box::new(lhs), Box::new(rhs)));

        let add_op = just(Token::Plus).to(Expr::Add as fn(_, _) -> _);
        let sub_op = just(Token::Minus).to(Expr::Sub as fn(_, _) -> _);
        let sum = product
            .clone()
            .then(add_op.or(sub_op).then(product).repeated())
            .foldl(|lhs, (op, rhs)| op(Box::new(lhs), Box::new(rhs)));

        sum
    })
    .then_ignore(end())
}

parser() 関数の型を見てみましょう。文字列ではなく Token の列を対象にパースするので、 Parser の最初の型引数は Token です。また、エラー型に Cheap を指定しています。 Simple の型引数は Hash + Eq を要求しているため使えません。

関数内で、 chumsky::select! マクロが使用されています。 => の左辺に match 式のパターンを書き、右辺に値を書くと、「入力がパターンにマッチした場合のみ、 => の右辺の出力を返す」パーサーが作れます。今回の select! { Token::Number(x) => Expr::Number(x) } の場合、「入力が Token::Number(x) にマッチした場合のみ、出力として Expr::Number(x) を返す」パーサーとなります。文字列以外の入力で、内包されている値を取り出す場合は select! マクロを使いましょう。取り出す値が特に無い場合は、素直に just() で大丈夫です。

あとは四則演算で実装したパーサーと同じ内容です。ここから追加で Call と Let のパーサーを実装します。

追加のパーサーを実装する前に、識別子パーサー ident と宣言パーサー decl を実装します。

fn parser() -> impl Parser<Token, Expr, Error = Cheap<Token>> {
    recursive(|expr| {
        let number = select! { Token::Number(x) => Expr::Number(x) };

        let ident = select! { Token::Ident(s) => s };
        let decl = ident
            .then(ident.repeated())
            .then_ignore(just(Token::Equal))
            .then(expr.clone())
            .map(|((name, params), expr)| (name, params, expr));

        // 省略
    })
    .then_ignore(end())
}

ident は Token::Ident() に内包されている値を取り出すだけのパーサーです。

decl は let の関数宣言部の 1 エントリをパースし、タプルとして出力するパーサーです。文法の以下の部分に相当する部分をパースします。

decl ::= ident ident* "=" atom

これらを用いて call と r#let を書き、 atom の候補に追加しましょう。

fn parser() -> impl Parser<Token, Expr, Error = Cheap<Token>> {
    recursive(|expr| {
        let number = /* 省略 */;

        let ident = /* 省略 */;
        let decl = /* 省略 */;

        let parenthesis = /* 省略 */;
        let call = ident
            .then(expr.clone().repeated())
            .map(|(name, params)| Expr::Call(name, params));
        let r#let = just(Token::Let)
            .ignore_then(decl.separated_by(just(Token::Comma)))
            .then_ignore(just(Token::Comma).or_not())
            .then_ignore(just(Token::In))
            .then(expr)
            .map(|(decls, expr)| Expr::Let(decls, Box::new(expr)));

        let atom = choice((number, parenthesis, call, r#let));

        // 省略
    })
    .then_ignore(end())
}

call については特に解説することは無いと思います。

r#let で separated_by() というコンビネータが登場です。これは、引数で指定したもので区切られたリストをパースし、配列として出力してくれるものです。今回の例では decl を just(Token::Comma) で区切ったリストを配列として出力してくれます。その後の .then_ignore(just(Token::Comma).or_not()) は、いわゆるケツカンマ部分です。リスト末尾に Token::Comma があってもなくても大丈夫なようにします。最近の言語だとよくある仕様ですね。

これで parser() の完成です。関数がちょっと長くなってしまいましたが、意外とあっさり終わりました。

エラー型の作成と API の作成

tokenizer() や parser() を使いやすくするために、 pub な parse() 関数を作ります。エラーに関する型 ParserError も定義します。

#[derive(Debug)]
pub enum ParserError {
    TokenizerError(Vec<Simple<char>>),
    ParserError(Vec<Cheap<Token>>),
}

pub fn parse(source: &str) -> Result<Expr, ParserError> {
    let tokenized = match tokenizer().parse(source) {
        Ok(tokenized) => tokenized,
        Err(err) => return Err(ParserError::TokenizerError(err)),
    };
    println!("{:#?}", tokenized);
    let parsed = match parser().parse(tokenized) {
        Ok(parsed) => parsed,
        Err(err) => return Err(ParserError::ParserError(err)),
    };
    Ok(parsed)
}

ランタイムの作成

パースしたらその式を実際に評価してみたいですよね。 src/runtime.rs を作成し、ランタイムを作りましょう。

use crate::parser::Expr;

fn eval_impl(expr: &Expr, stack: &[&(String, Vec<String>, Expr)]) -> f64 {
    match expr {
        Expr::Number(n) => *n,
        Expr::Call(func, params) => {
            let (index, &(_name, args, func)) = stack
                .iter()
                .enumerate()
                .rev()
                .find(|(_index, (name, args, _expr))| name == func && params.len() == args.len())
                .unwrap_or_else(|| panic!("Not found: {}", func));
            let params = args
                .iter()
                .zip(params.iter())
                .map(|(name, param)| (name.clone(), vec![], Expr::Number(eval_impl(param, stack))))
                .collect::<Vec<_>>();
            eval_impl(
                func,
                &[&stack[0..index], &params.iter().collect::<Vec<_>>()[..]].concat(),
            )
        }
        Expr::Let(decls, expr) => eval_impl(
            expr,
            &[stack, &decls.iter().collect::<Vec<_>>()[..]].concat(),
        ),
        Expr::Neg(expr) => -eval_impl(expr, stack),
        Expr::Add(lhs, rhs) => eval_impl(lhs, stack) + eval_impl(rhs, stack),
        Expr::Sub(lhs, rhs) => eval_impl(lhs, stack) - eval_impl(rhs, stack),
        Expr::Mul(lhs, rhs) => eval_impl(lhs, stack) * eval_impl(rhs, stack),
        Expr::Div(lhs, rhs) => eval_impl(lhs, stack) / eval_impl(rhs, stack),
    }
}

pub fn eval(expr: &Expr) -> f64 {
    eval_impl(expr, &[])
}

eval() 関数は外部向けに使いやすくしたもので、実装の本体は eval_impl() 関数に書いてあります。

stack という引数があります。これは、現時点で利用できる関数の情報が積まれた配列への参照です。最初は空の配列ですが、 Let に遭遇すると、関数宣言を stack に積んでから、最終的な式を評価します。 Call に遭遇した時は、 stack に積まれている関数を参照し、評価します。 stack の末尾から、関数名と引数の数が一致するものをピックし、実引数を評価して、それをさらに stack に積んでから関数の内容を評価します。関数名と引数の数が一致する関数が見つからなかった場合は panic します。

使ってみる

src/main.rs で使ってみましょう。

use runtime::eval;

mod parser;
mod runtime;

fn main() {
    let source = "
let
    myfunc a b = a + b,
    myvalue = 42,
    x = 123,
    y = x + 333,
in
    (myfunc -(x + 1) y) * myvalue
    ";
    let parsed = parser::parse(source);
    println!("{}", eval(&parsed.unwrap()));
}

見事、 13944 と表示されます。やった！

チャレンジ

これで自作言語パーサーは完成となりますが、まだまだ言語に足りない機能があります。チャレンジとして以下の機能を実装してみてください。

• コメントのパース
• f64 以外の型への対応
• 比較演算子の実装
• if 〜 then 〜 else の三項演算子の実装
• ラムダ式の実装
• map_with_span() を使用したソースコード位置の保持と分かりやすいエラー表示
• Inkwell などを使用した LLVM IR の出力

終わりに

Chumsky で自作言語のパーサーを書き、それを評価するところまで紹介しました。ライブラリを使う際のとっかかりとなれば幸いです。

ここで紹介しきれなかった機能もたくさんあります。 Chumsky の examples ディレクトリ にたくさん使用例が載っているので参考にしてみてください。

良い自作 DSL ライフを!