Hatena::ブログ(Diary)

あどけない話

2011-01-31

正規表現ちっくなパーサーコンビネーター

たとえば、論文を書いていて、図が本文からちゃんと参照されているかを調べたいとします。LaTeX で書いているなら、\ref{} と \label{} の中の文字列を突き合わす訳です。正規表現を使えば、テキスト全体からこれらの文字列を抽出するのは簡単です。でも、Haskell から正規表現を使うのは、かっこ悪いなぁという気がします。そこで、Parsec を使って、以下のようなパーサーを定義します。

label :: Parser String
label = string "\\label{" *> many1 (noneOf "}") <* char '}'

さて、このパーサーが受理する部分を全部返すというパーサーコンビネーターを書く訳ですが、これが意外と難しい。というか、パーサーのことを深く理解してないと書けない気がします。という訳で、こんなのを書いてみました。

appear :: Parser a -> Parser [a]
appear p = before pOrEof *> many (p <* before pOrEof) <* eof
  where
    pOrEof = (() <$ p) <|> eof

before :: Parser a -> Parser ()
before p = (() <$ try (lookAhead p)) <|> (anyChar >> before p)

appear label で parse すれば、\label{} の中の文字列を抽出しリストにして返してくれます。という訳で、質問なんですが appear はもっと簡単に実現できますか? あと、もっといい名前も募集したいです。

おまけ:\ref{}と\label{}を付き合わせるプログラム

module Main where

import Control.Applicative hiding ((<|>), many)
import Data.List
import Text.Parsec hiding (label)
import Text.Parsec.String

label :: Parser String
label = string "\\label{" *> many1 (noneOf "}") <* char '}'

ref :: Parser String
ref = string "\\ref{" *> many1 (noneOf "}") <* char '}'

appear :: Parser a -> Parser [a]
appear p = before pOrEof *> many (p <* before pOrEof) <* eof
  where
    pOrEof = (() <$ p) <|> eof

before :: Parser a -> Parser ()
before p = (() <$ try (lookAhead p)) <|> (anyChar >> before p)

parseIt :: Parser a -> String -> a
parseIt p cs = case parse p "dummy" cs of
    Left  e -> error . show $ e
    Right r -> r
        
main :: IO ()
main = do
    cs <- getContents
    let ls = parseIt (appear label) cs
        rs = parseIt (appear ref) cs
        ls' = nub . sort $ ls
        rs' = nub . sort $ rs
    putStrLn $ "labels - refs: " ++ show (ls' \\ rs')
    putStrLn $ "refs - labels: " ++ show (rs' \\ ls')

追加

Maybe を使って非効率にやるなら、こうかな。

appear :: Parser a -> Parser [a]
appear p = catMaybes <$> many p'
  where
    p' = try (Just <$> p) <|> (anyChar >> return Nothing)

これが一番奇麗かも。

appear :: Parser a -> Parser [a]
appear p = before p *> many (p <* before p)

before :: Parser a -> Parser ()
before p = (() <$ try (lookAhead p)) <|> (anyChar >> before p) <|> eof

t さんから教えてもらったコードをちょっと変更:

appear :: Parser a -> Parser [a]
appear p = (:) <$> try p <*> appear p
       <|> anyChar *> appear p
       <|> [] <$ eof

Otter_OOtter_O 2011/02/01 16:51 Text.ParserCombinators.Parsec.Combinator.ManiTill :: Parser a -> Parser b -> Paser [a]
というのを使ったことがあります。
ここでは
manyTill p eof
がappear見たいな感じになるんでしょうか…
実際試したわけではないので、うまくいかなかったらごめんなさい。

kazu-yamamotokazu-yamamoto 2011/02/01 17:02 manyTill だと、ゴミ(切り出したい部分以外のところ)の方を返しませんか?

Otter_OOtter_O 2011/02/01 17:14 それはpの定義次第なんではないかと思います。manyTillのドキュメンテーションによると、以下のコードで、コメントボディの抽出ができるようです。

simpleComment = do{ string "<!--"
; manyTill anyChar (try (string "-->"))
}

try... のところが、僕にはちょっとなぞなんですが…

kazu-yamamotokazu-yamamoto 2011/02/01 17:21 どう説明すればいいのかなぁ。うまくいかないんですよ、manyTill では。実際にやってみると分かると思います。

あと、try がないと、"-->" じゃなくて "->" という文字列が合った場合、"-" が消費された後に失敗しますよね。

Otter_OOtter_O 2011/02/01 18:05 なるほど、Try、わかりました。
僕がmanyTillを使ったのはXMLのパーサーだったんですけど、そのときは特に問題なく動きました。
違いは、Kazuさんのおっしゃるゴミの部分ですね。僕が書いたXMLパーサーは入力文字列にはゴミがないという仮定をしていたのですが、こちらはそうではないですね。
ちょっと苦しいですが、
Appear p = manyTil p' eof
Where p' = try p <|> (anyChar >> return "")
見たいな感じだととりあえずごみは出なくなるかもしれません…

kazu-yamamotokazu-yamamoto 2011/02/01 18:13 p と return "" の型が合わないので、ダメでしょうね。

Otter_OOtter_O 2011/02/01 18:17 いやーためしもしないで書くのはいけませんね。失礼しました。要はごみの時には何も返したくないので、
pがPasrer (Maybe a)になっていれば、Nothingとかを活用できる気もしますが…

kazu-yamamotokazu-yamamoto 2011/02/01 18:27 Maybe を使うなら、manyTill ではなく、many で十分ですね。記事の最後に追加しました。

tt 2011/02/03 17:26 appear p = ((:) <$> try p <|> flip const <$> anyChar) <*> appear p <|> [] <$ eof

じゃだめですか?

cabal info parsec では 3 が available で 2 が installed って出るのに、
なぜか cabal upgrade parsec で 3 を入れられないので試してないんですが。

kazu-yamamotokazu-yamamoto 2011/02/03 17:29 現在は、"parsec3" というパッケージを入れることになっています。上記のコードは、今から試してみます。

kazu-yamamotokazu-yamamoto 2011/02/03 17:41 動きました! ありがとうございます。さらに簡略化(?)してみました。
appear p = (:) <$> try p <*> appear p
<|> anyChar *> appear p
<|> [] <$ eof

tt 2011/02/03 18:03 parsec3 入りました! ありがとうございます。

再帰使うならそっちのほうが良いかもですね。
最初の書き方なら many 使うほうがいいのかも。

appear p = foldr ($) [] <$> many ((:) <$> try p <|> flip const <$> anyChar)

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/kazu-yamamoto/20110131/1296466529