C#のパーサコンビネータライブラリSpracheでML風言語のインタプリタを実装する

C#の [Sprache](https://github.com/sprache/Sprache/blob/develop/README.md)というパーサーコンビネータライブラリの紹介記事です。

# Sprache とは
 C#のパーサーコンビネータライブラリです。Spracheを使うとパーサーコンビネータ方式で簡単にパーサーを作ることができます。今回はSpracheを使ってML風言語のパーサーを実際に作ってみました。今回実装したソースコードは[こちら](https://github.com/yuchiki/YuchiKaml)です。
ちなみにSpracheという単語は「ことば」を意味するドイツ語で、ʃpʁaːxə（シュプラーヘ/シュプラーハ）と読みます。

## パーサーとは？

文字列を受け取って構文解析した結果を返すプログラムです。
たとえば、`1+x*3` という５文字の文字列を受け取り、 

トップ... +
トップ左... 定数1
トップ右... *
トップ右の\*の左...変数x
トップ右の\*の右...定数3

といったような分析をします。

## パーサーコンビネータとは？

パースすべき式の仕様が大きくなるにつれて、式全体をパースするパーサーを書くことは困難になっていきます。そこで、大きなパーサーを作る手法として、小さなパーサーを組み合わせて作るパーサーコンビネータという仕組みがあります。

### 例

整数をパースするパーサーIntParserと、booleanをパースするパーサーBoolParserと、変数をパースするVarParserが書けているとします。

```csharp

Parser<Expr> IntParser = ...;
Parser<Expr> BoolParser = ...;
Parser<Expr> VarParser = ...;
```

Spracheにおいて、パーサーの型は`Parser<T>`です。`Parse<T>`型のパーサーは、文字列を受け取ってそれをパースした結果のT型の値を返すParseメソッドを備えています。
今、整数定数かbool定数か変数のいずれかが起こりうる式Primaryが定義されているとします。

```
Primary p ::= n | b | x
```

PrimaryのパーサーはIntParser, BoolParser, VarParserを使って次のように書けます。

```csharp

Parser<Expr> PrimaryParser = IntParser.Or(BoolParser.Or(VarParser));

```

さらに、この Primaryを踏まえてexprが次の用に定義されているとします。

```
expr e ::= if p then p else p 
```

このexprのパーサーは、先ほど定義したPrimaryParserを用いて次のように書けます。

```csharp
Parser<Expr> IfParser =
    from ifToken in Parse.String("if").Token()
    from p1 in PrimaryParser
    from thenToken in Parse.String("then").Token()
    from p2 in PrimaryParser
    from elseToken in Parse.String("else").Token
    from p3 in PrimaryParser
    select new IfExpr(p1, p2, p3);
```

このように、より小さい単位のパーサーを組み合わせてより大きい単位のパーサーを作れる仕組みがパーサーコンビネータです。

# ML言語風言語の実例
 
試しにSpracheを使って自作ML言語風トイ言語、[YuchiKaml](https://github.com/yuchiki/YuchiKaml) のインタプリタを作ってみました。

## どんな言語？

YuchiKamlの式は以下のBNFで定義します。

![Screenshot from 2018-12-30 13-08-52.png](https://qiita-image-store.s3.amazonaws.com/0/211640/89d8c122-5026-d739-8560-91407343523e.png)

上の`x`は変数を、`n`は整数を表します。文法の詳細はこの記事の本質ではないのでここでは詳しく語りませんが、気になる人のために[こちら](https://github.com/yuchiki/YuchiKaml_Document/blob/master/document.pdf)のpdfに文法の詳細を記しました。

## C#による式の表現

YuchiKamlの式をC#でどう表現しましょう？
式は式でも、その実はbool定数であったり、整数定数であったり、式+式、式-式の形であったり、 様々です。この色々な形をひっくるめて式として扱うために、継承を使います。
まず、式全体を表す抽象クラスExprを定義します。

```csharp
    public abstract class Expr {}
```

次に、それぞれの形をExprの子クラスとして定義します。

```csharp

    class CBool : Expr { //bool定数を表す
        public bool Value { get; }
        public CInt(bool value) => Value = value;
    }

    class CInt : Expr { //整数定数を表す
        public int Value { get; }
        public CInt(int value) => Value = value;
    }


    class Add : Expr { // 式+式を表す
        public Expr Left { get; }
        public Expr Right { get; } 
        public Add(Expr left, Expr right) => (Left, Right) = (left, right);
    }

    class Sub : Expr { // 式-式を表す
        public Expr Left { get; }
        public Expr Right { get; } 
        public Sub(Expr left, Expr right) => (Left, Right) = (left, right);
    }
    ....
```

これで様々な形を式として扱えるようになりました。
式全体の定義は[こちら](https://github.com/yuchiki/YuchiKaml/blob/master/Syntax.cs)にあります。ソースコード中では、プリティプリントの関係や二項演算子の定義の共通化などの関係で、上に示した形と少し形が異なっています。

## パーサーの定義

Spracheを使ってパーサーを作ります。SpracheのAPIと実装は[ここ](https://github.com/sprache/Sprache/blob/develop/src/Sprache/Parse.cs)から確認できます。
整数定数をパースするパーサーを例に取ります。

### 整数定数のパーサー

```csharp

private static Parser<Expr> IntParser =
    from digits in Parse.Digit.AtLeastOnce().Text().Token()
    select new CInt(int.TryParse(digits, out var n) ? n : -1);
```

まず、クエリ構文一行目の`in`の右側を解説します。
上に出てくる`Parse.Digit`は、0から9の数字一文字を得るパーサーです。
その他の拡張メソッドは、引数のパーサーから別のパーサーを作るメソッドです。

| 名前                | 引数のパーサー | 戻り値のパーサー
| :--                | :-- | :-- |
| `AtLeastOnce<T>()` | Parser<T>型 | 引数のパーサーを一回以上繰り返し適用
| `Text()`           | `Parser<IEnumerable<char>>`型 | 結果の文字の列を結合
| `Token<T>()`          | Parser<T>型 | 前後の空白を無視

すなわち、上の例の`from`の右側のパーサーは以下のようなパーサーになります。

| パーサー                                  | 型 | パース結果 |
| :--                                      | :--                         | :--
| Parse.Digit                              | `Parser<char>`              | 0から9の数字一文字
| Parse.Digit.AtLeastOnce()                | `Parser<IEnumerable<char>>` | 数字を表す文字型の値の列
| Parse.Digit.AtLeastOnce().Text()         | `Parser<string>`            | 数字を表す文字列型の値
| Parse.Digit.AtLeastOnce().Text().Token() | `Parser<string>`            | 空白を読み飛ばした、数字を表す文字列型の値

クエリ構文`from t in P`では、tはパーサーPのパース結果を表しています。
すなわち、以下のdigitsは数字列を表す文字列です。

```csharp

from digits in Parse.Digit.AtLeastOnce().Text().Token()
```
この次の行の

```csharp

select new CInt(int.TryParse(digits, out var n) ? n : -1);
```

では、`digits`を`int`型に変換し、 更に `new CInt()`で 整数定数を表す式に変換したものを`select`しています。
クエリ式全体では、`CInt`型の値を得るパーサー、`Parser<CInt>`になっています。
`CInt`は`Expr`の子クラスなので、`Parser<CInt>`型の値は`Parser<Expr>`型の変数 `IntParser`に格納できます。

### カッコの中の式のパーサー

式全体をパースするパーサーMainParserを定義したとき、
`(e)`を読むパーサーは次のように書けます。

```csharp

private static readonly Parser<Expr> parenParserInner =
    from lParen in Parse.Char('(')
    from e in MainParser
    from rParen in Parse.Char(')')
    select e;
```

開きカッコと閉じカッコを読まれはするものの無視され、単純に中身の式を結果とするパーサーになっています。

### 二項演算子

補助関数BinOpParserを定義し、以下のようにパーサーを作成しました。
`Expr.Foo`は引数を２つ受け取りFoo型の式を作る関数です。

```csharp

private static readonly Parser<Expr> BinaryOperatorsParser =
    BinOpParser(UnaryParser, new(string, OperatorCreator) [][] {
        new(string, OperatorCreator) [] {
            ("*", Expr.Mul), ("/", Expr.Div)
        },
        new(string, OperatorCreator) [] {
            ("+", Expr.Add), ("-", Expr.Sub)
        },
        new(string, OperatorCreator) [] {
            ("<=", Expr.Leq), ("<", Expr.Lt), (">=", Expr.Geq), (">", Expr.Gt)
        },
        new(string, OperatorCreator) [] {
            ("==", Expr.Eq), ("!=", Expr.Neq)
        },
        new(string, OperatorCreator) [] {
            ("&&", Expr.And)
        },
        new(string, OperatorCreator) [] {
            ("||", Expr.Or)
        },
        new(string, OperatorCreator) [] {
            ("|>", (left, right) => Expr.App(right, left)),
            (">>", (left, right) => Expr.Abs("x", Expr.App(right, Expr.App(left, Expr.Var("x")))))
        }
    });
```

補助関数BinOpParserは[演算子の優先順位](https://ja.wikipedia.org/wiki/%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E5%84%AA%E5%85%88%E9%A0%86%E4%BD%8D)に気を付けつつ、[左再帰除去](https://ja.wikipedia.org/wiki/%E5%B7%A6%E5%86%8D%E5%B8%B0)をしつつ、二項演算子たちのパーサーをまとめて構築する関数です。
まず、同一優先順位の演算子たちについて左再帰除去をしたパーサーを組み立てる補助関数BinOpParserを定義します。

```csharp

private static Parser<Expr> BinOpParser(Parser<Expr> elemParser, IEnumerable < (string, OperatorCreator) > operators) {
    Parser<Func<Expr, Expr>> restParser =
        operators
        .Select(x => from _ in Parse.String(x.Item1).Token() from elem in elemParser select new Func<Expr, Expr>(l => x.Item2(l, elem)))
        .Aggregate((x, y) => x.Or(y));
    return
        from elem in elemParser
        from rest in restParser.Many()
        select rest.Aggregate(elem, (acc, f) => f(acc));
}
```

上の補助関数BinOpParserをオーバーロードし、複数の優先順位の演算子に対応した補助関数BinOpParserを定義します。

```csharp

private static Parser<Expr> BinOpParser(Parser<Expr> elemParser, IEnumerable < IEnumerable < (string, OperatorCreator) >> operators)
    => operators.Aggregate(elemParser, BinOpParser);
```

これを用いて、左結合の二項演算子のパーサーをまとめて定義しています。
補助関数を用いることによりボイラープレートを減らせています。

## コード例

今回のパーサーに[インタプリタ](https://github.com/yuchiki/YuchiKaml/blob/master/Syntax.cs)＋数個の[組み込み関数](https://github.com/yuchiki/YuchiKaml/blob/master/BuiltIns.cs)を組み合わせ以下のようなコードが実行できるようになりました。

### GCD

gcdは２数の最大公約数を求める関数です。

```ocaml

let rec gcd m n =
    if m > n then gcd (m - n) n
    else if m < n then gcd m (n - m)
    else m
in gcd 120 45
```


### ABC114 A問題

競技プログラミングのコンテスト、[第114回AtCoder Beginer's ContestのA問題](https://atcoder.jp/contests/abc114/tasks/abc114_a)の解答プログラムです。

```ocaml
#include<IO>

let x = read_num () in
let ans = if x == 3 || x == 5 || x == 7 then "YES" else "NO" in
print_endline ans
```
### ABC114 B問題

競技プログラミングのコンテスト、[第114回AtCoder Beginer's ContestのB問題](https://atcoder.jp/contests/abc114/tasks/abc114_b)の解答プログラムです。

```ocaml

#include<basic>
#include<IO>
#include<list>
#include<math>

let s = read_line () |> chars_of_string in
map (flip drop s >> take 3 >> concat_strings >> num_of_string) (range 0 (length s - 3))
    |> map (subt 753 >> abs)
    |> fold 100000 min
    |> print_endline

```

## まとめ

Spracheは今回初めて使ったのですが、非常に直感的で使いやすかったです。
みなさんもぜひ使ってみてください。

他にもSpracheの紹介をしている記事はいくつかありますので紹介いたします。

- [C#のパーサコンビネータライブラリSpracheを使ってみる](https://qiita.com/ousttrue/items/0a970d1a1f13d98b686a)

    Spracheを使ったパーサー開発の流れがよくわかる記事です。

- [Spracheでコメントを飛ばしてパースしてみる](https://qiita.com/ousttrue/items/1cd2fadc1af8bc5882e2)

    コメントの読み飛ばしもしてくれるToken関数を作成しています。
    Spracheには[CommentParser](https://github.com/sprache/Sprache/blob/develop/src/Sprache/CommentParser.cs)もあるので、この記事の手法と組み合わせればかなり楽にコメントを扱えそうです。

- [例のキヨシチェックを Sprache で書いてみる](https://qiita.com/fum1h1ro/items/98fae35ef475cba7462c)

    ズン・ズン・ズン・ズン・ドコの並びを検知する遊びが流行った頃の記事のようです。
    ズンとドコの並びをパーサーで検出する面白い記事です。

- [Sprache 使って Parser 書いたけどすごく戸惑ったって話](https://qiita.com/myzktkyk/items/b702d31ee7fb5f9b69d4)

    そう！Spracheの公式サンプルって結構読むのが難しいんですよ！
    こちらの記事では公式サンプルにわかりやすいコメントを入れてくださっています。

よろしかったら是非いいねを押してくださいませ！