komorebikoboshiのブログ

プログラミング記事（趣味レベル）が多め。

FParsecでパーサコンビネータのお勉強

プログラミング F#

はじめに

この記事はF# Advent Calendar 2013の18日目のです。ひとつ前の記事は@さんのDeedle で遊ぼう - 捨てられたブログです。

パーサコンビネータとは

文字列の構造を解析するプログラムをパーサと言いますが、パーサコンビネータはその中の一種です。単純なパーサ関数を合成することで複雑なパーサを作り上げることができます。HaskellのParsecが有名ですが、FParsecはそれをF#に移植したものです。チュートリアルが和訳されています（#112 FParsec日本語チュートリアル « F# « a wandering wolf）ので、どういうものか知りたい方はそちらを。

パースする

それでは、具体的なパーサとして浮動小数点数をパースするpfloatを見ていきます。
pfloatは CharStream<'u> 型の引数を取り Reply 型の値を返す関数です。（型略称によって Parser 型となっています）
ここで、 'u という型はUser Stateの型を表しているのですが、この記事ではUser Stateは扱わないためこれ以降は無視します。User Stateについてはこの記事に詳しく書かれていますFParsecで遊ぶ - 2つのアンコール
さて、まずCharStream型ですが、これはパース対象の文字列の入れ物のようなものです。文字列の先頭から順番に文字を読みだすことができるのですが、そのとき「どこまで読んだのか」という状態を保持しておくことができます。
次にReply型ですが、これは

  • Error
  • Result
  • Status

という3つのフィールドを持つ構造体です。
pfloat関数はCharStreamのまだ読まれていない部分の先頭から、浮動小数点数っぽい文字の並びがあるかどうかを、既読位置を変化させずに調べます。そして、成功したときはあらためて文字列を読み込んで（このとき既読位置が変化します）、数値に変換してReplyのResultフィールドに入れます。

パース前
123.45abcde
^

パース後
123.45abcde
      ^

もしパースに失敗したときは、Errorフィールドにエラーメッセージを入れます。（この時はCharStreamの既読位置は変化しません）

パース前
abcabcde
^

パース後
abcabcde
^

そしてStatusフィールドには、成功したか、あるいは失敗したかを表す列挙体が代入されます。
目的の値を得るには返り値のStatusフィールドを調べて、成功ならResult、失敗ならErrorをそれぞれ調べればいいのですが、あとでもっといい方法がでてきます。

パーサを合成する

pfloat関数だけでは、「[]で囲まれた小数をパースしたいんだ」とかのニーズに応えることができません。そういうときは、パーサ同士を合成することで新しいパーサを作り出します。例えば今言ったようなパーサ関数は

let floatBetweenBrackets = pstring "[" >>. pfloat .>> pstring "]"
(* (pstring "[") で"["から始まる文字列をパースする関数が作れる *)

とすることで作ることができます。
ここで注目したいのは (pstring "[") と pfloat という2つのパーサ関数を引数に取る(>>.)という演算子です。
この演算子はParser型（つまりパーサ関数と同じ型）の関数を返すのですが、その関数がどういう働きをするかというと、まず一つ目の関数で与えられたCharStream型の値をパースして、それが成功したら二つ目のパーサで続けてパースします。両方成功したら後の方のパーサで得られた結果を返し、失敗したらパーサから得られたエラーメッセージを適切に返します。

             成功                成功
一つ目のパース -----> 二つ目のパース -------> 二つ目のパーサの結果を返す
              |                     | 
              +--> 結果をErrorに    +-> 結果をErrorに
             失敗                   失敗

これが(>>.)演算子のおおまかな働きです。(.>>)も大体同じです。（一つ目のパーサの結果を返します）ここで重要なのは、これらの演算子がParser型を引数に取り、同じParser型を返すということです。それはつまりパーサを合成した結果得られたパーサをまた他のパーサと合成することができるということです。FParsecでパーサの合成を行う演算子はほとんどが、このようにパーサを受け取りパーサを返します。いくら合成したとしても、得られたパーサは新しいパーサの材料となるのです！たとえ単純なパーサや演算子しかなかったとしても、可能性は無限に広がります。

パーサを走らせる

さて、今までパーサの本体を見てきましたが、これは直接使うにはあまり使い勝手がよくありません。CharStream型のインスタンスを生成しなければなりませんし、返り値から欲しい値を取り出すのも面倒です。そこで、FParsecにはrunという関数があります。

val run: Parser<'a, unit> -> string -> ParserResult<'a,unit>

パーサと文字列を引数にとり、ParserResult型という判別共用体を返します。ParserResult型はSuccessとFailureという2値を取り、それぞれ成功時の値、失敗時のエラーメッセージを保持します。
run関数にパーサ関数を渡した時点で新しい関数が生成されているとみることもできます。これもコンビネータ（関数を受け取り関数を返す関数）と言うことができるでしょう。

まとめ

ほんのちょっとですがFParsecの中身について見てきました。小さな関数でも組み合わさることで大きな仕事をすることができるようになるというのはステキですね。合成の対象となる関数と、その結果生成される関数の型をそろえることで何度でも合成可能になることは、自分でコンビネータを作ろうとするとき*1にも意識しておこうと思います。
拙い文章にここまで付き合ってくださり、本当にありがとうございました。

*1:たぶんないと思いますが