人気ブログランキング | 話題のタグを見る

Parsec 再入門 parse 関数

プログラム言語のプログラムは結局のところ連綿と続く一連の文字列だ。それをプログラムとして解釈するためにはパーサーという翻訳機を通さなければならない。

一続きの文字列は先頭からパーサーによって検査され、変数名や、関数や、演算子などに切り分けられる。Parsec はこのような作業を行うためのライブラリなのだ。

そうはいっても引数の二乗を計算するなどのような単純な関数と違って、パーサーの場合はどのようなことをするのか複雑すぎてイメージをつかむことが難しい。使い方を一口に説明することができないのだ。

したがって、これからの説明を読む前に、過去記事の「Haskell 記事リスト」の 7章のParsec の記事を一通り読んでもらった方がいいだろうと思う。この記事は Parsec, a fast combinator parser というインターネットの記事を読んで実験した結果を書いたものだ。

この記事を書いたときは Hugs を使っていたので ghci で動かない場合があったが、おりおり元記事を訂正してコピペでも使えるようにするつもりだ。プログラム言語の説明は、文章を読ん理解できない場合も、短いプログラム例をコピペして動かすととたんに仕組みが分かったりすることが多い。無駄に分かりづらい文章と格闘するよりも、さっとプログラム例を試してみて、それから文章にとりくんだほうがいい。

前置きはさておき、核心部分にはいろう。それは、parse 関数についてだ。この関数が Parsec ライブラリの中心部分になるからだ。

Haskell のプログラムは様々な関数の定義を含んでいるが、最終的には main 関数を呼び出すことでそれらの関数が有機的に結び合わされてプログラムが動き始める。Parsec ライブラリの場合、この main 関数に相当するものが parse 関数だ。parse 関数の型は次のようになる。

Prelude> :m Text.ParserCombinators.Parsec
Prelude Text.ParserCombinators.Parsec> :t parse
parse
:: Text.Parsec.Prim.Stream s Data.Functor.Identity.Identity t =>
Text.Parsec.Prim.Parsec s () a
-> SourceName -> s -> Either ParseError a

ごちゃごちゃしているが、簡単にいうと parse 関数は、第1引数に文字列のパターンをあらわす関数、第2引数に parse 関数が実行された場所の名称、第3引数に解析のターゲットになる文字列をとる。第1引数は関数(コンビネータ)なので、parse は高階関数だ。

さらに、戻り値は Either 型のデータになる。Maybe 型も処理が成功した場合の Just a と失敗した場合の Nothing という二つのデータコンストラクタからなっているが、Either 型では、処理が成功した場合には Right a が返され、失敗した場合には Left err が返されると同時にエラー例外を発生させる。Either 型はエラー処理機能を持った Maybe 型と考えてもいい。

上の説明は、プログラミングを言葉で説明する場合の悪い例の見本みたいなもので非常に分かりにくいと思うが、そういうときは parse 関数を実際に使ってみればそう難しい話でもないことが分かる。次の例はパターンマッチが成功した場合の動作例だ。

Prelude Text.ParserCombinators.Parsec> parse (string "hello") "Test" "hello, world"
Right "hello"

parse 関数の第1引数はパターンを表す関数(コンビネータ)だ。(string "hello") は文字列 "hello" にマッチするパターンを表している。上の例の場合 "hello, world" の先頭部分が "hello" とマッチしているからその部分が切り取られて Right "hello" として返される。

次の例はパターンとして (string "world") が parse 関数に渡されているが、第3引数の文字列の先頭部分は "world" ではないので、Left "Test" のように第2引数が Left にラッピングされて返され。同時にエラー割り込みが発生してエラーメッセージが表示される。

Prelude Text.ParserCombinators.Parsec> parse (string "world") "Test" "hello, world"
Left "Test" (line 1, column 1):
unexpected "h"
expecting "world"

これで、Parsec の全体像がつかめたと思う。つまり、Parsec モジュールを使ってやるプログラムは、文字列のパターンを表す関数を定義して、parsec の第1引数として渡すというやり方で作られるのだ。

文字列のパターンを表す関数は、基本的なものが Parsec に定義されており、次のようなものがある。

letter : 数字や記号以外の1文字にマッチする。
digit : 数字1文字にマッチする。
char 'a' : 1文字 'a' にマッチする。
string "foo" : "foo" という文字列にマッチする。

また、これらを組み合わせるための関数もある。

many pattern : pattern の0回以上の繰り返しにマッチする。
many1 pattern : pattern の1回以上の繰り返しにマッチする。例えば many1 letter は単語にマッチする。

さらに、pattern の連接と選択も記述できる。

do pattern1; pattern2 は pattern1 のあとに pattern2 が続いている場合にマッチする。例えば (do char 'a'; char 'b') は "ab" にマッチする。

pattern <|> pattern2 は pattern1 か pattern 2のどれかにマッチする。例えば stirng "hello" <|> string "world" は文字列の先頭部分が "hello" かまたは "world" のときにマッチする。

このように、Parsec では基本となるパターンを表す関数(コンビネータ)を組み合わせて複雑なパターンを作ることが、プログラミングの主な仕事となる。つまり、Perl のような複雑なプログラム言語のパーサーもパターンを表す関数(コンビネータ)を組み合わせることで迅速に実装できるということになる。

また、説明が長くなってしまったので、ghci で実験してその感覚を身につけてみよう。

Prelude Text.ParserCombinators.Parsec> parse (string "hello") "" "hello, world"
Right "hello"
Prelude Text.ParserCombinators.Parsec> parse (many1 letter) "" "hello, world"
Right "hello"
Prelude Text.ParserCombinators.Parsec> parse (do char 'h'; char 'e') "" "hello, world"
Right 'e'
Prelude Text.ParserCombinators.Parsec> parse (string "world" <|> string "hello") "" "hello, world"
Right "hello"

これまでの説明で、parse 関数に渡すパターンの関数(コンビネータ)の使い方が大体掴めたと思うが、パーサはパターンの判別だけではなく、パターンがマッチしたときに何かの操作(アクション)をしないと文字列が文法的に正しいかどうかのチェックしかできない。

Parsec では、このようなアクションも第1引数のパターン判別関数の部分に記述できる。

じつは Parsec のパターンを記述する関数(コンビネータ)は Parser モナドの関数なのだ。評判の悪い IO モナドを思い出して腰が引けたかもしれないが、IO モナドに限らずモナドというものは、1引数戻り値1個の関数を >>= 演算子で数珠つなぎにつなぐことができる関数というふうにとらえると、非常に分かりやすい。Unix のパイプラインのようなものだ。

ここでは詳しく説明しないが、過去記事の「IO モナドとのつきあい方」や「IOモナドとHaskellの最も単純なイメージ」を読んでもらうとその辺りのイメージが掴めると思う。

このパータン関数(コンビネータ)が Parser モナドだということを利用すると、パターンの定義の中にアクションを一緒に記述できてしまう。ここでは詳しくは述べないが、次の例の動作を見てもらうと確かにアクションが記述できるのが分かる。

Prelude Text.ParserCombinators.Parsec> parse (do str <- string "hello"; return (reverse str)) "" "hello, world"
Right "olleh"

駆け足で、Parsec を使ったプログラミングはどのようなものかということを、parse 関数を中心にして述べてきた。大筋のアイディアが分かればあとは詳細の設計になるが、何をしようとしているのかが分かれば、コンパイルエラーが出ても問題の特定がしやすいだろう。この記事を書きながら自分で分かったのは、やっぱり Parsec は便利だということだ。

自作のプログラムを作っても、どうしても、それを操作するためのコマンド体系が発生するし、それを実行するためのパーサーの作成は必須になってくる。Parsec を使いこなせるようになったら、どのような場合でも統一的な設計ができるので便利だろうと思う。
by tnomura9 | 2013-01-02 10:22 | Haskell | Comments(0)
<< Parsec 再入門 Pars... Parsec 再入門 >>