Markdownパーサの作成

parsecというHaskellの構文解析用パッケージをしばらく触っていたので、その一つの成果として「md-parser」(Markdownパーサ)という車輪を生産しました。見事な車輪ですが、Markdownパーサのシンプルな、でも理解しやすいパーサを作りたかったというのも隠れた目的としてあります (これが達成できているかは怪しい)。

実装自体はgithubを見て頂ければいいとして、ここではもし自分を含め誰かが同じようにMarkdownパーサを書いてみようと思ったとき参考になればという情報をまとめています。

Markdownの文書構造
Markdown解析用型クラス、インスタンス宣言
Inlineのパース
Blockのパース
課題とか

1. Markdownの文書構造

まずはMarkdownの文書構造がどのようになっているかを確認しておきます。とはいえMarkdown自体はHTMLの別記法なだけなので実質HTMLの部分構造と同値です。

HTMLと同様ツリー構造を持つ。
Markdownのルートを文書(Document)とする。
Documentは1つ以上の複数のブロック要素(Block)から成る。例えば、HTMLでいう ‘p’, ‘div’ といった要素。
Blockは1つ以上のインライン要素(Inline)から成る。例えば、HTMLでいう ‘strong’, ‘a’ といった要素。
- 平文もHTMLのインライン要素に直接当てはまるものがあるわけではないが、Inlineの一種とみなす。

これを踏まえ、Markdownを表す内部的なデータ構造を以下のように表現しました。各値コンストラクタへの命名はMarkdown文法を参考にしています。

Document型は[Block]を値として持つ。 (値として持つ、という言い方が正確なのかは疑問)
Block型は各種HTMLのブロック要素にあたるものを値コンストラクタに持ち、それぞれは[Inline]を値として持つ。
Inline型は各種HTMLのインライン要素にあたるものを値コンストラクタに持つ。

なおDocument型にはMetaDataというデータ型も持たせていますが、この一番の理由は後述するreference linkへの対応のためです。

-- | Intermediate data structure between markdown and html
data Document = Document [Block] MetaData
  deriving (Show, Eq)

-- | Data representing html block elements
data Block = Header Int [Inline]
           | BlockHtml [Inline]
           | HorizontalRule
           | List ListItem
           | CodeBlock [Inline]
           | BlockQuote [Block]
           | Paragraph [Inline]
           | NullB
           deriving (Show, Eq)

-- | Data representing html inline elements
data Inline = LineBreak
            | SoftBreak
            | Space
            | Strong [Inline]
            | Emphasis [Inline]
            | InlineLink String String (Maybe String)
            | ReferenceLink String RefId
            | InlineCode [Inline]
            | InlineHtml [Inline]
            | Str String
            | NullL
            deriving (Show, Eq)

2. Markdown解析用型クラス、インスタンス宣言

今回は構文解析用のパッケージとしてparsecを使用しました。

Markdown解析用の型クラスとしてReadMarkDownというものを定義します。parser :: Parsec String ParseContext aはStringを読込元のデータ型、ParseContextを構文解析中に参照できる状態、aを解析結果として返す型に指定した解析用関数です。ParseContextは先述のMetaDataやその他解析中に必要な情報を管理する先としています。

-- | Can be read as markdown
class ReadMarkDown a where
  parser :: Parsec String ParseContext a

上記Markdown用のデータ型をそれぞれReadMarkDownクラスのインスタンスとします。

インスタンスの実装では、(おおよそ)各要素毎に定義された解析用の関数をP.choiceへ渡しています。P.choice関数は渡されたパーサのリストを順番に適用し、最初に成功したもののパース結果を返します。例えば、Inlineの解析でいうと、次の文字が*であればpEmphasis関数によりEmphasisが返され、[foo](http://foo.com)を見つければpInlineLink関数によりInlineLinkが返されるという感じで機能します。

-- parsec package is imported as 'P'

instance ReadMarkDown Document where
  parser = do blocks <- P.manyTill parser P.eof
              meta   <- metadata <$> P.getState
              return $ Document blocks meta

instance ReadMarkDown Block where
  parser = P.choice [ pHeader
                    , pHtmlBlock
                    , pHorizontalRule
                    , pListBlock
                    , pReference
                    , pCodeBlock
                    , pBlockQuote
                    , pParagraph
                    ]
          <?> "block"

instance ReadMarkDown Inline where
  parser = P.choice [ pLineBreak
                    , pSoftBreak
                    , pSpace
                    , pStrong
                    , pEmphasis
                    , pInlineLink
                    , pInlineCode
                    , pInlineHtml
                    , pReferenceLink
                    , pStr
                    , pHtmlEscape
                    , pMark
                    ]
          <?> "inline"

3. Inlineのパース

上で解析に必要なデータ型やクラスは定義したので、あとは各Markdown要素に応じたパース関数を定義すれば構文解析の実装完了となります。ただ実装する中で苦労する要素もあったので、いくつか記載しておこうと思います。

newlineへの対応

Markdown記法では以下のように改行が特別な意味を持っています。

各Block要素間の区切りをnewline2つ以上としている
Markdown内の文章中の改行は変換後のHTMLではspace(‘ ‘)として扱われる
ただし文末にspace2つ以上が挿入されている場合、 に変換される

なのでBlockの読み方と改行の扱い方に関しては以下のような方針になるかと思います。

該当Block解析開始
space2つ以上、改行の連続を発見した場合、LineBreakとする
改行を発見した場合SoftBreakとする
newline2つを発見した場合、該当Blockの解析を終了する

この方針に従った実装例が以下のようになります。

import           Text.Parsec                   (Parsec, ParsecT, Stream, (<?>),
                                                (<|>))
import qualified Text.Parsec                   as P
import qualified Text.ParserCombinators.Parsec as P hiding (runParser, try)

{-
> P.parseTest (P.many1 pBlock) "foo1\nfoo2\n\nbar1  \nbar2"
[[Sentence "foo1",SoftBreak,Sentence "foo2"],[Sentence "bar1",LineBreak,Sentence "bar2"]]
-}

data SimpleInline = Sentence String
                  | LineBreak
                  | SoftBreak
                  deriving (Show, Eq)

-- Parser for pseudo block elements
pBlock :: Parsec String () [SimpleInline]
pBlock = do inlines <- P.many1 (P.notFollowedBy pSepBlock *> pSimpleInline)
            pSepBlock
            return inlines

-- Parser for inlines
pSimpleInline = P.choice [ pLineBreak
                         , pSoftBreak
                         , pSentence
                         ]

-- Parser for the separator between blocks
pSepBlock =  moreThan 2 P.newline *> return ()
         <|> P.eof

pLineBreak = P.try (moreThan 2 (P.char ' ') *> P.newline *> P.notFollowedBy P.newline) *> return LineBreak
pSoftBreak = P.try (P.newline *> P.notFollowedBy P.newline) *> return SoftBreak
pSentence  = Sentence <$> P.many1 P.alphaNum

moreThan count p = do xs <- P.count count p
                      ys <- P.many p
                      return $ xs ++ ys

ただ実際の実装を見返すと4.を明確に意識できていない箇所があるので、うまくまとめればもっとすっきりするかなという気がします。

ReferenceLink

reference linkはMarkdownのInline要素の1つで以下のような記述をするリンクです。リンク先を別途参照しているのが通常のInlineLinkとは異なる点です。

[foo][1]

[1]: http://foo.com "this is foo"

リンク先([1])がドキュメント内どこで宣言してもよいことになっているので、解析中にこの対応を解決するのは難しいと思います。なので方針としては

[x]: yyy "zzz"のような形式をBlock要素の解析とみなし、MetaDataが持つ「’x’をキー、(‘yyy’,’zzz’)を値とするMap」に格納する (実装ではpReference関数により解析)
[foo][x]はInline要素のReferenceLinkとして解析
HTML書き出し時に、ReferenceLinkは’x’をもとに必要な情報をMapから取り出し、リンクタグを作成する

といった感じにしています。

4. Blockのパース

Inline要素のパースと同様、苦労したものに関して少し記述をば。

List

恐らくMarkdown記法の中でもよく使われるものの一つだと思います。私も頻繁に使用しますが、実際に文法を確認すると知らなかったルールや記法が結構ありました。

普段Listを書くときは

頭にマーク(‘-‘, ‘+’, ‘*’) をつける
スペース4つ(2つでも良い場合が多い) を空けてリストの入れ子を書ける

といったことしか意識していませんでしたが、他には

List項目が複数行にわたる場合、2行目以降は1行目にインデントを合わせてもよいし、合わせなくてもよい
各List項目間に空行を挟むと項目が段落になる

ということもできるようです。

つまり以下の2つのListは同じListを表し、

- one
oneone
- two
twotwo

- one
  oneone
- two
  twotwo

以下のListはHTMLに変換されると<ul><li>one</li><li>two</li></ul>のように各項目がで囲まれます。

- one

- two

この「各項目段落になる」というのが個人的には大変で、というのも項目自体も複数段落から構成され得るために、改行まわりの処理がどうしても複雑になってしまいました。また最終的にデータ構造としても妥協した形にしてしまったので、もう少しHaskel力がついたら書き直したいなと思っています。

BlockQuote

最後に実装した要素はBlockQuote(引用)だったのですが、一番悩ましい要素だったのもこれな気がします。

念のため確認しておくと、BlockQuoteの基本的な記法は以下のようになります。List同様2行目以降の’>’は省略可能で、両者はともに<blockquote>one two</blockquote>へと変換されます。

> one
> two

> one
two

まず悩んだのは「行頭の’>’を認識する」という処理でした。ここまで基本的にBlockと思われるものを読み始めるときには、先頭の何文字かでBlockの種類を決定し、あとはInlineのリストとして解析されるように実装してきていました。 BlockQuoteも同様にBlock先頭の’>’を認識して判断することはできるのですが、それ以降Block内部の解析時には行頭の’>’が存在すればそれを無視する必要があります。

ということで、単純に考えるとどうしてもBlockQuote中の解析か否かを判断するフラグが必要になり、それをParseContextに持たせるようにしました。前にpandocのソースを確認したときに「xxxの解析中」といったフラグが多くてうっと思ったのですが、他にいい手が思いつかないのでこのようにしています。

また「行頭」の判断は「newlineのあと」とみなせるので、改行処理時に余分な’>’はskipさせるというような実装としています。

次に手を焼いたのが「引用中でのMarkdown記法の有効化」でした。 BlockQuote中でもBlock及びInline要素に対するMarkdownが有効なため、

> one
>
> > two
>
> three

のtwoは二重の引用となり<blockquote>one<blockquote>two</blockquote>three</blockquote>に変換され、

> # title
>
> - one
> - two

は<blockquote><h1>title</h1><ul><li>one</li><li>two</li></ul></blockquote>に変換されます。

実装の方針としては、BlockQuote内でさらにBlockのパースを開始するだけと考えてよいと思うのですが、細かい改行やインデントへの対応が必要で思った程綺麗には実装できませんでした。何となく「改行と一緒に行頭の’>’を処理する」という方針が間違っているせいな気がするのですが、これもうまい手は思いつかないのでそのままで進みました。

5. 課題とか

全体的に構文解析の仕方が冗長 (tryをめっさ使っている)
- そもそもMarkdownの構文をBNFなり何なりで明確に認識できていない
- Markdownって文法でいうと何になるんだ？ LL(k)でいいのか?
- 構文解析にまつわる小話たちというスライドによると、Markdownは(Table記法を除けば)少なくとも文脈自由文法ではある。
Listの冗長なところ
- 自身のHakell力の不足による
StringではなくTextを使う
図との連携
- 折角my実装を作ったので、my拡張を加えてもよいかと