2011年12月18日日曜日

Haskell で parser を書くには (初心者編)

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 するには
1
char c
を使います。文字が、複数の文字リスト(ex:数字列)のどれかにマッチすればよい場合は、
1
oneOf [Char]
を使います。 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 してテストしてみましょう。
1
parseTest expr "1+2*3"
うまく行きませんね。あ、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 の使い方について、もう少し詳しい解説記事があると、喜ぶ人が多そうです(私も含めて)。私も上記の文書は、まだ勉強できていませんが、理解が進んだらまた紹介したいと思います。

4 件のコメント:

  1. 山本です。

    attoparsec を終了させるには空文字列を feed する必要があります。

    返信削除
  2. 山本さんのコメントにもあるように空文字列を feed しても良いのですが、1 つしか入力を与えないのであれば Data.Attpparsec.parseOnly を使うと良いと思います。

    返信削除
  3. コメントが遅くなってしまいました。

    > 山本さん
    ご指摘ありがとうございます。 attoparsec をまだ触ったばかりなので、知りませんでした。

    > thimura さん
    parseOnly というのがあるのですね.. 勉強になります。なかなかゆっくり調べたり Document 読んだりする時間がないので、いろいろ教えていただけるのは非常にありがたいです。

    どうもありがとうございました。

    返信削除
  4. I'm glad to be reading this article, I simply want to offer you a huge thumbs up for your great information.
    Tableau Guru
    http://www.sqiar.com

    返信削除