Markdownをhtmlに変換するパーサーを作った

最近はパーサーの実装にハマっており、直近だとRubyでJSONパーサー(json形式のテキストをRubyのハッシュに変換)を作りました。

少し間が空いてしまいましたが、今回はMarkdown形式のテキストをhtmlに変換するパーサーを作ってみました。
本当はもっと早く記事にできる予定だったのですが、実装にかなり手間取っていました。3日もあれば完成するだろう...と思っていたものの、結果的に2週間もかかってしまいました。

今までRubyを使って実装してきましたが、今回は気分転換のためにGolangを選択しました。
久しぶりにGolangをゴリゴリと書けたので楽しかったのですが、エラーハンドリングの単調さはどうも好きにはなれません...。

作った物

githubにて公開しています。

github.com

Markdown形式のテキストファイルを読み取り、htmlファイルに変換するというシンプルなプログラムです。
例を挙げると# h1はhtmlの<h1>h1</h1>に変換されます。Markdownとhtmlは互換性があるので、最終的にそれぞれが対応するhtmlタグに変換するようになっています。
現在(2023/10/18)のバージョンで対応しているのは以下の構文です。

見出し(h1 ~ h6)
リスト(ネスト可能)
太字
斜体
通常のテキスト
インライン
シンタックスハイライト(なおハイライトはなし)
リンク

あまりサポートはできていませんが、概ねコアになるものはサポートしたつもりです。
特にリストはネスト可能なので、非常に頭を悩まされました。同様に太字や斜体もテキスト中に何度も出現する上、合わせ掛けも可能なため、AST(抽象構文木)でどのようなデータ構造にするかが難しかったです。

動作イメージ

以下のようなMarkdown形式のテキストを与えるとhtmlファイルが生成されます。

# h1
## h2
### h3
#### h4
##### h5
###### h6

- a
- b
- c

- a
  - b
    - c

- a
  - **b**
    - __c__
      - **b** and __c__

**weight**
__italic__
**weight** and __italic__

hello world

※見やすさのため整形してありますが、実際は改行されただけのシンプルなものが出力されます。

<html>
  <head>
    <title>Generate html from markdown!</title>
  </head>
  <body>
    <h1>h1</h1>
    <h2>h2</h2>
    <h3>h3</h3>
    <h4>h4</h4>
    <h5>h5</h5>
    <h6>h6</h6>
    <br />
    <ul>
      <li>a</li>
      <li>b</li>
      <li>c</li>
    </ul>
    <br />
    <ul>
      <li>a</li>
      <ul>
        <li>b</li>
        <ul>
          <li>c</li>
        </ul>
      </ul>
    </ul>
    <br />
    <ul>
      <li>a</li>
      <ul>
        <li><b>b</b></li>
        <ul>
          <li><i>c</i></li>
          <ul>
            <li><b>b</b> and <i>c</i></li>
          </ul>
        </ul>
      </ul>
    </ul>
    <p><b>weight</b></p>
    <p><i>italic</i></p>
    <p><b>weight</b> and <i>italic</i></p>
    <p>hello world</p>
  </body>
</html>

生成したhtmlファイルをブラウザで確認すると、こんな感じになります。
やりたいことは最低限できたかな...という感じです。

処理の流れ

このパーサーは3つのステップで処理されていきます。
特に珍しいステップはなく、よくある実装だと思います。

lexer(字句解析): ファイルから1文字ずつ読み取り、それぞれトークン(構造体)に変換する
parser(構文解析): トークンをAST(構造体の配列)に変換する
generator(コード生成): ASTをhtml形式に変換する

以下の記事を参考にさせて頂きました。
詳しい解説もされているので、気になる方は合わせてご覧ください。

www.m3tech.blog

最終的にAST(抽象構文木)は構造体を要素に持つ配列で実装した所、いい感じになりました。
今までAST(抽象構文木)は二分木である必要があると思っていたのですが、必ずしもそうである必要はないようです。

パース例

# タイトルを与えた場合、こんな感じでパースされて最終的にhtmlとなります。

// 
// lexer
token := &Token {
    Kind: RESERVED,
    Value: "#",
    Depth: 0
    Next: &Token {
        Kind: PLAIN_TEXT,
        Value: "タイトル",
        Depth: 0,
        Next: nil,
    },
}
// parser
ast := [&Node {
    Kind: ND_HEADER,
    Level: 1,
    Depth: 0,
    Value: "",
    Sub: nil,
    Next: &Node {
        Kind: ND_VALUE,
        Level: 1,
        Depth: 0,
        Value: "",
        Sub: nil,
        Nest: nil
    }
}]
// generator
html := "<h1>タイトル</h1>"

それっぽいですが、実は反省ポイントがあります。

反省点...

やってしまったなぁ...と思っているのが初期実装でlexerがファイルから1文字ずつテキストを読み込み空白をスキップするようにした点です。計算式やJSONのパースでは空白や改行は基本的に不要となるので、1文字ずつ読み込んで、該当する値はトークン化せずにスキップするようにしていました。
しかしMarkdownでは空白や改行がとても重要な情報になります。
Markdownという形式への理解が浅いまま実装を進めてしまったのです...。

func Tokenize(f *os.File) (*Token, error) {
    :
        if unicode.IsSpace(c) {
            spaceCnt++
            if IsSeparete(c) {
                curToken = NewToken(curToken, SEPARATE, string(c), 0)
                spaceCnt = 0
            }
            continue
        }
    :
}

空白はテキスト中に出現するものと、リスト等でネストの際に記述されるものがあり、扱いが非常に難しいです。
ファイルから1文字ずつ読み込むと、この判断が本当に難しくてリストのネストには苦労させられました。次にやるならファイルから1行ずつ読み込んで正規表現で判定する方法も候補に上がります。