久しぶりにBisonとFlexを使ったのですが、いつの間にC++用機能が搭載されたんですか？ 2008年くらい？ BisonもFlexも両方ともクラスが出力できるようになっていてびっくりしました。Flexの出力がnamespaceでくくれなくて残念ですが、まあ、我慢しましょう。強引にやるなら.cppを#includeでしょうが……。基本的な使い方はFlex Bison C++ Template - sourceforge.jpのソースを見たらよく分かりました。FlexLexer::yylexが引数を取らない仕様なのを回避する方法がキモ(イ)ですね。
それで、BisonをC++で使うならば、当然意味値(semantic value)にstd::stringなんかを使いたくなるわけですが、%unionを使ってしまうとunionのメンバになってしまうのでPOD以外は使えません。上のFlex Bison C++ Templateではstd::string *とポインターにして使っていますが、これでは使いにくくてかないません。
%unionをやめてYYSTYPEを直接指定すれば良いわけですが、複数の型を共存させるためにはいくつか方法が考えられます。
- YYSTYPEをboost::shared_ptr<SemanticValueBase>にし、SemanticValueBaseを継承したclass SVInt, class SVDouble, class SVStringを作る。
- YYSTYPEをboost::variant<int, double, std::string>にする。
前者はコードを書くにせよ使うにせよ面倒なので、やりは後者にしたくなります。ちなみに、Bisonが生成するC++用コードはスタックにdequeを使うので、これらの型をちゃんと持たせられますので安心して下さい。
それでYYSTYPEをboost::variantにしたとして、次の問題は意味動作(semantic action)から意味値を参照する方法です。
たとえばunionを使った以下のような書き方があったとします。
%union {
int int_val;
char *str_val;
}
%token <int_val> INTEGER
%token <str_val> ID
%type <int_val> expr
%type <int_val> prim
%%
expr : prim '+' prim { $$ = $1 + $2; }
prim : INTEGER { $$ = $1;}
| ID { $$ = get_int_variable($1);}
これをvariantにすると……
%code requires {
#include <string>
#include <boost/variant.hpp>
#define YYSTYPE boost::variant<int, std::string>
}
%token INTEGER
%token ID
%type expr
%type prim
%%
expr : prim '+' prim { $$ = boost::get<int>($1) + boost::get<int>($2); }
prim : INTEGER { $$ = boost::get<int>($1);}
| ID { $$ = get_int_variable(boost::get<std::string>($1));}
のようになって、boost::getを多用しなければならなくなります。なんとかしてこれを改善できないものでしょうか。%unionを使っていないので%tokenや%typeの型指定が使えないのが痛い。
あれ、本当に%tokenや%typeの型指定は使えないのでしょうか。Bisonの生成したコードを眺めてみると、%token <int_val>の指定は結局のところ$$や$1のところで yyval.int_val や yysemantic_stack_[(1) - (1)].int_val のように使われるだけのようです。ということは、%token <as_int()>とすれば yyval.as_int() と展開されるのです！
以下が最終的なコードです。意味動作のところがすっきりしました。
%code requires {
#include <string>
#include <boost/variant.hpp>
struct SemanticValue {
boost::variant<int, std::string> var;
//getter
int &as_int() { return get_var_as<int>();}
std::string &as_int() { return get_var_as<std::string>();}
template<typename U>
U &get_var_as()
{
if(U *p = boost::get<U>(&var)){
return *p;
}
else{
var = U(); //use default constructor
return boost::get<U>(var);
}
}
//setter(for lex)
SemanticValue &operator=(int v) { var = v; return *this;}
SemanticValue &operator=(const string_type &v) { var = v; return *this;}
};
#define YYSTYPE SemanticValue
}
%token <as_int()> INTEGER
%token <as_string()> ID
%type <as_int()> expr
%type <as_int()> prim
%%
expr : prim '+' prim { $$ = $1 + $2; }
prim : INTEGER { $$ = $1;}
| ID { $$ = get_int_variable($1);}
まず、boost::variant<int, std::string>を包み込んだSemanticValueクラスを定義し、指定された型の参照を返すメンバ関数as_int、as_stringを用意します。そして、%tokenや%typeのところで<as_int()>や<as_string()>のように指定します。これだけで意味動作のところで$$と書けばyyval.as_int()となり、variantのint部分にアクセスできるというわけです。
get_var_asの中でデフォルトコンストラクタを呼んでいます。この部分は $$ = $1 と書いたときに yyval.as_int() = yysemantic_stack_[(1) - (1)].as_int() のように展開されることになり、as_intがそのままboost::get<int>(var)だけだと、左辺についてvariantがstd::stringだったときにbad_get例外が飛ぶからです。初期化の無駄や右辺の型チェック上の問題がありますが、まあ、今回はこのくらいで許して下さい(直後に代入すると分かっているのに初期化するのは無駄だと言うことと、右辺は必ず期待した型になるはずなので型が違う場合例外を投げる方がより安全だと言うこと)。
意味値としてvariantを使うとメモリ使用量上無駄が生じます。variantは内部に型タグを持っているでしょうから、その分は本来解析状態を使えば省くことができるはずです。ただ、その量はスタックの最大深度に比例し、文法と解析対象に依りますが、多くの用途で問題になる量では無いでしょう。
variantの中にstd::listやstd::vector等のコンテナを入れることもできます。そうするとコピーのコストが高くなるので注意が必要でしょう。意味動作のところでswapやmoveを使うことである程度回避できますが、それでもBisonが生成するyysemantic_stack_.push (yylval)等のところでコピーが発生してしまいます。気になるならshared_ptrで包むくらいでしょうか。そもそもvariantではなくshared_ptr<void>を使うという手もあるのかもしれませんけど。
