PyPy Advent Calendar 二日目 - ebnfparse を使ってみた

みなさん処理系作ってますか?

PyPy 楽しいですよね!

というわけで昨日とは打って変わって PyPy Advent Calendar 二日目を担当する [twitter:@shomah4a] です。
他の人が翻訳ネタでエントリを書く宣言をしている中、空気を読まずに開発系エントリです。

PyPy って

そもそも PyPy ってなによ? ってのはきっと昨日 pypy-ja 総帥であるところの [twitter:@rokujyouhitoma] 氏が書いていると思うのですっ飛ばします。

と思ったら総帥が忙しいらしく、 [twitter:@Surgo] 氏が代打でした。
Kosei Kitahara's Blog: PyPy! - PyPy Advend Calendar

なので、 PyPy については slideshare に上げた PyPy 紹介を見てください。

なんのためのネタ?

このエントリでは、私が PyPy を使って勉強のために作っている Scheme 処理系 schepy を作る際に使った諸々のメモです。
と言っても、まだパースしてリスト化までしかしていないので、あまり書けることはありませんが…。

今回はソースコードのパースに使った ebnfparse を題材にします。

EBNF

で、 EBNF です。

EBNF とは、拡張バッカス・ナウア記法 (Extended Backus-Naur Form) と呼ばれるもので、文法の定義につかわれます。
EBNF を処理するライブラリがあるとプログラム言語の文法を定義して、パースしてくれたりするので処理系を作る上で面倒な部分である「ソースコードのパース処理」が楽にかけたりします。

詳しいことは Wikipedia へ

PyPy と EBNF

PyPy では、 pypy.rlib.parsing.ebnfparse として EBNF で文法定義するためのライブラリが存在します。

これを使うことでソースコードのパースが楽になるという寸法です。

パースやらなにやらのライブラリに関しては大体ここらへんに載っています。
http://doc.pypy.org/en/latest/rlib.html

pypy/rlib/parsing/test/test_ebnfparse.py なんかを見てみると、それぞれの言語での EBNF によるパーサの定義なんかが書いてあります。

例えば、 Prolog なんかは以下のような EBNF を使うと書けるようです。

"""
ATOM: "[a-z]([a-zA-Z0-9]|_)*";
VAR: "[A-Z]([a-zA-Z0-9]|_)*|_";
NUMBER: "0|[1-9][0-9]*";
IGNORE: "[ \\n\\t]";
file: fact file | fact;
fact: complexterm "." | complexterm ":-" compoundexpr ".";
compoundexpr: complexterm "," compoundexpr | complexterm ";" compoundexpr | complexterm;
complexterm: ATOM "(" exprlist ")" | ATOM;
exprlist: expr "," exprlist | expr;
expr: complexterm | ATOM | NUMBER | VAR;
"""

はい、簡単ですね。とはいえ Prolog はわからないので正しいのかどうかはわかりません。

他にも JSON は以下のようなものらしいです。

"""
    STRING: "\\"[^\\\\"]*\\"";
    NUMBER: "\-?(0|[1-9][0-9]*)(\.[0-9]+)?([eE][\+\-]?[0-9]+)?";
    IGNORE: " |\n";
    value: <STRING> | <NUMBER> | <object> | <array> | <"null"> |
           <"true"> | <"false">;
    object: ["{"] (entry [","])* entry ["}"];
    array: ["["] (value [","])* value ["]"];
    entry: STRING [":"] value;
"""

これでパーサの定義が出来上がり、 JSON のパースができるのですから楽なものですね。

なんかパースしてみる

なので、今回はこのテストコードを見ながら S式をパースしてみようと思います。

S式の EBNF

クオートやら準クオートやら足りないものもありますが、 S式のパーサは以下のような感じで定義しました。

sexprbnf = r'''
    IGNORE: " ";
    INTEGER: "0|[1-9][0-9]*";
    FLOAT: "(0|[1-9][0-9]*)\.[0-9]*";
    SYMBOL: "[a-zA-Z_-][a-zA-Z0-9_-]*";
    STRING: "\"[^\\"]*\"";

    sexpr: SYMBOL | INTEGER | FLOAT | STRING | list;
    list: "(" sexpr* list_left? ")";
    list_left: "." sexpr;
'''

これは、テストコードで定義されていた以下のようなS式っぽいパーサを拡張しただけです。

'''
    IGNORE: " ";
    ATOM: "[\+a-zA-Z_][a-zA-Z0-9_]*";

    sexpr: ATOM | list;
    list: "(" sexpr* ")";
'''

下地があるのでとっても楽ですね!

ebnfparse モジュールを使う

で、これをどう使うかというと、以下のように使います。

#-*- coding:utf-8 -*-

from pypy.rlib.parsing import ebnfparse


def make_parser():
    u'''
    パーサ作る
    '''
    
    sexprbnf = r'''
    IGNORE: " ";
    INTEGER: "0|[1-9][0-9]*";
    FLOAT: "(0|[1-9][0-9]*)\.[0-9]*";
    SYMBOL: "[a-zA-Z_-][a-zA-Z0-9_-]*";
    STRING: "\"[^\\"]*\"";

    sexpr: SYMBOL | INTEGER | FLOAT | STRING | list;
    list: "(" sexpr* list_left? ")";
    list_left: "." sexpr;
'''

    regexs, rules, to_ast = ebnfparse.parse_ebnf(sexprbnf)

    parser = ebnfparse.make_parse_function(regexs, rules)

    return parser, to_ast


parser, to_ast = make_parser()

parsed = parser('(a b c (1 2 3) . (e f . d))')

ebnfparse.parse_ebnf に自分で定義した EBNF を食わせてコンパイルします。

その後 ebnfparse.make_parse_function でパースするための関数を生成し、その関数にパースする対象のソースを食わせて終了です。

これだけで S 式がパースできるので、かなーり楽じゃないですか奥さん!

パースしたら…

さて、ここまでで S 式のパースができたので、ここからは S式として処理するために意味のあるデータを生成します。
パースしたトークン情報から、リストに変換する処理です。

で、ドキュメントの記述によると、「pypy.rlib.parsing.tree.RPythonVisitor を使うと Visitor パターンで書けるぜ!」みたいなことが書いてあったりするのですが、 dispatch メソッドに "NOT_RPYTHON" なんてタグが付いていて translate.py を通してバイナリ化する際にエラーが出てしまうのでこれは無理そうです。

なので、このドキュメントを参考に頑張ってパース結果からコンスセルっぽいデータ構造を吐くための処理を書きました。

ここらへん他の人はどうしているんでしょうね。

visitor 周りの処理は https://github.com/shomah4a/schepy/blob/master/schepy/parser/visitor.py この辺りに置いてあります。

おそらく visit メソッドが使えない理由は、リフレクションを行って動的に呼び出すメソッドを取ってくるというあたりなのかなと思います。
なので、ここは辞書+関数ポインタ(風)に書き換えることでなんとかやり過ごしているという感じです。

というか最初からリフレクションしなければいいのに。

これから

ここまででソースコードのパースからデータ表現までできたので、あとはこの S 式を評価する評価器さえ書けば Lisp 処理系ができてしまうわけですね。
まあ、その評価器が大変なのですが…。

S 式くらい自力でパースすりゃいいじゃんという話もあるはあるけれど、なにはともあれ PyPy を使うとこんな簡単にパースしたりデータ化したりできるんだよーという一例でした。

明日

明日は [twitter:@iizukak] 氏のターンです。
皆様ご期待ください!