| /*============================================================================= |
| Copyright (c) 2001-2010 Joel de Guzman |
| |
| Distributed under the Boost Software License, Version 1.0. (See accompanying |
| file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| =============================================================================*/ |
| /////////////////////////////////////////////////////////////////////////////// |
| // |
| // A Calculator example demonstrating generation of AST |
| // |
| // [ JDG April 28, 2008 ] |
| // |
| /////////////////////////////////////////////////////////////////////////////// |
| |
| #include <boost/config/warning_disable.hpp> |
| #include <boost/spirit/include/qi.hpp> |
| #include <boost/variant/recursive_variant.hpp> |
| #include <boost/variant/apply_visitor.hpp> |
| #include <boost/spirit/include/phoenix_operator.hpp> |
| #include <boost/spirit/include/phoenix_function.hpp> |
| |
| #include <iostream> |
| #include <vector> |
| #include <string> |
| |
| namespace client |
| { |
| namespace qi = boost::spirit::qi; |
| namespace ascii = boost::spirit::ascii; |
| |
| /////////////////////////////////////////////////////////////////////////// |
| // Our AST |
| /////////////////////////////////////////////////////////////////////////// |
| struct binary_op; |
| struct unary_op; |
| struct nil {}; |
| |
| struct expression_ast |
| { |
| typedef |
| boost::variant< |
| nil // can't happen! |
| , unsigned int |
| , boost::recursive_wrapper<expression_ast> |
| , boost::recursive_wrapper<binary_op> |
| , boost::recursive_wrapper<unary_op> |
| > |
| type; |
| |
| expression_ast() |
| : expr(nil()) {} |
| |
| template <typename Expr> |
| expression_ast(Expr const& expr) |
| : expr(expr) {} |
| |
| expression_ast& operator+=(expression_ast const& rhs); |
| expression_ast& operator-=(expression_ast const& rhs); |
| expression_ast& operator*=(expression_ast const& rhs); |
| expression_ast& operator/=(expression_ast const& rhs); |
| |
| type expr; |
| }; |
| |
| struct binary_op |
| { |
| binary_op( |
| char op |
| , expression_ast const& left |
| , expression_ast const& right) |
| : op(op), left(left), right(right) {} |
| |
| char op; |
| expression_ast left; |
| expression_ast right; |
| }; |
| |
| struct unary_op |
| { |
| unary_op( |
| char op |
| , expression_ast const& subject) |
| : op(op), subject(subject) {} |
| |
| char op; |
| expression_ast subject; |
| }; |
| |
| expression_ast& expression_ast::operator+=(expression_ast const& rhs) |
| { |
| expr = binary_op('+', expr, rhs); |
| return *this; |
| } |
| |
| expression_ast& expression_ast::operator-=(expression_ast const& rhs) |
| { |
| expr = binary_op('-', expr, rhs); |
| return *this; |
| } |
| |
| expression_ast& expression_ast::operator*=(expression_ast const& rhs) |
| { |
| expr = binary_op('*', expr, rhs); |
| return *this; |
| } |
| |
| expression_ast& expression_ast::operator/=(expression_ast const& rhs) |
| { |
| expr = binary_op('/', expr, rhs); |
| return *this; |
| } |
| |
| // We should be using expression_ast::operator-. There's a bug |
| // in phoenix type deduction mechanism that prevents us from |
| // doing so. Phoenix will be switching to BOOST_TYPEOF. In the |
| // meantime, we will use a phoenix::function below: |
| struct negate_expr |
| { |
| template <typename T> |
| struct result { typedef T type; }; |
| |
| expression_ast operator()(expression_ast const& expr) const |
| { |
| return expression_ast(unary_op('-', expr)); |
| } |
| }; |
| |
| boost::phoenix::function<negate_expr> neg; |
| |
| /////////////////////////////////////////////////////////////////////////// |
| // Walk the tree |
| /////////////////////////////////////////////////////////////////////////// |
| struct ast_print |
| { |
| typedef void result_type; |
| |
| void operator()(qi::info::nil) const {} |
| void operator()(int n) const { std::cout << n; } |
| |
| void operator()(expression_ast const& ast) const |
| { |
| boost::apply_visitor(*this, ast.expr); |
| } |
| |
| void operator()(binary_op const& expr) const |
| { |
| std::cout << "op:" << expr.op << "("; |
| boost::apply_visitor(*this, expr.left.expr); |
| std::cout << ", "; |
| boost::apply_visitor(*this, expr.right.expr); |
| std::cout << ')'; |
| } |
| |
| void operator()(unary_op const& expr) const |
| { |
| std::cout << "op:" << expr.op << "("; |
| boost::apply_visitor(*this, expr.subject.expr); |
| std::cout << ')'; |
| } |
| }; |
| |
| /////////////////////////////////////////////////////////////////////////// |
| // Our calculator grammar |
| /////////////////////////////////////////////////////////////////////////// |
| template <typename Iterator> |
| struct calculator : qi::grammar<Iterator, expression_ast(), ascii::space_type> |
| { |
| calculator() : calculator::base_type(expression) |
| { |
| using qi::_val; |
| using qi::_1; |
| using qi::uint_; |
| |
| expression = |
| term [_val = _1] |
| >> *( ('+' >> term [_val += _1]) |
| | ('-' >> term [_val -= _1]) |
| ) |
| ; |
| |
| term = |
| factor [_val = _1] |
| >> *( ('*' >> factor [_val *= _1]) |
| | ('/' >> factor [_val /= _1]) |
| ) |
| ; |
| |
| factor = |
| uint_ [_val = _1] |
| | '(' >> expression [_val = _1] >> ')' |
| | ('-' >> factor [_val = neg(_1)]) |
| | ('+' >> factor [_val = _1]) |
| ; |
| } |
| |
| qi::rule<Iterator, expression_ast(), ascii::space_type> |
| expression, term, factor; |
| }; |
| } |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // Main program |
| /////////////////////////////////////////////////////////////////////////////// |
| int |
| main() |
| { |
| std::cout << "/////////////////////////////////////////////////////////\n\n"; |
| std::cout << "Expression parser...\n\n"; |
| std::cout << "/////////////////////////////////////////////////////////\n\n"; |
| std::cout << "Type an expression...or [q or Q] to quit\n\n"; |
| |
| using boost::spirit::ascii::space; |
| using client::expression_ast; |
| using client::ast_print; |
| |
| typedef std::string::const_iterator iterator_type; |
| typedef client::calculator<iterator_type> calculator; |
| |
| calculator calc; // Our grammar |
| |
| std::string str; |
| while (std::getline(std::cin, str)) |
| { |
| if (str.empty() || str[0] == 'q' || str[0] == 'Q') |
| break; |
| |
| std::string::const_iterator iter = str.begin(); |
| std::string::const_iterator end = str.end(); |
| expression_ast ast; |
| ast_print printer; |
| bool r = phrase_parse(iter, end, calc, space, ast); |
| |
| if (r && iter == end) |
| { |
| std::cout << "-------------------------\n"; |
| std::cout << "Parsing succeeded\n"; |
| printer(ast); |
| std::cout << "\n-------------------------\n"; |
| } |
| else |
| { |
| std::string rest(iter, end); |
| std::cout << "-------------------------\n"; |
| std::cout << "Parsing failed\n"; |
| std::cout << "stopped at: \": " << rest << "\"\n"; |
| std::cout << "-------------------------\n"; |
| } |
| } |
| |
| std::cout << "Bye... :-) \n\n"; |
| return 0; |
| } |
| |
| |