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 を使ってあっという間にひとりで書き上げてしまったというのも納得できる。
by tnomura9
| 2009-09-29 18:50
| Haskell
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||