PEG(Parsing Expression Grammar) を試す→ parboiled を使用

markdown のサブセット mini-mark のパーサを実装した話。

パーサを実装といっても、PEGで表記したものを parboiled で実装しただけです。

PEGという文法があり、これを定義しておけばパーサになる（ただしPEGを解釈して実際のパーサに変換してくれる何かしらのツール等が必要ですが）という世界らしい。（よくわかっていません。） ここでは、PEGの Java 実装の一つであるらしい parboiled を使ってパーサを実装してみます。

mini-mark の例

こんな感じのマークアップされたテキストをパースしたい。 説明の都合上これを mini-mark と呼びます。

# h1 header

This is a paragraph.

## h2 header

This is another paragraph.

mini-mark の PEG

厳密な記述ではないですが、だいたいこんな感じでしょうか。

Doc      ← Block*
Block    ← NewLine / HeadLine / ParaLine
HeadLine ← '#'+ Spaces ParaLine
ParaLine ← Inline NewLine
Inline   ← \n以外のすべての文字*
NewLine  ← '\n'
Spaces   ← ' '+

mini-mark PEGを parboiled 用に書きかえ

以下を念頭にPEG表記をparboiledに変換します。

• A B, 出現順指定→ Sequence(A, B)
• A / B, A そうでなければ B → FirstOf(A, B)
• ０回以上出現→ ZeroOrMore(ルール)
• 1回以上出現→ OneOrMore(ルール)
• 特定の文字 → String(文字)
• 特定の文字以外の文字 → NoneOf(文字)

記述方法の詳細情報はこちら
https://github.com/sirthias/parboiled/wiki/Rule-Construction-in-Java

完成したコードは以下の通り。 PEG表記と比べて冗長さは増えましたが、ほぼそのまま機械的に置きかえるだけで済むのは素敵です。

MiniMarkParser.groovy

@BuildParseTree 
class MiniMarkParser extends BaseParser<Object> {

    Rule Doc() {
        ZeroOrMore(Block())
    }

    Rule Block(){
        FirstOf( NewLine(), HeadLine(), ParaLine() )
    }

    Rule HeadLine(){
        Sequence( OneOrMore('#'), Spaces(), ParaLine() )
    }

    Rule ParaLine(){
        Sequence( Inline(), NewLine() )
    }

    Rule Inline(){
        ZeroOrMore(NoneOf('\n'))
    }

    Rule NewLine(){
        String('\n')
    }

    Rule Spaces(){
        OneOrMore(' ')
    }
}

まとめ

パース対象となる文字列の文法だけ定義して、あとは機械的な作業でパーサーの実装がつくることができれば、実装が楽なだけでなく、保守の面から考えてもとても魅力的です。