パターンの再帰的定義

Prelude Text.Parsec> parens = (do {char '('; parens; char ')'; parens} <|> 
return "OK") :: Parsec String () String
Prelude Text.Parsec> parseTest parens "()"
"OK"
Prelude Text.Parsec> parseTest parens "(())"
"OK"

再帰的なパーサの動作

再帰的なパーサがどのように動作するかを見てみよう。"()" という文字列に対し parens がどのように動作するかを見る。

"()" -> parens を適用 -> '(' が消費され parens が呼ばれる。
")" -> parens を適用 -> ')' とはマッチしないので return "OK" が実行される。
")" -> char ')' を適用 -> ')' が消費され parens が呼ばれる。
"" -> parens を適用 -> '(' とはマッチしないので return "OK" が実行される。
すなわち、char '('; parens; char ')'; parense パターンが終了する。
"OK" が表示される。

ややこしいが、ひとつずつステップを追っていくとパターンマッチが機械的に行われているのが分かる。

次のプログラムは、四則演算の文法チェックをするだけのプログラムだが、expr パーサが再帰的に定義されている。

Prelude> :l expr.hs
[1 of 1] Compiling Expr ( expr.hs, interpreted )
Ok, modules loaded: Expr.
*Expr> parseTest expr "(1+2)*(3+4)"
"OK"

ファイル名: expr.hs

module Expr where

import Text.Parsec

expr :: Parsec String () String
expr = do {term; many (do {char '+'; term}); return "OK"}

term :: Parsec String () ()
term = do {factor; many (do {char '*'; factor}); return ()}

factor :: Parsec String () ()
factor = do {char '('; expr; char ')'; return ()} <|> do {many1 digit;
 return ()}

Parsec ではこのようなパーサの再帰的定義ができるため、数式の演算のような複雑な式をパースすることができる。