LoginSignup
2
1

More than 3 years have passed since last update.

@Kray-G

Kinx ライブラリ - パーサ・コンビネータ（その1）

Last updated at Posted at 2020-07-03

Kinx ライブラリ - パーサ・コンビネータ（その1）

はじめに

「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。今回はパーサ・コンビネータです。

前回 JIT ライブラリ を紹介しましたが、最後以下の言葉で締めくくりましたね。

これでパーサ・コンビネータとか実装して組み合わせたらたら、ちょっとした JIT 付き言語処理系が作れますね。

ええ、そこで急遽作りましたよ。パーサ・コンビネータ・ライブラリ。その名も Parsek。Parsec ならぬ Parsek。

インタフェースは Parsimmon を参考にしましたが、実装は全くの独自です。API はこんなに充実してませんが、それなりに使えます。インタフェースを追加するのは簡単なので、追々必要に応じて追加しよう。

長くなりそうなので記事を 2 回に分けようかと思います。

今回はこれを使って、四則演算文法をパースして AST（Abstract Syntax Tree = 抽象構文木）を作るところまでいきましょう。次回、最後には JIT コンパイルして実行するところまでいきます。

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

小さい（単純な）パーサーを組み合わせて大きなパーサーを作るためのライブラリ。詳しくは他の記事に譲るとして、以下、サンプルを見ながらわかるようにしてみましょう。

サンプル

今回は趣向を変えて、サンプルを使いながら説明してみます。サンプルは正の整数（自然数）による四則演算です。簡単のために負の数は扱いません（結果が負になることはあり得ます）。

普通はここで BNF とか PEG とかの説明に入るのでしょうが、無視します。サンプルを通してまず動かすところからスタートです。

using Parsek

パーサ・コンビネータ・ライブラリは標準組み込みではないので、using しましょう。また、ライブラリはクラスとして提供されているのでインスタンス化しておきましょう。

using Parsek;

var $ = new Parsek();

何気に $ は変数名として使えます。

小さな（単純な）パーサーとは？

一つずつ例を挙げてみます。

数値をパースするパーサー

まず、正の整数を定義してみましょう。これが一つ目の小さな（単純な）パーサーです。一つ目ですが、いきなり正規表現です。まぁ、それほど難しくないのでわかりやすいでしょう。

ひとつだけ落とし穴なのは、使っているエンジン（＝鬼車）が POSIX NFA ではない ので、長くマッチするほうを先に書かないといけません。簡単に言うと、以下の例では "123" はきちんと "123" でマッチしますが、逆（/[0-9]|[1-9][0-9]*/）に書くと最初に書いた [0-9] にマッチして検索をやめてしまうので "1" となって "23" にマッチしません。注意しましょう。

var number = $.regex(/[1-9][0-9]*|[0-9]/);

これでこの number というパーサーは数値（が書かれた文字列）をパースできるようになります。やってみましょう。

実際にパースを行うのは parseAll() メソッドです。parse() というのもありますが、これは途中で終了しても成功するメソッドで、通常は内部で使われます。parseAll() の場合は全て解析し終わって後処理まで実施して結果を返します。

using Parsek;

var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/);

System.println(number.parseAll("0"));       // => {"position":1,"status":1,"value":"0"}
System.println(number.parseAll("10"));      // => {"position":2,"status":1,"value":"10"}
System.println(number.parseAll("129"));     // => {"position":3,"status":1,"value":"129"}
System.println(number.parseAll("abc"));     // => {"position":0,"status":0,"value":null}
System.println(number.parseAll("0129"));    // => {"position":1,"status":0,"value":null}

復帰値の position はパースした文字列の完了位置で、status が成功・失敗（1 が成功）、value が実際にパースが成功した文字列です。見て分かる通り、失敗すると value は null です。

しかしよく見ると value は文字列ですね。文字列を解釈しているだけなので当たり前です。ここで、value に対して変換を行うメソッドが .map() です。以下のように変換用の関数を与えます。

using Parsek;

var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(&(value) => Integer.parseInt(value));

System.println(number.parseAll("129"));     // => {"position":3,"status":1,"value":129}

数値になりましたね。上記の場合、単に値をパススルーしているだけなので、Integer.parseInt を直接渡しても同じです。

var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);

このほうが簡潔ですね。

四則演算の演算子をパースするパーサー

演算子によって優先度が違うので 2 つに分けます。

  • + または -
  • * または / または %

一文字の or を解釈するのに便利なのが $.oneOf() です。以下のように使います。

var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");

簡単ですねー。早速試してみましょう。

using Parsek;

var $ = new Parsek();
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");

System.println(addsub.parseAll("+"));       // => {"position":1,"status":1,"value":"+"}
System.println(addsub.parseAll("-"));       // => {"position":1,"status":1,"value":"-"}
System.println(addsub.parseAll("*"));       // => {"position":0,"status":0,"value":null}
System.println(muldiv.parseAll("*"));       // => {"position":1,"status":1,"value":"*"}
System.println(muldiv.parseAll("/"));       // => {"position":1,"status":1,"value":"/"}
System.println(muldiv.parseAll("%"));       // => {"position":1,"status":1,"value":"%"}
System.println(muldiv.parseAll("a"));       // => {"position":0,"status":0,"value":null}

期待通りです。

カッコをパースするパーサー

もう一つ、数値演算には必要なカッコを解釈させましょう。特定の文字列にマッチするパーサーは $.string() を使います。ここでは 1 文字ですが、何文字の文字列でも OK です。

var lbr = $.string("(");
var rbr = $.string(")");

これも試してみるとうまく動きます。$.string() の効果を見るために別の文字列でも試してみましょう。

using Parsek;

var $ = new Parsek();
var lbr = $.string("(");
var rbr = $.string(")");
var hoge = $.string("hoge");

System.println(lbr.parseAll("("));          // => {"position":1,"status":1,"value":"("}
System.println(lbr.parseAll(")"));          // => {"position":0,"status":0,"value":null}
System.println(rbr.parseAll("("));          // => {"position":0,"status":0,"value":null}
System.println(rbr.parseAll(")"));          // => {"position":1,"status":1,"value":")"}
System.println(hoge.parseAll("hoge"));      // => {"position":4,"status":1,"value":"hoge"}
System.println(hoge.parseAll("fuga"));      // => {"position":0,"status":0,"value":null}

正しくマッチしているのが分かります。

組み合わせるとは？（コンビネーター）

これで小さな（単純な）パーサーという道具が揃いました。

var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
var lbr = $.string("(");
var rbr = $.string(")");

これらを組み合わせてみましょう。ここで PEG を出しておきます。BNF でもいいですが、PEG のほうがコンビネーターには合ってますね。文法はこうですよ、というのを示しておかないと何やってるかわからなくなりそうですので。意味は追々触れていきます。

number <- regex(/[1-9][0-9]*|[0-9]/)
addsub <- '+' / '-'
muldiv <- '*' / '/' / '%'
lbr <- '('
rbr <- ')'

expression <- term (addsub term)*
term <- factor (muldiv factor)*
factor <- number / (lbr expression rbr)

PEG の優先度付選択の記号 / と除算の指定 '/' が紛らわしいですが、よく見ると分かります。

トップダウン、ボトムアップどちらもありですが、ここではボトムアップでパーサーを構築していきます。

factor

まずは factor です。

factor <- number / (lbr expression rbr)

factor は number か lbr expression rbr か、になります。プログラムにそのまま落とせます。ここで使うのは以下のメソッドです。

  • ここではまだ expression が定義されていないので、遅延評価させるために $.lazy() を使います。$.lazy() を使うと実際に評価されるときにパーサーが作られます。
  • どちらかを選ぶ、というメソッドは $.alt() です。複数のものから最初に成功したパーサーの結果を返します。
  • lbr expression rbr というように複数のものが連続している、ということを表すのが $.seq() です。

さて書いてみましょう。expression は事前に宣言だけしておきます。

var expression;
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr)));

term

次は term です。

term <- factor (muldiv factor)*

これは、factor の後に (muldiv factor) が 0 回以上続く、という意味です。0 回も許されるので、何も続かない、というのも OK です。muldiv factor といった感じに並べるのはさっきの lbr expression rbr と同じで連続していることを意味します。ここで使うメソッドは以下です。

  • 0 回以上の繰り返し、はパーサーに対して .many() を指定します。

では定義してみましょう。

var term = $.seq(factor, $.seq(muldiv, factor).many());

これで term が定義できました。

expression

最後に expression です。形は term と一緒ですね。

expression <- term (addsub term)*

そのまま書いてみましょう。

expression = $.seq(term, $.seq(addsub, term).many());

これでパーサーが揃いました。試しにパースしてみましょう！

パース

一旦、ソースコードを全部載せてみます。とはいってもそんなにないですね。

using Parsek;

var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
var lbr = $.string("(");
var rbr = $.string(")");

var expression;
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr)));
var term = $.seq(factor, $.seq(muldiv, factor).many());
expression = $.seq(term, $.seq(addsub, term).many());

// parse expression!
System.println(expression.parseAll("1+2*3+2*(14-2)"));
// => {"position":14,"status":1,"value":[[1,{}],[["+",[2,[["*",3]]]],["+",[2,[["*",["(",[[14,{}],[["-",[2,{}]]]],")"]]]]]]]}
System.println(expression.parseAll("1+2*3+2*(14-2-)"));
// => {"position":7,"status":0,"value":null}

最初のは（長いですが）成功したことが分かります。結果を読むのは大変ですが、これは後で整形しましょう。そして、2 つ目は失敗していることが分かります。最後の (14-2-) がどの規則にもマッチしてないからですね。

ではこの結果を整形していきましょう。活躍するのは number で使った .map() です。

カッコの式

まず、$.seq(lbr, expression, rbr) の部分です。$.seq() は値として結果の配列を返します。カッコの式というのは、値としてはカッコは不要で中にある式の結果だけあればいいですね。ということで、以下のように変えます。

var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr).map(&(value) => value[1])));

修正すると結果は次のようになります。

System.println(expression.parseAll("1+2*3+2*(14-2)"));
// => {"position":14,"status":1,"value":[[1,{}],[["+",[2,[["*",3]]]],["+",[2,[["*",[[14,{}],[["-",[2,{}]]]]]]]]]]}

ちょっと短くなりましたね。

term、expression

次に、term と expression です。ここでは、後で解析するために AST（Abstract Syntax Tree = 抽象構文木）の形に整形するようにしましょう。基本的には二項演算子なので、LHS（Left Hand Side = 左辺）と RHS（Right Hand Side = 右辺）と演算子（Operator）の組み合わせのオブジェクトを作ります。

ここで、$.seq() をやめて、$.seqMap() を使うように変更します。これは $.seq() と .map() を一緒にしたようなもので、結果リストを引数として最後の引数に指定した関数にコールバックしてくれる便利なメソッドです。こんな風に使います。

var term = $.seqMap(factor, $.seq(muldiv, factor).many(), &(first, rest) => {
    var expr = first;
    for (var i = 0, l = rest.length(); i < l; ++i) {
        expr = { lhs: expr, op: rest[i][0], rhs: rest[i][1] };
    }
    return expr;
});

first は factor の結果で、rest は $.seq(muldiv, factor).many() の結果です。なので、rest は各要素が [演算子, 右辺] の形の配列です（空配列の場合もある）。それを AST の形に整形しています。結果、例えば "2 * 3 * 4" みたいなものは以下のように整形されます。

  • コールバック時
    • まず、first は 2
    • rest は [['*', 3], ['*', 4]]
  • expr に 2 が入る
  • ループに入り、expr が { lhs: 2, op: '*', rhs: 3 } になる。
  • もう一つ要素があるので、expr が { lhs: { lhs: 2, op: '*', rhs: 3 }, op: '*', rhs: 4 } になる。

左側の枝が伸びていく形の AST になります（これを左結合という）。今回の演算子は全て左結合です。

expression も一緒なので、同じように書きましょう。中身は全く同じですなので関数化して使いまわしましょう。

function makeAST(first, rest) {
    var expr = first;
    for (var i = 0, l = rest.length(); i < l; ++i) {
        expr = { lhs: expr, op: rest[i][0], rhs: rest[i][1] };
    }
    return expr;
}
var term = $.seqMap(factor, $.seq(muldiv, factor).many(), makeAST);
expression = $.seqMap(term, $.seq(addsub, term).many(), makeAST);

すっきりしました。

では、プログラム一式です。たったこれだけの定義で四則演算を（演算子の優先順位も考慮された形で）パースできてしまいます。素晴らしいですね！

using Parsek;

function makeAST(first, rest) {
    var expr = first;
    for (var i = 0, l = rest.length(); i < l; ++i) {
        expr = { lhs: expr, op: rest[i][0], rhs: rest[i][1] };
    }
    return expr;
}

var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
var lbr = $.string("(");
var rbr = $.string(")");

var expression;
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr).map(&(value) => value[1])));
var term = $.seqMap(factor, $.seq(muldiv, factor).many(), makeAST);
expression = $.seqMap(term, $.seq(addsub, term).many(), makeAST);

// test
System.println(expression.parseAll("1+2*3+2*(14-2)").value.toJsonString(true));

結果はこうなります。うまくいってますね！

"lhs": {
    "lhs": 1,
    "op": "+",
    "rhs": {
        "lhs": 2,
        "op": "*",
        "rhs": 3
    }
},
"op": "+",
"rhs": {
    "lhs": 2,
    "op": "*",
    "rhs": {
        "lhs": 14,
        "op": "-",
        "rhs": 2
    }
}

おわりに

さて、目的の AST ができました。次回、これを解釈して実行させます。せっかく作った JIT ライブラリも使いますよ！

ではまた次回！

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1