libstx-exparser/ExpressionParser.cc

Go to the documentation of this file.

// $Id: ExpressionParser.cc 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
 */

#include "ExpressionParser.h"

#include <boost/spirit/core.hpp>

#include <boost/spirit/tree/ast.hpp>
#include <boost/spirit/tree/tree_to_xml.hpp>

#include <boost/spirit/utility/lists.hpp>
#include <boost/spirit/utility/distinct.hpp>
#include <boost/spirit/utility/escape_char.hpp>
#include <boost/spirit/utility/grammar_def.hpp> 

#include <iostream>
#include <sstream>
#include <cmath>

// #define STX_DEBUG_PARSER

namespace stx {

namespace Grammar {

using namespace boost::spirit;

enum parser_ids
{
    boolean_const_id = 1,
    integer_const_id,
    long_const_id,
    double_const_id,
    string_const_id,
    constant_id,

    function_call_id,
    function_identifier_id,

    varname_id,

    atom_expr_id,

    unary_expr_id,
    mul_expr_id,
    add_expr_id,

    cast_expr_id,
    cast_spec_id,

    comp_expr_id,
    and_expr_id,
    or_expr_id,

    expr_id,
    exprlist_id,
};

distinct_parser<> keyword_p("a-zA-Z0-9_");

struct ExpressionGrammar : public grammar<ExpressionGrammar>
{
    template <typename ScannerT>
    struct definition : public grammar_def<rule<ScannerT, parser_context<>, parser_tag<expr_id> >,
                                           rule<ScannerT, parser_context<>, parser_tag<exprlist_id> > >
    {
        definition(ExpressionGrammar const& /*self*/)
        {
            // *** Constants

            constant
                = double_const
                | integer_const
                | long_const
                | boolean_const
                | string_const
                ;
            
            boolean_const
                = as_lower_d[keyword_p("true") | keyword_p("false")]
                ;

            integer_const
                = int_p
                ;

            // this is needed because spirit's int_parsers don't work with
            // these long numbers
            long_const
                = token_node_d[ lexeme_d[ !( ch_p('+') | ch_p('-' ) ) >> +( range_p('0','9') ) ] ]
                ;

            double_const
                = strict_real_p
                ;

            string_const
                = lexeme_d[
                    token_node_d[ '"' >> *(c_escape_ch_p - '"') >> '"' ]
                    ]
                ;

            // *** Function call and function identifier

            function_call
                = root_node_d[function_identifier]
                >> discard_node_d[ ch_p('(') ] >> exprlist >> discard_node_d[ ch_p(')') ]
                ;

            function_identifier
                = lexeme_d[ 
                    token_node_d[ alpha_p >> *(alnum_p | ch_p('_')) ]
                    ]
                ;

            // *** Expression names

            varname
                = lexeme_d[ 
                    token_node_d[ alpha_p >> *(alnum_p | ch_p('_')) ]
                    ]
                ;

            // *** Valid Expressions, from small to large

            atom_expr
                = constant
                | inner_node_d[ ch_p('(') >> expr >> ch_p(')') ]
                | function_call
                | varname
                ;

            unary_expr
                = !( root_node_d[ as_lower_d[ch_p('+') | ch_p('-') | ch_p('!') | str_p("not")] ] )
                >> atom_expr
                ;

            cast_spec
                = discard_node_d[ ch_p('(') ]
                >> (
                    keyword_p("bool") |
                    keyword_p("char") | keyword_p("short") | keyword_p("int") | keyword_p("integer") | keyword_p("long") |
                    keyword_p("byte") | keyword_p("word") | keyword_p("dword") | keyword_p("qword") |
                    keyword_p("float") | keyword_p("double") |
                    keyword_p("string")
                    )
                >> discard_node_d[ ch_p(')') ]
                ;

            cast_expr
                = root_node_d[ !cast_spec ] >> unary_expr
                ;

            mul_expr
                = cast_expr
                >> *( root_node_d[ch_p('*') | ch_p('/')] >> cast_expr )
                ;

            add_expr
                = mul_expr
                >> *( root_node_d[ch_p('+') | ch_p('-')] >> mul_expr )
                ;

            comp_expr
                = add_expr
                >> *( root_node_d[( str_p("==") | str_p("!=") |
                                    str_p("<=") | str_p(">=") | str_p("=<") | str_p("=>") |
                                    ch_p('=') | ch_p('<') | ch_p('>') )] >> add_expr )
                ;

            and_expr
                = comp_expr
                >> *( root_node_d[ as_lower_d[str_p("and") | str_p("&&")] ] >> comp_expr )
                ;

            or_expr
                = and_expr
                >> *( root_node_d[ as_lower_d[str_p("or") | str_p("||")] ] >> and_expr )
                ;

            // *** Base Expression and List

            expr
                = or_expr
                ;

            exprlist
                = infix_node_d[ !list_p(expr, ch_p(',')) ]
                ;

            // Special spirit feature to declare multiple grammar entry points
            this->start_parsers(expr, exprlist); 

#ifdef STX_DEBUG_PARSER
            BOOST_SPIRIT_DEBUG_RULE(constant);

            BOOST_SPIRIT_DEBUG_RULE(boolean_const);
            BOOST_SPIRIT_DEBUG_RULE(integer_const);
            BOOST_SPIRIT_DEBUG_RULE(long_const);
            BOOST_SPIRIT_DEBUG_RULE(double_const);
            BOOST_SPIRIT_DEBUG_RULE(string_const);

            BOOST_SPIRIT_DEBUG_RULE(function_call);
            BOOST_SPIRIT_DEBUG_RULE(function_identifier);
            
            BOOST_SPIRIT_DEBUG_RULE(varname);

            BOOST_SPIRIT_DEBUG_RULE(atom_expr);

            BOOST_SPIRIT_DEBUG_RULE(unary_expr);
            BOOST_SPIRIT_DEBUG_RULE(mul_expr);
            BOOST_SPIRIT_DEBUG_RULE(add_expr);

            BOOST_SPIRIT_DEBUG_RULE(cast_spec);
            BOOST_SPIRIT_DEBUG_RULE(cast_expr);

            BOOST_SPIRIT_DEBUG_RULE(comp_expr);
            BOOST_SPIRIT_DEBUG_RULE(and_expr);
            BOOST_SPIRIT_DEBUG_RULE(or_expr);

            BOOST_SPIRIT_DEBUG_RULE(expr);
            BOOST_SPIRIT_DEBUG_RULE(exprlist);
#endif
        }

        rule<ScannerT, parser_context<>, parser_tag<constant_id> >              constant;

        rule<ScannerT, parser_context<>, parser_tag<boolean_const_id> >         boolean_const;
        rule<ScannerT, parser_context<>, parser_tag<integer_const_id> >         integer_const;
        rule<ScannerT, parser_context<>, parser_tag<long_const_id> >            long_const;
        rule<ScannerT, parser_context<>, parser_tag<double_const_id> >          double_const;
        rule<ScannerT, parser_context<>, parser_tag<string_const_id> >          string_const;

        rule<ScannerT, parser_context<>, parser_tag<function_call_id> >         function_call;
        rule<ScannerT, parser_context<>, parser_tag<function_identifier_id> >   function_identifier;

        rule<ScannerT, parser_context<>, parser_tag<varname_id> >               varname;

        rule<ScannerT, parser_context<>, parser_tag<atom_expr_id> >             atom_expr;

        rule<ScannerT, parser_context<>, parser_tag<unary_expr_id> >            unary_expr;
        rule<ScannerT, parser_context<>, parser_tag<mul_expr_id> >              mul_expr;
        rule<ScannerT, parser_context<>, parser_tag<add_expr_id> >              add_expr;

        rule<ScannerT, parser_context<>, parser_tag<cast_spec_id> >             cast_spec;
        rule<ScannerT, parser_context<>, parser_tag<cast_expr_id> >             cast_expr;

        rule<ScannerT, parser_context<>, parser_tag<comp_expr_id> >             comp_expr;
        rule<ScannerT, parser_context<>, parser_tag<and_expr_id> >              and_expr;
        rule<ScannerT, parser_context<>, parser_tag<or_expr_id> >               or_expr;

        rule<ScannerT, parser_context<>, parser_tag<expr_id> >                  expr;
        rule<ScannerT, parser_context<>, parser_tag<exprlist_id> >              exprlist;
    };
};

// *** Classes representing the nodes in the resulting parse tree, these need
// *** not be publicly available via the header file.

class PNConstant : public ParseNode
{
private:
    class AnyScalar     value;

public:
    PNConstant(AnyScalar::attrtype_t type, std::string strvalue)
        : ParseNode(), value(type)
    {
        // check whether to dequote the incoming string.
        if (type == AnyScalar::ATTRTYPE_STRING)
            value.setStringQuoted(strvalue);
        else
            value.setString(strvalue); // not a string, but an integer or double or boolean value
    }

    PNConstant(const AnyScalar &_value)
        : value(_value)
    {
    }

    virtual AnyScalar evaluate(const class SymbolTable &) const
    {
        return value;
    }

    virtual bool evaluate_const(AnyScalar *dest) const
    {
        if (dest) *dest = value;
        return true;
    }

    virtual std::string toString() const
    {
        if (value.getType() == AnyScalar::ATTRTYPE_STRING) {
            return value.getStringQuoted();
        }
        return value.getString();
    }
};

class PNVariable : public ParseNode
{
private:
    std::string         varname;

public:
    PNVariable(std::string _varname)
        : ParseNode(), varname(_varname)
    {
    }

    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
        return st.lookupVariable(varname);
    }

    virtual bool evaluate_const(AnyScalar *) const
    {
        return false;
    }

    virtual std::string toString() const
    {
        return varname;
    }
};

class PNFunction : public ParseNode
{
public:
    typedef std::vector<const class ParseNode*> paramlist_type;

private:
    std::string         funcname;

    paramlist_type      paramlist;

public:
    PNFunction(std::string _funcname, const paramlist_type& _paramlist)
        : ParseNode(), funcname(_funcname), paramlist(_paramlist)
    {
    }

    ~PNFunction()
    {
        for(unsigned int i = 0; i < paramlist.size(); ++i)
            delete paramlist[i];
    }

    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
        std::vector<AnyScalar> paramvalues;

        for(unsigned int i = 0; i < paramlist.size(); ++i)
        {
            paramvalues.push_back( paramlist[i]->evaluate(st) );
        }

        return st.processFunction(funcname, paramvalues);
    }

    virtual bool evaluate_const(AnyScalar *) const
    {
        return false;
    }

    virtual std::string toString() const
    {
        std::string str = funcname + "(";
        for(unsigned int i = 0; i < paramlist.size(); ++i)
        {
            if (i != 0) str += ",";
            str += paramlist[i]->toString();
        }
        return str + ")";
    }
};

class PNUnaryArithmExpr : public ParseNode
{
private:
    const ParseNode     *operand;

    char        op;

public:
    PNUnaryArithmExpr(const ParseNode* _operand, char _op)
        : ParseNode(), operand(_operand), op(_op)
    {
        if (op == 'n' || op == 'N') op = '!';
    }

    virtual ~PNUnaryArithmExpr()
    {
        delete operand;
    }

    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
        AnyScalar dest = operand->evaluate(st);

        if (op == '-') {
            dest = -dest;           
        }
        else if (op == '!')
        {
            // This should not happend, as types are constant in the parse tree
            if (dest.getType() != AnyScalar::ATTRTYPE_BOOL)
                throw(BadSyntaxException("Invalid operand for !. Operand must be of type bool."));

            dest = -dest;
        }
        else {
            assert(op == '+');
        }

        return dest;
    }

    virtual bool evaluate_const(AnyScalar *dest) const
    {
        if (!dest) return false;

        bool b = operand->evaluate_const(dest);

        if (op == '-') {
            *dest = -(*dest);
        }
        else if (op == '!')
        {
            if (dest->getType() != AnyScalar::ATTRTYPE_BOOL)
                throw(BadSyntaxException("Invalid operand for !. Operand must be of type bool."));

            *dest = -(*dest);
        }
        else {
            assert(op == '+');
        }
        
        return b;
    }

    virtual std::string toString() const
    {
        return std::string("(") + op + " " + operand->toString() + ")";
    }
};

class PNBinaryArithmExpr : public ParseNode
{
private:
    const ParseNode     *left;

    const ParseNode     *right;

    char        op;

public:
    PNBinaryArithmExpr(const ParseNode* _left,
                       const ParseNode* _right,
                       char _op)
        : ParseNode(),
          left(_left), right(_right), op(_op)
    { }

    virtual ~PNBinaryArithmExpr()
    {
        delete left;
        delete right;
    }

    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
        AnyScalar vl = left->evaluate(st);
        AnyScalar vr = right->evaluate(st);

        if (op == '+') {
            return (vl + vr);
        }
        else if (op == '-') {
            return (vl - vr);
        }
        else if (op == '*') {
            return (vl * vr);
        }
        else if (op == '/') {
            return (vl / vr);
        }

        assert(0);
        return 0;
    }

    virtual bool evaluate_const(AnyScalar *dest) const
    {
        if (!dest) return false;

        AnyScalar vl(AnyScalar::ATTRTYPE_INVALID), vr(AnyScalar::ATTRTYPE_INVALID);
        
        bool bl = left->evaluate_const(&vl);
        bool br = right->evaluate_const(&vr);

        if (op == '+') {
            *dest = vl + vr;
        }
        else if (op == '-') {
            *dest = vl - vr;
        }
        else if (op == '*') {
            *dest = vl * vr;
        }
        else if (op == '/') {
            *dest = vl / vr;
        }

        return (bl && br);
    }

    virtual std::string toString() const
    {
        return std::string("(") + left->toString() + " " + op + " " + right->toString() + ")";
    }
};

class PNCastExpr : public ParseNode
{
private:
    const ParseNode*    operand;

    AnyScalar::attrtype_t       type;

public:
    PNCastExpr(const ParseNode* _operand, AnyScalar::attrtype_t _type)
        : ParseNode(),
          operand(_operand), type(_type)
    { }

    virtual ~PNCastExpr()
    {
        delete operand;
    }

    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
        AnyScalar val = operand->evaluate(st);
        val.convertType(type);
        return val;
    }

    virtual bool evaluate_const(AnyScalar *dest) const
    {
        if (!dest) return false;

        bool b = operand->evaluate_const(dest);
        dest->convertType(type);
        return b;
    }

    virtual std::string toString() const
    {
        return std::string("((") + AnyScalar::getTypeString(type) + ")" + operand->toString() + ")";
    }
};

class PNBinaryComparisonExpr : public ParseNode
{
private:
    const ParseNode     *left;

    const ParseNode     *right;

    enum { EQUAL, NOTEQUAL, LESS, GREATER, LESSEQUAL, GREATEREQUAL } op;

    std::string         opstr;

public:
    PNBinaryComparisonExpr(const ParseNode* _left,
                           const ParseNode* _right,
                           std::string _op)
        : ParseNode(),
          left(_left), right(_right), opstr(_op)
    {
        if (_op == "==" || _op == "=")
            op = EQUAL;
        else if (_op == "!=")
            op = NOTEQUAL;
        else if (_op == "<")
            op = LESS;
        else if (_op == ">")
            op = GREATER;
        else if (_op == "<=" || _op == "=<")
            op = LESSEQUAL;
        else if (_op == ">=" || _op == "=>")
            op = GREATEREQUAL;
        else
            throw(BadSyntaxException("Program Error: invalid binary comparision operator."));
    }

    virtual ~PNBinaryComparisonExpr()
    {
        delete left;
        delete right;
    }

    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
        AnyScalar vl = left->evaluate(st);
        AnyScalar vr = right->evaluate(st);

        AnyScalar dest(AnyScalar::ATTRTYPE_BOOL);

        switch(op)
        {
        case EQUAL:
            dest = AnyScalar( vl.equal_to(vr) );
            break;

        case NOTEQUAL:
            dest = AnyScalar( vl.not_equal_to(vr) );
            break;

        case LESS:
            dest = AnyScalar( vl.less(vr) );
            break;

        case GREATER:
            dest = AnyScalar( vl." greater-than.">greater(vr) );
            break;

        case LESSEQUAL:
            dest = AnyScalar( vl.less_equal(vr) );
            break;

        case GREATEREQUAL:
            dest = AnyScalar( vl.=" greater-or-equal-than.">greater_equal(vr) );
            break;

        default:
            assert(0);
        }

        return dest;
    }

    virtual bool evaluate_const(AnyScalar *dest) const
    {
        if (!dest) return false;

        AnyScalar vl(AnyScalar::ATTRTYPE_INVALID), vr(AnyScalar::ATTRTYPE_INVALID);
        
        bool bl = left->evaluate_const(&vl);
        bool br = right->evaluate_const(&vr);

        switch(op)
        {
        case EQUAL:
            *dest = AnyScalar( vl.equal_to(vr) );
            break;

        case NOTEQUAL:
            *dest = AnyScalar( vl.not_equal_to(vr) );
            break;

        case LESS:
            *dest = AnyScalar( vl.less(vr) );
            break;

        case GREATER:
            *dest = AnyScalar( vl.greater(vr) );
            break;

        case LESSEQUAL:
            *dest = AnyScalar( vl.less_equal(vr) );
            break;

        case GREATEREQUAL:
            *dest = AnyScalar( vl.greater_equal(vr) );
            break;

        default:
            assert(0);
        }

        return (bl && br);
    }

    virtual std::string toString() const
    {
        return std::string("(") + left->toString() + " " + opstr + " " + right->toString() + ")";
    }
};

class PNBinaryLogicExpr : public ParseNode
{
private:
    ParseNode*          left;

    ParseNode*          right;

    enum { OP_AND, OP_OR } op;

public:
    PNBinaryLogicExpr(ParseNode* _left,
                      ParseNode* _right,
                      std::string _op)
        : ParseNode(),
          left(_left), right(_right)
    {
        if (_op == "and" |