tutorial 4 -- 電卓 β
構文をいったん木構造(AST)の形に変換するタイプの電卓です。ちょっと難しくなります。
ASTファイル
AST(抽象構文木)を以下のように定義し、calc1_ast.hppとしました。
struct Node {
virtual ~Node(){}
virtual int calc() = 0;
};
struct Expr : public Node {
};
struct Term : public Node {
};
struct Number : public Node {
int number;
Number( int n ) : number( n ) {}
int calc() { return number; }
};
struct AddExpr : public Expr {
Expr* lhs;
Expr* rhs;
AddExpr( Expr* x, Expr* y ) : lhs( x ), rhs( y ) {}
int calc() { return lhs->calc() + rhs->calc(); }
};
struct SubExpr : public Expr {
Expr* lhs;
Expr* rhs;
SubExpr( Expr* x, Expr* y ) : lhs( x ), rhs( y ) {}
int calc() { return lhs->calc() - rhs->calc(); }
};
struct TermExpr : public Expr {
Term* term;
TermExpr( Term* x ) : term( x ) {}
int calc() { return term->calc(); }
};
struct MulTerm : public Term {
Term* lhs;
Term* rhs;
MulTerm( Term* x, Term* y ) : lhs( x ), rhs( y ) {}
int calc() { return lhs->calc() * rhs->calc(); }
};
struct DivTerm : public Term {
Term* lhs;
Term* rhs;
DivTerm( Term* x, Term* y ) : lhs( x ), rhs( y ) {}
int calc() { return lhs->calc() / rhs->calc(); }
};
struct NumberTerm : public Term {
Number* number;
NumberTerm( Number* x ) : number( x ) {}
int calc() { return number->calc(); }
};
文法ファイル
%token Number<Number*> 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)
;
文法ファイルはcalc0とあまり変わりませんが、以下のように各記号の型が変わっています。
Number<Number*> Expr<Expr*> Term<Term*>
※今回、簡単のため、メモリリークについては考えないものとします。
この文法から生成されるパーサは内部で"Number" "Expr" "Term"等の型を必要としますので、パーサをincludeするより先にASTの定義をincludeする必要があります。そこで、以下のような内容のファイルを作成し、"calc1.hpp"として保存します。
#include "cacl1_ast.hpp" #include "cacl1_parser.hpp"
パーサを一箇所からしか使用しないことがわかっているなら、当然そこで両方includeするようにしても構いませんが、calc1_parser.cpgから作成したcalc1_parser.hppよりも先にcalc1_ast.hppをincludeする必要があることは覚えておいてください。さもないと、Exprなどが未定義であるというコンパイルエラーがでてしまいます。
操作ファイル
#include "calc1.hpp"
#include <iostream>
class unexpected_char : public std::exception {};
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( Node*& v )
{
v = NULL;
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 = new Number( 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, Node* y ) { x = static_cast<T*>( y ); }
template < class T >
void upcast( Node*& x, T* y ) { x = y; }
Expr* MakeExpr( Term* x ) { return new TermExpr( x ); }
Expr* MakeAdd( Expr* x, Term* y )
{
std::cerr << "expr " << x << " + " << y << std::endl;
return new AddExpr( x, new TermExpr( y ) ) ;
}
Expr* MakeSub( Expr* x, Term* y )
{
std::cerr << "expr " << x << " - " << y << std::endl;
return new SubExpr( x, new TermExpr( y ) ) ;
}
Term* MakeTerm( Number* x ) { return new NumberTerm( x ); }
Term* MakeMul( Term* x, Number* y )
{
std::cerr << "expr " << x << " * " << y << std::endl;
return new MulTerm( x, new NumberTerm( y ) ) ;
}
Term* MakeDiv( Term* x, Number* y )
{
std::cerr << "expr " << x << " / " << y << std::endl;
return new DivTerm( x, new NumberTerm( y ) ) ;
}
};
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< Node*, SemanticAction > parser( sa );
calc::Token token;
for(;;) {
Node* v;
token = s.get( v );
if( parser.post( token, v ) ) { break; }
}
Node* v;
if( parser.accept( v ) ) {
std::cerr << "accpeted\n";
std::cerr << v->calc() << std::endl;
}
return 0;
}
やや長くなっています。
まず、scannerは、int型でなくNode*型をトークンの値として返すようになっています。具体的には、token_Numberを返すときに値としてnew Number(n)したものを返します。
次にセマンティックアクションについて。今回、値集合全体の要素を現す型としては、Node*を用います。そして文法ファイルの項目で示したように、各文法要素の型はNode*とは異なるので、それにあわせて変換を行う必要があります。
このケースでは、downcastがNode*→Expr*/Term*/Number*の変換に用いられます。Expr/Term/NumberはいずれもNodeの派生クラスなので、templateメンバ関数を定義すればすべて一緒くたに扱うことが可能です。
template < class T >
void downcast( T*& x, Node* y ) { x = static_cast<T*>( y ); }
逆にExpr*/Term*/Number*→Node*の変換を行う場合、Expr/Term/NumberはいずれもNodeの派生クラスなので、これも一緒くたにして以下のように扱うことができます。
template < class T >
void upcast( Node*& x, T* y ) { x = y; }
以上をふまえて、セマンティックアクションはたとえば以下のようになります。
Expr* MakeAdd( Expr* x, Term* y )
{
std::cerr << "expr " << x << " + " << y << std::endl;
return new AddExpr( x, new TermExpr( y ) ) ;
}
特に難しいことはないと思います。yaccなどでASTを作るときによく必要になる、キャストのコードが必要ないことがわかりますね(といっても、パーサはユーザから見えないようにupcast/downcastを駆使してくれているわけですが)。
main関数はほとんど変わりありません。accept結果はASTのルートノードになりますので、そのcalc関数を実行して演算結果を表示しています。