(Pythonで)ゼロから作るパーサーコンビネーター入門

この間手が空いていたので、と言っても筆者はニートなので常時手は空いているのですが、パーサーコンビネーターをPythonでゼロから実装してみました。作ろうと思った背景として、markdownのパーサーを作る上でParsimmonというJSによって実装されたパーサーコンビネーターにcontributeした経験があったのと、C++のboost::spirit::qiというパーサーコンビネーターライブラリに触発されたという二点があります。

この2つのライブラリの良いところを取り合わせつつ書きやすいパーサーコンビネーターを作ろうと思いました。

完成したPEGパーサーコンビネーターはこちらです。

minamorl/trishula: The modern PEG parser combinator for python

このパーサーコンビネーターは実際の利用を考慮してmap、オペレーターオーバーロード、正規表現への対応、再帰を実現するためのパーサーの遅延評価、名前空間といったいくつかの追加的な処理を含んでいます。Parsimmonのメンテナの方にフィードバックをもらいつつ開発している最中です。

完全な実装を説明するのは余計な混乱を招きそうなので、今回はこのプロダクトを簡略化したものをベースに説明して行こうと思います。

パーサーコンビネーターとは

誤解を恐れずに言うと正規表現を強力にしたものです。というとイメージはしやすいかもしれません。パーサーを作るための文法を定義するツールと言ったほうがわかりやすいかも知れません。パーサーコンビネーターを作る上でPEGについて説明したいと思います。Wikipediaを参考にします。重要な箇所はこれだけです:

「atomic parsing expression」は次のいずれかである。
任意の終端記号
任意の非終端記号
空文字列 ε

これは簡単ですね。重要なのは次です:

任意の既存のparsing expressionを e, e1, e2 としたとき、以下のように構築されるものもparsing expressionである。
並び: e1 e2
選択: e1 / e2
ゼロ個以上: e*
1個以上: e+
省略可能: e?
AND predicate: &e
NOT predicate: !e

それぞれ文字列の並び、文字列の選択、といった形で読み替えると分かりやすいです。これらの組み合わせによって文法(≒パーサー)を定義し、パースするというのがパーサーコンビネーターの主な役割となります。

今回作るプロダクトの完成像

今回は簡略化のため、並びと選択の2つに対応させたいと思います。

Sequence(Value("aaa"), Value("bbb")).parse("aaabbb", 0)
# ==> (True, 6, ['aaa', 'bbb'])

それぞれパースの成否、現在の文字列のインデクス、パース結果をタプルにしたものです。

ベースとなる文字列クラスの定義

まず文字列を定義するクラスを考えていきましょう。

class Value:
    def __init__(self, val):
        self.val = val

Value("aaa")

次に、このクラスに対してパースする処理を書いていきましょう。パースする、ということは文字列を消費して結果の成否とインデックスを返すこととします。

class Value:
    def __init__(self, val):
        self.val = val

    def parse(self, target, i):
        if target[i : i + len(self.val)] == self.val:
            return (True, i + len(self.val), self.val)
        return (False, i)

このクラスは次のように使われることを想定しています:

Value("aaa").parse("aaa", 0)
# ==> (True, 3, 'aaa')
Value("aaa").parse("ccc", 0)
# ==> (False, 0)

Trueの場合次の処理へ継続して、Falseの場合そこでストップする、というのが基本動作になります。これをベースにして作っていきましょう。

選択(ordered choice)

選択はaとbという2つのパーサーを受け取り、順次に実行してパースに成功した方の結果を返します:

class OrderedChoice:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def parse(self, target, i):
        resultA = self.a.parse(target, i)
        if resultA[0] is True:
            return resultA
        resultB = self.b.parse(target, i)
        if resultB[0] is True:
            return resultB
        return (False, i)

失敗したときの戻り値は(False, i)で、これはもとのポジションで失敗したことを意味します。

並び(sequence)

並びはaとbという2つのパーサーを受け取り、aを実行した結果が真ならそのポジションからbを実行し、その結果が真なら2つを組み合わせた値を返します:

class Sequence:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def parse(self, target, i):
        resultA = self.a.parse(target, i)
        if resultA[0] is True:
            resultB = self.b.parse(target, resultA[1])
            if resultB[0] is True:
                return (True,
                    resultB[1],
                    [resultA[2], resultB[2]],
                )
        return (False, i)

同じく失敗したときの戻り値は(False, i)で、これはもとのポジションで失敗したことを意味します。

組み合わせ

それではここまでの結果をまとめます。使い方はシンプルです。

grammar = Sequence(Value("aaa"), OrderedChoice(Value("bbb"), Value("ccc")))

print(grammar.parse("aaaccc", 0))
print(grammar.parse("aaaddd", 0))

実行結果はこうです:

(True, 6, ['aaa', 'ccc'])
(False, 0)

出来ました。完成ですね。

結び

ゼロ個以上、1個以上、省略可能、AND、NOTの実装も同様です。Trishulaの基本の実装自体は1日でほぼ完成したので簡単にできると思います。ちなみに拙作のTrishulaではこれらをベースとしてオペレーターオーバーロードを活用して次のように書けるようにしています:

grammar = Value("aaa") >> (Value("bbb") | Value("ccc"))

PEGの表現力は強力で、下手な正規表現を書くよりよほど簡潔に色々なことができます。
開発もまだまだ初期段階でissueも活発なので興味を持たれた方は是非使ってみて開発に参加してみてくださいね。

minamorl/trishula: The modern PEG parser combinator for python