tutorial 5 -- Calculator γ
The next sample uses boost::variant for AST.
You can do programming like a functional language
(boost::apply_visitor is similar to the pattern matching like ocaml etc.)
It's very severe. Severe in compilation time and hard to understand compilation error messages...
The AST File
#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 ) {}
};
(The output function is omitted)
If we let it equivalent to calc1, it become like it.
The Grammar File
%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)
;
The types of Number/Term/Expr are not pointer types as below:
Number<int> Term<Term> Expr<Expr>
This time program doesn't leak any memory.
The Handling File
#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 ) );
// symbols
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;
}
// integers
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** )
{
// The scanner
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;
}
At first, as follows, define the almighty type that stores all the semantic values.
boost::variant< int, Term, Expr > Value;
We use this for the return values of scanner or template parameters.
This time, there was only three kinds of semantic items, so we used variant.
If you want to define larger grammar, you may want boost::any
to avoid the upper limit of variant.
(It's different matter from variant used in calc2_ast.hpp. I warned!)
At second, semantic actions.
It's almost trivial, but you have to be a bit careful about downcast and upcast.
You should write them like following code in order to adapt to boost::variant specification.
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; }
The calculator that scans AST will be realized as follows:
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 );
}
};
Great! You can do double dispatches too.
See details at boost::variant documentation.