/* Copyright (C) 2014 InfiniDB, Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; version 2 of the License. This program 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 General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ /*********************************************************************** * $Id: exp_templates.h 9210 2013-01-21 14:10:42Z rdempsey $ * * ***********************************************************************/ /** @file */ #pragma once #include #include #include #include #include #include #include //#include namespace expression { enum precedence { none, lower, equal, higher }; struct not_an_acceptor_tag { }; struct acceptor_tag { }; struct accumulating_acceptor_tag { }; template struct acceptor_traits { typedef typename Acceptor::acceptor_category acceptor_category; typedef typename Acceptor::input_symbol_type input_symbol_type; typedef typename Acceptor::result_type result_type; }; // Constants indicating possible operator placements. An incoming operator // may be ambiguous so its position will be the bitwise or of several of // these positions. const int prefix = 0x01; const int postfix = 0x02; const int infix = 0x04; const int open = 0x08; const int close = 0x10; const int function_open = 0x20; const int function_close = close; enum associativity { non_associative, left_associative, right_associative }; struct default_expression_parser_error_policy { template void invalid_operand_position(Operand) { std::cerr << "Invalid operand position\n"; } template void invalid_operator_position(Operator) { std::cerr << "Invalid operator position\n"; } template void requires_precedence_relation(Operator, Operator) { std::cerr << "Requires precedence relation\n"; } template void requires_associativity_relation(Operator, Operator) { std::cerr << "Requires associativity relation\n"; } template void ambiguity(Operator, Operator) { std::cerr << "Unresolvable ambiguity\n"; } template void unbalanced_confix(Operator) { std::cerr << "Unbalanced confix operator\n"; } template void missing_operand(Operator) { std::cerr << "Missing operand\n"; } }; #define EXP_TEMPLATE \ template #define EXP_ACCEPTOR expression_acceptor namespace detail { enum action { shift, reduce, prec, prec_assoc, invalid }; // Current larser state enum state { accepting, rejected, pre_operand, post_operand, lookahead }; // The operator placements that are allowed for each state const int pre_positions = prefix | open; const int post_positions = postfix | close | infix | function_open; const action parse_action[6][6] = { /* prefix postfix infix open close func open */ /* prefix */ {shift, prec, prec, shift, reduce, prec}, /* postfix */ {invalid, reduce, reduce, reduce, reduce, reduce}, /* infix */ {shift, prec, prec_assoc, shift, reduce, prec}, /* open */ {shift, shift, shift, shift, shift, shift}, /* close */ {reduce, reduce, reduce, reduce, reduce, reduce}, /* func open */ {shift, shift, shift, shift, shift, shift}}; template , typename OperatorStack = std::stack > class expression_acceptor { private: class assignment_proxy { public: explicit assignment_proxy(expression_acceptor* acceptor) : m_expression_acceptor(acceptor) { } assignment_proxy& operator=(const Token& t) { m_expression_acceptor->disambiguate_and_parse(t); return *this; } private: expression_acceptor* m_expression_acceptor; }; friend class assignment_proxy; public: typedef accumulating_acceptor_tag acceptor_category; typedef Token input_symbol_type; typedef Operand result_type; typedef std::output_iterator_tag iterator_category; typedef Token value_type; typedef Token& reference; typedef Token* pointer; typedef int difference_type; explicit expression_acceptor(const Policy& policy, OperandStack& operandStack, OperatorStack& operatorStack) : m_policy(policy) , m_operand_stack(operandStack) , m_operator_stack(operatorStack) , m_state(detail::pre_operand) { } assignment_proxy operator*() { return assignment_proxy(this); } expression_acceptor& operator++() { return *this; } expression_acceptor& operator++(int) { return *this; } bool accepted(); bool trapped() { return m_state == rejected; } operator Operand() { return this->accepted() ? m_operand_stack.top() : Operand(); } private: void disambiguate_and_parse(const Token&); int operator_type_index(int); void parse_operator(const Operator&); void do_reduce(); private: Policy m_policy; OperandStack& m_operand_stack; // changed to reference by Zhixuan Zhu OperatorStack& m_operator_stack; // changed to reference by Zhixuan Zhu state m_state; Token m_ambiguous_operator; }; EXP_TEMPLATE bool EXP_ACCEPTOR::accepted() { if (m_state == accepting) { return true; } else if (m_state == rejected) { return false; } else if (m_state == lookahead) { m_state = post_operand; int position = m_policy.positions(m_ambiguous_operator); parse_operator(m_policy.as_operator(m_ambiguous_operator, position & (postfix | close))); } while (!m_operator_stack.empty() && m_state != rejected) { do_reduce(); } if (m_state == rejected) { return false; } else if (m_operand_stack.size() > 1 || !m_operator_stack.empty()) { m_state = rejected; return false; } else { m_state = accepting; return true; } } EXP_TEMPLATE void EXP_ACCEPTOR::disambiguate_and_parse(const Token& t) { assert(m_state != accepting); if (m_state == rejected) return; if (m_policy.is_operator(t)) { int operator_positions = m_policy.positions(t); if (m_state == lookahead) { bool could_be_pre = ((operator_positions & pre_positions) != 0); bool could_be_post = ((operator_positions & post_positions) != 0); int ambiguous_position = m_policy.positions(m_ambiguous_operator); if ((could_be_pre && could_be_post) || (!could_be_pre && !could_be_post)) { m_policy.ambiguity(m_ambiguous_operator, t); m_state = rejected; return; } else if (could_be_pre) { ambiguous_position &= (infix | function_open); parse_operator(m_policy.as_operator(m_ambiguous_operator, ambiguous_position)); m_state = pre_operand; } else { ambiguous_position &= (postfix | close); parse_operator(m_policy.as_operator(m_ambiguous_operator, ambiguous_position)); m_state = post_operand; } } int valid_positions = (m_state == pre_operand) ? pre_positions : post_positions; int positions = operator_positions & valid_positions; switch (positions) { case infix: case function_open: m_state = pre_operand; // Fall through case prefix: case postfix: case open: case close: parse_operator(m_policy.as_operator(t, positions)); break; case postfix | infix: case close | infix: case postfix | function_open: case function_open | function_close: m_state = lookahead; m_ambiguous_operator = t; break; default: m_policy.invalid_operator_position(t); m_state = rejected; return; } } else { if (m_state == lookahead) { int positions = m_policy.positions(m_ambiguous_operator); positions &= (infix | function_open); parse_operator(m_policy.as_operator(m_ambiguous_operator, positions)); m_state = post_operand; } else if (m_state == post_operand) { m_policy.invalid_operand_position(m_policy.as_operand(t)); m_state = rejected; return; } else { m_state = post_operand; } m_operand_stack.push(m_policy.as_operand(t)); } } EXP_TEMPLATE inline int EXP_ACCEPTOR::operator_type_index(int position) { switch (position) { case prefix: return 0; case postfix: return 1; case infix: return 2; case open: return 3; case close: return 4; case function_open: return 5; } assert(0); return 0; } EXP_TEMPLATE void EXP_ACCEPTOR::parse_operator(const Operator& cur_operator) { if (m_operator_stack.empty()) { m_operator_stack.push(cur_operator); } else { int cur_index = operator_type_index(m_policy.position(cur_operator)); Operator& prev_operator = m_operator_stack.top(); int prev_index = operator_type_index(m_policy.position(prev_operator)); switch (parse_action[prev_index][cur_index]) { case shift: m_operator_stack.push(cur_operator); break; case reduce: do_reduce(); parse_operator(cur_operator); break; case prec: switch (m_policy.precedence(prev_operator, cur_operator)) { case lower: m_operator_stack.push(cur_operator); break; case higher: do_reduce(); parse_operator(cur_operator); break; default: m_policy.requires_precedence_relation(prev_operator, cur_operator); m_state = rejected; return; } break; case prec_assoc: switch (m_policy.precedence(prev_operator, cur_operator)) { case lower: m_operator_stack.push(cur_operator); break; case higher: do_reduce(); parse_operator(cur_operator); break; case equal: switch (m_policy.associativity(prev_operator, cur_operator)) { case left_associative: do_reduce(); parse_operator(cur_operator); break; case right_associative: m_operator_stack.push(cur_operator); break; default: m_policy.requires_associativity_relation(prev_operator, cur_operator); m_state = rejected; return; } break; default: m_policy.requires_precedence_relation(prev_operator, cur_operator); m_state = rejected; return; } break; case invalid: m_policy.invalid_operator_position(cur_operator); m_state = rejected; return; } } } EXP_TEMPLATE void EXP_ACCEPTOR::do_reduce() { Operator op = m_operator_stack.top(); m_operator_stack.pop(); switch (m_policy.position(op)) { case prefix: case postfix: { if (m_operand_stack.empty()) { m_policy.missing_operand(op); m_state = rejected; return; } Operand operand = m_operand_stack.top(); m_operand_stack.pop(); m_operand_stack.push(m_policy.reduce(op, operand)); } break; case infix: { if (m_operand_stack.size() < 2) { m_policy.missing_operand(op); m_state = rejected; return; } Operand rhs = m_operand_stack.top(); m_operand_stack.pop(); Operand lhs = m_operand_stack.top(); m_operand_stack.pop(); m_operand_stack.push(m_policy.reduce(op, lhs, rhs)); } break; case open: m_policy.unbalanced_confix(op); m_state = rejected; return; case close: if (m_operator_stack.empty()) { m_policy.unbalanced_confix(op); m_state = rejected; return; } if (m_operand_stack.empty()) { m_policy.missing_operand(op); m_state = rejected; return; } { Operator open = m_operator_stack.top(); m_operator_stack.pop(); Operand operand = m_operand_stack.top(); m_operand_stack.pop(); if (m_policy.position(open) == function_open) { if (m_operand_stack.empty()) { m_policy.missing_operand(open); m_state = rejected; return; } Operand function = m_operand_stack.top(); m_operand_stack.pop(); m_operand_stack.push(m_policy.reduce(function, open, operand, op)); } else { m_operand_stack.push(m_policy.reduce(open, op, operand)); } } return; default: assert(0); } } } // namespace detail EXP_TEMPLATE inline bool accepted(const detail::EXP_ACCEPTOR& acceptor) { return acceptor.accepted(); } EXP_TEMPLATE inline bool trapped(const detail::EXP_ACCEPTOR& acceptor) { return acceptor.trapped(); } template , typename OperatorStack = std::stack > class expression_parser { public: typedef detail::EXP_ACCEPTOR acceptor; typedef Token token_type; typedef Operand operand_type; typedef Operator operator_type; typedef Policy policy_type; typedef Token input_symbol_type; typedef Operand result_type; expression_parser() : m_policy() { } explicit expression_parser(const Policy& policy) : m_policy(policy) { } template Operand parse(InputIterator first, InputIterator last) { try { return std::copy(first, last, start()); } catch (const std::runtime_error&) { m_policy.cleanup(operandStack, operatorStack); throw; } } acceptor start() { // pass in operator and operand stacks to acceptor constructor. // this is to chean up the pointers in the stack when exception // is thrown. the exception is then passed to the upper level. // changed by Zhixuan Zhu 07/03/06 try { return acceptor(m_policy, operandStack, operatorStack); } catch (const std::runtime_error&) { m_policy.cleanup(operandStack, operatorStack); throw; } } private: Policy m_policy; // added operand and operator stacks by Zhixuan Zhu OperandStack operandStack; OperatorStack operatorStack; }; #undef EXP_ACCEPTOR #undef EXP_TEMPLATE } // namespace expression