目的

マークダウンのパーサライブラリがどのように実装されているのか学ぶことにしました。（唐突）
Javaのdomパーサの設計（デザインパターン）が素晴らしいとのことですが、まずは慣れているPythonのライブラリを探してみました。

ちなみにJavaのはこれ。
https://www.tutorialspoint.com/java_xml/java_dom_parse_document.htm

今回は以下のライブラリのソースを読んでみます。

Python-Markdown
https://github.com/Python-Markdown

Markdown->HTMLへの変換ができるみたいです。
当然、中でMarkdownの解析を行なっているわけで、どのような設計になっているのか、拝見しましょう！

理解が間違っている箇所などありましたら、ご指摘ください...！

注意書き

Python-Markdown/markdown/markdown/ 以下にコアな関数たちが集められているようです。
今後は面倒なので、基本的にこのディレクトリ以下のファイルをsample.pyのように省略して表示します。

また、以下に載せるソースコードは基本的に必要な部分のみを抜粋（＋コメントアウトでメモ書き）したものになっています。

メイン部分を最初にネタバレ

結論から言うと、特定のエレメントを検出する各プロセッサーをブロックごとに順番に作用させていました。
作用させる対象は、元のテキストを「\n\n」で分割した各ブロックになっています。
これは例えば、

<b>タグが不完全ですが、太字です

太字ではありません</b>

のように空白行が入る（＝「\n\n」が現れる）と、エレメントの有効範囲が途切れてしまうからですね。

この例だと、まず

["<b>タグが不完全ですが、太字です", "太字ではありません</b>"」

のように各ブロックにして、まず"<b>タグが不完全ですが、太字です"に対して各要素を検出するプロセッサーを順番に作用させ、次のブロックへ進んで...
といった流れになるかと思います。

処理の流れ

このライブラリでユーザが使用するインターフェースの中心となるのは、以下のMarkdownクラスとそのconvertメソッドです。

core.py

class Markdown:

    # ここでhtmlに変換
    def convert(self, source):
        # source : マークダウンのテキスト

convertメソッドにコメントが付いており、和訳するとこんな感じ。

１、preprocessorたちがテキストを変換する
２、１で前処理されたテキストの高レベル構造elementをElementTreeにパースする
３、ElementTreeをtreeprocessorたちが処理する。例えばInlinePatternsはinline要素を見つける
４、ElementTreeをテキストにシリアライズしたものに、いくつかのpost-processorsを作用させる
５、結果を文字列に書き出す

もはや原文の方が読みやすいかもw

ステップ１　preprocessors

core.py


class Markdown:

    def convert(self, source):
        < 略 >
        self.lines = source.split("\n")
        for prep in self.preprocessors:
            self.lines = prep.run(self.lines)

まず各行に分割して、前処理を噛ませる。
preprocessorsは以下で取得しています。

preprocessors.py


def build_preprocessors(md, **kwargs):
    """ Build the default set of preprocessors used by Markdown. """
    preprocessors = util.Registry()
    preprocessors.register(NormalizeWhitespace(md), 'normalize_whitespace', 30)
    preprocessors.register(HtmlBlockPreprocessor(md), 'html_block', 20)
    preprocessors.register(ReferencePreprocessor(md), 'reference', 10)
    return preprocessors

NormalizeWhitespace > HtmlBlockPreprocessor > ReferencePreprocessor
の優先順位で前処理が登録されています。

名前の通り
NormalizeWhitespace：　空白、改行文字の正規化（10行程度の実装）
HtmlBlockPreprocessor：　html要素の解析（250行...！）
ReferencePreprocessor：　[タイトル](リンク）の形式で表現されるリンクを見つけて辞書Markdown.referencesに登録（30行）

HtmlBlockPreprocessorの中身は飛ばしましょう。同じような要素検出処理はステップ２や３で待ち構えているはずです...

（余談）
ReferencePreprocessorのように、次の行までその要素の中身になるかの判定をしなければいけない場面はパーサではよく出てきて、自作（勉強がてら）の時は

while lines:
    line_num += 1
    line = self.lines[line_num]
    <処理>
    if (次の行まで含める):
        line_num += 1
        line = self.lines[line_num]

のようにしていましたが、ReferencePreprocessorではpopを使っています。

while lines:
    line = lines.pop(0)

うん、そうするべきでした...汗

（余談おわり）

ステップ２　ErementTreeにパース

この処理は以下の部分です。

core.py


class Markdown:

    def convert(self, source):
        < 略 >
        # Parse the high-level elements.
        root = self.parser.parseDocument(self.lines).getroot()

ここでself.parserというのは以下の関数で取得したBlockParserになります。

blockprocessors.py


def build_block_parser(md, **kwargs):
    """ Build the default block parser used by Markdown. """
    parser = BlockParser(md)
    parser.blockprocessors.register(EmptyBlockProcessor(parser), 'empty', 100)
    parser.blockprocessors.register(ListIndentProcessor(parser), 'indent', 90)
    parser.blockprocessors.register(CodeBlockProcessor(parser), 'code', 80)
    parser.blockprocessors.register(HashHeaderProcessor(parser), 'hashheader', 70)
    parser.blockprocessors.register(SetextHeaderProcessor(parser), 'setextheader', 60)
    parser.blockprocessors.register(HRProcessor(parser), 'hr', 50)
    parser.blockprocessors.register(OListProcessor(parser), 'olist', 40)
    parser.blockprocessors.register(UListProcessor(parser), 'ulist', 30)
    parser.blockprocessors.register(BlockQuoteProcessor(parser), 'quote', 20)
    parser.blockprocessors.register(ParagraphProcessor(parser), 'paragraph', 10)
    return parser

こちらも優先順位とともにプロセッサーが登録されています。
BlockParser.praseDocument()はこちら。

blockparser.py


class BlockParser:

    def __init__(self, md):
        self.blockprocessors = util.Registry()
        self.state = State()
        self.md = md

    # ElementTreeを作成する
    def parseDocument(self, lines):
        self.root = etree.Element(self.md.doc_tag)
        self.parseChunk(self.root, '\n'.join(lines))
        return etree.ElementTree(self.root)

    def parseChunk(self, parent, text):
        self.parseBlocks(parent, text.split('\n\n'))

    def parseBlocks(self, parent, blocks):
        while blocks:
            for processor in self.blockprocessors:
                if processor.test(parent, blocks[0]):
                    if processor.run(parent, blocks) is not False:
                        break

要するに、

core.py

root = self.parser.parseDocument(self.lines).getroot()

の部分では各BlockProcessorに処理をさせているわけですね。

例えば、ハッシュタグによるヘッダー「# ヘッダー」形式をさばくプロセッサーは以下のように定義されています。

blockprocessors.py


class HashHeaderProcessor(BlockProcessor):
    """ Process Hash Headers. """

    RE = re.compile(r'(?:^|\n)(?P<level>#{1,6})(?P<header>(?:\\.|[^\\])*?)#*(?:\n|$)')

    def test(self, parent, block):
        return bool(self.RE.search(block))

    def run(self, parent, blocks):
        block = blocks.pop(0)
        m = self.RE.search(block)
        if m:
            ``` ここから ```
            before = block[:m.start()]
            after = block[m.end():]
            if before:
                # beforeの部分のみ再帰処理
                self.parser.parseBlocks(parent, [before])
            h = etree.SubElement(parent, 'h%d' % len(m.group('level')))
            h.text = m.group('header').strip()
            if after:
　　　　　　　　　 # 次にafterを処理するために、blocksの先頭に追加
                blocks.insert(0, after)
            ``` ここまでがコアってことよね ```
        else:
            logger.warn("We've got a problem header: %r" % block)

もう１つ、「> 文章」形式の引用ブロックのプロセッサーを見てみましょう。

引用ブロックで考えなければいけないことは
・複数行に連続したブロックは、１つのブロックとしてみなす
・ブロックの中身もパースしなければいけない
ってことですね。

blockprocessors.py


class BlockQuoteProcessor(BlockProcessor):

    RE = re.compile(r'(^|\n)[ ]{0,3}>[ ]?(.*)')

    def test(self, parent, block):
        return bool(self.RE.search(block))

    def run(self, parent, blocks):
        block = blocks.pop(0)
        m = self.RE.search(block)
        if m:
            before = block[:m.start()]
            # ここはさっきのHashHeaderProcessorと同じだね
            self.parser.parseBlocks(parent, [before])
            # 各行先頭の">"を削除
            block = '\n'.join(
                [self.clean(line) for line in block[m.start():].split('\n')]
            )
        ``` 引用ブロックが今まで続いてきたか、ここが先頭かを考慮 ```
        sibling = self.lastChild(parent)
        if sibling is not None and sibling.tag == "blockquote":
            quote = sibling
        else:
            quote = etree.SubElement(parent, 'blockquote')
        self.parser.state.set('blockquote')
        ``` 引用ブロックの中身（block）をパース。親は現在のブロック（quote）にしているね ```
        self.parser.parseChunk(quote, block)
        self.parser.state.reset()

ちなみに、siblingは兄弟や姉妹を表す単語なんだね。

２つのプロセッサークラスをみてきましたが、パース結果をどこに保存しているかとえば、
etree.SubElement(parent, <tagname>)
の部分が怪しい。

そもそもetreeとは、pythonの標準ライブラリにあるxml.etree.ElementTreeインスタンスになります。
etree.SubElement(parent, <tagname>)によって、BlockParser().root（これもまたElementTreeインスタンス）に子要素を加えていることになります。

プロセスが進むにつれ、結果がBlockParser().rootとして保存されていくわけですね。

ステップ３　treeprocessor

今までと同様に、今度はtreeprocessorを噛ませます。

treeprocessors.py


def build_treeprocessors(md, **kwargs):
    """ Build the default treeprocessors for Markdown. """
    treeprocessors = util.Registry()
    treeprocessors.register(InlineProcessor(md), 'inline', 20)
    treeprocessors.register(PrettifyTreeprocessor(md), 'prettify', 10)
    return treeprocessors

InlineProcessor　：　インライン要素に対する処理
PrettifyTreeprocessor　：　改行文字などの処理

終わりに

え、いきなりおしまい！？
でも、今まで見てきた中でこのライブラリの大まかなデザインパターンはわかったのではないでしょうか？
あとは気になる部分があれば、各自で見るのが良いでしょう...

ちょっと、疲れました。

最後までご覧いただきありがとうございます...！

目的

注意書き

メイン部分を最初にネタバレ

処理の流れ

ステップ１ preprocessors

ステップ２ ErementTreeにパース

ステップ３ treeprocessor

終わりに

ステップ１　preprocessors

ステップ２　ErementTreeにパース

ステップ３　treeprocessor