「駄目日記/2006年04月26日/Parsecを使ってみる。」の編集履歴（バックアップ）一覧はこちら

「駄目日記/2006年04月26日/Parsecを使ってみる。」(2006/04/26 (水) 17:53:50) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

#blognavi

このサイトでは最終的にHaskellで[[KISSローダー>http://www.kiss-wkp.com/]]を作るという野望があるわけで。

今回は、コンフィグファイルの読み込みで使うであろう、Parsecに手を付けてみました。

[[Parsecのサイト>http://www.cs.uu.nl/~daan/parsec.html]]

Parsecを使えば簡単にLL(n)文法のテキストファイルを簡単に読み込めるようになるらしいです。（理論的なことはよくわかってない）

自分は、上記のサイトのparsec-2.0.zip をダウンロードしてきたあと、Hugsの作業フォルダにTextフォルダ以下を展開しました。こうすればとりあえずは使えるようになります。
（詳しくはHugsやGHCのマニュアルを読んでください）

-Parsecの特徴
Yacc+LexやJavaCCが「文法ファイルからプログラムソースを自動生成するツール」なのに対し、Parsecは「ただのHaskellのライブラリ」です。
本体の言語のほかに「文法ファイルの文法」を覚える必要がありません。

-とりあえず試してみる
 module Main where
 import Text.ParserCombinators.Parsec
 
 paren :: Parser Char
 paren = (char '{') >> (char '}')
こんだけ。
見れば分かるとおりモナドです。
まず文字列の頭から'{'かどうかチェックして次に'}'かどうかチェックしてます。
 Main> parseTest paren "{}" ← parseTestはParsecの関数
 '}'                        ← 成功したのか？

 Main> parseTest paren "{x}"  ← わざと間違ってみる。
 parse error at (line 1, column 2): ← それっぽいエラーが。
 unexpected "x"
 expecting "}"
どうやらうまくいってる様子。
パース成功したときに'}'とでているのは後述。

もちろんモナドだからdo構文だって使えます。
 paren2 = do
    char '{'
    char '}'
繰り返しはこう
 starplus = do
    many (char '*')
    many1 (char '+')
これで、「'*'の０回以上の繰り返しのあとに'+'の１回以上の繰り返し。」になります。

正規表現の(a|b)『aまたはb』は<|>という新しい演算子を使います。
 starplus2 =
    many1 (char '*' <|> char '+')
これで「'*'か'+'の１回以上の繰り返し」になります。

正規表現の[ab]のようなもの。
引数の文字列のいずれか１文字とマッチします。
 starplus3 = many1 (oneOf "*+")
ちょっと試してみる。
 Main> parseTest starplus2 "+*+" 
 "+*+"
 
 Main> parseTest starplus2 "+*+@" ←ためしに駄目っぽい入力を
 "+*+"                            ←成功してしまった
 
 Main> parseTest starplus2 "@   " ←やっと失敗した
 parse error at (line 1, column 1): 
 unexpected "@"
 expecting "*" or "+"
途中までパースに成功していればエラーにならないようです。

最後まできっちりチェックしたければこうするっぽい。
 starplus4 = do
    many1 (char '*' <|> char '+')
    eof --正規表現の$に相当する関数。最後にのみマッチ
１文字づつチェックは面倒ですから文字列でまとめてチェックする(string)という組み込みパーサーも使ってみます。
 dame = string "abc" <|> char '+'

 Main> :l sample.hs 
 ERROR "sample.hs":23 - Type error in application
 *** Expression     : string "abc" <|> char '+'
 *** Term           : string "abc"
 *** Type           : GenParser Char b String
 *** Does not match : GenParser Char a Char
型不整合になってしまいました。

実は、Parsecのパーサーもただの(Parserモナドの)関数ですから、返り値をもっていて(<|>)を使うときは左右それぞれ型が合っていなければならないようです。
つまり(string "abc")は成功したときは(Parser String)という型の値を返しますが、char '+'の返り値は(Parser Char)だから駄目ということ。
（エラーメッセージと少しちがいますがだいたいそんな感じ。）

とりあえずこうしてみた。
(（>>)より(<|>)のほうが結合の優先順位がたかいので注意。）
 abcplus :: Parser String
 abcplus = 
    string "abc" <|> (char '+' >> return "+")
 
 abcplus2 :: Parser String
 abcplus2 = --これでもOK
    string "abc" <|> 
    ( do
        char '+' 
        return "+"
    )
 
 abcplus3 :: Parser ()
 abcplus3 = --どっちも返り値なしで合わせてみたパターン
    (string "abc" >> return ()) <|> (char '+' >> return () )
見れば分かるとおり、Parserモナドのreturn関数はチェックをまったくせずに任意のParser型の返り値を作れます。

（>>）や（>>=）で結合した場合はもちろん最後の値が有効になりますから
『(char '{') >> (char '}')』の結果が成功したときには'}'が表示されていたわけです。

ちなみにmanyやmany1は繰り返しの結果をリストにして返します。
いままで(char x)をmanyに適用させていたのでうまいぐあいに(Parser [Char])つまりは(Parser String)が帰ってきていたわけでした。

あと、気をつけなければならないのは(<|>)は最初の（左側の）関数を試したあとで『そのままでは後戻りしない』らしいこと↓。
(以下[[邦訳ドキュメント>http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tmp/Parsec.html]]の受け売り。)
 testOr  =   string "(a)"
         <|> string "(b)"
これを parserTest testOr "(b)" でためしてみると
パースに失敗してしまいます。
 Main> parserTest testOr "(b)"
 ERROR - Undefined variable "parserTest"
 Main> parseTest testOr "(b)"
 parse error at (line 1, column 1):
 unexpected "b"
 expecting "(a)"
これは<|>の最初の関数でひとたび２文字以上先に進んでしまうと二度と後戻りしないからのようです。

これには２通り解決方法があります。
最初は(try)という関数を使う方法。
 testOr2  = try( string "(a)" ) <|> string "(b)"
基本的にtryの中にはいくらでも複雑なパーサーが入れられるようですがそれだけ後戻り用メモリや処理時間のペナルティも大きくなります。

二番目の方法は、実現したい文法によっては難しいこともあるかも。
 testOr3  = do
        char '('
        (string "a" <|> string "b")
        char ')'
ここがParsecと正規表現の違う点だと思いました。

なるべくtryを使わないように、また使うとすればなるべく範囲を狭くするようにするのが高速化のコツでしょうか。

最後に返り値を使った例を。
 pair :: Parser (String,String)
 pair = do
    char '{'
    a <- many1 (noneOf ",}") -- noneOf x はx以外のものとマッチ
    char ','
    b <- many1 (noneOf ",}")
    char '}'
    return (a,b)

 pairs :: Parser [(String,String)]
 pairs = many1 pair

{a,b}を入力すると
("a","b")というタプルを返します。
 Main> parseTest pair "{,}"        ←わざとエラーに
 parse error at (line 1, column 2):
 unexpected ","
 
 Main> parseTest pair "{a,b}"      ←成功！
 ("a","b")
 
 Main> parseTest pairs "{a,b}{c,d}{xxx,yyy}"  ←こっちも試す
 [("a","b"),("c","d"),("xxx","yyy")]
複雑なdata型なども作れそうです。

以上でParsecの基本は一通りみたでしょうか。

正規表現でできるようなことはだいたいできるようになりました。
しかし、これだけで実用的なパーサーを１から作るのは結構大変です。
正規表現よりタイプ量がものすごく多くなりますし。
コンパイルと型チェックできるだけでもそれなりに自分にはありがたいのですけどね。
（他の言語で正規表現は単なる文字列値として扱われて実行時まで記述ミスがわからないことも多い）

実際にParsecを使ってパーサーを書くときには、char や string といった低レベルな関数ばかりでなく、空白やコメントを読み飛ばしながらリテラルや予約語をとりだせるような、もうすこし高機能な関数を使用することになります。
(↓下記ドキュメントにも解説が載っています）
だたし、こういった高機能な関数はコメントの定義(/* */,--など)や、識別子や演算子に使える文字の種類など設定項目が結構あります。

この辺の使い方も気が向いたら書こうかと思います。

今回のエントリに関しては下記のParsecの和訳ドキュメントに
大いにお世話になりました。
http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tmp/Parsec.html

あと、ここもリンク集と使用レポートおせわになりました。
http://221.112.61.214/~kzk/column/haskell_parsec.html


#right{
カテゴリ: &#x5b;[[プログラミング>駄目日記/カテゴリ/プログラミング]]&#x5d; - &trackback() - 2006年04月26日 17:53:13
}
#comment(nostyle,nsize8,size30)
#blognavi

#blognavi

このサイトでは最終的にHaskellで[[KISSローダー>http://www.kiss-wkp.com/]]を作るという野望があるわけで。

今回は、コンフィグファイルの読み込みで使うであろう、Parsecに手を付けてみました。

[[Parsecのサイト>http://www.cs.uu.nl/~daan/parsec.html]]

Parsecを使えば簡単にLL(n)文法のテキストファイルを簡単に読み込めるようになるらしいです。（理論的なことはよくわかってない）

自分は、上記のサイトのparsec-2.0.zip をダウンロードしてきたあと、Hugsの作業フォルダにTextフォルダ以下を展開しました。こうすればとりあえずは使えるようになります。
（詳しくはHugsやGHCのマニュアルを読んでください）

-Parsecの特徴
Yacc+LexやJavaCCが「文法ファイルからプログラムソースを自動生成するツール」なのに対し、Parsecは「ただのHaskellのライブラリ」です。
本体の言語のほかに「文法ファイルの文法」を覚える必要がありません。

-とりあえず試してみる
 module Main where
 import Text.ParserCombinators.Parsec
 
 paren :: Parser Char
 paren = (char '{') >> (char '}')
こんだけ。
見れば分かるとおりモナドです。
まず文字列の頭から'{'かどうかチェックして次に'}'かどうかチェックしてます。
 Main> parseTest paren "{}" ← parseTestはParsecの関数
 '}'                        ← 成功したのか？

Main> parseTest paren "{x}"  ← わざと間違ってみる。
parse error at (line 1, column 2): ← それっぽいエラーが。
unexpected "x"
expecting "}"

どうやらうまくいってる様子。
パース成功したときに'}'とでているのは後述。

もちろんモナドだからdo構文だって使えます。
 paren2 = do
    char '{'
    char '}'
繰り返しはこう
 starplus = do
    many (char '*')
    many1 (char '+')
これで、「'*'の０回以上の繰り返しのあとに'+'の１回以上の繰り返し。」になります。

正規表現の(a|b)『aまたはb』は<|>という新しい演算子を使います。
 starplus2 =
    many1 (char '*' <|> char '+')
これで「'*'か'+'の１回以上の繰り返し」になります。

正規表現の[ab]のようなもの。
引数の文字列のいずれか１文字とマッチします。
 starplus3 = many1 (oneOf "*+")
ちょっと試してみる。

Main> parseTest starplus2 "+*+" 
"+*+"

Main> parseTest starplus2 "+*+@" ←ためしに駄目っぽい入力を
"+*+"                            ←成功してしまった

Main> parseTest starplus2 "@   " ←やっと失敗した
parse error at (line 1, column 1): 
unexpected "@"
expecting "*" or "+"

途中までパースに成功していればエラーにならないようです。

最後まできっちりチェックしたければこうするっぽい。
 starplus4 = do
    many1 (char '*' <|> char '+')
    eof --正規表現の$に相当する関数。最後にのみマッチ
１文字づつチェックは面倒ですから文字列でまとめてチェックする(string)という組み込みパーサーも使ってみます。
 dame = string "abc" <|> char '+'

Main> :l sample.hs 
ERROR "sample.hs":23 - Type error in application
*** Expression     : string "abc" <|> char '+'
*** Term           : string "abc"
*** Type           : GenParser Char b String
*** Does not match : GenParser Char a Char

型不整合になってしまいました。

実は、Parsecのパーサーもただの(Parserモナドの)関数ですから、返り値をもっていて(<|>)を使うときは左右それぞれ型が合っていなければならないようです。
つまり(string "abc")は成功したときは(Parser String)という型の値を返しますが、char '+'の返り値は(Parser Char)だから駄目ということ。
（エラーメッセージと少しちがいますがだいたいそんな感じ。）

とりあえずこうしてみた。
(（>>)より(<|>)のほうが結合の優先順位がたかいので注意。）
 abcplus :: Parser String
 abcplus = 
    string "abc" <|> (char '+' >> return "+")
 
 abcplus2 :: Parser String
 abcplus2 = --これでもOK
    string "abc" <|> 
    ( do
        char '+' 
        return "+"
    )
 
 abcplus3 :: Parser ()
 abcplus3 = --どっちも返り値なしで合わせてみたパターン
    (string "abc" >> return ()) <|> (char '+' >> return () )
見れば分かるとおり、Parserモナドのreturn関数はチェックをまったくせずに任意のParser型の返り値を作れます。

（>>）や（>>=）で結合した場合はもちろん最後の値が有効になりますから
『(char '{') >> (char '}')』の結果が成功したときには'}'が表示されていたわけです。

ちなみにmanyやmany1は繰り返しの結果をリストにして返します。
いままで(char x)をmanyに適用させていたのでうまいぐあいに(Parser [Char])つまりは(Parser String)が帰ってきていたわけでした。

あと、気をつけなければならないのは(<|>)は最初の（左側の）関数を試したあとで『そのままでは後戻りしない』らしいこと↓。
(以下[[邦訳ドキュメント>http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tmp/Parsec.html]]の受け売り。)
 testOr  =   string "(a)"
         <|> string "(b)"
これを parserTest testOr "(b)" でためしてみると
パースに失敗してしまいます。

Main> parserTest testOr "(b)"
ERROR - Undefined variable "parserTest"
Main> parseTest testOr "(b)"
parse error at (line 1, column 1):
unexpected "b"
expecting "(a)"

これは<|>の最初の関数でひとたび２文字以上先に進んでしまうと二度と後戻りしないからのようです。

これには２通り解決方法があります。
最初は(try)という関数を使う方法。
 testOr2  = try( string "(a)" ) <|> string "(b)"
基本的にtryの中にはいくらでも複雑なパーサーが入れられるようですがそれだけ後戻り用メモリや処理時間のペナルティも大きくなります。

二番目の方法は、実現したい文法によっては難しいこともあるかも。
 testOr3  = do
        char '('
        (string "a" <|> string "b")
        char ')'
ここがParsecと正規表現の違う点だと思いました。

なるべくtryを使わないように、また使うとすればなるべく範囲を狭くするようにするのが高速化のコツでしょうか。

最後に返り値を使った例を。
 pair :: Parser (String,String)
 pair = do
    char '{'
    a <- many1 (noneOf ",}") -- noneOf x はx以外のものとマッチ
    char ','
    b <- many1 (noneOf ",}")
    char '}'
    return (a,b)

 pairs :: Parser [(String,String)]
 pairs = many1 pair

{a,b}を入力すると
("a","b")というタプルを返します。

Main> parseTest pair "{,}"        ←わざとエラーに
parse error at (line 1, column 2):
unexpected ","
 
Main> parseTest pair "{a,b}"      ←成功！
("a","b")

Main> parseTest pairs "{a,b}{c,d}{xxx,yyy}"  ←こっちも試す
[("a","b"),("c","d"),("xxx","yyy")]


複雑なdata型なども作れそうです。

以上でParsecの基本は一通りみたでしょうか。

正規表現でできるようなことはだいたいできるようになりました。
しかし、これだけで実用的なパーサーを１から作るのは結構大変です。
正規表現よりタイプ量がものすごく多くなりますし。
コンパイルと型チェックできるだけでもそれなりに自分にはありがたいのですけどね。
（他の言語で正規表現は単なる文字列値として扱われて実行時まで記述ミスがわからないことも多い）

実際にParsecを使ってパーサーを書くときには、char や string といった低レベルな関数ばかりでなく、空白やコメントを読み飛ばしながらリテラルや予約語をとりだせるような、もうすこし高機能な関数を使用することになります。
(↓下記ドキュメントにも解説が載っています）
だたし、こういった高機能な関数はコメントの定義(/* */,--など)や、識別子や演算子に使える文字の種類など設定項目が結構あります。

この辺の使い方も気が向いたら書こうかと思います。

今回のエントリに関しては下記のParsecの和訳ドキュメントに
大いにお世話になりました。
http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tmp/Parsec.html

あと、ここもリンク集と使用レポートおせわになりました。
http://221.112.61.214/~kzk/column/haskell_parsec.html


#right{
カテゴリ: &#x5b;[[プログラミング>駄目日記/カテゴリ/プログラミング]]&#x5d; - &trackback() - 2006年04月26日 17:53:13
}
#comment(nostyle,nsize8,size30)
#blognavi