最強のパーザー、Parser Combinator

実は昨日の話題はこれから書こうとする話とつながりがあるのだ。
(直接的には無いけど)

Yaccと正規表現とParser Combinatorと

(序)

突然であるが、Haskellは文字列処理が強力だと思う。
それも最強レベルに。
他のいわゆる文字列処理が得意であるとされる言語のように
正規表現による置換が可能であるとか、文字列がオブジェクトで
有用なメソッドがたくさん使えるとかそういった
小手先のものではなくてもっと根本的なレベルで強力なのである。

それはHaskellに於いて文字列が文字のリストであらわされていることに
起因する。わからない人から見ると文字列がリストであるということは
Cにおいて文字列が配列で表されているのとかぶるかもしれない。
Haskellが文字列をリストとして持っていてうれしいというのは
Haskellが全言語中でもほとんど最強のリスト操作能力を持っているからである。
Cで文字列が配列になっていても何もうれしくないのは、
Cが配列操作が大して得意ではないためである。

たとえば、単純置換なら (文字xを文字列yに置換)

str >>= (\c -> if c == x then y else [c])

置換対象が文字列→文字列も

replace x y str = inner str where
  inner  = 
  inner str@(s:ss)
    | isPrefixOf x s = y:inner (drop lx)
    | otherwise = s:inner ss
  lx = length x

このように定義すれば行える。(定義しなければならんのだけど)
定義さえすれば複数の置換を一度に行うのもなんのそのである。

replaceMultiple = foldl (\f (x,y) -> f . replace x y) id
...
replaceMultiple [("foo","bar"),("hello","world")] str

もちろんこのようなケースは非常に単純で、
現実にはもう少し複雑なマッチングが必要になることが多いだろう。
単純比較では無理だけど、CFG*1を持ち出すほどでも…
といった場合、多くの言語では正規表現の力を借りる。
正規表現は確かに便利である。
便利なのだが、正規表現は大体の場合において全く言語とは独立である。
プログラマは"特定の正規表現の文法"に従って"文字列"でそれを
指定することになる。
これは言語とは別に正規表現の文法を覚える必要があることを意味し、
さらに言語処理系と独立なので実行時まで正規表現が正しいかどうかを
確かめられない。

Haskellだとこういった場合、Parser combinatorを使う。
Parser combinatorはHaskellにとっては普通の関数であり、
別段特殊なものではないことを一応断っておく。
普通のプログラムなので、正規表現の言語クラスにとらわれることなく
BNFで表現できる文法もパーズできる。
(BNFで表現できないクラスの文法(0型言語、チューリングマシンと等価)
も解析できるけど…)

とりあえず一例を書いてみる。
与えられた文字列からY/M/Dの形で与えられた文字列を
M.D,Yに置換するようなプログラムである。
なお、以下のプログラムではパーザコンビネータの"実装の一例"である
Text.ParserCombinators.Parsecを使っている。

main = putStrLn $ repl "today is 2004/07/30 desu."

repl str =
  case parse p "" str of
    Left err -> error "え〜っ?!エラー?ありえなぁ〜い!!"
    Right ls -> ls
  where
    p = do
      ls <- many $ (try date) <|> (anyChar >>= \c -> return [c])
      return $ concat ls

    date = do
      y <- many1 digit
      char '/'
      m <- many1 digit
      char '/'
      d <- many1 digit
      return $ m ++ "." ++ d ++ "," ++ y

$ ./a.out
today is 07.30,2004 desu.

正規表現を使う場合に比べてコードは長くなっていると思われるが、
エラーはコンパイル時にチェックできるし、
何よりパーザーがオブジェクトとして存在しているのである。
上記ソースだと"date"がY/M/Dを認識しM,D.Yを返すパーザーである。

このことはパーザーに関する演算を定義できることを意味する。
先のソース中でパーザーは、pとdateである。
dateはまさにこの問題のために作成したものであるが、
pが行っているのはdateで解析できるかどうかをチェックし続けているだけで、
これはこの問題固有の処理ではない。
dateを抽象化し、もっと一般的に使用できるのである。

main = putStrLn $ replaceBy date "today is 2004/07/30 desu."
  where
    date = do
      y <- many1 digit
      char '/'
      m <- many1 digit
      char '/'
      d <- many1 digit
      return $ m ++ "." ++ d ++ "," ++ y

replaceBy :: Parser String -> String -> String
replaceBy p str = 
  case parse (repAll p) "" str of
    Left err -> error "え〜っ?!(略"
    Right ls -> ls

repAll :: Parser String -> Parser String
repAll p = do
  ls <- many $ (try p) <|> (anyChar >>= \c -> return [c])
  return $ concat ls

replaceByはパーザーを引数にとり、変換関数を返す関数となる。
ここで、"today"という文字列を"yesterday"にも変える、
と動作を変更したい場合、

main = putStrLn $ replaceBy (date <|> today) "today is 2004/07/30 desu."
  where
    date  = ...
    today = string "today" >> return "yesterday"

と変更すればよい。
最初に書いたreplaceもreplaceByを用いて

replace x y = replaceBy (string x >> return y)

と書きなおすことが出来る。

string x >> return y という部分も複数回出てきたので、

replaceParser :: String -> String -> Parser String
replaceParser x y = string x >> return y

これもこのように抽象化するのがよいかも知れない。

とまぁ、なんかいろいろ出来るという話で今回はまだ
具体的なところまで突っ込むつもりは無かったのだが…
取り留めのない話になってきたので、今回はこの辺で。
次あたりにParser Combinatorというものについてを
書こうと思う。(私が書く必要も無いような気もするけど)
実践的プログラムはさらにその先にでも。

*1:文脈自由文法