Parsecを初めて学ぶ

Haskell の世界を漂流していたら、Parsec というものにたどり着いたのですこし勉強してみた。

参考にしたサイトは、
https://wiki.haskell.org/Parsec
http://book.realworldhaskell.org/read/using-parsec.html

Parsecとコンビネータ

Parsec lets you construct parsers by combining higher-order Combinators to create larger expressions.

Parsec を使うと、コンビネータ（パーサを引数に取る）を組み合わせることでより大きく複雑なパーサを構成することができるということらしい。

ここで、コンビネータ(combinators)という言葉がよくわからなかったが、
https://wiki.haskell.org/Combinator
https://wiki.haskell.org/Combinator_pattern
の解説を読んで少しだけ分かった気になる。

Haskell の世界では、広義の意味で使われることが多く、広義の意味ではシンプルな機能を、目的に応じたコンビネータを使って組み合わせ、より複雑な機能に作り上げていく と言った使われ方をする。

ちなみに狭義では、A function or definition with no free variables. ということで、引数のみを使うラムダ式\f a b = f a b など がそれに該当するらしい。

Parsec はもちろんのこと、例えばIOモナドも

The Haskell IO system itself builds whole programs out of small I/O actions using >>= and return.

というように、>>= や return を組み合わせてより複雑なIOアクションを作り上げている、という具合だ。

記述の凡例

（自分にとっては）長い英語、かつParsec のベースとなる重要なことだと思ったので意訳をしながら書いた。
わかりづらいので、内容に対しては次のような凡例を設けています。

これは引用文

これは意訳

これは自分のコメント

Chapter 16. Using Parsec

解説サイトの内容を実践する。
http://book.realworldhaskell.org/read/using-parsec.html

Regular expressions are nice for many tasks, but they rapidly become unwieldy, or cannot be used at all, when dealing with a complex data format. For instance, we cannot use regular expressions to parse source code from most programming languages.

正規表現は複雑なデータフォーマットの取り扱いには向いておらず、例えばほとんどのプログラミング言語のソースコードを、正規表現を用いて解析することはできない。

Parsec is a useful parser combinator library, with which we combine small parsing functions to build more sophisticated parsers. Parsec provides some simple parsing functions, as well as functions to tie them all together.

Parsec は便利なパーサコンビネータライブラリであり、小さなパース関数をつなぎ合わせてより洗練されたパーサを作り上げる。Parsec はシンプルなパース関数、またそれらを結びつける関数を提供する。

Parsing is sometimes divided into two stages: lexical analysis (the domain of tools like flex) and parsing itself (performed by programs such as bison). Parsec can perform both lexical analysis and parsing.

パースは2段階のステージを経る。Parsecはこのどちらも対応している

• lexical analysis
• parsing itself

TODO:あとから調査しないと何を言っているのかわからない。

First Steps with Parsec: Simple CSV Parsing

Each line is a record, and each field in the record is separated from the next by a comma.

CSV ファイルの定義として、各行はレコードを指し、レコードの各フィールドは隣のフィールドとカンマで区切られている。

トップダウンでパース方式を定めるために、まずこのような宣言を行っている。

サンプルコード

サンプルコードは長いのでhttp://book.realworldhaskell.org/read/using-parsec.html参照

This first example is much longer than it really needs to be.

最終的に作ろうとしているものよりも幾分長いコードであることに注意。

CSVFile Parser

The type of this function is GenParser Char st [[String]].This means that the type of the input is a sequence of characters, which is exactly what a Haskell string is, since String is the same as [Char]. It also means that we will return a value of type [[String]]: a list of a list of strings. The st can be ignored for now.

この関数の型は、GenParser Char st [[String]] である。入力は文字の列（普通に文字列:Stringと呼んだ方が良いか）になることを意味している。また、 String 型のリストのリストを返す。引数の st はとりあえず無視する( 気になる! )

Parsec programmers often omit type declarations, since we write so many small functions. Haskell's type inference can figure it out.

Parsed のプログラマはたくさんの小さな関数を書くので、（面倒だから？）型宣言を端折る。でも Haskell の型推論がわかってくれる。

The csvFile uses a do block. As this implies, Parsec is a monadic library: it defines its own special parsing monad, GenParser.

Parsec はモナディックライブラリで、GenParser という解析する文脈を持ったモナドを定義している。

many is a function that takes a function as an argument. It tries to repeatedly parse the input using the function passed to it. It gathers up the results from all that repeated parsing and returns a list of them.

many は関数を取る関数である。渡された関数を使って、入力データを繰り返し解析しようと試みる。そしてすべての解析結果を集約し、それらのリストを返す。

Finally, we return the result. So, a CSV file is made up of many lines, then the end of file. We can often read out Parsec functions in plain English just like this.

ということで、CSV ファイルは複数の行とend of file で構成される。Persec の関数( の定義 )はしばしば、普通の英語のように読み出すことができる。

csvFile :: GenParser Char st [[String]]
csvFile = 
    do result <- many line
       eof
       return result

line Parser

We define the line function to do just that. Reading the function, we can see that a line consists of cells followed by the end of line character.

line は複数のセル、そしてend of file が後につづく形で構成されている。

cell Parser

The cells of a line start with the content of the first cell, then continue with the content of the remaining cells, if any.

記事コメントをのぞくと、このように書いてある。こっちの方がわかりやすい。

"We define the list of cells recursively: a list of cells consists of the first cell followed by a comma followed by the remaining cells. The contents of each cell is defined by the 'cellContent' function."

cells は再帰的に定義している: 「セルのリスト」は最初のセル、次にカンマ、次に残りの複数のセルという構成になっていて、セルそれぞれは、cellContent パーサとして定義されている。

cellContets　Parser

The noneOf function matches one item, so long as it isn't in the list of items that we pass. So, saying many (noneOf ",\n") defines a cell the way we want it.

noneOf 関数は、それが引数に渡した文字のリストに含まれていない限りは任意の文字にマッチする。だから、many (noneOF, ",\n") は「セル」を適切に定義している。

remainingCell Parser

Back in remainingCells, we have the first example of a choice in Parsec. The choice operator is <|>. This operator behaves like this: it will first try the parser on the left. If it consumed no input[35], it will try the parser on the right.

<|>演算子は、解析の分岐を表す。まず最初に左辺のパーサを試してみて、もし一文字もパーサが食べなかったら（最初の一文字からマッチしなかったら）右辺のパーサを試すことになる。

If we see a comma after parsing a cell, it means that at least one more cell follows. Otherwise, we're done. So, our first choice in remainingCells is char ','. This parser simply matches the passed character in the input. If we found a comma, we want this function to return the remaining cells on the line. At this point, the "remaining cells" looks exactly like the start of the line, so we call cells recursively to parse them. If we didn't find a comma, we return the empty list, signifying no remaining cells on the line.

もし「セル」をパースした後でカンマを発見したなら、それは、まだ残りのセルが少なくとも一つあることを意味しているか、パースが終わったことを意味している。というわけで、remainingCell パーサの動きとしてはまず、「 char ',' を使い、もしカンマにマッチしたら残りのセル全部を返す」ことになる。この時「残りのセル全部」の部分は cell パーサを再帰的に呼び出す。次の選択肢として、もしカンマが見つからなかったら、1行分解析終了を示す、空リストを返す。

eol Parser

Finally, we must define what the end-of-line indicator is. We set it to char '\n', which will suit our purposes fine for now.

最後に、eof文字をパースする必要があるので、char '\n' をセットする。

parseCSV Parser

At the very end of the program, we define a function parseCSV that takes a String and parses it as a CSV file. This function is just a shortcut that calls Parsec's parse function, filling in a few parameters. parse returns Either ParseError [[String]] for the CSV file. If there was an error, the return value will be Left with the error; otherwise, it will be Right with the result.

文字列を取って、それをCSVとしてパースする関数をparseCSVとして定義する。このパーサは、Persecの解析関数のショートカットとなっている。パース結果はEither ParseError [[String]]で帰ってくるので、もしエラーが発生したら Left値となり、そうでなければ実行結果がRight値となる。

この章から学んだこと

このコードは本来使うものではないが、Parsec の基本的な動きとしてはこのような流れになるのだろう。

• パース方式をトップダウンで設計する
• 具体的なパーサでは、<|> 演算子を使って解析の優先度を決めつつ、どの文字をパースするのか指定する
• 目的の文字列を全てパースするために、 main 関数や再帰を用いる
• パースの型は、GenParser Char st a 型で表す
• consume input する（≒入力を食べる）と、解析位置がその分進むことになる

The sepBy and endBy Combinators

sepBy/endBy

This function takes two functions as arguments: the first function parses some sort of content, while the second function parses a separator. sepBy starts by trying to parse content, then separators, and alternates back and forth until it can't parse a separator. It returns a list of all the content that it was able to parse.

The second tool is endBy. It's similar to sepBy, but expects the very last item to be followed by the separator. That is, it continues parsing until it can't parse any more content.

sepBy 関数は２つの引数をとる。一つ目はパーサで、二つ目はセパレータになる。sepBy 関数はまずパースを試みて、次にセパレータをみる。セパレータがマッチできなくなるまで、代わる代わる解析を続ける。返り値は、パースできたすべての文字のリストになる。endBy 関数も似ているが、これは最後の文字がセパレータとなることを期待している。つまり、パースはこれ以上何も解析できなくなるまで続く。

endBy x : x_x_x_x_x
sepBy x _: x_x_x_x_x

ニュアンスについては記事コメントにあったこっちの方がわかりやすいかも。

するとこのようにプログラムでき、かつコードを見ればパースの方式も理解できる形となる。

csvFile' :: GenParser Char st [[String]]
csvFile'    = endBy line' eol

line' :: GenParser Char st [String]
line'       = sepBy cell (char ',')

cell :: GenParser Char st String
cell        = many (noneOf ",\n")

eol :: GenParser Char st Char
eol = char '\n'

parseCSV' :: String -> Either ParseError [[String]]
parseCSV' input = parse csvFile' "(unknown)" input

• CSVファイルは、行と\n 文字で構成されている
• 行は、セルとカンマで構成されている
• セルはカンマ、\n ではない文字で構成されている

Choices

一つのパースの内部に、選択肢を設けることができる。上のケースでは、EOL文字がプラットフォームによって異なる事象をカバーできていないが、この選択肢を使えば対応できる。

<|>

上に書いてあるとおり。

<|>演算子は、解析の分岐を表す。まず最初に左辺のパーサを試してみて、もし一文字もパーサが食べなかったら（最初の一文字からマッチしなかったら）右辺のパーサを試すことになる。

ただ、これだけだと問題が発生する。例えばこのプログラムでは、

let eol'  = string "\n" <|> string "\n\r"

-- | EOL記号をパースし、EOF記号をパースする
parse (eol >> eof)' "" "\n\r"

次のような流れでエラーが発生する。

1. \n がEOL文字としてパースされる。残りの文字は`\r'
2. EOF文字をパースしようとしたが、期待する文字がなかった

実行結果

*Main> parse (eol' >> eof) "" "\n"
Right ()
*Main Data.Either> parse (eol' >> eof) "" "\n\r"
Left (line 2, column 1):
unexpected '\r'
expecting end of input

try

try 関数は Lookahead を表現する。引数に渡すパーサで解析が失敗すると、失敗の直前まで解析位置を戻すことができる。そのため、 <|> 演算子の左辺に try 関数を使うことで、両辺のパーサを試すことが可能となる。

eol :: GenParser Char st String
eol = do
    try (string "\n\r") <|> try (string "\r\n") <|> string "\n" <|> string "\r"

実行結果

*Main> parse (eol >> eof) "" "\n\r"
Right ()

Errors

パースに失敗した時の制御をプログラマが指定できる。上のコードでパースに失敗すると、すこしビジーなメッセージが出力される。

実行結果

*Main> parseCSV "line!"
Left "(unknown)" (line 1, column 6):
unexpected end of input
expecting ",", "\n\r", "\r\n", "\n" or "\r"

プログラムを次のように変更すると、メッセージから意味を汲み取ることができる。

eol = do
    try (string "\n\r") <|> try (string "\r\n") <|> string "\n" <|> string "\r"
    <?> "end of line"

実行結果

*Main> parseCSV "line!"
Left "(unknown)" (line 1, column 6):
unexpected end of input
expecting "," or end of line

このほかのサンプル

サイトでは、この後、もっとリッチなCSVファイルパーサ（例えば、上のプログラムでは、カンマの含まれたセルを処理できない）や、URLエンコードされた文字列やJSONファイルのパースなどを取り上げている。Applicative なパース方式の定義の仕方なども解説があり、結構ボリュームが多かったのでとりあえずここまで。