第8章 関数型パーサー #3

間を空けると感覚が鈍ってだめだなあ。

パーサーの部品

ひたすら写経。

import Data.Char

sat :: (Char -> Bool) -> Parser Char
sat p = item >>- \x ->
        if p x then return' x else failure

digit   :: Parser Char
digit    = sat isDigit

lower   :: Parser Char
lower    = sat isLower

upper   :: Parser Char
upper    = sat isUpper

letter   :: Parser Char
letter    = sat isAlpha

alphanum :: Parser Char
alphanum  = sat isAlphaNum

char     :: Char -> Parser Char
char x    = sat (== x)

string :: String -> Parser String
string []     = return' []
string (x:xs) = char x >>- \d1 ->
                string xs >>- \d2 ->
                return' (x:xs)

many  :: Parser a -> Parser [a]
many p = many1 p +++ return' []

many1  :: Parser a -> Parser [a]
many1 p = p >>- \v ->
          many p >>- \vs ->
          return' (v:vs)

ident :: Parser String
ident  = lower >>- \x ->
         many alphanum >>- \xs ->
         return' (x:xs)

nat :: Parser Int
nat  = many1 digit >>- \xs ->
       return' (read xs)

space :: Parser ()
space  = many (sat isSpace) >>- \d ->
         return' ()

パーサーはモナド（もどき）なのでbind（もどき）ができて、合成もできる。最後の3つ（識別子パーサー、自然数パーサー、空白パーサー）まで積み上がっていくのはなかなか凄いねえ。

空白の扱い

さっきの部品を使って、前後の空白を無視する(単に消費する)パーサーを組み上げる。

token  :: Parser a -> Parser a
token p = space >>- \d1 ->
          p >>- \v ->
          space >>- \d2 ->
          return' v

identifier :: Parser String
identifier  = token ident

natural :: Parser Int
natural  = token nat

symbol   :: String -> Parser String
symbol xs = token (string xs)

ここまでできると、応用として空白を無視する整数リストのパーサーができる。

p :: Parser [Int]
p = symbol "[" >>- \d1 ->
    natural >>- \n ->
    many (symbol "," >>- \d2 -> natural) >>- \ns ->
    symbol "]" >>- \d3 ->
    return' (n:ns)

Hugsでの実行サンプルはこちら。

Main> parse p " [ 1 , 2 , 3   ] "
[([1,2,3],"")]
Main> parse p " [ 1 , a , 3   ] "
[]

慣れてくるとパーサー定義が「読める」ようになってくる。ある種のDSL。関数型言語ならではなのか、Haskellならではなのか。