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/spirit/include/qi.hpp>
30#include <boost/variant/recursive_variant.hpp>
31#include <boost/variant/apply_visitor.hpp>
32#include <boost/fusion/include/adapt_struct.hpp>
33#include <boost/foreach.hpp>
34
35#include <iostream>
36#include <string>
37
38namespace client { namespace ast
39{
40 ///////////////////////////////////////////////////////////////////////////
41 // The AST
42 ///////////////////////////////////////////////////////////////////////////
43 struct nil {};
44 struct signed_;
45 struct program;
46
47 typedef boost::variant<
48 nil
49 , unsigned int
50 , boost::recursive_wrapper<signed_>
51 , boost::recursive_wrapper<program>
52 >
53 operand;
54
55 struct signed_
56 {
57 char sign;
58 operand operand_;
59 };
60
61 struct operation
62 {
63 char operator_;
64 operand operand_;
65 };
66
67 struct program
68 {
69 operand first;
70 std::list<operation> rest;
71 };
72}}
73
74BOOST_FUSION_ADAPT_STRUCT(
75 client::ast::signed_,
76 (char, sign)
77 (client::ast::operand, operand_)
78)
79
80BOOST_FUSION_ADAPT_STRUCT(
81 client::ast::operation,
82 (char, operator_)
83 (client::ast::operand, operand_)
84)
85
86BOOST_FUSION_ADAPT_STRUCT(
87 client::ast::program,
88 (client::ast::operand, first)
89 (std::list<client::ast::operation>, rest)
90)
91
92namespace client { namespace ast
93{
94 ///////////////////////////////////////////////////////////////////////////
95 // The AST Printer
96 ///////////////////////////////////////////////////////////////////////////
97 struct printer
98 {
99 typedef void result_type;
100
101 void operator()(nil) const {}
102 void operator()(unsigned int n) const { std::cout << n; }
103
104 void operator()(operation const& x) const
105 {
106 boost::apply_visitor(visitor: *this, visitable: x.operand_);
107 switch (x.operator_)
108 {
109 case '+': std::cout << " add"; break;
110 case '-': std::cout << " subt"; break;
111 case '*': std::cout << " mult"; break;
112 case '/': std::cout << " div"; break;
113 }
114 }
115
116 void operator()(signed_ const& x) const
117 {
118 boost::apply_visitor(visitor: *this, visitable: x.operand_);
119 switch (x.sign)
120 {
121 case '-': std::cout << " neg"; break;
122 case '+': std::cout << " pos"; break;
123 }
124 }
125
126 void operator()(program const& x) const
127 {
128 boost::apply_visitor(visitor: *this, visitable: x.first);
129 BOOST_FOREACH(operation const& oper, x.rest)
130 {
131 std::cout << ' ';
132 (*this)(oper);
133 }
134 }
135 };
136
137 ///////////////////////////////////////////////////////////////////////////
138 // The AST evaluator
139 ///////////////////////////////////////////////////////////////////////////
140 struct eval
141 {
142 typedef int result_type;
143
144 int operator()(nil) const { BOOST_ASSERT(0); return 0; }
145 int operator()(unsigned int n) const { return n; }
146
147 int operator()(operation const& x, int lhs) const
148 {
149 int rhs = boost::apply_visitor(visitor: *this, visitable: x.operand_);
150 switch (x.operator_)
151 {
152 case '+': return lhs + rhs;
153 case '-': return lhs - rhs;
154 case '*': return lhs * rhs;
155 case '/': return lhs / rhs;
156 }
157 BOOST_ASSERT(0);
158 return 0;
159 }
160
161 int operator()(signed_ const& x) const
162 {
163 int rhs = boost::apply_visitor(visitor: *this, visitable: x.operand_);
164 switch (x.sign)
165 {
166 case '-': return -rhs;
167 case '+': return +rhs;
168 }
169 BOOST_ASSERT(0);
170 return 0;
171 }
172
173 int operator()(program const& x) const
174 {
175 int state = boost::apply_visitor(visitor: *this, visitable: x.first);
176 BOOST_FOREACH(operation const& oper, x.rest)
177 {
178 state = (*this)(oper, state);
179 }
180 return state;
181 }
182 };
183}}
184
185namespace client
186{
187 namespace qi = boost::spirit::qi;
188 namespace ascii = boost::spirit::ascii;
189
190 ///////////////////////////////////////////////////////////////////////////////
191 // The calculator grammar
192 ///////////////////////////////////////////////////////////////////////////////
193 template <typename Iterator>
194 struct calculator : qi::grammar<Iterator, ast::program(), ascii::space_type>
195 {
196 calculator() : calculator::base_type(expression)
197 {
198 qi::uint_type uint_;
199 qi::char_type char_;
200
201 expression =
202 term
203 >> *( (char_('+') >> term)
204 | (char_('-') >> term)
205 )
206 ;
207
208 term =
209 factor
210 >> *( (char_('*') >> factor)
211 | (char_('/') >> factor)
212 )
213 ;
214
215 factor =
216 uint_
217 | '(' >> expression >> ')'
218 | (char_('-') >> factor)
219 | (char_('+') >> factor)
220 ;
221 }
222
223 qi::rule<Iterator, ast::program(), ascii::space_type> expression;
224 qi::rule<Iterator, ast::program(), ascii::space_type> term;
225 qi::rule<Iterator, ast::operand(), ascii::space_type> factor;
226 };
227}
228
229///////////////////////////////////////////////////////////////////////////////
230// Main program
231///////////////////////////////////////////////////////////////////////////////
232int
233main()
234{
235 std::cout << "/////////////////////////////////////////////////////////\n\n";
236 std::cout << "Expression parser...\n\n";
237 std::cout << "/////////////////////////////////////////////////////////\n\n";
238 std::cout << "Type an expression...or [q or Q] to quit\n\n";
239
240 typedef std::string::const_iterator iterator_type;
241 typedef client::calculator<iterator_type> calculator;
242 typedef client::ast::program ast_program;
243 typedef client::ast::printer ast_print;
244 typedef client::ast::eval ast_eval;
245
246 std::string str;
247 while (std::getline(is&: std::cin, str&: str))
248 {
249 if (str.empty() || str[0] == 'q' || str[0] == 'Q')
250 break;
251
252 calculator calc; // Our grammar
253 ast_program program; // Our program (AST)
254 ast_print print; // Prints the program
255 ast_eval eval; // Evaluates the program
256
257 std::string::const_iterator iter = str.begin();
258 std::string::const_iterator end = str.end();
259 boost::spirit::ascii::space_type space;
260 bool r = phrase_parse(first&: iter, last: end, expr: calc, skipper: space, attr&: program);
261
262 if (r && iter == end)
263 {
264 std::cout << "-------------------------\n";
265 std::cout << "Parsing succeeded\n";
266 print(program);
267 std::cout << "\nResult: " << eval(program) << std::endl;
268 std::cout << "-------------------------\n";
269 }
270 else
271 {
272 std::string rest(iter, end);
273 std::cout << "-------------------------\n";
274 std::cout << "Parsing failed\n";
275 std::cout << "stopped at: \" " << rest << "\"\n";
276 std::cout << "-------------------------\n";
277 }
278 }
279
280 std::cout << "Bye... :-) \n\n";
281 return 0;
282}
283
284
285

source code of boost/libs/spirit/example/qi/compiler_tutorial/calc4.cpp