言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella
トップ > parsec

parsec

最近 Haskell に触ってなくて寂しいなあと思い、パーサーコンビネータと言うのを試してみました。まず import はこのようにします。

import Text.ParserCombinators.Parsec

Parsec には便利なパーサの部品が沢山ありますが、勉強のためあえて自作します。まずある文字列の先頭が a の時だけマッチするやつを作ります。特定の文字にマッチするには char 関数を使います。char 関数以外は、パーサを駆動するだけのための部品です。

aParser :: String -> IO()
aParser input = out (parse (char 'a') "error" input)
    where out (Right x) = print x
          out (Left err) = print err

-- Main> aParser "abc"
-- 'a'

-- Main> aParser "def"
-- "error" (line 1, column 1):
-- unexpected "d"
-- expecting "a"

以降、パーサ本体(p)とパーサを駆動する部品 (run) にわけます。

run :: Show a => Parser a -> String -> IO()
run p input = out (parse p "error" input)
    where out (Right x) = print x
          out (Left err) = print err

次に数字一文字にマッチするパーサを作ります。数字は 0 から 9 まで 10 文字ありますが、選択するには <|> を使います。このように、char を使ったパース結果は文字自身です。

num :: Parser Char
num = char '0' <|> char '1' <|> char '2' <|> char '3' <|> char '4' <|>
      char '5' <|> char '6' <|> char '7' <|> char '8' <|> char '9'

-- Main> run num "123"
-- '1'

-- Main> run num "abc"
-- "error" (line 1, column 1):
-- unexpected "a"
-- expecting "0", "1", "2", "3", "4", "5", "6", "7", "8" or "9"

次に数字二文字を連接した物にマッチさせます。連接にはモナド演算子を使います。

twoNums = num >> num

-- Main> run twoNums "123"
-- '2'

>> は前段の結果を捨てるモナド演算子なので、二文字あっても最後の文字しか反りません。二つとも文字を返すには >>= を使います。

twoNums' :: Parser String
twoNums' = num >>= \a -> num >>= \b -> return [a, b]

-- Main> run twoNums' "123"
-- "12"

>>= よりも do の好きな人はそちらも使えます。私は twoNums' ::= num:a num:b -> [a,b] のように読めるので >>= の方が好きです。

twoNums'' = do a <- num
               b <- num
               return [a, b]

-- Main> run twoNums'' "123"
-- "12"

連接 >>= と 選択 <|> そして再帰を使えば任意長の列をパース出来ます。

number = num >>= \d -> (number >>= \ds -> return (d:ds)) <|> return [d]

do も使えます。

number' = do d <- num
             ds <- number
             return (d:ds) <|> return [d]

文字列を読んでそのまま返すだけでは面白く無いので、読んだ文字列を加工します。ここでは単に文字列の "123" が来たら数字の 123 が来るようにします。read "123" :: Int としてしまえば一発で終了ですが、これも自分でわざわざ作ります。なぜかというと、数字は典型的な左再帰のデータ構造で面白いからです。左再帰というのは、123 = ((1) * 10 + 2) * 10 + 3 のように、左から読む事を言います。左再帰のデータ構造は媒介変数を使うのが定石なので

numValue :: Parser Int
numValue = numValue' 0

numValue' :: Int -> Parser Int
numValue' n = num >>= \d ->
                let ds = n * 10 + (fromEnum d - fromEnum '0')
                in numValue' ds <|> return ds

-- Main> run numValue "123abc"
-- 123

思ったよりきれいに書けなかった。。。一応書いておくと、組み込みの関数を使って書くとこんなに簡単。

numValue''' :: Parser Int                                 
numValue''' = many1 digit >>= return . read

参考