Utotch Blog: 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 は以下です。

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 するには

char c

を使います。文字が、複数の文字リスト(ex:数字列)のどれかにマッチすればよい場合は、

1	`oneOf [Char]`

を使います。 ParsecSample1.hs

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+23" parseTest expr "(1+2)3"`

等で解析結果を確認できます。

(3): (2) を Applicative スタイルにする

Applicative スタイルにすると、もっと簡潔に記述できます。やってみましょう。
ParsecSample2.hs

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

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 で、参考になる情報源を紹介していただいたので、ここにまとめてみます。

あどけない話:Applicativeのススメ本記事の元ネタです。Parsec3 の入門記事としても読めます。kazu さんの記事は、どれも非常に参考になります。
プログラミングHaskell 8章関数型パーサ ruicc 氏による関数型パーサの解説。関数型パーサの考え方についての非常に素晴しい解説資料だと思います。
Write Yourself a Scheme in 48 Hours Scheme を実装しながら Parser を学ぶらしい
Implementing functional languages: a tutorial 関数型言語の実装解説
Parsec, a fast combinator parser
還暦プログラマの挑戦(Haskell に挑む→F#による言語造り)
Parsec3
attoparsec

Parsec3 や、attoparsec の使い方について、もう少し詳しい解説記事があると、喜ぶ人が多そうです(私も含めて)。私も上記の文書は、まだ勉強できていませんが、理解が進んだらまた紹介したいと思います。

3 件のコメント:

Unknown2011年12月19日 10:32
山本です。

attoparsec を終了させるには空文字列を feed する必要があります。
返信削除
返信
thimura2011年12月19日 16:56
山本さんのコメントにもあるように空文字列を feed しても良いのですが、1 つしか入力を与えないのであれば Data.Attpparsec.parseOnly を使うと良いと思います。
返信削除
返信
utotch2011年12月28日 0:11
コメントが遅くなってしまいました。

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

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

どうもありがとうございました。
返信削除
返信

コメントを追加

Utotch Blog

2011年12月18日日曜日