tutorial 5 -- 電卓 γ
次のサンプルは、ASTにboost::variantを使う例です。関数型言語っぽいプログラムが組めます。(boost::apply_visitorがocaml等のパターンマッチに似ている)
結構強烈です。コンパイル時間の長さとコンパイルエラーのわかりづらさも強烈ですが……
ASTファイル
#include <boost/variant.hpp>
#include <iostream>
struct Add;
struct Sub;
struct Mul;
struct Div;
template < class OpTag > struct BinOpTerm;
template < class OpTag > struct BinOpExpr;
typedef boost::variant<
int,
boost::recursive_wrapper< BinOpTerm<Mul> >,
boost::recursive_wrapper< BinOpTerm<Div> > >
Term;
typedef boost::variant<
Term,
boost::recursive_wrapper< BinOpExpr<Add> >,
boost::recursive_wrapper< BinOpExpr<Sub> > >
Expr;
template < class OpTag >
struct BinOpTerm {
Term lhs;
Term rhs;
BinOpTerm( const Term& x, const Term& y )
: lhs( x ), rhs( y ) {}
};
template < class OpTag >
struct BinOpExpr {
Expr lhs;
Expr rhs;
BinOpExpr( const Expr& x, const Expr& y )
: lhs( x ), rhs( y ) {}
};
(出力用関数は省略)
calc1と等価のものにしようとすると、大体このようになります。
文法ファイル
%token Number<int> Add Sub Mul Div;
%namespace calc;
%dont_use_stl;
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)
;
これもほとんど代わりませんが、Number/Term/Exprの型は
Number<int> Term<Term> Expr<Expr>
と、どれもポインタ型ではなくなりました。今回のプログラムはメモリリークしません。
操作ファイル
#include "calc2.hpp"
#include <iostream>
class unexpected_char : public std::exception {};
typedef boost::variant< int, Term, Expr > Value;
template < class It >
class scanner {
public:
typedef int char_type;
public:
scanner( It b, It e ) : b_(b), e_(e), c_(b), unget_(EOF) { }
calc::Token get( Value& v )
{
int c;
do {
c = getc();
} while( isspace( c ) );
// 記号類
switch( c ) {
case '+': return calc::token_Add;
case '-': return calc::token_Sub;
case '*': return calc::token_Mul;
case '/': return calc::token_Div;
case EOF: return calc::token_eof;
}
// 整数
if( isdigit( c ) ) {
int n = 0;
while( c != EOF && isdigit( c ) ) {
n *= 10;
n += c - '0';
c = getc();
}
ungetc( c );
v = n;
return calc::token_Number;
}
std::cerr << char(c) << std::endl;
throw unexpected_char();
}
private:
char_type getc()
{
int c;
if( unget_ != EOF ) {
c = unget_;
unget_ = EOF;
} else if( c_ == e_ ) {
c = EOF;
} else {
c = *c_++;
}
return c;
}
void ungetc( char_type c )
{
if( c != EOF ) {
unget_ = c;
}
}
private:
It b_;
It e_;
It c_;
char_type unget_;
};
struct SemanticAction {
void syntax_error(){}
void stack_overflow(){}
template < class T >
void downcast( T& x, Value y ) { x = boost::get<T>( y ); }
template < class T >
void upcast( Value& x, const T& y ) { x = y; }
Expr MakeExpr( const Term& x ) { return Expr( x ); }
Expr MakeAdd( const Expr& x, const Term& y )
{
std::cerr << "expr " << x << " + " << y << std::endl;
return BinOpExpr<Add>( x, y );
}
Expr MakeSub( const Expr& x, const Term& y )
{
std::cerr << "expr " << x << " - " << y << std::endl;
return BinOpExpr<Sub>( x, y );
}
Term MakeTerm( int x ) { return Term( x ); }
Term MakeMul( const Term& x, int y )
{
std::cerr << "expr " << x << " * " << y << std::endl;
return BinOpTerm<Mul>( x, y );
}
Term MakeDiv( const Term& x, int y )
{
std::cerr << "expr " << x << " / " << y << std::endl;
return BinOpTerm<Div>( x, y );
}
};
struct calculator : public boost::static_visitor<int> {
int operator()( int n ) const { return n; }
int operator()( const Term& x ) const
{
return boost::apply_visitor( calculator(), x );
}
int operator()( const BinOpTerm<Mul>& x ) const
{
return boost::apply_visitor( calculator(), x.lhs ) *
boost::apply_visitor( calculator(), x.rhs );
}
int operator()( const BinOpTerm<Div>& x ) const
{
return boost::apply_visitor( calculator(), x.lhs ) /
boost::apply_visitor( calculator(), x.rhs );
}
int operator()( const Expr& x ) const
{
return boost::apply_visitor( calculator(), x );
}
int operator()( const BinOpExpr<Add>& x ) const
{
return boost::apply_visitor( calculator(), x.lhs ) +
boost::apply_visitor( calculator(), x.rhs );
}
int operator()( const BinOpExpr<Sub>& x ) const
{
return boost::apply_visitor( calculator(), x.lhs ) -
boost::apply_visitor( calculator(), x.rhs );
}
};
int main( int, char** )
{
// スキャナ
typedef std::istreambuf_iterator<char> is_iterator;
is_iterator b( std::cin );
is_iterator e;
scanner< is_iterator > s( b, e );
SemanticAction sa;
calc::Parser< Value, SemanticAction > parser( sa );
calc::Token token;
for(;;) {
Value v;
token = scanner.get( v );
if( parser.post( token, v ) ) { break; }
}
Value v;
if( parser.accept( v ) ) {
std::cerr << "accpeted\n";
std::cerr << boost::apply_visitor( calculator(), v )
<< std::endl;
}
return 0;
}
まず、以下のように、すべての値を格納できる型を定義します。
boost::variant< int, Term, Expr > Value;
これをスキャナの戻り値やパーサのテンプレートパラメータとして用います。今回は文法要素のとりうる値が3種類しかないのでvariantを使っていますが、より大きな文法ではvariantの上限にひっかかる可能性があるので、boost::anyを使うことになるかもしれません。
(calc2_ast.hppで使っているvariantとはまったく別の話なので、注意してください。)
次にセマンティックアクションです。おおむね自明だと思いますが、downcast・upcastは少し注意が必要です。boost::variantの仕様にあわせて以下のようにする必要があります。
template < class T >
void downcast( T& x, Value y ) { x = boost::get<T>( y ); }
template < class T >
void upcast( Value& x, const T& y ) { x = y; }
パーサとは無関係ですが、ASTを走査する計算機は以下のように作ります。
struct calculator : public boost::static_visitor<int> {
int operator()( int n ) const { return n; }
int operator()( const Term& x ) const
{
return boost::apply_visitor( calculator(), x );
}
int operator()( const BinOpTerm<Mul>& x ) const
{
return boost::apply_visitor( calculator(), x.lhs ) *
boost::apply_visitor( calculator(), x.rhs );
}
int operator()( const BinOpTerm<Div>& x ) const
{
return boost::apply_visitor( calculator(), x.lhs ) /
boost::apply_visitor( calculator(), x.rhs );
}
int operator()( const Expr& x ) const
{
return boost::apply_visitor( calculator(), x );
}
int operator()( const BinOpExpr<Add>& x ) const
{
return boost::apply_visitor( calculator(), x.lhs ) +
boost::apply_visitor( calculator(), x.rhs );
}
int operator()( const BinOpExpr<Sub>& x ) const
{
return boost::apply_visitor( calculator(), x.lhs ) -
boost::apply_visitor( calculator(), x.rhs );
}
};
ダブルディスパッチもできるようで、ocaml等のmatchほどではないですが、なかなかすごいことになってます。
詳しくはboost::variantのドキュメントをご覧ください。