1 /*=============================================================================
2 Copyright (c) 2001-2011 Joel de Guzman
3
4 Distributed under the Boost Software License, Version 1.0. (See accompanying
5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 =============================================================================*/
7 ///////////////////////////////////////////////////////////////////////////////
8 //
9 // A Calculator example demonstrating generation of AST. The AST,
10 // once created, is traversed, 1) To print its contents and
11 // 2) To evaluate the result.
12 //
13 // [ JDG April 28, 2008 ] For BoostCon 2008
14 // [ JDG February 18, 2011 ] Pure attributes. No semantic actions.
15 //
16 ///////////////////////////////////////////////////////////////////////////////
17
18 // Spirit v2.5 allows you to suppress automatic generation
19 // of predefined terminals to speed up complation. With
20 // BOOST_SPIRIT_NO_PREDEFINED_TERMINALS defined, you are
21 // responsible in creating instances of the terminals that
22 // you need (e.g. see qi::uint_type uint_ below).
23 #define BOOST_SPIRIT_NO_PREDEFINED_TERMINALS
24
25 #if defined(_MSC_VER)
26 # pragma warning(disable: 4345)
27 #endif
28
29 #include <boost/config/warning_disable.hpp>
30 #include <boost/spirit/include/qi.hpp>
31 #include <boost/variant/recursive_variant.hpp>
32 #include <boost/variant/apply_visitor.hpp>
33 #include <boost/fusion/include/adapt_struct.hpp>
34 #include <boost/foreach.hpp>
35
36 #include <iostream>
37 #include <string>
38
39 namespace client { namespace ast
40 {
41 ///////////////////////////////////////////////////////////////////////////
42 // The AST
43 ///////////////////////////////////////////////////////////////////////////
44 struct nil {};
45 struct signed_;
46 struct program;
47
48 typedef boost::variant<
49 nil
50 , unsigned int
51 , boost::recursive_wrapper<signed_>
52 , boost::recursive_wrapper<program>
53 >
54 operand;
55
56 struct signed_
57 {
58 char sign;
59 operand operand_;
60 };
61
62 struct operation
63 {
64 char operator_;
65 operand operand_;
66 };
67
68 struct program
69 {
70 operand first;
71 std::list<operation> rest;
72 };
73 }}
74
75 BOOST_FUSION_ADAPT_STRUCT(
76 client::ast::signed_,
77 (char, sign)
78 (client::ast::operand, operand_)
79 )
80
81 BOOST_FUSION_ADAPT_STRUCT(
82 client::ast::operation,
83 (char, operator_)
84 (client::ast::operand, operand_)
85 )
86
87 BOOST_FUSION_ADAPT_STRUCT(
88 client::ast::program,
89 (client::ast::operand, first)
90 (std::list<client::ast::operation>, rest)
91 )
92
93 namespace client { namespace ast
94 {
95 ///////////////////////////////////////////////////////////////////////////
96 // The AST Printer
97 ///////////////////////////////////////////////////////////////////////////
98 struct printer
99 {
100 typedef void result_type;
101
operator ()client::ast::printer102 void operator()(nil) const {}
operator ()client::ast::printer103 void operator()(unsigned int n) const { std::cout << n; }
104
operator ()client::ast::printer105 void operator()(operation const& x) const
106 {
107 boost::apply_visitor(*this, x.operand_);
108 switch (x.operator_)
109 {
110 case '+': std::cout << " add"; break;
111 case '-': std::cout << " subt"; break;
112 case '*': std::cout << " mult"; break;
113 case '/': std::cout << " div"; break;
114 }
115 }
116
operator ()client::ast::printer117 void operator()(signed_ const& x) const
118 {
119 boost::apply_visitor(*this, x.operand_);
120 switch (x.sign)
121 {
122 case '-': std::cout << " neg"; break;
123 case '+': std::cout << " pos"; break;
124 }
125 }
126
operator ()client::ast::printer127 void operator()(program const& x) const
128 {
129 boost::apply_visitor(*this, x.first);
130 BOOST_FOREACH(operation const& oper, x.rest)
131 {
132 std::cout << ' ';
133 (*this)(oper);
134 }
135 }
136 };
137
138 ///////////////////////////////////////////////////////////////////////////
139 // The AST evaluator
140 ///////////////////////////////////////////////////////////////////////////
141 struct eval
142 {
143 typedef int result_type;
144
operator ()client::ast::eval145 int operator()(nil) const { BOOST_ASSERT(0); return 0; }
operator ()client::ast::eval146 int operator()(unsigned int n) const { return n; }
147
operator ()client::ast::eval148 int operator()(operation const& x, int lhs) const
149 {
150 int rhs = boost::apply_visitor(*this, x.operand_);
151 switch (x.operator_)
152 {
153 case '+': return lhs + rhs;
154 case '-': return lhs - rhs;
155 case '*': return lhs * rhs;
156 case '/': return lhs / rhs;
157 }
158 BOOST_ASSERT(0);
159 return 0;
160 }
161
operator ()client::ast::eval162 int operator()(signed_ const& x) const
163 {
164 int rhs = boost::apply_visitor(*this, x.operand_);
165 switch (x.sign)
166 {
167 case '-': return -rhs;
168 case '+': return +rhs;
169 }
170 BOOST_ASSERT(0);
171 return 0;
172 }
173
operator ()client::ast::eval174 int operator()(program const& x) const
175 {
176 int state = boost::apply_visitor(*this, x.first);
177 BOOST_FOREACH(operation const& oper, x.rest)
178 {
179 state = (*this)(oper, state);
180 }
181 return state;
182 }
183 };
184 }}
185
186 namespace client
187 {
188 namespace qi = boost::spirit::qi;
189 namespace ascii = boost::spirit::ascii;
190
191 ///////////////////////////////////////////////////////////////////////////////
192 // The calculator grammar
193 ///////////////////////////////////////////////////////////////////////////////
194 template <typename Iterator>
195 struct calculator : qi::grammar<Iterator, ast::program(), ascii::space_type>
196 {
calculatorclient::calculator197 calculator() : calculator::base_type(expression)
198 {
199 qi::uint_type uint_;
200 qi::char_type char_;
201
202 expression =
203 term
204 >> *( (char_('+') >> term)
205 | (char_('-') >> term)
206 )
207 ;
208
209 term =
210 factor
211 >> *( (char_('*') >> factor)
212 | (char_('/') >> factor)
213 )
214 ;
215
216 factor =
217 uint_
218 | '(' >> expression >> ')'
219 | (char_('-') >> factor)
220 | (char_('+') >> factor)
221 ;
222 }
223
224 qi::rule<Iterator, ast::program(), ascii::space_type> expression;
225 qi::rule<Iterator, ast::program(), ascii::space_type> term;
226 qi::rule<Iterator, ast::operand(), ascii::space_type> factor;
227 };
228 }
229
230 ///////////////////////////////////////////////////////////////////////////////
231 // Main program
232 ///////////////////////////////////////////////////////////////////////////////
233 int
main()234 main()
235 {
236 std::cout << "/////////////////////////////////////////////////////////\n\n";
237 std::cout << "Expression parser...\n\n";
238 std::cout << "/////////////////////////////////////////////////////////\n\n";
239 std::cout << "Type an expression...or [q or Q] to quit\n\n";
240
241 typedef std::string::const_iterator iterator_type;
242 typedef client::calculator<iterator_type> calculator;
243 typedef client::ast::program ast_program;
244 typedef client::ast::printer ast_print;
245 typedef client::ast::eval ast_eval;
246
247 std::string str;
248 while (std::getline(std::cin, str))
249 {
250 if (str.empty() || str[0] == 'q' || str[0] == 'Q')
251 break;
252
253 calculator calc; // Our grammar
254 ast_program program; // Our program (AST)
255 ast_print print; // Prints the program
256 ast_eval eval; // Evaluates the program
257
258 std::string::const_iterator iter = str.begin();
259 std::string::const_iterator end = str.end();
260 boost::spirit::ascii::space_type space;
261 bool r = phrase_parse(iter, end, calc, space, program);
262
263 if (r && iter == end)
264 {
265 std::cout << "-------------------------\n";
266 std::cout << "Parsing succeeded\n";
267 print(program);
268 std::cout << "\nResult: " << eval(program) << std::endl;
269 std::cout << "-------------------------\n";
270 }
271 else
272 {
273 std::string rest(iter, end);
274 std::cout << "-------------------------\n";
275 std::cout << "Parsing failed\n";
276 std::cout << "stopped at: \" " << rest << "\"\n";
277 std::cout << "-------------------------\n";
278 }
279 }
280
281 std::cout << "Bye... :-) \n\n";
282 return 0;
283 }
284
285
286