モナディックなパーザーコンビネータ作ってみた
タイトル通りで作ってみたました. もともと研究で違うことやってたはずなのに目的を見失ってなんか面白そうだしこれならゼミで話しても怒られなさそうという考えからこの頃ずっと勉強してた.
OCamlで実装しようかHaskellで実装しようか迷っててどっちでも良かったんだけど最終的にはHaskellで書いた. 最初はOCamlの勉強も少ししてて、とにかく本を買いたくなかったので以下のページを読んでた.
けど素直にHaskellでやったほうが楽そうという気持ちになり途中からHaskellに切り替えた. Haskellの文法は雰囲気がわかる程度だったのでなんとかなるだろうと思い特に何もしなかった. モナドは「モナドは単なる自己関手の圏におけるモノイド対象だよ。何か問題でも?」という感じだったので以下のページを読んでだ.
パーザーコンビネータはググるといろんな人が実装しててるのでそれを参考にするといいかもしれない. こんなふうにParserの型が決まった時点で考えることはあんまりなくて型すごいって思いながら実装しいくとできたし型すごい.
type Result = Either String type Parser v = StateT String Result v
PEGパーザにした気でいるんですがもしかしたらこれではいけないかもしれないので間違っていたらスマンという感じです.
import Control.Monad.State import GHC.Base((<|>)) import Data.Char type Result = Either String type Parser v = StateT String Result v runParser = runStateT look :: Parser Char look = do x:_ <- get return x item :: Parser Char item = do x:xs <- get put xs return x satisfy :: (Char -> Bool) -> Parser Char satisfy f = do a <- item if f a then return a else mzero unsatisfy :: (Char -> Bool) -> Parser Char unsatisfy f = satisfy (not . f) cjoin :: Parser a -> Parser a -> Parser [a] cjoin p1 p2 = do a <- p1 b <- p2 return [a, b] select :: Parser a -> Parser a -> Parser a select = (<|>) many :: Parser a -> Parser [a] many f = many1 f <|> return [] many1 :: Parser a -> Parser [a] many1 f = do a <- f b <- many f return $ a:b
例えばExpr <- Number + Number
を受理するためのは以下のように書くとちゃんと計算結果が返ってくる.
number :: Parser Integer number = do n <- many1 digit return $ read n where digit = satisfy isDigit expr :: Parser Integer expr = do a <- number op <- token (=='+') >> return (+) b <- number return $ op a b main :: IO () main = print $ runStateT expr2 "1+2;" -- => Right (3,";")
4則演算バージョンがあるのでぜひ
参考
- http://d.hatena.ne.jp/kazu-yamamoto/20080920/1221881130
- http://www.geocities.jp/m_hiroi/func/haskell32.html