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 意味論 >>