パーサーコンビネータの実装 パート2
シリーズのパート2へようこそ。ここではHaskellを使ってシンプルなパーサーコンビネータライブラリを一から実装します。第一回目では、Parser 型を定義し、それに必要な全ての型クラスを実装しました。ソースはこちらで確認できます。それに加えて、いくつかのコンビネータを定義し、次のようなパーサーを定義しました。
pKv :: Parser KV
pKv = KV <$> parseKv
where
parseKv = (,) <$> many alpha <* char ':' <* spaces <*> many alpha
このシンプルなパーサーは、キーと値のペアをHaskellのデータ型に変換します。また、パーサーを_run_することもできます。
runParser pKv "key: value" -- Right (KV ("key","value"))
これはすでにかなり便利ですが、もっとリッチな感じにするために、さらにコンビネータを実装しましょう。前に定義した_pKv_ パーサーを拡張して、キーと値のペアのリストを簡単に解析できるようになるといいですね。_sepBy_というコンビネータを定義すれば、これは簡単です。
sepBy1 :: Parser a -> Parser b -> Parser [a]
sepBy1 p sep = (:) <$> p <*> many (sep *> p)
sepBy :: Parser a -> Parser b -> Parser [a]
sepBy parser separator = sepBy1 parser separator <|> pure []
_strict_バージョンを使用して_sepBy_を定義したことに注意してください。もし解析する_kv_が1つだけの場合、_sepBy1_は失敗しますが、_sepBy_は喜んで解析します。
ここで、_kv_のリストを解析するパーサーを定義するのは簡単です。
pKvs :: Parser [KV]
pKvs = pKv `sepBy` char ','
runParser pKvs "key: value,foo: bar" -- Right [KV ("key","value"),KV ("foo","bar")]
素晴らしいですね。そういえば、数値も解析できるようになるといいですね。そう思います！
import Data.Maybe (fromMaybe)
import Data.Applicative (Alternative(..), optional)
import Data.Functor (($>))
digit :: Parser Char
digit = satisfy "digit" Char.isDigit
decimal :: (Integral a, Read a) => Parser a
decimal = read <$> many1 digit
signedDecimal :: Parser Int
signedDecimal = fromMaybe id <$> optional (char '-' $> negate) <*> decimal
これで数字を解析できるようになりました、万歳！こちらがいくつかの例です。
runParser (decimal @Int) "123" -- Right (123)
runParser (decimal @Int) "-123" -- Left "Expecting digit at position 0"
runParser signedDecimal "-123" -- Right (-123)
特に_レキサー_を書くときに、空白文字を解析するのは一般的なタスクです。_レキシング_をもっと便利にするためにいくつかの便利なコンビネータを定義しましょう。
spaces :: Parser ()
spaces = void $ many (satisfy "whitespace" Char.isSpace)
newline :: Parser ()
newline = char '\n' <|> (char '\r' *> char '\n')
horizontalSpaces :: Parser ()
horizontalSpaces = void . many $
satisfy "horizontal whitespace" $ \c ->
Char.isSpace c && c /= '\n' && c /= '\r'
先程解析したキーと値のペアはコンマで区切られていましたが、改行で区切られたキーと値のペアを解析したくなるかもしれません。
key: value
foo: bar
これに対するパーサーを書きます。
pKvsNewLine :: Parser [KV]
pKvsNewLine = pKv `sepBy` newline
runParser pKvsNewLine "key: value\nfoo: bar" -- Right [KV ("key","value"),KV ("foo","bar")]
あるいは、コンマで区切られたが間にランダムなスペースがある_kv_を解析したいかもしれません。例えば "key: value , foo: bar" のような。_horizontalSpaces_を使えばできます！
pKvsHorizontal :: Parser [KV]
pKvsHorizontal = pKv `sepBy` s
where s = horizontalSpaces *> char ',' <* horizontalSpaces
runParser pKvsHorizontal "key: value , foo: bar" -- Right [KV ("key","value"),KV ("foo","bar")]
この時点で、かなりパワフルなツールを手に入れました。まだ、この機械で面白いユースケースを見ていませんが、次回はシンプルなプログラミング言語のためのパーサーを定義します。
読んでいただき、ありがとうございました。楽しんでいただけたら幸いです。良い一日を！
- Joona
パート1
私の他のブログ投稿
こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。
https://dev.to/japiirainen/implementing-parser-combinators-pt-2-3bae
