Spracheというパーサーコンビネータライブラリの紹介記事です。C#のパーサーコンビネータライブラリです。Spracheを使うとパーサーコンビネータ方式で簡単にパーサーを作ることができます。今回はSpracheを使ってML風言語のパーサーを実際に作ってみました。今回実装したソースコードはこちらです。ちなみにSpracheという単語は「ことば」を意味するドイツ語で、ʃpʁaːxə(シュプラーヘ/シュプラーハ)と読みます。パーサーとは?文字列を受け取って構文解析した結果を返すプログラムです。*トップ右の*の左...変数xトップ右の*の右...定数3といったような分析をします。パーサーコンビネータとは?パースすべき式の仕様が大きくなるにつれて、式全体をパースするパーサーを書くことは困難になっていきます。そこで、大きなパーサーを作る手法として、小さなパーサーを組み合わせて作るパーサーコンビネータという仕組みがあります。整数をパースするパーサーIntParserと、booleanをパースするパーサーBoolParserと、変数をパースするVarParserが書けているとします。...;Spracheにおいて、パーサーの型はParser<T>です。Parse<T>型のパーサーは、文字列を受け取ってそれをパースした結果のT型の値を返すParseメソッドを備えています。今、整数定数かbool定数か変数のいずれかが起こりうる式Primaryが定義されているとします。VarParserを使って次のように書けます。Primaryを踏まえてexprが次の用に定義されているとします。このexprのパーサーは、先ほど定義したPrimaryParserを用いて次のように書けます。p3);このように、より小さい単位のパーサーを組み合わせてより大きい単位のパーサーを作れる仕組みがパーサーコンビネータです。インタプリタを作ってみました。どんな言語?YuchiKamlの式は以下のBNFで定義します。上のxは変数を、nは整数を表します。文法の詳細はこの記事の本質ではないのでここでは詳しく語りませんが、気になる人のためにこちらのpdfに文法の詳細を記しました。この色々な形をひっくるめて式として扱うために、継承を使います。式全体を表す抽象クラスExprを定義します。{}次に、それぞれの形をExprの子クラスとして定義します。....これで様々な形を式として扱えるようになりました。式全体の定義はこちらにあります。ソースコード中では、プリティプリントの関係や二項演算子の定義の共通化などの関係で、上に示した形と少し形が異なっています。パーサーの定義Spracheを使ってパーサーを作ります。SpracheのAPIと実装はここから確認できます。整数定数をパースするパーサーを例に取ります。-1);まず、クエリ構文一行目のinの右側を解説します。上に出てくるParse.Digitは、0から9の数字一文字を得るパーサーです。その他の拡張メソッドは、引数のパーサーから別のパーサーを作るメソッドです。前後の空白を無視すなわち、上の例のfromの右側のパーサーは以下のようなパーサーになります。Pでは、tはパーサーPのパース結果を表しています。以下のdigitsは数字列を表す文字列です。整数定数を表す式に変換したものをselectしています。クエリ式全体では、CInt型の値を得るパーサー、Parser<CInt>になっています。IntParserに格納できます。式全体をパースするパーサーMainParserを定義したとき、(e)を読むパーサーは次のように書けます。BinOpParserを定義し、以下のようにパーサーを作成しました。Expr.Fooは引数を2つ受け取りFoo型の式を作る関数です。});補助関数BinOpParserは演算子の優先順位に気を付けつつ、左再帰除去をしつつ、二項演算子たちのパーサーをまとめて構築する関数です。同一優先順位の演算子たちについて左再帰除去をしたパーサーを組み立てる補助関数BinOpParserを定義します。f(acc));}上の補助関数BinOpParserをオーバーロードし、複数の優先順位の演算子に対応した補助関数BinOpParserを定義します。BinOpParser);これを用いて、左結合の二項演算子のパーサーをまとめて定義しています。補助関数を用いることによりボイラープレートを減らせています。今回のパーサーにインタプリタ+数個の組み込み関数を組み合わせ以下のようなコードが実行できるようになりました。GCDgcdは2数の最大公約数を求める関数です。ContestのA問題の解答プログラムです。ContestのB問題の解答プログラムです。print_endlineまとめSpracheは今回初めて使ったのですが、非常に直感的で使いやすかったです。みなさんもぜひ使ってみてください。他にもSpracheの紹介をしている記事はいくつかありますので紹介いたします。C#のパーサコンビネータライブラリSpracheを使ってみるSpracheを使ったパーサー開発の流れがよくわかる記事です。Spracheでコメントを飛ばしてパースしてみるコメントの読み飛ばしもしてくれるToken関数を作成しています。SpracheにはCommentParserもあるので、この記事の手法と組み合わせればかなり楽にコメントを扱えそうです。書いてみるズン・ズン・ズン・ズン・ドコの並びを検知する遊びが流行った頃の記事のようです。ドコの並びをパーサーで検出する面白い記事です。書いたけどすごく戸惑ったって話そう!Spracheの公式サンプルって結構読むのが難しいんですよ!こちらの記事では公式サンプルにわかりやすいコメントを入れてくださっています。upLoginユーザーは見つかりませんでした。