1 /*=============================================================================
2 Copyright (c) 2001-2003 Daniel Nuffer
3 http://spirit.sourceforge.net/
4
5 Use, modification and distribution is subject to the Boost Software
6 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt)
8 =============================================================================*/
9 ///////////////////////////////////////////////////////////////////////////////
10 //
11 // Demonstrates parse trees. This is discussed in the
12 // "Trees" chapter in the Spirit User's Guide.
13 //
14 ///////////////////////////////////////////////////////////////////////////////
15 #define BOOST_SPIRIT_DUMP_PARSETREE_AS_XML
16
17 #include <boost/spirit/include/classic_core.hpp>
18 #include <boost/spirit/include/classic_parse_tree.hpp>
19 #include <boost/assert.hpp>
20
21 #include <iostream>
22 #include <stack>
23 #include <functional>
24 #include <string>
25
26 #ifdef BOOST_SPIRIT_DUMP_PARSETREE_AS_XML
27 #include <boost/spirit/include/classic_tree_to_xml.hpp>
28 #include <map>
29 #endif
30
31 ////////////////////////////////////////////////////////////////////////////
32 // This example shows how to use a parse tree
33 using namespace std;
34 using namespace BOOST_SPIRIT_CLASSIC_NS;
35
36 // Here's some typedefs to simplify things
37 typedef char const* iterator_t;
38 typedef tree_match<iterator_t> parse_tree_match_t;
39 typedef parse_tree_match_t::const_tree_iterator iter_t;
40
41 typedef pt_match_policy<iterator_t> match_policy_t;
42 typedef scanner_policies<iteration_policy, match_policy_t, action_policy> scanner_policy_t;
43 typedef scanner<iterator_t, scanner_policy_t> scanner_t;
44 typedef rule<scanner_t> rule_t;
45
46 // grammar rules
47 rule_t expression, term, factor, integer;
48
49 ////////////////////////////////////////////////////////////////////////////
50 // Here's the function prototypes that we'll use. One function for each
51 // grammar rule.
52 long evaluate(const tree_parse_info<>& info);
53 long eval_expression(iter_t const& i);
54 long eval_term(iter_t const& i);
55 long eval_factor(iter_t const& i);
56 long eval_integer(iter_t const& i);
57
evaluate(const tree_parse_info<> & info)58 long evaluate(const tree_parse_info<>& info)
59 {
60 return eval_expression(info.trees.begin());
61 }
62
63 // i should be pointing to a node created by the expression rule
eval_expression(iter_t const & i)64 long eval_expression(iter_t const& i)
65 {
66 parser_id id = i->value.id();
67 BOOST_ASSERT(id == expression.id()); // check the id
68
69 // first child points to a term, so call eval_term on it
70 iter_t chi = i->children.begin();
71 long lhs = eval_term(chi);
72 for (++chi; chi != i->children.end(); ++chi)
73 {
74 // next node points to the operator. The text of the operator is
75 // stored in value (a vector<char>)
76 char op = *(chi->value.begin());
77 ++chi;
78 long rhs = eval_term(chi);
79 if (op == '+')
80 lhs += rhs;
81 else if (op == '-')
82 lhs -= rhs;
83 else
84 BOOST_ASSERT(0);
85 }
86 return lhs;
87 }
88
eval_term(iter_t const & i)89 long eval_term(iter_t const& i)
90 {
91 parser_id id = i->value.id();
92 BOOST_ASSERT(id == term.id());
93
94 iter_t chi = i->children.begin();
95 long lhs = eval_factor(chi);
96 for (++chi; chi != i->children.end(); ++chi)
97 {
98 char op = *(chi->value.begin());
99 ++chi;
100 long rhs = eval_factor(chi);
101 if (op == '*')
102 lhs *= rhs;
103 else if (op == '/')
104 lhs /= rhs;
105 else
106 BOOST_ASSERT(0);
107 }
108 return lhs;
109 }
110
eval_factor(iter_t const & i)111 long eval_factor(iter_t const& i)
112 {
113 parser_id id = i->value.id();
114 BOOST_ASSERT(id == factor.id());
115
116 iter_t chi = i->children.begin();
117 id = chi->value.id();
118 if (id == integer.id())
119 return eval_integer(chi->children.begin());
120 else if (*(chi->value.begin()) == '(')
121 {
122 ++chi;
123 return eval_expression(chi);
124 }
125 else if (*(chi->value.begin()) == '-')
126 {
127 ++chi;
128 return -eval_factor(chi);
129 }
130 else
131 {
132 BOOST_ASSERT(0);
133 return 0;
134 }
135 }
136
eval_integer(iter_t const & i)137 long eval_integer(iter_t const& i)
138 {
139 // extract integer (not always delimited by '\0')
140 string integer(i->value.begin(), i->value.end());
141
142 return strtol(integer.c_str(), 0, 10);
143 }
144
145 ////////////////////////////////////////////////////////////////////////////
146 int
main()147 main()
148 {
149
150 // Start grammar definition
151 integer = lexeme_d[ token_node_d[ (!ch_p('-') >> +digit_p) ] ];
152 factor = integer
153 | '(' >> expression >> ')'
154 | ('-' >> factor);
155 term = factor >>
156 *( ('*' >> factor)
157 | ('/' >> factor)
158 );
159 expression = term >>
160 *( ('+' >> term)
161 | ('-' >> term)
162 );
163 // End grammar definition
164
165
166 cout << "/////////////////////////////////////////////////////////\n\n";
167 cout << "\t\tThe simplest working calculator...\n\n";
168 cout << "/////////////////////////////////////////////////////////\n\n";
169 cout << "Type an expression...or [q or Q] to quit\n\n";
170
171 string str;
172 while (getline(cin, str))
173 {
174 if (str.empty() || str[0] == 'q' || str[0] == 'Q')
175 break;
176
177 const char* first = str.c_str();
178
179 tree_parse_info<> info = pt_parse(first, expression);
180
181 if (info.full)
182 {
183 #if defined(BOOST_SPIRIT_DUMP_PARSETREE_AS_XML)
184 // dump parse tree as XML
185 std::map<parser_id, std::string> rule_names;
186 rule_names[integer.id()] = "integer";
187 rule_names[factor.id()] = "factor";
188 rule_names[term.id()] = "term";
189 rule_names[expression.id()] = "expression";
190 tree_to_xml(cout, info.trees, first, rule_names);
191 #endif
192
193 // print the result
194 cout << "parsing succeeded\n";
195 cout << "result = " << evaluate(info) << "\n\n";
196 }
197 else
198 {
199 cout << "parsing failed\n";
200 }
201 }
202
203 cout << "Bye... :-) \n\n";
204 return 0;
205 }
206
207
208