「ほっ」と。キャンペーン

<   2009年 09月 ( 39 )   > この月の画像一覧

Parsec 式の定義 buildExpressionParser

Parsec の勉強もやっと式のパースを行えるところまでやってきた。Parsec で式を定義するのには便利な関数 buildExpressionParser がある。この関数は、Text.ParserCombinators.Parsec.Expr モジュールに定義されている。式の定義を考える前に、まず一般的な EBNF 記法による式の文法の定義を見てみよう。

expr ::= expr '+' term | term
term ::= term '*' factor | factor
factor ::= '(' expre ') | digit+
digit ::= '0' | '1' | ... | '9'

これを見ると、*の演算は+の演算より優先度が高く、またこの演算が左結合型であることを左再帰で表している。この EBNF 記法をそのまま Parsec のコンビネータで表現するのは面倒なので、式の演算をテーブルに定義しておけばそれを元に式の定義を作ってしまうのが、buildExpressionParser 関数だ。

buildExpressionParser 関数は二つの引数を取る。一つは演算の規則を定義したテーブルのリスト。もう一つは factor(要素) を定義したパーサ関数だ。演算の左結合、右結合はテーブルに定義し、演算の優先度はテーブルのリスト内での前後関係で定義する。

buildExpressionParser 関数を使って0以上の整数の四則演算をする計算機プログラム expr.hs は次のようになる。

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr

expr :: Parser Integer
expr = buildExpressionParser table factor
      <?> "expression"

table = [[op "*" (*) AssocLeft, op "/" div AssocLeft]
        ,[op "+" (+) AssocLeft, op "-" (-) AssocLeft]
        ]
      where
        op s f assoc
          = Infix (do{ string s; return f}) assoc

factor = do{ char '('
           ; x <- expr
           ; char ')'
           ; return x
           }
        <|> number
        <?> "simple expression"

number :: Parser Integer
number = do{ ds <- many1 digit
           ; return (read ds)
           }
        <?> "number"

実行例:
Hugs> :e expr.hs
Hugs> :l expr.hs
Main> parseTest expr "1+2*3"
7

このプログラムでは数と演算子の間にスペースを置くと正しく動作しないが、やっと、式の演算ができるところまでたどり着いた。
[PR]
by tnomura9 | 2009-09-30 19:00 | Haskell | Comments(0)

Parsec ユーザ定義のエラーメッセージ

Parsec は <?> 演算子でユーザ定義のエラーメッセージを設定できる。次のようにすれば word パーサにユーザ定義のエラーメッセージを設定できる。

word :: Parser String
word = many1 letter <?> "word"

簡単な例を Hugs のコンソールからテストしてみた。

Hugs> :l Text.ParserCombinators.Parsec
Text.ParserCombinators.Parsec> parseTest word "123" where word = many1 letter <?> "word"
parse error at (line 1, column 1):
unexpected "1"
expecting word

expecting の後のエラーメッセージがデフォールトの代わりに word が追加されている。

エラーメッセージはパーサ関数のどのレベルにも設定できる。sentence.hs パーサの word パーサに設定した例が、Parsec, a fast combinator parser に解説してある。

import Text.ParserCombinators.Parsec

sentence    :: Parser [String]
sentence    = do{ words <- sepBy1 word separator
                ; oneOf ".?!"
                ; return words
                }
                
separator   :: Parser ()
separator   = skipMany1 (space <|> char ',')

word :: Parser String
word = many1 (letter <?> "") <?> "word"

実行例:
Text.ParserCombinators.Parsec> :e sentence.hs
Text.ParserCombinators.Parsec> :l sentence.hs
Main> parseTest sentence "hi,123"
parse error at (line 1, column 4):
unexpected "1"
expecting space, "," or word
[PR]
by tnomura9 | 2009-09-30 16:37 | Haskell | Comments(0)

Parsec セパレータ

"abc, def, ghi" のようなCSVのデータのようにデータがセパレータで分けられているものがある。こういう文字列を効果的に処理できるのが、sepBy コンビネータだ。sepBy コンビネータは、第1引数にデータ部分のパーサを、第2引数にセパレータのパーサをとる。戻り値はデータのリストだ(Parser モナドの形で返される)。many, many1 の時と同じく、データが0個でもマッチする sebBy と、最低1個のデータが必要な sepBy1 がある。

Hugs> :l Text.ParserCombinators.Parsec
Text.ParserCombinators.Parsec> parseTest (sepBy word (char ',')) "abc,def,ghi" where word = many1 letter
["abc","def","ghi"]

Parsec, a fast combinator parser には、sepBy1 に加えて、セパレータ前後の空白を無視する機能、複数個の行末の区切り文字を認識してパースを中止する機能を加えた例 sentence が紹介されている。

import Text.ParserCombinators.Parsec

sentence    :: Parser [String]
sentence    = do{ words <- sepBy1 word separator
                ; oneOf ".?!"
                ; return words
                }
                
separator   :: Parser ()
separator   = skipMany1 (space <|> char ',')

word :: Parser String
word = many1 letter

実行例:
Main> parseTest sentence "hi,di,hi."
["hi","di","hi"]
[PR]
by tnomura9 | 2009-09-30 11:38 | Haskell | Comments(0)

Parsec 文字や文字列の繰り返し

文字列のマッチングを考えるとき、文字や文字集合の繰り返しを検出したいことはよくある。Parsec の繰り返しに関するコンビネータには、many, many1, skipMany, skipMany1 がある。例えば、letter パーサは数字以外のキャラクタにマッチするので。次のパーサ word は、キャラクタが連続する文字列にマッチする。

word = many letter

Hugs のプロンプトで実験した結果は次のようになる。

Hugs> :l Text.ParserCombinators.Parsec
Text.ParserCombinators.Parsec> parseTest word "abcdef123" where word = many letter
"abcdef"

many と many1 があるが、many は 0 回以上の繰り返しにマッチし、many1 は 1 以上の繰り返しにマッチするという違いがある。

Text.ParserCombinators.Parsec> parseTest (do {char 'a'; many (char 'b')}) "abcdef"
"b"

Text.ParserCombinators.Parsec> parseTest (do {char 'a'; many (char 'b')}) "acdef"
""

Text.ParserCombinators.Parsec> parseTest (do {char 'a'; many1 (char 'b')}) "abcdef"
"b"

Text.ParserCombinators.Parsec> parseTest (do {char 'a'; many1 (char 'b')}) "acdef"
parse error at (line 1, column 2):
unexpected "c"
expecting "b"

また、skipMany, skipMany1 というのがある。many と many1 と同じマッチングをするが、入力の文字列を消費するだけで、結果は返さない。

Text.ParserCombinators.Parsec> parseTest (skipMany (char 'a')) "aaaabc"
()

実験では、繰り返しの要素が letter, char 'a' などの一文字だったが、"hello" などの文字列に対しても、many などは使うことができる。

繰り返しのコンビネータが揃ったので、パターンマッチの道具立てがだんだんできてきた。道具が揃ったら、Parsec を使いこなすための知識は、これらの道具を使ってパーサ関数をどう記述するかということになる。Parsec で何ができるかというのが少し分かり始めた。
[PR]
by tnomura9 | 2009-09-30 06:10 | Haskell | Comments(0)

Parsec パターンの再帰的定義

Parsec, a fast combinator parser の中に出てくる例でパターンの再帰的定義をしたものがある。

parens.hs : 括弧のペアでできているパターンのパーサ

:import Text.ParserCombinators.Parsec

parens  :: Parser ()
parens  = do{ char '('
            ; parens
            ; char ')'
            ; parens
            }
        <|> return ()


実行例
Hugs> :e parens.hs
Main> :l parens.hs
Main> parseTest parens "(())()"
()

Main> parseTest parens "(()()"
parse error at (line 1, column 6):
unexpected end of input
expecting "(" or ")"

Main> parseTest parens "()()()()()()((()))"
()

上の実行例を見ると、parens パーサは括弧のペアの続きにマッチすることができる。括弧のペアは入れ子になっていても、横に続いていてもよい。どうしてこういうことができるのだろうか。

まず、parens が "()" にマッチする様子を考えてみよう。parens は次の二つのパターンにマッチすることができる。

1.'(' parens ')' parens というパターン。
2.文字列が何もないパターン。

入力 "()" が与えられたとき、先頭の文字は '(' なので '(' parens ')' parens パターンの第1文字である '(' にマッチすることが分かる。次にマッチするのは、parens パターンなので、 '(' parens ')' parens パターンか、() -- 文字列が何もないパターン -- にマッチしないといけない。ここでは () パタンがマッチする。次の文字は ')' だからパターンマッチが起きて、次は parens にマッチしなければならない。これは、() とマッチするから、結局、”()” は parens パーサにマッチすることになる。この辺の事情を、マッチした文字列は消していくという方法で式で表してみる。

"()"
= '(' parens ')' parens --- "()"
= parens ')' parens ---- ")"
= () ')' parens --- ")"
= ')' parens --- ")"
= parens --- ""
= () --- ""

全部が消えてしまったのでマッチが起きたことになる。

上の実行例のようなパターンを正規表現で表現するのは大変だろう。Parsec のパタン記述能力の高さが推測できる。Perl 6 を Parsec を使ってあっという間にひとりで書き上げてしまったというのも納得できる。
[PR]
by tnomura9 | 2009-09-29 18:50 | Haskell | Comments(0)

Parsec 意味論

パーサでパターンを検知したときは普通同時にアクションを伴う。Parsec ではアクションは do 記法の中に記述する。

Text.ParserCombinators.Parsec> parseTest (do {string "abc"; return "hello, there"}) "abcdefg"
"hello, there"

Text.ParserCombinators.Parsec> parseTest (do {string "abc"; return "hello, there"}) "bacdefg"
parse error at (line 1, column 1):
unexpected "b"
expecting "abc"

これで、プライマリーのパーサ関数(char, letter, digit, string など)、プライマリーのパーサ関数を組み合わせる関数または演算子(do, <|>)、パーサ関数を文字列に適用する parser 関数、そして、パターンがマッチしたときのアクションの記述という4種類の道具が揃った。

入力列からパーサでパターンを検出し、マッチしたときはアクションを起こすというのがパーサの役目だから、Parsec の基本的な骨組みは分かった気がする。
[PR]
by tnomura9 | 2009-09-29 16:08 | Haskell | Comments(0)

Parsec try

string パーサは文字列にマッチするパーサなので、testOr = string "(a)" <|> "(b)" は、"(a)" または "(b)" にマッチするように思うが、"(a)" にはマッチするが、"(b)" にはマッチしてくれない。

Hugs> :l Text.ParserCombinators.Parsec
Text.ParserCombinators.Parsec> parseTest (string "(a)" <|> string "(b)") "(a)"
"(a)"

Text.ParserCombinators.Parsec> parseTest (string "(a)" <|> string "(b)") "(b)"
parse error at (line 1, column 1):
unexpected "b"
expecting "(a)"

これはエラーメッセージの unexpected "b" で分かるように、最初の "(a)" とのマッチが失敗した時に、"(b)" の '(' が消費されてしまって、次に "(b)" とマッチさせようとしたときに、入力文字が "b)" になってしまっているからだ。Parsec は "predictive" (予見的)なパーサなので、指示しなければバックトラックをしてくれない。Parsec にバックトラックをさせようと思ったら、次のように try 関数を使う。

Text.ParserCombinators.Parsec> parseTest ((try (string "(a)")) <|> string "(b)") "(b)"
"(b)"
[PR]
by tnomura9 | 2009-09-29 06:59 | Haskell | Comments(0)

Parsec 連接と選択

char 'a' は一文字にマッチするパーサだ。

Hugs> :l Text.ParserCombinators.Parsec
Text.ParserCombinators.Parsec> parseTest (char 'a') "abc"
'a'

しかし "ab" のような文字の並びにマッチするようなパーサを作りたい場合がある。そのような連接にマッチするパーサを作るときは、do 記法を使う。

Text.ParserCombinators.Parsec> parseTest sequence "abc" where sequence = do {char 'a'; char 'b'}
'b'

また、'a' か 'b' のどちらかにマッチするような選択のパーサを作るには <|> 演算子を使う。

Text.ParserCombinators.Parsec> parseTest choice "bac" where choice = char 'a' <|> char 'b'
'b'

このように、do 記法や <|> 演算子を使うことで記号の組み合わせにマッチするパーサを定義できる。
[PR]
by tnomura9 | 2009-09-28 23:57 | Haskell | Comments(0)

Parsec - run

今、Parsec, a fast combinator parser を読んでいる。一気に読んでもなかなか分かりづらいのでわかった部分を細切れにして記事にしてみることにした。

まずは、parse 関数の使い方で run という短い関数が紹介されていた。やっていることは、parse 関数に、パーサ関数と入力文字列を渡し、戻ってきた戻り値のモナドからフィールドの値を取り出す作業だ。モナドから値を取り出す方法は、パターンマッチを利用している。この関数に、Parsec を実用的に使う使うときのエッセンスが含まれているような気がする。

import Text.ParserCombinators.Parsec

simple :: Parser Char
simple = letter

run :: Show a => Parser a -> String -> IO ()
run p input
  = case (parse p "" input) of
    Left err -> do putStr "parse error at "
                   print err
    Right x -> print x

実行例:
Main> run simple "abc"
'a'

run と同じ動作をする関数は、Parsec モジュールに parseTest というなまえで定義済みなので、プログラムを書かなくてもパーサ関数をテストできる。

Main> parseTest digit "123"
'1'

コンピュータネタが続くが、Parsec だけはやっておきたい気がする。
[PR]
by tnomura9 | 2009-09-28 13:17 | Haskell | Comments(0)

Parsec パーサコンビネータの意味

Parsec はパーサコンビネータだ。それでは、パーサコンビネータとは何かということになるが、どうも基本的なパーサの関数を組み合わせて複雑なパーサを作り上げる仕組みらしい。Hugs のプロンプトから Parsec を load して、いろいろ試してみた。

Main> :l Text.ParserCombinators.Parsec
Text.ParserCombinators.Parsec>

次の例のように、char 'a' というパーサ関数は 'a' 一文字にマッチするが、

Text.ParserCombinators.Parsec> parse (char 'a') "" "aaabc"
Right 'a'

これに many1 関数を加えると 'a' の繰り返しにマッチする。

Text.ParserCombinators.Parsec> parse (many1 (char 'a')) "" "aaabc"
Right "aaa"

また、string "hi" というパーサ関数は、"hi" という文字列にマッチするが、

Text.ParserCombinators.Parsec> parse (string "hi") "" "hihihi"
Right "hi"

これに、many 関数を組み合わせると、"hi" の繰り返しにマッチしそれを配列として戻す。

Text.ParserCombinators.Parsec> parse (many (string "hi")) "" "hihihi"
Right ["hi","hi","hi"]

このほかにも、基本的なパーサ関数や、それらを組み合わせるための高階関数が Parsec には揃っているようだ。それらを組み合わせることで BNF 記法で表すような複雑なパーサも簡単に作ることができるらしい。Parsec の使い方のようなものが見えてきたが、残念なのはドキュメントがないことだ。Haskell も日本語の本がもっと出てくれば爆発的に流行するような気がする。
[PR]
by tnomura9 | 2009-09-27 22:40 | Haskell | Comments(0)