]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 from which we generate | |
11 | // a simple byte code representation being interpreted by a similar virtual | |
12 | // machine. | |
13 | // | |
14 | // [ JDG April 28, 2008 ] | |
15 | // [ HK May 05, 2008 ] | |
16 | // | |
17 | /////////////////////////////////////////////////////////////////////////////// | |
7c673cae FG |
18 | |
19 | #include <iostream> | |
20 | #include <vector> | |
21 | #include <string> | |
22 | ||
23 | #include "calc2_ast_vm.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 | { | |
39 | 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 | /////////////////////////////////////////////////////////////////////////////// | |
67 | // The Virtual Machine | |
68 | /////////////////////////////////////////////////////////////////////////////// | |
69 | class vmachine | |
70 | { | |
71 | public: | |
72 | union element { | |
73 | int code; | |
74 | char bytes[sizeof(int)]; | |
75 | }; | |
76 | ||
77 | vmachine(unsigned stackSize = 4096) | |
78 | : stack(stackSize) | |
79 | , stack_ptr(stack.begin()) | |
80 | { | |
81 | } | |
82 | ||
83 | int top() const { return stack_ptr[-1]; }; | |
84 | void execute(std::vector<element> const& code); | |
85 | ||
86 | private: | |
87 | std::vector<int> stack; | |
88 | std::vector<int>::iterator stack_ptr; | |
89 | }; | |
90 | ||
91 | void vmachine::execute(std::vector<element> const& code) | |
92 | { | |
93 | std::vector<element>::const_iterator pc = code.begin(); | |
94 | stack_ptr = stack.begin(); | |
95 | ||
96 | while ((*pc).code && pc != code.end()) | |
97 | { | |
98 | switch ((*pc++).code) | |
99 | { | |
100 | case op_neg: | |
101 | stack_ptr[-1] = -stack_ptr[-1]; | |
102 | break; | |
103 | ||
104 | case op_add: | |
105 | --stack_ptr; | |
106 | stack_ptr[-1] += stack_ptr[0]; | |
107 | break; | |
108 | ||
109 | case op_sub: | |
110 | --stack_ptr; | |
111 | stack_ptr[-1] -= stack_ptr[0]; | |
112 | break; | |
113 | ||
114 | case op_mul: | |
115 | --stack_ptr; | |
116 | stack_ptr[-1] *= stack_ptr[0]; | |
117 | break; | |
118 | ||
119 | case op_div: | |
120 | --stack_ptr; | |
121 | stack_ptr[-1] /= stack_ptr[0]; | |
122 | break; | |
123 | ||
124 | case op_int: | |
125 | *stack_ptr++ = (*pc++).code; | |
126 | break; | |
127 | } | |
128 | } | |
129 | } | |
130 | ||
131 | // We need to tell fusion about our binary_op and unary_op structs | |
132 | // to make them a first-class fusion citizen | |
133 | // | |
134 | // Note: we register the members exactly in the same sequence as we need them | |
135 | // in the grammar | |
136 | BOOST_FUSION_ADAPT_STRUCT( | |
137 | binary_op, | |
138 | (expression_ast, left) | |
139 | (expression_ast, right) | |
140 | (int, op) | |
141 | ) | |
142 | ||
143 | BOOST_FUSION_ADAPT_STRUCT( | |
144 | unary_op, | |
145 | (expression_ast, right) | |
146 | (int, op) | |
147 | ) | |
148 | ||
149 | /////////////////////////////////////////////////////////////////////////////// | |
150 | // Our AST grammar for the generator, this just dumps the AST as a expression | |
151 | /////////////////////////////////////////////////////////////////////////////// | |
152 | template <typename OuputIterator, typename Delimiter> | |
153 | struct generate_byte_code | |
154 | : karma::grammar<OuputIterator, expression_ast(), Delimiter> | |
155 | { | |
156 | generate_byte_code() : generate_byte_code::base_type(ast_node) | |
157 | { | |
158 | ast_node %= int_node | binary_node | unary_node; | |
159 | int_node %= dword(op_int) << dword; | |
160 | binary_node %= ast_node << ast_node << byte_; | |
161 | unary_node %= ast_node << byte_; | |
162 | } | |
163 | ||
164 | karma::rule<OuputIterator, expression_ast(), Delimiter> ast_node; | |
165 | karma::rule<OuputIterator, int(), Delimiter> int_node; | |
166 | karma::rule<OuputIterator, binary_op(), Delimiter> binary_node; | |
167 | karma::rule<OuputIterator, unary_op(), Delimiter> unary_node; | |
168 | }; | |
169 | ||
170 | /////////////////////////////////////////////////////////////////////////////// | |
171 | // helper function helping to deduce the delimiter type | |
172 | template <typename Delimiter> | |
173 | bool generate_vm_code(expression_ast const& ast, | |
174 | std::vector<vmachine::element>& code, Delimiter const& d) | |
175 | { | |
176 | // Our generator grammar definitions | |
177 | typedef char* output_iterator_type; | |
178 | typedef generate_byte_code<output_iterator_type, Delimiter> generate_byte_code; | |
179 | ||
180 | char* outbuffer = (*code.begin()).bytes; | |
181 | generate_byte_code gen_vm; | |
182 | return karma::generate_delimited(outbuffer, gen_vm, d, ast); | |
183 | } | |
184 | ||
185 | /////////////////////////////////////////////////////////////////////////////// | |
186 | // Main program | |
187 | /////////////////////////////////////////////////////////////////////////////// | |
188 | int | |
189 | main() | |
190 | { | |
191 | std::cout << "/////////////////////////////////////////////////////////\n\n"; | |
192 | std::cout << "Compile simple expressions to bytecode...\n\n"; | |
193 | std::cout << "/////////////////////////////////////////////////////////\n\n"; | |
194 | std::cout << "Type an expression...or [q or Q] to quit\n\n"; | |
195 | ||
196 | // Our parser grammar definitions | |
197 | typedef std::string::const_iterator iterator_type; | |
198 | typedef calculator<iterator_type> calculator; | |
199 | ||
200 | calculator calc; | |
201 | ||
202 | std::string str; | |
203 | while (std::getline(std::cin, str)) | |
204 | { | |
205 | if (str.empty() || str[0] == 'q' || str[0] == 'Q') | |
206 | break; | |
207 | ||
208 | expression_ast ast; | |
209 | std::string::const_iterator iter = str.begin(); | |
210 | std::string::const_iterator end = str.end(); | |
211 | bool r = qi::phrase_parse(iter, end, calc, space, ast); | |
212 | ||
213 | if (r && iter == end) | |
214 | { | |
215 | // we assume a vm code size of 4096 is sufficient | |
216 | std::vector<vmachine::element> code (4096); | |
217 | r = generate_vm_code(ast, code, pad(4)); | |
218 | ||
219 | if (r) | |
220 | { | |
221 | vmachine vm; | |
222 | vm.execute(code); | |
223 | std::cout << "\nresult = " << vm.top() << std::endl; | |
224 | std::cout << "-------------------------\n"; | |
225 | } | |
226 | else | |
227 | { | |
228 | std::cout << "-------------------------\n"; | |
229 | std::cout << "Generating failed\n"; | |
230 | std::cout << "-------------------------\n"; | |
231 | } | |
232 | } | |
233 | else | |
234 | { | |
235 | std::string rest(iter, end); | |
236 | std::cout << "-------------------------\n"; | |
237 | std::cout << "Parsing failed\n"; | |
238 | std::cout << "stopped at: \": " << rest << "\"\n"; | |
239 | std::cout << "-------------------------\n"; | |
240 | } | |
241 | } | |
242 | ||
243 | std::cout << "Bye... :-) \n\n"; | |
244 | return 0; | |
245 | } | |
246 | ||
247 |