/*

File: parse_arith.cpp
Author: David Bergman

This file describes a simple arithmetic language
using Boost.Spirit.

It does so by creating an AST and then implementing
an evaluating visitor for such nodes. Not really a
visitor, since it handles the traversal itself, but
you get the point...

*/

#include <string>
#include <iostream>
#include <map>
#include <boost/lexical_cast.hpp>
#include <boost/function.hpp>
#include <boost/spirit/core.hpp>
#include <boost/spirit/tree/ast.hpp>

using namespace std;
using namespace boost::spirit;
using namespace boost;

typedef tree_match<const char*> TreeMatch;
typedef TreeMatch::tree_iterator TreeIter;

// We use Abstract Syntax Trees

struct expression : public grammar<expression>
{
  // Need explicit identifiers to switch properly
  // when evaluating the AST
  static const int factorID = 1;
  static const int termID = 2;
  static const int expID = 3;

  // Meta function from scanner type to a proper
  // rule type
  template<typename ScannerT>
  struct definition
  {
    rule<ScannerT, parser_context<>,
	 parser_tag<expID> > exp_p;
    rule<ScannerT, parser_context<>, 
	 parser_tag<factorID> > factor_p;
    rule<ScannerT, parser_context<>, 
	 parser_tag<termID> > term_p;
    definition(const expression& self) {
      factor_p = 
	leaf_node_d[int_p] | 
	inner_node_d['(' >> exp_p >> ')'];
      term_p =
	factor_p >> *(root_node_d[ch_p('*')] >>
		      factor_p
		      |
		      root_node_d[ch_p('/')] >> 
		      factor_p);
      exp_p = term_p >>
	*(root_node_d[ch_p('+')] >> term_p |
	  root_node_d[ch_p('-')] >> term_p);
      BOOST_SPIRIT_DEBUG_RULE(factor_p);
      BOOST_SPIRIT_DEBUG_RULE(term_p);
      BOOST_SPIRIT_DEBUG_RULE(exp_p);
    }
    
    const rule<ScannerT, parser_context<>,
	       parser_tag<expID> >&
    start()
      const {
      return exp_p;
    }
  };
};

// Map operators to operations

static map<char, function<int (int, int)> > op;

// The evaluation function for the ASTs

static int eval_expression(const TreeIter& i);

int evaluate(tree_parse_info<> match)
{
  return eval_expression(match.trees.begin());
}

int eval_expression(const TreeIter& i)
{
  return 
    (i->value.id() == expression::factorID) ?
    // Simple numeric literal
    lexical_cast<int>(string(i->value.begin(),
			     i->value.end())) :
    // A dyadic operation
    op[*i->value.begin()]
    (eval_expression(i->children.begin()),
     eval_expression(i->children.begin() + 1));
}

int main(int argc, char* argv[])
{
  // Init the operations

  op['*'] = multiplies<int>();
  op['/'] = divides<int>();
  op['+'] = plus<int>();
  op['-'] = minus<int>();

  const string input(argv[1]);
  expression my_exp;
  tree_parse_info<const char*> tree =
    ast_parse(input.c_str(), my_exp);
  if (tree.full) {
    cout << "result is " << evaluate(tree)
	 << endl;
  }
}