caperのHaxeジェネレータ

7446 ワード
パーサジェネレータ C++ Haxe C++ テキストリンク

現在、以前紹介したcaperでHaxeジェネレータを実装しています。

だいたいの実装は済んだのですが、Haxe版出力で型安全性を狙ったところまでうまくもっていけていない状態です。

そういうわけで、Haxeエキスパートのお力をお借りできないかと思いこのドキュメントを書いています。

説明がだいぶ足りない気もするので、わからないことがあったらどんどん聞いてください。

実装を見てみたい場合は、

  1. https://github.com/jonigata/caper から最新版を持ってくる
  2. caper/caperでmake
  3. caper/caper/samples/haxeでmake
  4. Calc1Parser.hxをいじって
  5. haxe calc1.hxml
  6. 4、5を繰り返す繰り返す

などするとよいかと思います。

Haxe出力の話の前にC++出力の説明

C++では、このようになっています。

肝は、パーサクラスにテンプレートパラメータとして「SemanticAction」を与えることで、依存性を「使用側プログラム→caperが出力したパーサ」の一方向にしていることです。

これついては別のやり方、例えばパーサジェネレータの出力でJavaのinterfaceを定義し、ユーザはそれを継承するようなやり方も可能です。実際、Java出力はそうなっています。C++出力でテンプレートを使うようにしたのは、C++では「メモリ管理は完全にオーナ側に任せる、標準ライブラリも含めて外部ライブラリを使わない、のような要件があるためです。

Haxe版の問題点

このような文法ファイル

%token Number<Int> Add Sub Mul Div;
%namespace;

Expr<Expr> 
    : [makeExpr] Term(0)
    | [makeAdd] Expr(0) Add Term(1)
    | [makeSub] Expr(0) Sub Term(1)
    ;

Term<Term> 
    : [makeTerm] Number(0)
    | [makeMul] Term(0) Mul Number(1)
    | [makeDiv] Term(0) Div Number(1)
    ;

を与えた場合、Haxe版は、だいたいこのような出力

enum Token {
    eof;
    Add;
    Div;
    Mul;
    Number;
    Sub;
}

class Stack<T> { /* 実装略 */ }

private typedef Expr = Dynamic;
private typedef Term = Dynamic;
private typedef SemanticAction = {
    function syntaxError(): Void;
    function stackOverflow(): Void;
    function makeAdd(arg0: Expr, arg1: Term): Expr;
    function makeSub(arg0: Expr, arg1: Term): Expr;
    function makeExpr(arg0: Term): Expr;
    function makeTerm(arg0: Int): Term;
    function makeDiv(arg0: Term, arg1: Int): Term;
    function makeMul(arg0: Term, arg1: Int): Term;
}

class Parser {
    public function new(sa: SemanticAction){ /* 実装略 */ }

    public function post(token: Token, value: Dynamic): Bool { /* 実装略 */ }

    public function accept(): Dynamic { /* 実装略 */ }

    public function error(): Bool { return this.failed; }

    // 以下実装略
}

を行います。

一方これを利用する側では、次のようなコードを書くことになります。

import Calc1Parser;

enum MyTerm {
    Mul(a: MyTerm, b: Int);
    Div(a: MyTerm, b: Int);
    Term(a: Int);
}

enum MyExpr {
    Add(a: MyExpr, b: MyTerm);
    Sub(a: MyExpr, b: MyTerm);
    Expr(a: MyTerm);
}

class MySemanticAction {
    public function new() {}
    public function stackOverflow() {}
    public function syntaxError() {}

    public function makeAdd(a: MyExpr, b: MyTerm): MyExpr {
        return Add(a, b);
    }
    public function makeSub(a: MyExpr, b: MyTerm): MyExpr {
        return Sub(a, b);
    }
    public function makeExpr(a: MyTerm): MyExpr {
        return Expr(a);
    }
    public function makeMul(a: MyTerm, b: Int): MyTerm {
        return Mul(a, b);
    }
    public function makeDiv(a: MyTerm, b: Int): MyTerm {
        return Div(a, b);
    }
    public function makeTerm(a: Int): MyTerm {
        return Term(a);
    }
}

class Calc1 {
    static function scanner(s: String) { /* 実装略 */ }

    static function parse(s) {
        var parser = new Calc1Parser.Parser(new MySemanticAction());

        while(true) {
            var a = scanner(s);
            trace(a);
            if (parser.post(a.token, a.value)) {
                break;
            }
            s = a.rest;
        }
        trace(parser.accept());
    }

    public static function main(): Void {
        parse('3+7*8+2');
    }
}

ここで問題があります。一見makeAddなどのセマンティックアクションが型安全に書かれているように見えますが、実際は違います。

Parserがコンストラクタで要求しているのはprivate SemanticAction型ですが、

private typedef Expr = Dynamic;
private typedef Term = Dynamic;
private typedef SemanticAction = {
    function syntaxError(): Void;
    function stackOverflow(): Void;
    function makeAdd(arg0: Expr, arg1: Term): Expr;
    function makeSub(arg0: Expr, arg1: Term): Expr;
    function makeExpr(arg0: Term): Expr;
    function makeTerm(arg0: Int): Term;
    function makeDiv(arg0: Term, arg1: Int): Term;
    function makeMul(arg0: Term, arg1: Int): Term;
}

の定義からわかるように、引数は実は全部Dynamicです。なので、これを構造的部分型としてMySemanticAction

class MySemanticAction {
    public function new() {}
    public function stackOverflow() {}
    public function syntaxError() {}

    public function makeAdd(a: MyExpr, b: MyTerm): MyExpr {
        return Add(a, b);
    }
    public function makeSub(a: MyExpr, b: MyTerm): MyExpr {
        return Sub(a, b);
    }
    public function makeExpr(a: MyTerm): MyExpr {
        return Expr(a);
    }
    public function makeMul(a: MyTerm, b: Int): MyTerm {
        return Mul(a, b);
    }
    public function makeDiv(a: MyTerm, b: Int): MyTerm {
        return Div(a, b);
    }
    public function makeTerm(a: Int): MyTerm {
        return Term(a);
    }
}

を渡しても、パーサはSemanticActionだと思っているので、正しく型チェックしてくれるとは限りません。例えば、

    public function makeAdd(a: MyExpr, b: MyTerm): MyExpr {
        return Add(a, b);
    }

ここを

    public function makeAdd(a: MyExpr, b: Int): MyExpr {
        return Add(a, Term(b));
    }

こう書き換えてもコンパイルエラーにはなりません。もちろん実行結果はめちゃくちゃです。

そもそも、なぜMySemanticActionのmakeAddがSemanticActionのmakeAddの上位互換ではないのにこのコードのコンパイルが通るのか、それも私はよくわかってないのですが。

インターフェイスを継承する場合

これはHaxeに限ったことではないのですが、上の方で述べたように、パーサがinterfaceを出力してMySemanticActionではそれを継承するといった構造も考えられます。ですがその場合、引数の型を先に定義しておく必要があります。ユーザ側で中間型（下のコードのMyTerm、MyExprなど）を定義する際にそれをパーサの出力したインターフェイス型を継承しないといけない、などの不利益も生じます。つまりこんな感じです。

パーサの出力

interface Expr {
}
interface Term {
}
interface SemanticAction {
  makeAdd(Expr, Term);
}

ユーザコード

class MyExpr implements Expr {
}
class MyTerm implements MyTerm {
}
class MySemanticAction implements SemanticAction {
}

ですが、Haxeのユーザコードで中間型を実装するときはまずenumを使うと思われるので、これの採用はナイと思っています。

また、caperの出力の要件として「ユーザがパースツリーを作るとは限らない」「中間型はネイティブ型かもしれない」というものもあるため、この方式だとその要件を満たせません。なので、既存のジェネレータでテンプレートのない静的型付け言語では、結局Objectなどの最も汎用的な型になっています。

といったわけで

この辺りをどうしたらよいか考えてくださる方がいらっしゃると嬉しいです。あまり複雑なことは諦めて、Dynamicで済ますというのも手ではあるかなと思います。興味のない言語だったら即諦めてしまうところですが、Haxeは常用している言語なのでできればなんとかしたいですね。