Parsecをモナド変換子で模倣

Haskellの実験メモです。

Parsecは挙動から動作原理が見えにくいと感じて敬遠していましたが、どうにか折り合いが付けられないかを試みました。

モナド変換子の知識を前提としています。

• Haskell モナド変換子 超入門 2015.1.4

この記事は次の続編のようなものです。

• MaybeとStateを合成 2015.4.24

この記事をベースに、学習用にまとめた記事があります。

• Haskell 構文解析 超入門 2015.7.31

Parsecの初歩

最初の1文字が指定した文字種ならそれを表示して、そうでないならエラーになる例です。

import Text.Parsec

main = do
    print $ runParser anyChar () "test1" "abc"
    print $ runParser letter  () "test2" "abc"
    print $ runParser digit   () "test3" "abc"
    print $ runParser digit   () "test4" ""

実行結果

Right 'a'
Right 'a'
Left "test3" (line 1, column 1):
unexpected "a"
expecting digit
Left "test4" (line 1, column 1):
unexpected end of input
expecting digit

runParserはParsecのアクションを実行する関数です。StateモナドでのrunStateに相当します。

• 引数: アクション ユーザー状態 ソース名 ソース
  • 第2引数（ユーザー状態）は使わないため()
  • 第3引数（ソース名）はデバッグ用のタグとして使用
• 戻り値（Eitherモナド）
  • Right: 正常終了
  • Left: エラー（文字が指定と異なる）

parse

ユーザー状態が省略できる関数です。取っ掛かりとしてはrunParserよりもparseが紹介されることが多いようです。

import Text.Parsec

main = do
    print $ parse anyChar "test1" "abc"
    print $ parse letter  "test2" "abc"
    print $ parse digit   "test3" "abc"
    print $ parse digit   "test4" ""

実行結果

Right 'a'
Right 'a'
Left "test3" (line 1, column 1):
unexpected "a"
expecting digit
Left "test4" (line 1, column 1):
unexpected end of input
expecting digit

parseTest

printやソース名を省略できる関数です。

import Text.Parsec

main = do
    parseTest anyChar "abc"
    parseTest letter  "abc"
    parseTest digit   "abc"
    parseTest digit   ""

実行結果

'a'
'a'
parse error at (line 1, column 1):
unexpected "a"
expecting digit
parse error at (line 1, column 1):
unexpected end of input
expecting digit

以後、主にparseTestを使用します。

アクションの合成

IOアクションなどと同様に>>で合成できます。

import Text.Parsec

main = do
    parseTest (letter >> digit) "abc"
    parseTest (letter >> digit) "a12"

実行結果

parse error at (line 1, column 2):
unexpected "b"
expecting digit
'1'

後のdigitで指定した文字しか取得できていません。

文字を拾う

前の文字も取得するには結果を束縛してreturnで返します。

import Text.Parsec

letterDigit = do
    a <- letter
    b <- digit
    return [a, b]

main = do
    parseTest letterDigit "abc"
    parseTest letterDigit "a12"

実行結果

parse error at (line 1, column 2):
unexpected "b"
expecting digit
"a1"

今回はParsec入門が目的ではないため、使用方法の確認はこの辺で止めます。

再実装

Parsecは中の動きが想像しにくいと感じて敬遠していましたが、いつまでも避けては通れません。しかしソースを軽く眺めても複雑で、先に原理を理解しないと読み解くのは困難だと感じました。

そこで同じような原理で動く簡略化したパーサーを再実装して、まずは動きが推測できることを目指します。

動作原理については『プログラミングHaskell』の『第8章 関数型パーサー』を参考にしました。今回はモナドやbindの実装を避けるため同書には準拠せず、モナド変換子を使ってParsecと同じ名前の関数を実装します。

取っ掛かり

最初の1文字だけを確認します。簡単のためエラーの詳細は省略します。

import Control.Monad
import Data.Char

evalParse f (c:_) = f c
evalParse _ _     = Nothing

parseTest f s = case evalParse f s of
    Just c  -> print c
    Nothing -> putStrLn "ERROR"

anyChar c = Just c
letter  c = guard (isLetter c) >> Just c
digit   c = guard (isDigit  c) >> Just c

main = do
    parseTest anyChar "abc"
    parseTest letter  "abc"
    parseTest digit   "abc"
    parseTest digit   ""

実行結果

'a'
'a'
ERROR
ERROR

合成

>>でアクションを合成すると、2文字目を取得する仕組みがないため誤動作します。

import Control.Monad
import Data.Char

evalParse f (c:_) = f c
evalParse _ _     = Nothing

parseTest f s = case evalParse f s of
    Just c  -> print c
    Nothing -> putStrLn "ERROR"

anyChar c = Just c
letter  c = guard (isLetter c) >> Just c
digit   c = guard (isDigit  c) >> Just c

main = do
    parseTest (letter >> digit) "abc"
    parseTest (letter >> digit) "a12"

実行結果

ERROR
ERROR

StateT

合成したアクション間では「何文字目を見ているか」という状態が受け渡されます。状態をStateモナドで表現するため、既に使っているMaybeモナドをStateTモナド変換子で包みます。

import Control.Monad
import Control.Monad.State
import Data.Char

parseTest f s = case evalStateT f s of
    Just c  -> print c
    Nothing -> putStrLn "ERROR"

anyChar :: StateT String Maybe Char
anyChar = do
    (x:xs) <- get
    put xs
    return x

letter = do
    c <- anyChar
    guard $ isLetter c
    return c

digit = do
    c <- anyChar
    guard $ isDigit c
    return c

main = do
    parseTest (letter >> digit) "abc"
    parseTest (letter >> digit) "a12"

実行結果

ERROR
'1'

うまく動いています。型注釈はややこしいですが、コードはシンプルです。

文字を拾う

前の文字が取得できるか確認します。

import Control.Monad
import Control.Monad.State
import Data.Char

parseTest f s = case evalStateT f s of
    Just c  -> print c
    Nothing -> putStrLn "ERROR"

anyChar :: StateT String Maybe Char
anyChar = do
    (x:xs) <- get
    put xs
    return x

letter = do
    c <- anyChar
    guard $ isLetter c
    return c

digit = do
    c <- anyChar
    guard $ isDigit c
    return c

letterDigit = do
    a <- letter
    b <- digit
    return [a, b]

main = do
    parseTest letterDigit "abc"
    parseTest letterDigit "a12"

実行結果

ERROR
"a1"

成功しています。

まとめ

再実装を通して、Parsecの内部はStateモナドとMaybeモナドの両方の性質を併せ持っていることが見えて来ました。

参考

Parsecの初歩について参考にした記事です。

• @utotch: Utotch Blog: Haskell で parser を書くには (初心者編) 2011.12.18
• Parsec 再入門 Parser と ParserCombinator : tnomuraのブログ 2013.1.3
• @sirocco_jp: Parsecにちょっと触ってみる。 - sirocco の書いてもすぐに忘れるメモ 2010.10.24
• @esehara: Parsecというパーサーライブラリで電卓を作る簡単な方法 - 蟲！虫！蟲！ - #!/usr/bin/bugrammer 2011.11.17

再実装について参考にした記事です。

• @nnabeyang: 『プログラミングHaskell』の関数型パーサーをStateTを使って書き直す - Qiita 2014.1.10