Haskell で parser を書くには (初心者編)
勝手に Haskell Advent Calendar 2011
Haskell Advent Calendar 2011 にはエントリーできませんでしたけど、一人寂しく「勝手に Haskell Advent Calendar 2011」を開催して、わくわくクリスマスを待ちたいと思います。
目的:
Parsec3 と attoparsec の基本的使用法, Applicative スタイルを習得する
前置き:
Haskell で parser を書くにはどうすればいいのでしょうか? 私は、これを勉強すべく情報源を探しましたが、一体どこからどう始めればいいのか分からず、非常に混乱しました。「この記事を読めば大体概要が全部分かる」という情報源が日本語でも英語でも見つけられなかったからです。なので自分でまとめてみることにしました。 (私は、まだ Haskell 初心者+αのレベルで、parser の情報も現時点での情報ということをご理解ください)
私が混乱したのは、以下のような情報に出会ったからです。
- Programming In Haskell に書いてある parser は、本の中のコードのみでは動かない
- Haskell で parser を書くには、Parsec を使うとよいらしい
- Parsec2 は使うな。Parsec3 使え。
- Real World Haskell は Parsec2 で記述されているので古い
- Parsec は遅い。attoparsec は速い。
- attoparsec は、エラーメッセージが不親切
？？？。一体どうすればいいのでしょうか? Parsec はいいの?ダメなの? attoparsec はいいの?ダメなの? 最良の選択肢は、どれなの??
勉強会で質問してみた結果、以下のように理解しました。
- デファクトスタンダードが どれか一つ というわけではなく、皆さんは "Parsec3" と "attoparsec" を使い分けているようだ
- Parsec3 は attoparsec より速度は遅いが、エラーメッセージが親切
- attoparsec は Parsec3 より速度は速いが、エラーメッセージが不親切
- ニーズに応じて Parsec3 と attoparsec を使い分ける(もしくは両方使う)のがオススメ。でも、Parsec2 は古いので使わないことをオススメ
やっと状況が分かりました。Parsec3 と attoparsec を理解すればいいようです。しかし、それでも まだ困惑は残りました。なぜなら、Parsec3 と attoparsec の初心者向けの、よい Tutorial 記事を見つけられなかったからです。
この記事では、「Parsec3 と attoparsec の基本的な書きかたを理解する」ことを目的とします。副産物として、Applicative スタイルというのに触れます。
順番としては、以下の順番で書きます。
- (1): 簡単な BNF を定義する
- (2): Parsec3 で、(1) を解析してみる
- (3): (2) を Applicative スタイルにする
- (4): (3) を attoparsec に移植する
- (5): さらに勉強するための情報源
尚, 内容のほとんどは、
kazu-yamamoto さんの記事 を参考にさせていただいてます。(kazu さん ありがとうございます)
(1): 簡単な BNF を定義する
プログラミング Haskell の 8章の内容を多少簡単化して、 "1ケタの数字の加算と乗算ができるパーサー" を題材にします。BNF は以下です。
1
2
3
4
| expr ::= term '+' expr | term
term ::= factor '*' term | factor
factor ::= '(' expr ')' | nat
nat ::= '0' | '1' | '2' | ...
|
1ケタの数値のみしか扱えませんが、()が使え、乗算が加算より優先順位が高く、'+','*'は右結合になっています。
(2): Parsec3 で、(1) を解析してみる
上記 (1) のBNF を解析し、data Exp 型の結果を返す parser を Parsec3 で実装します。Parsec3 を使うには
1
2
| import Text.Parsec
import Text.Parsec.String
|
します。 次に、BNF の定義を Haskell のコードに対応させて実装していきます。BNF で、選択を意味する '|' は、Haskellでは、Text.Parsec.(<|>) という二項演算子です。 (本:プログラミングHaskell では、(+++) と記述されています) 一文字の記号 '+', '*' を parse するには
を使います。文字が、複数の文字リスト(ex:数字列)のどれかにマッチすればよい場合は、
を使います。
ParsecSample1.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| import Data.Char (ord)
import Text.Parsec (char, oneOf, (<|>), parseTest)
import Text.Parsec.String (Parser)
data Exp = Add Exp Exp | Mul Exp Exp | Nat Int deriving Show
{- BNF of one digit addtion & multiplication
expr ::= term ('+' expr | ε)
term ::= factor ('*' term | ε)
factor ::= '(' expr ')' | nat
nat ::= '0' | '1' | '2' | ...
-}
-- expr ::= term ('+' expr | ε)
expr::Parser Exp
expr =
do
t <- term
do
char '+'
e <- expr
return (Add t e)
<|> return t
-- term ::= factor ('*' term | ε)
term::Parser Exp
term =
do
f <- factor
do
char '*'
t <- term
return (Mul f t)
<|> return f
-- factor ::= '(' expr ')' | nat
factor::Parser Exp
factor =
do
char '('
e <- expr
char ')'
return e
<|> nat
-- nat ::= '0' | '1' | '2' | ...
nat::Parser Exp
nat =
do
c <- oneOf ['0'..'9']
return (Nat (charToInt c))
where
charToInt c = ord c - ord '0'
{- How to test this
parseTest expr "1+2*3"
parseTest expr "(1+2)*3"
-}
|
do の後に、素直に BNF の個々の定義を並べて処理して行けばよいのですが、ちょっと読みにくいですね(このままだと、「BNFをそのまま実装できる」は、ちょっと言い過ぎな感じ)。 動作をテストするには、ghci にロードして
1
2
| parseTest expr "1+2*3"
parseTest expr "(1+2)*3"
|
等で解析結果を確認できます。
(3): (2) を Applicative スタイルにする
Applicative スタイル にすると、もっと簡潔に記述できます。やってみましょう。
ParsecSample2.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| import Control.Applicative ((<$>),(*>),(<*),pure)
import Data.Char (ord)
import Text.Parsec (char, oneOf, (<|>), parseTest)
import Text.Parsec.String (Parser)
data Exp = Add Exp Exp | Mul Exp Exp | Nat Int deriving Show
{- BNF of one digit addtion & multiplication
expr ::= term ('+' expr | ε)
term ::= factor ('*' term | ε)
factor ::= '(' expr ')' | nat
nat ::= '0' | '1' | '2' | ...
-}
-- expr ::= term ('+' expr | ε)
expr::Parser Exp
expr =
do
t <- term
(Add t <$> (char '+' *> expr)) <|> pure t
-- term ::= factor ('*' term | ε)
term::Parser Exp
term =
do
f <- factor
(Mul f <$> (char '*' *> term)) <|> pure f
-- factor ::= '(' expr ')' | nat
factor::Parser Exp
factor = (char '(' *> expr <* char ')') <|> nat
-- nat ::= '0' | '1' | '2' | ...
nat::Parser Exp
nat = Nat . charToInt <$> oneOf ['0'..'9']
where
charToInt c = ord c - ord '0'
{- How to test this
parseTest expr "1+2*3"
parseTest expr "(1+2)*3"
-}
|
ぐっと短くなりましたね。これなら BNF を、そのまま Haskell コードに実装できると言っても過言ではなさそうです。 Applicative スタイルの詳細は、kazu さんの記事を参照していただくとよいですが、
- pure は return と同じ (値を返り値の型に wrap する)
- (<$>) は fmap (文脈に持ち上げる)
- (*>) は左の処理結果を捨てて連結
- (<*) は右の処理結果を捨てて連結
という意味のようです(私も勉強中...。)
(4): (3) を attoparsec に移植する
なんとか Parsec3 を使って簡単な BNF を Haskell で解析できるようになりました。でも、
attoparsec も使ってみたいです。やってみましょう。
1
| cabal install attoparsec
|
等で適当にインストールしてください(省略)。 attoparsec を使うには、先程の Parsec3 の import の変わりに、以下を記述します。
1
2
| import Data.Attoparsec.Text
import Data.Text
|
attoparsec は String ではなくて、ByteString と Text を parse するようです。ここでは、Data.Text を使います。
もしかして、import を変えれば、そのまま動いたりして、、と思ったのですが、Parsec3 にあった
oneOf という関数が無いようです。attoparsec の satisfy 関数を使ってテキトーに作ります。
1
2
| oneOf::[Char]->Parser Char -- attoparsec には oneOf がないので自作
oneOf xs = satisfy $ flip elem $ xs
|
ここだけ変更すれば、そのまま行けそうです。
AttoparsecSample1.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| import Control.Applicative ((<$>),(*>),(<*),pure,(<|>))
import Data.Char (ord)
-- import Text.Parsec (char, oneOf, (<|>), parseTest)
-- import Text.Parsec.String (Parser)
import Data.Attoparsec.Text (char, Parser, parseTest, satisfy)
import Data.Text (pack)
oneOf::[Char]->Parser Char -- attoparsec には oneOf がないので自作
oneOf xs = satisfy $ flip elem $ xs
data Exp = Add Exp Exp | Mul Exp Exp | Nat Int deriving Show
{- BNF of one digit addtion & multiplication
expr ::= term ('+' expr | ε)
term ::= factor ('*' term | ε)
factor ::= '(' expr ')' | nat
nat ::= '0' | '1' | '2' | ...
-}
-- expr ::= term ('+' expr | ε)
expr::Parser Exp
expr =
do
t <- term
(Add t <$> (char '+' *> expr)) <|> pure t
-- term ::= factor ('*' term | ε)
term::Parser Exp
term =
do
f <- factor
(Mul f <$> (char '*' *> term)) <|> pure f
-- factor ::= '(' expr ')' | nat
factor::Parser Exp
factor = (char '(' *> expr <* char ')') <|> nat
-- nat ::= '0' | '1' | '2' | ...
nat::Parser Exp
nat = Nat . charToInt <$> oneOf ['0'..'9']
where
charToInt c = ord c - ord '0'
{- How to test this
parseTest expr "1+2*3"
parseTest expr "(1+2)*3"
↓
parseTest expr $ pack "1+2*3 "
parseTest expr $ pack "(1+2)*3 "
※ 最後にスペースがないと、成功していても "Partial _" という出力になる
-}
|
ghci に load してテストしてみましょう。
うまく行きませんね。あ、String じゃなくて、Text にしないとダメだったかな? pack で String->Text にしてみます。
1
2
| > parseTest expr $ pack "1+2*3"
Partial _
|
あれ、"Partial _" とか言われますね。うまく行ってないのだろうか??? ちょっと末尾に余分なスペースを入れてみよう。
1
2
| > parseTest expr $ pack "1+2*3 "
Done " " Add (Nat 1) (Mul (Nat 2) (Nat 3))
|
どうやら、直前までは、うまく解析できてるみたい。。よかったー(?)。 今日は、この辺で勘弁してください。attoparsec を深く理解するには、ByteString,Text あたりの知識が必要かも(ByteString, Text については、私もまだ勉強していません)
(5): さらに勉強するための情報源
なんとか、Parsec3 と attoparsec を使って、動作するコードを実装し、雰囲気を掴みました。あとは、情報があれば、自分で勉強していけそうです。勉強会, Twitter で、参考になる情報源を紹介していただいたので、ここにまとめてみます。
Parsec3 や、attoparsec の使い方について、もう少し詳しい解説記事があると、喜ぶ人が多そうです(私も含めて)。私も上記の文書は、まだ勉強できていませんが、理解が進んだらまた紹介したいと思います。
