LoginSignup
26
20

More than 5 years have passed since last update.

@yuchiki1000yen(ゆーちき)

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

Last updated at Posted at 2018-12-30

C#の Spracheというパーサーコンビネータライブラリの紹介記事です。

Sprache とは

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

パーサーとは？

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

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

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

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

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

例

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


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を使って次のように書けます。


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

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

expr e ::= if p then p else p

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

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 のインタプリタを作ってみました。

どんな言語？

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

Screenshot from 2018-12-30 13-08-52.png

上のxは変数を、nは整数を表します。文法の詳細はこの記事の本質ではないのでここでは詳しく語りませんが、気になる人のためにこちらのpdfに文法の詳細を記しました。

C#による式の表現

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

    public abstract class Expr {}

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


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

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

パーサーの定義

Spracheを使ってパーサーを作ります。SpracheのAPIと実装はここから確認できます。
整数定数をパースするパーサーを例に取ります。

整数定数のパーサー


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

すなわち、上の例の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は数字列を表す文字列です。


from digits in Parse.Digit.AtLeastOnce().Text().Token()

この次の行の


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)を読むパーサーは次のように書けます。


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型の式を作る関数です。


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は演算子の優先順位に気を付けつつ、左再帰除去をしつつ、二項演算子たちのパーサーをまとめて構築する関数です。
まず、同一優先順位の演算子たちについて左再帰除去をしたパーサーを組み立てる補助関数BinOpParserを定義します。


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を定義します。


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

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

コード例

今回のパーサーにインタプリタ＋数個の組み込み関数を組み合わせ以下のようなコードが実行できるようになりました。

GCD

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


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問題の解答プログラムです。

#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問題の解答プログラムです。


#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の紹介をしている記事はいくつかありますので紹介いたします。

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

26
20
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
26
20