細・Haskellを使ってmarkdownをパースして... [Parsecライブラリの使い方]

今回書いてみたmarkdownパーサの中身を使って、私が学んだParsecの使い方について書いてみる。
GitHub - joker1007/markdown2hatena: markdown記法をはてな記法に変換する

文字のストリームをパースする

markParser :: Parser Bool
markParser = do isMark
                return False
             <|> do digit
                    satisfy (== '.')
                    return False
             where
               isMark = satisfy (`elem` "#*+->")

このコードは、その文字列がMarkdown記法で意味を持った記号で始まっていない
通常の行を示す文字列であることを確かめるためのパーサを記述している。


文字、つまりChar型のストリームをパースするには、
Parser a型を使う。
これは正確には、GenParser Char () aという型の別名で、Parsecで最初から定義されている。
aは、パースした結果として返したいデータ型が入る。


パースのルールを記述するには、do記法を使う。
markParserの定義を上から見ていくと、
まずisMark関数で、最初の文字が"#*+->"のどれかに含まれればパースに成功するパーサを返し、
それが成功したら、Falseをパース後の戻り値として返却するブロックを定義している。
続いて、<|>で連結された後ろにもう一つdoブロックがある。
こちらでは、digit関数で入力文字が数字であればパースに成功するパーサを返し、
次の文字が、「.」であればパースに成功するパーサを返し、
その二つが成功したら、Falseをパース後の戻り値として返却するブロックを定義している。
そして、<|>を使って結合することで二つのパーサのどちらかが成功すれば、そのパーサの戻り値を返すという、
選択的パーサを構築している。


実際にパースを行うのは以下のコードになる。

isNotMarkLine :: String -> Bool
isNotMarkLine cs = case parse markParser "" cs of
                      Right _ -> False
                      Left _ -> True

parse関数の型は以下の通り。

parse :: Parser a -> FilePath -> String -> Either ParseError a

parse関数はパーサと文字列を渡すことで、文字列入力を一文字ずつパーサに入力し、結果をEither ParserError a型で返す関数。
パースに成功していれば、Right a、失敗していればLeft ParserErrorが戻るため、パターンマッチを利用して場合分けを行う。
ちなみに、FilePathはエラーメッセージ表示用に使われる値であるため、不要であれば空文字列で構わない。


isNotMarkLine関数では、パースに成功すれば戻り値に関わらずFalseを返し、失敗すればTrueを返すことで、
意味を持った記号の行ではないことを判別する関数を定義している。



文字列のストリーム(行)をパースする

ライブラリで定義されているParser a型は、文字単位でのパースを行う型なので、
行単位でパースしたい場合は、別途自分でパーサの型を定義する必要がある。


以下のコードで行単位のパーサ型を定義している。
(以下のコードは、「ふつうのHaskellプログラミング」で紹介されていた
LazyLinesのコードを利用している。ライセンスはLGPL)

type LineParser a = GenParser String () a

lineSatisfy :: (String -> Bool) -> LineParser String
lineSatisfy f = tokenPrim showLine nextPos testLine
  where
    showLine line = show line
    nextPos pos line s = incSourceLine pos 1
    testLine line = if f line then Just line else Nothing

indented :: LineParser String
indented = firstChar isSpace

blank :: LineParser String
blank = lineSatisfy (null . dropWhile isSpace)

notBlank :: LineParser String
notBlank = lineSatisfy ((0 < ) . length . trim)

firstChar :: (Char -> Bool) -> LineParser String
firstChar f = lineSatisfy (test f)
  where
    test _ "" = False
    test f (c:_) = f c

{- from http://i.loveruby.net/ja/stdhaskell/lazylines.html -}


ここではGenParser String () aという型がポイントになる
この型を型変数で表わすと、GenParser tok st aとなる。
tokは、入力を何の型を単位とするトークンの集合として受け取るかを意味する。
stは、パースによって更新されるステータス値としてどの型を使うかを意味する。
aは、パースが成功した時に返す値の型を意味する。
つまり、LineParser a型は、文字列を単位として受け取り、ステータス値は利用せず、aという好きな型を返却するパーサの型を示している。


実際にパーサとしての基本動作を定義しているのは、lineSatisfy関数になる。
lineSatisfy関数は引数fで受けとった関数がTrueを返す時パースに成功し、その行全体を戻り値とするLineParser String型のパーサを返す関数を定義している。
内部で利用されているtokenPrimは、Parsecライブラリで定義されている関数で、
トークンを確認する時の文字列出力の関数、トークンの位置を更新する関数、
そのトークンがパースに成功するか確認し、結果をMaybeモナドに包んで返す関数、
この3つを引数に取る。
このコードでは、fという関数にlineを渡して結果がTrueであれば、Just lineで行全体を返し、FalseであればNothingを返すという定義になっている。
Just lineで行の文字列を返しているので、lineSatisfy関数は、LineParser String型を返す関数ということになる。



行パーサの利用

以下のコードで行単位のパーサを利用している

headline :: LineParser [Node]
headline = do line <- firstChar (== '#')
              let (mark, str) = span (== '#') line
              return $ [HeadLine (length mark) (trim str)]

firstCharは、入力された文字列の最初の文字が「#」だったら、パースに成功し、
その行全体を戻り値として返すパーサ。
そして、受けとった文字列を「#」の連続とそれ以外に分け、
「#」の数を数えて見出しレベルに、
残りの文字列から頭と末尾のスペースを取り除いたものを見出し文として
Node型を構築し、それをリストに包んで返している。
(Node型は、自分で定義した代数型)



行パーサと文字パーサの組み合わせ

リスト記法をパースするコードで、行パーサと文字パーサを組み合わせて利用している。

listblock :: LineParser [Node]
listblock = do manyLines <- many1 (lineSatisfy isListLine)
               return $ map listParse manyLines
            where
              listParse :: String -> Node
              listParse cs = case runParser levelParser 1 "" cs of
                                  Right node -> node
                                  Left err -> Paragraph $ show err
              levelParser :: GenParser Char Int Node
              levelParser = do try (count 4 space)
                               updateState (+1)
                               levelParser
                            <|> do tab
                                   updateState (+1)
                                   levelParser
                            <|> do listmark
                                   cs'' <- many anyChar
                                   level' <- getState
                                   return $ ListLine level' (trim cs'')
                            <|> do numberedlistmark
                                   cs'' <- many anyChar
                                   level' <- getState
                                   return $ NumberedList level' (trim cs'')
              isListLine :: String -> Bool
              isListLine cs = case parse p "" cs of
                                    Right _ -> True
                                    Left _ -> False
                                  where
                                    p :: Parser Bool
                                    p = do skipMany (space <|> tab)
                                           listmark <|> numberedlistmark
                                           return True
              listmark = satisfy (`elem` "*+-")
              numberedlistmark = digit >> (char '.')

listblockは、Node型のリストを返す行単位のパーサを表している。
まず、その行がリスト記法を表す行かをBool型で返すisListLineという関数を使って、
行全体をパースしている。


isListLine関数は、内部で文字パーサを使っており、
最初がスペースかタブの連続で、続けてリスト記法のマーク、もしくは数字付きリスト記法になっているかを
パースして成功すればTrue、失敗すればFalseを返す関数だ。


そして、many1関数でisListLineが1つ以上連続する行をパースし、
行のリストを返している。


次に、行のリストそれぞれに対して、
インデントの行数を数えてリストのインデントレベルを算出し、
記号を除いた文本体を取り出す必要がある。


そのため、取り出した行を再び文字単位のパーサにかけ、
インデントと、文本体をパースしている。
これを実現するパーサがlevelParser関数だ。


levelParserは、GenParser Char Int Node型を返す関数だ。
GenParserの二つ目の型引数にIntが入っている。
これは、ステータス更新を利用してインデントレベルを算出するためだ。

levelParser = do try (count 4 space)
                 updateState (+1)
                 levelParser
              <|> do tab
                     updateState (+1)
                     levelParser
              <|> do listmark
                     cs'' <- many anyChar
                     level' <- getState
                     return $ ListLine level' (trim cs'')
              <|> do numberedlistmark
                     cs'' <- many anyChar
                     level' <- getState
                     return $ NumberedList level' (trim cs'')


パーサが入力に対してスペース4つ、もしくはタブ一つを検出する度に、
ステータス値を1プラスして、再起的にパーサを呼び出して続きの文字をパースしていく。
リスト記法構文を検出したら、その後に続く文字列を文本体として取得し、
更新していたステータス値をgetState関数で引っ張ってきてインデントレベルとして利用する。


ステータスを利用するパーサを実行するには、parse関数ではなくrunParser関数を使う。
runParser levelParser 1 "" cs
この関数呼出で、levelParserを使って、ステータス初期値を1とし、csをパースしている。

パーサを組み合わせて大きなパーサを作る

document :: LineParser String
document = do nodes <- many1 block
              eof
              return $ join $ intersperse "\n" $ map compile (concat nodes)

block :: LineParser [Node]
block = do blank
           return $ [Paragraph ""]
        <|> headline
        <|> listblock
        <|> paragraph

これまでのパーサを組み合わせて、文書全体をパースするパーサを構築する。
do記法を使って、定義したパーサをどの順番で、どの場合分けでパースするかを順番に書いていくだけで実現できる。


最終的には、空行か、見出し行か、リストブロックか、段落を示すblockが一つ以上連続して、
入力末尾まで続いている文書をパースする関数を構築している。


後は、このパーサにMarkdown文書を入力すれば、パース結果を得ることが出来る。


以上がParsecを利用したパーサの一連の流れになる。

書いてみて

実際、listblockあたりは何か冗長に書いているような気がしているし、
全体的に、Haskellのコードとして、もっと書き方あるんじゃないかと思っている。
Parsecについても、裏ではもっと色々やってるみたいなんだけど、
そんなモナドの奥深くまで降りていける程Haskell脳が発達していないので、
私が理解した中では、このあたりが限界。


それにしても、Haskellのコードを説明するのは非常に辛い。
自分自身が良く分かってないこともあるけど、抽象的過ぎて何て言ったらいいのか分からん。