1 : // $Id: ExpressionParser.h 59 2007-07-17 14:43:23Z tb $
2 :
3 : /*
4 : * STX Expression Parser C++ Framework v0.7
5 : * Copyright (C) 2007 Timo Bingmann
6 : *
7 : * This library is free software; you can redistribute it and/or modify it
8 : * under the terms of the GNU Lesser General Public License as published by the
9 : * Free Software Foundation; either version 2.1 of the License, or (at your
10 : * option) any later version.
11 : *
12 : * This library is distributed in the hope that it will be useful, but WITHOUT
13 : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
15 : * for more details.
16 : *
17 : * You should have received a copy of the GNU Lesser General Public License
18 : * along with this library; if not, write to the Free Software Foundation,
19 : * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 : */
21 :
22 : /** \file ExpressionParser.h
23 : * Definition of a the public interface of the STX Expression Parser. It
24 : * exports the abstract interface to a ParseNode tree root and the parse
25 : * functions themselves.
26 : */
27 :
28 : #ifndef _STX_ExpressionParser_H_
29 : #define _STX_ExpressionParser_H_
30 :
31 : #include <string>
32 : #include <vector>
33 : #include <map>
34 : #include <assert.h>
35 : #include <boost/smart_ptr.hpp>
36 : #include "AnyScalar.h"
37 :
38 : /// STX - Some Template Extensions namespace
39 : namespace stx {
40 :
41 : /** Base class for other exceptions of the expression parser and
42 : * evaluators. \ingroup Exception */
43 : class ExpressionParserException : public std::runtime_error
44 5 : {
45 : public:
46 : /// Construct with a description string.
47 5 : inline ExpressionParserException(const std::string &s) throw()
48 5 : : std::runtime_error(s)
49 5 : { }
50 : };
51 :
52 : /** ConversionException is an exception class thrown by some combinations of
53 : * get and set in AnyScalar. \ingroup Exception */
54 :
55 : class ConversionException : public ExpressionParserException
56 1 : {
57 : public:
58 : /// Constructor of the exception takes the description string s.
59 1 : inline ConversionException(const std::string &s) throw()
60 1 : : ExpressionParserException(s)
61 1 : { }
62 : };
63 :
64 : /** ArithmeticException is an exception class thrown upon some arithmetic
65 : * errors like integer divison by zero. \ingroup Exception */
66 :
67 : class ArithmeticException : public ExpressionParserException
68 0 : {
69 : public:
70 : /// Constructor of the exception takes the description string s.
71 0 : inline ArithmeticException(const std::string &s) throw()
72 0 : : ExpressionParserException(s)
73 0 : { }
74 : };
75 :
76 : /** Exception class thrown when the parser recognizes a syntax error.
77 : * \ingroup Exception */
78 :
79 : class BadSyntaxException : public ExpressionParserException
80 1 : {
81 : public:
82 : /// Construct with a description string.
83 1 : inline BadSyntaxException(const std::string &s) throw()
84 1 : : ExpressionParserException(s)
85 1 : { }
86 : };
87 :
88 : /** Exception class thrown when the symbol table cannot find a variable or
89 : * function. \ingroup Exception */
90 :
91 : class UnknownSymbolException : public ExpressionParserException
92 2 : {
93 : public:
94 : /// Construct with a description string.
95 2 : inline UnknownSymbolException(const std::string &s) throw()
96 2 : : ExpressionParserException(s)
97 2 : { }
98 : };
99 :
100 : /** Exception class thrown when the symbol table cannot correctly execute a
101 : * function. \ingroup Exception */
102 :
103 : class BadFunctionCallException : public ExpressionParserException
104 1 : {
105 : public:
106 : /// Construct with a description string.
107 1 : inline BadFunctionCallException(const std::string &s) throw()
108 1 : : ExpressionParserException(s)
109 1 : { }
110 : };
111 :
112 : /** Abstract class used for evaluation of variables and function placeholders
113 : * within an expression. If you wish some standard mathematic function, then
114 : * derive your SymbolTable class from BasicSymbolTable instead of directly from
115 : * this one. */
116 : class SymbolTable
117 17 : {
118 : public:
119 : /// STL container type used for parameter lists: a vector
120 : typedef std::vector<AnyScalar> paramlist_type;
121 :
122 : /// Required for virtual functions.
123 : virtual ~SymbolTable();
124 :
125 : /// Return the (constant) value of a variable.
126 : virtual AnyScalar lookupVariable(const std::string &varname) const = 0;
127 :
128 : /// Called when a program-defined function needs to be evaluated within an
129 : /// expression.
130 : virtual AnyScalar processFunction(const std::string &funcname,
131 : const paramlist_type ¶mlist) const = 0;
132 : };
133 :
134 : /** Concrete class used for evaluation of variables and function placeholders
135 : * within an expression. This class will always throw an UnknownSymbolException
136 : * for both lookup functions. It can be used as a base class for symbol tables
137 : * without the standard functions included in BasicSymbolTable. */
138 : class EmptySymbolTable : public SymbolTable
139 : {
140 : public:
141 : /// STL container type used for parameter lists: a vector
142 : typedef std::vector<AnyScalar> paramlist_type;
143 :
144 : /// Required for virtual functions.
145 : virtual ~EmptySymbolTable();
146 :
147 : /// Return the (constant) value of a variable. In this dummy implementation
148 : /// no variables are defined, it always throws an UnknownSymbolException.
149 : virtual AnyScalar lookupVariable(const std::string &varname) const;
150 :
151 : /// Called when a program-defined function needs to be evaluated within an
152 : /// expression. In this dummy implementation no functions are defined, it
153 : /// always throws an UnknownSymbolException.
154 : virtual AnyScalar processFunction(const std::string &funcname,
155 : const paramlist_type ¶mlist) const;
156 : };
157 :
158 : /** Class representing variables and functions placeholders within an
159 : * expression. This base class contain two tables of variables and
160 : * functions. Variables may be filled into the STL map by the program. The
161 : * class also contains a set of basic mathematic functions.
162 : */
163 : class BasicSymbolTable : public SymbolTable
164 : {
165 : public:
166 : /// Signature of a function used in the symbol table.
167 : typedef AnyScalar (*functionptr_type)(const paramlist_type& paramlist);
168 :
169 : protected:
170 :
171 : /// Container used to save a map of variable names
172 : typedef std::map<std::string, AnyScalar> variablemap_type;
173 :
174 : /// Extra info about a function: the valid arguments.
175 : struct FunctionInfo
176 : {
177 : /// Number of arguments this function takes: either >= 0 for a fixed
178 : /// number of -1 for no checking.
179 : int arguments;
180 :
181 : /// Function pointer to call.
182 : functionptr_type func;
183 :
184 : /// Initializing Constructor
185 306 : FunctionInfo(int _arguments = 0, functionptr_type _func = NULL)
186 306 : : arguments(_arguments), func(_func)
187 : {
188 306 : }
189 : };
190 :
191 : /// Container used to save a map of function names
192 : typedef std::map<std::string, struct FunctionInfo> functionmap_type;
193 :
194 : private:
195 : /// Variable map which can be filled by the user-application
196 : variablemap_type variablemap;
197 :
198 : /// Function map used to lookup standard or user-added function
199 : functionmap_type functionmap;
200 :
201 : protected:
202 : // *** Lots of Standard Functions
203 :
204 : /// Return the value of PI as a double AnyScalar
205 : static AnyScalar funcPI(const paramlist_type& paramlist);
206 :
207 : /// Return the value of sin(x) as a double AnyScalar
208 : static AnyScalar funcSIN(const paramlist_type& paramlist);
209 :
210 : /// Return the value of cos(x) as a double AnyScalar
211 : static AnyScalar funcCOS(const paramlist_type& paramlist);
212 :
213 : /// Return the value of tan(x) as a double AnyScalar
214 : static AnyScalar funcTAN(const paramlist_type& paramlist);
215 :
216 : /// Return the value of abs(x) or fabs(f)
217 : static AnyScalar funcABS(const paramlist_type& paramlist);
218 :
219 : /// Return the value of exp(x) as a double AnyScalar
220 : static AnyScalar funcEXP(const paramlist_type& paramlist);
221 :
222 : /// Return the value of log(x) as a double AnyScalar
223 : static AnyScalar funcLOGN(const paramlist_type& paramlist);
224 :
225 : /// Return the value of pow(x,y) as a double AnyScalar
226 : static AnyScalar funcPOW(const paramlist_type& paramlist);
227 :
228 : /// Return the value of sqrt(x) as a double AnyScalar
229 : static AnyScalar funcSQRT(const paramlist_type& paramlist);
230 :
231 : public:
232 : /// Fills in the functionmap with the standard functions.
233 : BasicSymbolTable();
234 :
235 : /// Required for virtual functions.
236 : virtual ~BasicSymbolTable();
237 :
238 : /// Return the (constant) value of a variable. In this basic implementation
239 : /// no variables are defined, it always throws an UnknownSymbolException.
240 : virtual AnyScalar lookupVariable(const std::string &varname) const;
241 :
242 : /// Called when a program-defined function needs to be evaluated within an
243 : /// expression.
244 : virtual AnyScalar processFunction(const std::string &funcname,
245 : const paramlist_type ¶mlist) const;
246 :
247 : /// Add or replace a variable to the symbol table
248 : void setVariable(const std::string& varname, const AnyScalar &value);
249 :
250 : /// Add or replace a function to the symbol table
251 : void setFunction(const std::string& funcname, int arguments, functionptr_type funcptr);
252 :
253 : /// Clear variables table
254 : void clearVariables();
255 :
256 : /// Clear function table
257 : void clearFunctions();
258 :
259 : /// Add set of standard mathematic functions
260 : void addStandardFunctions();
261 : };
262 :
263 : /** ParseNode is the abstract node interface of different parse nodes. From
264 : * these parse nodes the the ExpressionParser constructs a tree which can be
265 : * evaluated using different SymbolTable settings.
266 : */
267 : class ParseNode
268 : {
269 : protected:
270 : /// Usual construction
271 222 : inline ParseNode()
272 222 : { }
273 :
274 : /// Disable copy construction
275 : ParseNode(const ParseNode &pn);
276 :
277 : /// And disable assignment
278 : ParseNode& operator=(const ParseNode &pn);
279 :
280 : public:
281 : /// Virtual destructor so derived classes can deallocate their children
282 : /// nodes.
283 222 : virtual ~ParseNode()
284 222 : {
285 222 : }
286 :
287 : /// Function to recursively evaluate the contained parse tree and retrieve
288 : /// the calculated scalar value based on the given symbol table.
289 : virtual AnyScalar evaluate(const class SymbolTable &st = BasicSymbolTable()) const = 0;
290 :
291 : /// (Internal) Function to check if the subtree evaluates to a constant
292 : /// expression. If dest == NULL then do a static check whether the node is
293 : /// always a constant (ignoring subnodes), if dest != NULL try to calculate
294 : /// the constant value and type recursively, thus the return value can be
295 : /// true for a non-constant tree node.
296 : virtual bool evaluate_const(AnyScalar *dest) const = 0;
297 :
298 : /// Return the parsed expression as a string, which can be parsed again.
299 : virtual std::string toString() const = 0;
300 : };
301 :
302 : /** ParseTree contains the root node of a parse tree. It correctly allocates
303 : * and deletes parse node, because they themselves are not copy-constructable
304 : * or assignable. Pimpl class pattern with exposed inner class. */
305 : class ParseTree
306 34 : {
307 : protected:
308 : /// Enclosed smart ptr so that the parse tree is not cloned when ParseTree
309 : /// instances are copied.
310 : boost::shared_ptr<ParseNode> rootnode;
311 :
312 : public:
313 : /// Create NULL parse tree object from the root ParseNode. All functions
314 : /// will assert() or segfault unless the tree is assigned.
315 : ParseTree()
316 : : rootnode(static_cast<ParseNode*>(NULL))
317 : {
318 : }
319 :
320 : /// Create parse tree object from the root ParseNode.
321 34 : ParseTree(ParseNode* pt)
322 34 : : rootnode(pt)
323 : {
324 34 : }
325 :
326 : /// Returns true if this object does not contain a parse tree.
327 : inline bool isEmpty() const
328 : {
329 : return (rootnode.get() == NULL);
330 : }
331 :
332 : /// Function to recursively evaluate the contained parse tree and retrieve
333 : /// the calculated scalar value based on the given symbol table.
334 17 : AnyScalar evaluate(const class SymbolTable &st = BasicSymbolTable()) const
335 : {
336 17 : assert(rootnode.get() != NULL);
337 17 : return rootnode->evaluate(st);
338 : }
339 :
340 : /// Return the parsed expression as a string, which can be parsed again.
341 34 : std::string toString() const
342 : {
343 34 : assert(rootnode.get() != NULL);
344 34 : return rootnode->toString();
345 : }
346 : };
347 :
348 : /// Parse the given input expression into a parse tree. The parse tree is
349 : /// represented by its root node, which can be evaluated.
350 : const ParseTree parseExpression(const std::string &input);
351 :
352 : /// Parse the given input expression into a parse tree. The parse tree is then
353 : /// transformed into a XML tree for better visualisation.
354 : std::string parseExpressionXML(const std::string &input);
355 :
356 : /** ParseTreeList contains the root parse nodes of a list of expressions. It
357 : * correctly allocates and deletes the parse nodes, because they themselves are
358 : * not copy-constructable or assignable. */
359 : class ParseTreeList : public std::vector<ParseTree>
360 0 : {
361 : protected:
362 : /// typedef of our parent class
363 : typedef std::vector<ParseTree> parent_type;
364 :
365 : public:
366 : /// Function to recursively evaluate all the contained parse trees and
367 : /// retrieve each calculated scalar value for the given symbol table.
368 : std::vector<AnyScalar> evaluate(const class SymbolTable &st = BasicSymbolTable()) const;
369 :
370 : /// Return the list of parsed expression as a string, which can be parsed
371 : /// again.
372 : std::string toString() const;
373 : };
374 :
375 : /// Parse the given input as an expression list "expr1, expr2, ..." into a
376 : /// vector of parse trees. Each parse tree is represented by its root node,
377 : /// which can be evaluated.
378 : ParseTreeList parseExpressionList(const std::string &input);
379 :
380 : } // namespace stx
381 :
382 : #endif // _STX_ExpressionParser_H_
|
