C++でプログラミング言語の構文木を表現する方法はそれこそ星の数ほどあると思われる。その中で自分の用途ではどのようなものが適しているのかしばしば考えることがある。
例えば単純な式を表す構文を考えよう。
<expr> ::= <add_expr>
<add_expr> ::= <mul_expr>
| <add_expr> "+" <mul_expr>
| <add_expr> "-" <mul_expr>
<mul_expr> ::= <primary_expr>
| <mul_expr> "*" <primary_expr>
| <mul_expr> "/" <primary_expr>
<primary_expr> ::= "(" <expr> ")"
| <integer_literal>
| <float_literal>
登場するのは+-*/の二項演算子、整数リテラル、浮動小数点数リテラルといった要素だ。これらの要素が抽象構文木のノードとなる。それぞれプログラム上ではBinOp、IntLit、FloatLitと書くことにする。
継承で表現する
C++で一番素直な方法と言ったら、やはり継承を使うことだと思う。
struct Location { int line, column; Location(int line, int column) : line(line), column(column){} }; struct Expr { Location loc; Expr(const Location &loc) : loc(loc){} virtual ~Expr(){} }; typedef boost::shared_ptr<Expr> ExprPtr; struct BinOp : Expr { enum OpType { OP_ADD, OP_SUB, OP_MUL, OP_DIV}; OpType op; ExprPtr lhs; ExprPtr rhs; BinOp(OpType op, ExprPtr lhs, ExprPtr rhs, const Location &loc) : Expr(loc), op(op), lhs(lhs), rhs(rhs) {} }; struct IntLit : Expr { int value; IntLit(int value, const Location &loc) : Expr(loc), value(value) {} }; struct FloatLit : Expr { double value; FloatLit(double value, const Location &loc) : Expr(loc), value(value) {} };
コードに対する補足説明:
- public:とかprivate:とか書くのが面倒なので、すべてstructにしてある。
- Locationはいきなり出てきたが、ソースコード上の位置を記憶しておくためのもの。こういったものがあるかどうかも設計に微妙に影響してくる。
- 各ノードはshared_ptrで取り回すことにした。解放が楽なので。循環参照の危険も今回はないので。
上のコードは式の基底クラスであるExprと、その派生クラスであるBinOp、IntLit、FloatLitを定義している。
素直なC++のコードだが、次の点が気になる。
- const Location &locやExpr(loc)があちこちに出現する。Exprにメンバを追加するたびにこれらを修正しなければならない。
- ノードを巡回する方法が未定。
一つ目の問題はコードの重複を気にするものだが、あまり良い方法は見当たらないのでひとまず置いておく。C++で継承をするとよくこの問題にぶつかる。マクロを使ったり、Exprを直接引数にとったり、包み込む別のクラスを作ってlocをそちらへ移動したり、初期化リストで初期化するのを諦めたり、独自のプリプロセスを行ったり、いくつか手は考えられるのだが、それぞれ良い面と悪い面がある。
二つ目の問題は実際に構文木を構築した後、どのように使うのかということだ。プログラムで構文木の各ノードを一つ一つ見て処理をしていく場合に、どうやって各ノードの種類を判別し、適切な処理を起動するのか。
dynamic_castによる訪問
例えば各ノードを訪問してテキスト出力するようなプログラムは次のようになる。
void print(const ExprPtr &expr) { if(const BinOp *binop = dynamic_cast<const BinOp *>(expr.get())){ std::cout << "BinOp(" << binop->op << 'n'; print(binop->lhs); print(binop->rhs); std::cout << ")n"; } else if(const IntLit *intlit = dynamic_cast<const IntLit *>(expr.get())){ std::cout << "IntLit(" << intlit->value << ")n"; } else if(const FloatLit *floatlit = dynamic_cast<const FloatLit *>(expr.get())){ std::cout << "FloatLit(" << floatlit->value << ")n"; } else{ throw std::runtime_error("Unknown Expr"); } } template<typename T> ExprPtr new_sp(const T &v) { return ExprPtr(new T(v));} int main() { // (123 + 234) * 1.25 ExprPtr expr = new_sp(BinOp( BinOp::OP_MUL, new_sp(BinOp( BinOp::OP_ADD, new_sp(IntLit(123, Location(1,2))), new_sp(IntLit(234, Location(1,8))), Location(1,6))), new_sp(FloatLit(1.25, Location(1,15))), Location(1,13))); print(expr); }
この方法ではdynamic_castを使用して基底クラスから派生クラスの種類を求めている。様々あるやり方の中では素直な方だし、見た目的にもシンプルで、決して悪い方法とは言えないだろう。ただ、問題があることも確かである。上から順にif文でテストしていくので線形探索相当になる。新しい派生クラスを追加したときにif文を追加し忘れるという問題もある。ディスパッチ処理(dynamic_castによる判別)と呼ばれる処理(テキスト出力)が一緒くたになっているのも気になるが、その気になればテンプレートを使って分離できるのでそれはさほど問題ではない。
visitorパターンによる訪問
この手の問題への解決方法にはVisitorパターンというものがよく知られている。どんな感じになるのかはWikipediaにC++の例が載っているので、見れば分かると思う。
C++で実装する典型的なVisitorパターンにはいくつか欠点があるように思う。
- 侵入的
- 各派生クラスにacceptを仕込む工夫が必要
- 一つの派生クラスに関する定義・宣言が複数の場所に散乱しがち(各accept関数の中身を書くにはVisitorインタフェースの完全な定義が必要だが、Visitorインタフェースを定義するには各派生クラスの宣言が必要。なので、各派生クラス毎に前方宣言を書くか、accept関数の定義をクラスの定義から分離するかしないといけない、と思う)
- accept関数の戻り値を自由にできない
- accept関数の引数型を自由にできない(constにするかしないか、参照で受けるかポインターで受けるか、shared_ptrで受けるか等)
種類を取得するメンバ関数を追加する方法
派生クラスの判別をどのように行うか。派生クラス自身に尋ねれば良い。この方法によって、典型的なVisitorパターンのいくつかの欠点は解決するが、また別の欠点が現れてくる。
struct Expr { //略 virtual int get_tag() const = 0; }; struct BinOp : Expr { //略 virtual int get_tag() const { return 0;} }; struct IntLit : Expr { //略 virtual int get_tag() const { return 1;} }; struct FloatLit : Expr { //略 virtual int get_tag() const { return 2;} };
訪問は次のように行う。
template<typename Result, typename Func> Result visit(Func f, const ExprPtr &expr) { switch(expr->get_tag()){ case 0: return f(boost::static_pointer_cast<BinOp>(expr)); case 1: return f(boost::static_pointer_cast<IntLit>(expr)); case 2: return f(boost::static_pointer_cast<FloatLit>(expr)); default: throw std::runtime_error("Unknown Expr"); } } struct Printer { void operator()(const ExprPtr &expr) const { visit<void>(*this, expr); } void operator()(const boost::shared_ptr<BinOp> &binop) const { std::cout << "BinOp" << std::endl; (*this)(binop->lhs); //略 } void operator()(const boost::shared_ptr<IntLit> &intlit) const { std::cout << "IntLit " << intlit->value << std::endl; } void operator()(const boost::shared_ptr<FloatLit> &floatlit) const { std::cout << "FloatLit " << floatlit->value << std::endl; } }; Printer()(expr);
すべての派生クラスにget_tag関数を仕込む手間が生じるという点で少しだけ侵入的であるが、ディスパッチ処理自体は継承ツリーの中に侵入していないので、いくらか柔軟性があると思う。
最大の欠点は0、1、2というget_tagが返す値(派生クラスの識別子)を正しく維持しなければならない点だろう。新しい派生クラスが追加されることを考えると、ある程度自動的に識別子を設定して欲しい。
少し考えただけでも次のような方法が思い浮かぶ。
- typeidを使う方法
- プリプロセッサでナンバリングする方法
- 型リストを使う方法
型リストを使って派生クラスの識別子を設定する
次のような型リストを作っておけば、
typedef boost::mpl::list< BinOp, IntLit, FloatLit > Types;
次のようなコードで型がリストの中で何番目かをコンパイル時定数で得ることが出来る。
boost::mpl::index_of<Types, IntLit>::type::value //== 1になる。
つまり、例えばIntLit::get_tagは次のように実装できることになる。
struct IntLit : Expr { //略 int get_tag() const { return boost::mpl::index_of<Types, IntLit>::type::value;} //Typesの中で何番目かを返す。 };
もちろんこんなのを派生クラス毎にいちいち書いていられない。
マクロを使って
struct IntLit : Expr { //略 GET_TAG_IMPL(IntLit); };
のように書くようにする手もあるが、少し見苦しい。
struct IntLit : DerivedImpl<IntLit, Expr> { //略 };
くらいにしたいところなので、
template<typename Derived, typename Base> struct DerivedImpl : Base { // コンストラクタ DerivedImpl() : Base(){} template<typename A0> DerivedImpl(const A0 &a0) : Base(a0){} template<typename A0, typename A1> DerivedImpl(const A0 &a0, const A1 &a1) : Base(a0, a1){} // get_tagの実装 int get_tag() const { return boost::mpl::index_of<typename Base::DerivedTypes::Types, Derived>::type::value;} };
のようなget_tagを実装してくれるクラスを用意することにした。
これが動くには基底クラスにDerivedTypes::Typesという名前で派生クラスの型リストが無ければならない。
struct Expr { struct DerivedTypes; //略 }; //各派生クラスの定義。 struct Expr::DerivedTypes { typedef boost::mpl::list< BinOp, IntLit, FloatLit > Types; };
Exprに直接型リストを書かないのは、前方宣言をできるだけしないでいいようにするためである。
型リストを使った場合のディスパッチ
型リストからswitch～caseを生成する。
template<typename Result, typename Func, typename Base> Result visit(Func f, Base &a) { typedef typename Base::DerivedTypes::Types Types; switch(a.get_tag()) { case 0: return f((typename boost::mpl::at_c<Types, 0>::type &)a); case 1: return f((typename boost::mpl::at_c<Types, 1>::type &)a); case 2: return f((typename boost::mpl::at_c<Types, 2>::type &)a); //case 3: return f((typename boost::mpl::at_c<Types, 3>::type &)a); //case 4: return f((typename boost::mpl::at_c<Types, 4>::type &)a); } }
型リストの長さを越えてat_cするとコンパイルが通らない。なので、インデックスが型リストのサイズを超えているかどうかでコードを切り替える必要がある。面倒なので説明は省略。
boost::variantのapply_visitorも内部でこのようなコードを使用している。
ライブラリ化
そんなこんなでライブラリとしてまとめたのが以下。
これの良いところは新しく作った派生クラスを型リストに追加し忘れても、ちゃんとエラーになってくれるところ。get_tagがコンパイルできないのでエラーになる。
boost::variantを使った構文木の表現
Recursive variant types - Advanced Topics - Boost.Variantチュートリアルに興味深い例が載っている。boost::variantを使って簡単な計算機を作る例だ。
これをまねて、今回の構文木に適用してみると、
struct Location { int line, column; Location(int line, int column) : line(line), column(column){} }; struct BinOp; struct IntLit; struct FloatLit; typedef boost::variant< boost::recursive_wrapper<BinOp>, IntLit, FloatLit > ExprBody; struct IntLit { int value; IntLit(int value) : value(value) {} }; struct FloatLit { double value; FloatLit(double value) : value(value) {} }; struct Expr { Location loc; ExprBody body; template<typename Body> Expr(const Body &body, const Location &loc) : loc(loc), body(body){} }; struct BinOp { enum OpType { OP_ADD, OP_SUB, OP_MUL, OP_DIV}; OpType op; Expr lhs; Expr rhs; BinOp(OpType op, const Expr &lhs, const Expr &rhs) : op(op), lhs(lhs), rhs(rhs) {} };
継承を使っていないのでコンストラクタがすっきりする。
しかし、派生クラスの前方参照をずらずら書かなければならなかったり、クラスの定義順に気を使わなければならなかったり、それを回避しようといろいろやっていると、結局ポインターで持った方が良いじゃん！ということになりかねなかったりする。
それと、ノードを作るときにExpr(IntLit(123), Location(1,1))と書かなければならないし、apply_visitorで個別の型を受け取れたとしてもLocationを別途受け取らなければならなかったりして意外と面倒。