1 /*=============================================================================
2 Copyright (c) 2001-2010 Joel de Guzman
3 Copyright (c) 2001-2010 Hartmut Kaiser
4
5 Distributed under the Boost Software License, Version 1.0. (See accompanying
6 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 =============================================================================*/
8 ///////////////////////////////////////////////////////////////////////////////
9 //
10 // A Calculator example demonstrating generation of AST which gets dumped into
11 // a reverse polish notation afterwards.
12 //
13 // [ JDG April 28, 2008 ]
14 // [ HK April 28, 2008 ]
15 //
16 ///////////////////////////////////////////////////////////////////////////////
17 #include <boost/config/warning_disable.hpp>
18
19 #include <iostream>
20 #include <vector>
21 #include <string>
22
23 #include "calc2_ast.hpp"
24
25 #include <boost/spirit/include/qi.hpp>
26 #include <boost/spirit/include/karma.hpp>
27 #include <boost/fusion/include/adapt_struct.hpp>
28
29 using namespace boost::spirit;
30 using namespace boost::spirit::ascii;
31
32 ///////////////////////////////////////////////////////////////////////////////
33 // Our calculator parser grammar
34 ///////////////////////////////////////////////////////////////////////////////
35 template <typename Iterator>
36 struct calculator
37 : qi::grammar<Iterator, expression_ast(), space_type>
38 {
calculatorcalculator39 calculator() : calculator::base_type(expression)
40 {
41 expression =
42 term [_val = _1]
43 >> *( ('+' >> term [_val += _1])
44 | ('-' >> term [_val -= _1])
45 )
46 ;
47
48 term =
49 factor [_val = _1]
50 >> *( ('*' >> factor [_val *= _1])
51 | ('/' >> factor [_val /= _1])
52 )
53 ;
54
55 factor =
56 uint_ [_val = _1]
57 | '(' >> expression [_val = _1] >> ')'
58 | ('-' >> factor [_val = neg(_1)])
59 | ('+' >> factor [_val = pos(_1)])
60 ;
61 }
62
63 qi::rule<Iterator, expression_ast(), space_type> expression, term, factor;
64 };
65
66 // We need to tell fusion about our binary_op and unary_op structs
67 // to make them a first-class fusion citizen
68 //
69 // Note: we register the members exactly in the same sequence as we need them
70 // in the grammar
71 BOOST_FUSION_ADAPT_STRUCT(
72 binary_op,
73 (expression_ast, left)
74 (expression_ast, right)
75 (char, op)
76 )
77
78 BOOST_FUSION_ADAPT_STRUCT(
79 unary_op,
80 (expression_ast, right)
81 (char, op)
82 )
83
84 ///////////////////////////////////////////////////////////////////////////////
85 // Our AST grammar for the generator, this prints the AST in reverse polish
86 // notation
87 ///////////////////////////////////////////////////////////////////////////////
88 template <typename OuputIterator>
89 struct ast_rpn
90 : karma::grammar<OuputIterator, expression_ast(), space_type>
91 {
ast_rpnast_rpn92 ast_rpn() : ast_rpn::base_type(ast_node)
93 {
94 ast_node %= int_ | binary_node | unary_node;
95 binary_node %= ast_node << ast_node << char_;
96 unary_node %= '(' << ast_node << char_ << ')';
97 }
98
99 karma::rule<OuputIterator, expression_ast(), space_type> ast_node;
100 karma::rule<OuputIterator, binary_op(), space_type> binary_node;
101 karma::rule<OuputIterator, unary_op(), space_type> unary_node;
102 };
103
104 ///////////////////////////////////////////////////////////////////////////////
105 // Main program
106 ///////////////////////////////////////////////////////////////////////////////
107 int
main()108 main()
109 {
110 std::cout << "/////////////////////////////////////////////////////////\n\n";
111 std::cout << "RPN generator for simple expressions...\n\n";
112 std::cout << "/////////////////////////////////////////////////////////\n\n";
113 std::cout << "Type an expression...or [q or Q] to quit\n\n";
114
115 // Our parser grammar definitions
116 typedef std::string::const_iterator iterator_type;
117 typedef calculator<iterator_type> calculator;
118
119 calculator calc;
120
121 // Our generator grammar definitions
122 typedef std::back_insert_iterator<std::string> output_iterator_type;
123 typedef ast_rpn<output_iterator_type> ast_rpn;
124
125 ast_rpn ast_grammar;
126
127 std::string str;
128 while (std::getline(std::cin, str))
129 {
130 if (str.empty() || str[0] == 'q' || str[0] == 'Q')
131 break;
132
133 expression_ast ast; // this will hold the generated AST
134
135 std::string::const_iterator iter = str.begin();
136 std::string::const_iterator end = str.end();
137 bool r = qi::phrase_parse(iter, end, calc, space, ast);
138
139 if (r && iter == end)
140 {
141 std::string generated;
142 output_iterator_type outit(generated);
143 r = karma::generate_delimited(outit, ast_grammar, space, ast);
144
145 if (r)
146 {
147 std::cout << "RPN for '" << str << "': \n" << generated
148 << std::endl;
149 std::cout << "-------------------------\n";
150 }
151 else
152 {
153 std::cout << "-------------------------\n";
154 std::cout << "Generating failed\n";
155 std::cout << "-------------------------\n";
156 }
157 }
158 else
159 {
160 std::string rest(iter, end);
161 std::cout << "-------------------------\n";
162 std::cout << "Parsing failed\n";
163 std::cout << "stopped at: \": " << rest << "\"\n";
164 std::cout << "-------------------------\n";
165 }
166 }
167
168 std::cout << "Bye... :-) \n\n";
169 return 0;
170 }
171
172
173