[入門]関数プログラミング―質の高いコードをすばやく直感的に書ける!

第5章 パーサコンビネータ―小さなパーサを組み合わせて大きなパーサを作る

この記事を読むのに必要な時間:およそ 4 分

この章では,関数型の至宝であるコンビネータライブラリについて説明します。

コンビネータとは何か?

この章でいうコンビネータとは,ある型の部品と部品を組み合わせて,同じ型のより大きな部品を作るための関数のことです。たとえば,パーサのコンビネータライブラリは,パーサを組み合わせるための各種コンビネータを提供しており,簡単にパーサを作成できます。コンビネータライブラリは,言語内DSLDomain Specific Languageと表現してもよいでしょう。

関数型では,パーサに加えて,データを文字列でわかりやすく表示するプリティプリンタ,SQL,XML,ハードウェア記述,そしてデリバティブ(金融商品)記述,楽譜記述など多様なコンビネータライブラリが作られ,実際に使われています。この章では,パーサのコンビネータライブラリを取り上げます。

CSVのパーサ

たとえ簡潔でも,実用的でないパーサの例だと興味が持てないでしょうし,一方実用的であっても長いと理解が難しくなるでしょう。そこで,実用的で手頃な大きさで,またみなさんが馴染み深いと思われるCSVのパーサを作ることを考えましょう。

CSVのBNF

CSVのBNF注1は,RFC 4180で定められています注2)⁠リスト1に,説明を簡単にするために1行目だけ手を加えたCSVのBNFを示します。

リスト1 CSVのBNF

csv = 1*(record CRLF)   (1)
record = field *(COMMA field)   (2)
field = (escaped / non-escaped)   (3)
escaped = DQUOTE *(TEXTDATA / COMMA / CR / LF /
2DQUOTE) DQUOTE   (4)
non-escaped = *TEXTDATA
TEXTDATA = %x20-21 / %x23-2B / %x2D-7E
COMMA = %x2C
CRLF = CR LF
CR = %x0D
LF = %x0A
DQUOTE = %x22

*1*2はそれぞれ,0回以上,1回以上,2回の繰り返しを意味します。%xは,ASCII文字を16進数表記していることを表します。

注1)
Backus-Naur Form。文法を定める言語のことです。
注2)
RFCで用いられるBNFは,ABNFというBNFの亜種です。

csv,record,fieldの意味

これを見ると,csvとはrecordの集まりであり,recordとはカンマで区切られたfieldの集まりであることがわかります。次に例を示します。

boo,foo,woo
goo,zoo,qoo

たとえば,全体がcsv,boo,foo,wooがrecord,fooがfieldに当たります。これはみなさんの理解通りでしょう。

fieldの内部

難しいのはfieldです。データ中にカンマや二重符号が出てこない場合はそのままでよいのですが,出てくる場合は二重符号で囲みます。二重符号でカンマを囲むと,区切り文字のカンマと区別がつきます。

boo,"foo,woo",goo

一方,二重符号に囲まれた二重符号は,囲みなのか二重符号文字そのものなのか区別がつきません。そこで,二重符号を重ねます。

boo,"foo""woo",goo

この例の"foo""woo"は,foo"wooを表します。

正規表現でCSVパーサを実装する場合

みなさんは,CSVパーサを正規表現で実装したくなるかもしれません。しかし,CSVパーサを正規表現で作るのは,とても難しいことが知られています。⁠詳説 正規表現 第3版』注3の5.4.2項には,CSVパーサを実装した例が載っていますので,興味があれば見てください。

正規表現がパーサを作るための技術としてあまり適していない理由は2つあります。まず第一に,正規表現が入れ子構造を表現できないことです。第二に,正規表現は部品化できないため,正規表現が長くなりがちで,保守しにくくなることです。

関数型言語でも正規表現のライブラリは提供されています。しかし簡単な問題であればリスト操作で解決できますし,複雑な問題だとパーサを書きます。そのため,正規表現はあまり使われていません。

注3)
Jeffrey E.F. Friedl著,株式会社ロングテール/長尾高弘訳,オライリー・ジャパン,2008年

パーサコンビネータParsecでCSVパーサを実装

では,CSVパーサをコンビネータライブラリを用いて実装してみましょう。今回は,Haskellのライブラリの中で,とても有名なパーサのコンビネータライブラリParsecを使用します。Parsecを用いると,BNF通りにパーサを作っていけば,魔法のように目的のパーサができあがります。

これから示すコードは,csv.hsというファイルに記述してください注4)⁠そのファイルの先頭には,必要なライブラリを読み込むために,次のコードを入れます。

import Control.Applicative ((<*),(*>))
import Text.Parsec
import Text.Parsec.String

今から,CSVのBNFを元にトップダウン的に実装していきます。そして,最後に動かしてみましょう。

注4)
WEB+DB PRESS Vol.67サポートサイトでも完成形を公開しています。

csvを実装する

まず,BNFのリスト1(1)の部分を実装します。このパターンにはコンビネータendBy1を使います。endBy1は,第二引数で終端される第一引数のパーサを1回以上繰り返すコンビネータです。

csv :: Parser [[String]]
csv = endBy1 record crlf

csvの型を見てください。Parserとは,パーサというコンテナ型を表しています。このようにパーサをコンテナとして実装するのが常套手段です。このParserというコンテナ同士をくっつけるのがParsecのコンビネータです。

内側の型は,Stringのリストのリストになっています。Stringとは[Char]の別名です。外側のリストが行を,内側のリストが列を意味します。つまり,CSVファイルをパースした結果は,文字列を要素に持つ二次元のリストになります。

recordとcrlfはこれから実装するパーサです。

recordを実装する

次はリスト1(2)に従いrecordを書きましょう。このパターンには,コンビネータsepBy1が利用できます。sepBy1は,第二引数で区切られる第一引数のパーサを1回以上繰り返すコンビネータです注5)⁠

record :: Parser [String]
record = sepBy1 field comma
注5)
1回の場合は区切り文字パーサは使われません。

fieldを実装する

次はfieldです。BNFはリスト1(3)です。/の部分を,選択を表すコンビネータ<|>に単純に置き換えるだけです。

field :: Parser String
field = escaped <|> nonEscaped

著者プロフィール

山本和彦(やまもとかずひこ)

株式会社IIJイノベーションインスティテュート(IIJ-II)技術研究所 主幹研究員。

開発した代表的なオープンソフトにMew,Firemacs,Mightyがある。『プログラミングHaskell』や『Haskellによる並列・並行プログラミング』の翻訳者。職場ではHaskell,家庭では3人の子供と格闘する日々を送っている。

web:http://www.mew.org/~kazu/

twitter:@kazu_yamamoto

コメント

コメントの記入