// $Id: ExpressionParser.h 59 2007-07-17 14:43:23Z tb $
/*
* STX Expression Parser C++ Framework v0.7
* Copyright (C) 2007 Timo Bingmann
*
* This library is free software; you can redistribute it and/or modify it
* under the terms of the GNU Lesser General Public License as published by the
* Free Software Foundation; either version 2.1 of the License, or (at your
* option) any later version.
*
* This library is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
* for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this library; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
/** \file ExpressionParser.h
* Definition of a the public interface of the STX Expression Parser. It
* exports the abstract interface to a ParseNode tree root and the parse
* functions themselves.
*/
#ifndef _STX_ExpressionParser_H_
#define _STX_ExpressionParser_H_
#include <string>
#include <vector>
#include <map>
#include <assert.h>
#include <boost/smart_ptr.hpp>
#include "AnyScalar.h"
/// STX - Some Template Extensions namespace
namespace stx {
/** Base class for other exceptions of the expression parser and
* evaluators. \ingroup Exception */
class ExpressionParserException : public std::runtime_error
{
public:
/// Construct with a description string.
inline ExpressionParserException(const std::string &s) throw()
: std::runtime_error(s)
{ }
};
/** ConversionException is an exception class thrown by some combinations of
* get and set in AnyScalar. \ingroup Exception */
class ConversionException : public ExpressionParserException
{
public:
/// Constructor of the exception takes the description string s.
inline ConversionException(const std::string &s) throw()
: ExpressionParserException(s)
{ }
};
/** ArithmeticException is an exception class thrown upon some arithmetic
* errors like integer divison by zero. \ingroup Exception */
class ArithmeticException : public ExpressionParserException
{
public:
/// Constructor of the exception takes the description string s.
inline ArithmeticException(const std::string &s) throw()
: ExpressionParserException(s)
{ }
};
/** Exception class thrown when the parser recognizes a syntax error.
* \ingroup Exception */
class BadSyntaxException : public ExpressionParserException
{
public:
/// Construct with a description string.
inline BadSyntaxException(const std::string &s) throw()
: ExpressionParserException(s)
{ }
};
/** Exception class thrown when the symbol table cannot find a variable or
* function. \ingroup Exception */
class UnknownSymbolException : public ExpressionParserException
{
public:
/// Construct with a description string.
inline UnknownSymbolException(const std::string &s) throw()
: ExpressionParserException(s)
{ }
};
/** Exception class thrown when the symbol table cannot correctly execute a
* function. \ingroup Exception */
class BadFunctionCallException : public ExpressionParserException
{
public:
/// Construct with a description string.
inline BadFunctionCallException(const std::string &s) throw()
: ExpressionParserException(s)
{ }
};
/** Abstract class used for evaluation of variables and function placeholders
* within an expression. If you wish some standard mathematic function, then
* derive your SymbolTable class from BasicSymbolTable instead of directly from
* this one. */
class SymbolTable
{
public:
/// STL container type used for parameter lists: a vector
typedef std::vector<AnyScalar> paramlist_type;
/// Required for virtual functions.
virtual ~SymbolTable();
/// Return the (constant) value of a variable.
virtual AnyScalar lookupVariable(const std::string &varname) const = 0;
/// Called when a program-defined function needs to be evaluated within an
/// expression.
virtual AnyScalar processFunction(const std::string &funcname,
const paramlist_type ¶mlist) const = 0;
};
/** Concrete class used for evaluation of variables and function placeholders
* within an expression. This class will always throw an UnknownSymbolException
* for both lookup functions. It can be used as a base class for symbol tables
* without the standard functions included in BasicSymbolTable. */
class EmptySymbolTable : public SymbolTable
{
public:
/// STL container type used for parameter lists: a vector
typedef std::vector<AnyScalar> paramlist_type;
/// Required for virtual functions.
virtual ~EmptySymbolTable();
/// Return the (constant) value of a variable. In this dummy implementation
/// no variables are defined, it always throws an UnknownSymbolException.
virtual AnyScalar lookupVariable(const std::string &varname) const;
/// Called when a program-defined function needs to be evaluated within an
/// expression. In this dummy implementation no functions are defined, it
/// always throws an UnknownSymbolException.
virtual AnyScalar processFunction(const std::string &funcname,
const paramlist_type ¶mlist) const;
};
/** Class representing variables and functions placeholders within an
* expression. This base class contain two tables of variables and
* functions. Variables may be filled into the STL map by the program. The
* class also contains a set of basic mathematic functions.
*/
class BasicSymbolTable : public SymbolTable
{
public:
/// Signature of a function used in the symbol table.
typedef AnyScalar (*functionptr_type)(const paramlist_type& paramlist);
protected:
/// Container used to save a map of variable names
typedef std::map<std::string, AnyScalar> variablemap_type;
/// Extra info about a function: the valid arguments.
struct FunctionInfo
{
/// Number of arguments this function takes: either >= 0 for a fixed
/// number of -1 for no checking.
int arguments;
/// Function pointer to call.
functionptr_type func;
/// Initializing Constructor
FunctionInfo(int _arguments = 0, functionptr_type _func = NULL)
: arguments(_arguments), func(_func)
{
}
};
/// Container used to save a map of function names
typedef std::map<std::string, struct FunctionInfo> functionmap_type;
private:
/// Variable map which can be filled by the user-application
variablemap_type variablemap;
/// Function map used to lookup standard or user-added function
functionmap_type functionmap;
protected:
// *** Lots of Standard Functions
/// Return the value of PI as a double AnyScalar
static AnyScalar funcPI(const paramlist_type& paramlist);
/// Return the value of sin(x) as a double AnyScalar
static AnyScalar funcSIN(const paramlist_type& paramlist);
/// Return the value of cos(x) as a double AnyScalar
static AnyScalar funcCOS(const paramlist_type& paramlist);
/// Return the value of tan(x) as a double AnyScalar
static AnyScalar funcTAN(const paramlist_type& paramlist);
/// Return the value of abs(x) or fabs(f)
static AnyScalar funcABS(const paramlist_type& paramlist);
/// Return the value of exp(x) as a double AnyScalar
static AnyScalar funcEXP(const paramlist_type& paramlist);
/// Return the value of log(x) as a double AnyScalar
static AnyScalar funcLOGN(const paramlist_type& paramlist);
/// Return the value of pow(x,y) as a double AnyScalar
static AnyScalar funcPOW(const paramlist_type& paramlist);
/// Return the value of sqrt(x) as a double AnyScalar
static AnyScalar funcSQRT(const paramlist_type& paramlist);
public:
/// Fills in the functionmap with the standard functions.
BasicSymbolTable();
/// Required for virtual functions.
virtual ~BasicSymbolTable();
/// Return the (constant) value of a variable. In this basic implementation
/// no variables are defined, it always throws an UnknownSymbolException.
virtual AnyScalar lookupVariable(const std::string &varname) const;
/// Called when a program-defined function needs to be evaluated within an
/// expression.
virtual AnyScalar processFunction(const std::string &funcname,
const paramlist_type ¶mlist) const;
/// Add or replace a variable to the symbol table
void setVariable(const std::string& varname, const AnyScalar &value);
/// Add or replace a function to the symbol table
void setFunction(const std::string& funcname, int arguments, functionptr_type funcptr);
/// Clear variables table
void clearVariables();
/// Clear function table
void clearFunctions();
/// Add set of standard mathematic functions
void addStandardFunctions();
};
/** ParseNode is the abstract node interface of different parse nodes. From
* these parse nodes the the ExpressionParser constructs a tree which can be
* evaluated using different SymbolTable settings.
*/
class ParseNode
{
protected:
/// Usual construction
inline ParseNode()
{ }
/// Disable copy construction
ParseNode(const ParseNode &pn);
/// And disable assignment
ParseNode& operator=(const ParseNode &pn);
public:
/// Virtual destructor so derived classes can deallocate their children
/// nodes.
virtual ~ParseNode()
{
}
/// Function to recursively evaluate the contained parse tree and retrieve
/// the calculated scalar value based on the given symbol table.
virtual AnyScalar evaluate(const class SymbolTable &st = BasicSymbolTable()) const = 0;
/// (Internal) Function to check if the subtree evaluates to a constant
/// expression. If dest == NULL then do a static check whether the node is
/// always a constant (ignoring subnodes), if dest != NULL try to calculate
/// the constant value and type recursively, thus the return value can be
/// true for a non-constant tree node.
virtual bool evaluate_const(AnyScalar *dest) const = 0;
/// Return the parsed expression as a string, which can be parsed again.
virtual std::string toString() const = 0;
};
/** ParseTree contains the root node of a parse tree. It correctly allocates
* and deletes parse node, because they themselves are not copy-constructable
* or assignable. Pimpl class pattern with exposed inner class. */
class ParseTree
{
protected:
/// Enclosed smart ptr so that the parse tree is not cloned when ParseTree
/// instances are copied.
boost::shared_ptr<ParseNode> rootnode;
public:
/// Create NULL parse tree object from the root ParseNode. All functions
/// will assert() or segfault unless the tree is assigned.
ParseTree()
: rootnode(static_cast<ParseNode*>(NULL))
{
}
/// Create parse tree object from the root ParseNode.
ParseTree(ParseNode* pt)
: rootnode(pt)
{
}
/// Returns true if this object does not contain a parse tree.
inline bool isEmpty() const
{
return (rootnode.get() == NULL);
}
/// Function to recursively evaluate the contained parse tree and retrieve
/// the calculated scalar value based on the given symbol table.
AnyScalar evaluate(const class SymbolTable &st = BasicSymbolTable()) const
{
assert(rootnode.get() != NULL);
return rootnode->evaluate(st);
}
/// Return the parsed expression as a string, which can be parsed again.
std::string toString() const
{
assert(rootnode.get() != NULL);
return rootnode->toString();
}
};
/// Parse the given input expression into a parse tree. The parse tree is
/// represented by its root node, which can be evaluated.
const ParseTree parseExpression(const std::string &input);
/// Parse the given input expression into a parse tree. The parse tree is then
/// transformed into a XML tree for better visualisation.
std::string parseExpressionXML(const std::string &input);
/** ParseTreeList contains the root parse nodes of a list of expressions. It
* correctly allocates and deletes the parse nodes, because they themselves are
* not copy-constructable or assignable. */
class ParseTreeList : public std::vector<ParseTree>
{
protected:
/// typedef of our parent class
typedef std::vector<ParseTree> parent_type;
public:
/// Function to recursively evaluate all the contained parse trees and
/// retrieve each calculated scalar value for the given symbol table.
std::vector<AnyScalar> evaluate(const class SymbolTable &st = BasicSymbolTable()) const;
/// Return the list of parsed expression as a string, which can be parsed
/// again.
std::string toString() const;
};
/// Parse the given input as an expression list "expr1, expr2, ..." into a
/// vector of parse trees. Each parse tree is represented by its root node,
/// which can be evaluated.
ParseTreeList parseExpressionList(const std::string &input);
} // namespace stx
#endif // _STX_ExpressionParser_H_
