parser.hpp

Go to the documentation of this file.

/*
  Copyright (C) 2017 Marcus N Campbell Bannerman <[email protected]>

  This file is part of stator.

  stator 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, either version 3 of the License, or
  (at your option) any later version.

  stator 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 stator. If not, see <http://www.gnu.org/licenses/>.
*/

#pragma once

#include <stator/symbolic/runtime.hpp>
#include <stator/exception.hpp>
#include <algorithm>
#include <cctype>
#include <map>
#include <sstream>

namespace sym {
  namespace detail {
    class ExprTokenizer {
    public:
      ExprTokenizer(const std::string& str):
    _str(str),
    _start(0),
    _end(0)
      {
    //Initialise the operators

    //These are left-associative operators, so we expect their RBP
    //to be LBP+1, and they can group with themselves
    //LBP, RBP, NBP

    //
    //LBP: Left binding power is the precedence of the right operator.
    //
    //RBP: Right binding power is the precedence that the operator
    //will collect as its right arguments (prefix operators have
    //no right arguments, thus RBP is unused). If this is higher
    //than the binding power, it will not collect itself (thus it
    //is left-associative). If it is equal or greater, it will
    //collect itself in its right argument (thus it is right
    //associative).
    //
    //NBP: Next binding power 
    
    _right_operators["+"].reset(new BinaryOpToken<detail::Add>());
    _right_operators["-"].reset(new BinaryOpToken<detail::Subtract>());
    _right_operators["*"].reset(new BinaryOpToken<detail::Multiply>());
    _right_operators["/"].reset(new BinaryOpToken<detail::Divide>());
    //Power is right-associative, thus its RBP is equal to its LBP
    //to ensure a^b^c is a^(b^c).
    _right_operators["^"].reset(new BinaryOpToken<detail::Power>());

    //The unary operators
//  _left_operators["+"].reset(new SkipToken<std::numeric_limits<int>::max()>());
//  _left_operators["-"].reset(new UnaryNegative<std::numeric_limits<int>::max()>());

    _left_operators["+"].reset(new SkipToken<detail::Add::leftBindingPower+1>());
    _left_operators["-"].reset(new UnaryNegative<detail::Add::leftBindingPower+1>());
 
    //The parenthesis operator is entirely handled by Parenthesis.
    _left_operators["("].reset(new ParenthesisToken);
    //A halt token stops parseExpression processing. The right
    //parenthesis should be handled by the previous entry.
    _right_operators[")"].reset(new HaltToken);
    
    //Unary operators have a maximum BP 
    _left_operators["sin"].reset(new UnaryOpToken<detail::Sine, std::numeric_limits<int>::max()>());
    _left_operators["cos"].reset(new UnaryOpToken<detail::Cosine, std::numeric_limits<int>::max()>());
    _left_operators["exp"].reset(new UnaryOpToken<detail::Exp, std::numeric_limits<int>::max()>());
    _left_operators["ln"].reset(new UnaryOpToken<detail::Log, std::numeric_limits<int>::max()>());
    
    //The actual tokenisation is done in the consume() member
    //function. The first call starts the process and clears the "end" state.
    consume();
      }

      std::string next() {
    return empty() ? "" : _str.substr(_start, _end - _start);
      }

      void expect(std::string token) {
    if (next() != token)
      stator_throw() << "Expected " << ((token.empty()) ? "end of expression": ("\""+token+"\"")) << " but found " << (empty() ? "the end of expression" : next()) << "\" instead?\n" << parserLoc();
    consume();
      }

      bool empty() const {
    return _start == _str.size();
      }
      
      void consume() {
    _start = _end;

    //Skip whitespace
    while ((_str[_start] == ' ') && (_start < _str.size())) ++_start;

    _end = _start;

    //Check for sequence end
    if (empty()) return;

    //Not at end of sequence so at least one character in symbol
    _end = _start + 1;

    //Parse numbers with decimal points and (possible signed)
    //exponents. Signs at the front of numbers are parsed as unary
    //operators.
    if (std::isdigit(_str[_start])) {
      consumeFloat();
      return;
    }

    //Parsing a string
    if (std::isalpha(_str[_start])) {
      while ((_end < _str.size()) && std::isalpha(_str[_end]))
        ++_end;
      return;
    }

    //Allow non-alpha single character operators (longer operators are usually strings and caught above!)
    if (_right_operators.find(_str.substr(_start, 1)) != _right_operators.end())
      return;
    if (_left_operators.find(_str.substr(_start, 1)) != _left_operators.end())
      return;
    
    stator_throw() << "Unrecognised token \"" << _str[_start] << "\"\n" << parserLoc();
      }

      void consumeFloat() {
    bool decimal = false;
    bool exponent = false;
      
    while (_end != _str.size()) {
      if (_str[_end] == '.') {
        if (!decimal && !exponent) {
          decimal = true;
          ++_end;
          continue;
        } else {
          stator_throw() << "Unexpected decimal point?\n" << parserLoc();
        }
      }
    
      if ((_str[_end] == 'e') || (_str[_end] == 'E')) {
        if (!exponent) {
          exponent = true;
          decimal = true; //Don't allow decimals in the exponent
          ++_end;

          if (_end == _str.size())
        stator_throw() << "String ended during parsing of exponent\n" << parserLoc();

          //Eat the exponent sign if present
          if ((_str[_end] == '+') || (_str[_end] == '-'))
        ++_end;
        
          if (_end == _str.size())
        stator_throw() << "String ended during parsing of exponent\n" << parserLoc();
        
          if (!std::isdigit(_str[_end]))
        stator_throw() << "Malformed exponent?\n" << parserLoc();
        
          continue;
        } else
          stator_throw() << "Double exponent?\n" << parserLoc();
      }
      
      if (std::isdigit(_str[_end])) {
        ++_end;
        continue;
      }
      
      break;
    }
      }
      
      std::string parserLoc() {
    return _str + "\n"
      + std::string(_start, ' ') + std::string((_start < _end) ? _end - _start -1: 0, '-') + "^";
      }

      struct RightOperatorBase {
    virtual Expr apply(Expr, ExprTokenizer&) const = 0;
    virtual int LBP() const = 0;
    virtual int NBP() const = 0;
      };

      struct LeftOperatorBase {
    virtual Expr apply(Expr, ExprTokenizer&) const = 0;
    virtual int BP() const = 0;
      };
      
      template<class Op>
      struct BinaryOpToken : RightOperatorBase {
    Expr apply(Expr l, ExprTokenizer& tk) const {
      return Op::apply(l, tk.parseExpression(detail::RBP<Op>()));
    }
        
    int LBP() const { return Op::leftBindingPower; }

    int NBP() const { return detail::NBP<Op>(); }
      };

      struct HaltToken : RightOperatorBase {
    virtual Expr apply(Expr, ExprTokenizer&) const { stator_throw() << "Should never be called!"; }
    //To ensure it is always treated as a separate expression, its BP is negative (nothing can claim it)
    virtual int LBP() const { return -1; }
    int NBP() const { stator_throw() << "Should never be called!"; }
      };

      struct ParenthesisToken : public LeftOperatorBase {
    Expr apply(Expr l, ExprTokenizer& tk) const {
      tk.expect(")");
      return l;
    }

    //Parenthesis bind the whole following expression
    int BP() const {
      return 0;
    }
      };
      
      template<class Op, int tBP>
      struct UnaryOpToken : LeftOperatorBase {
    Expr apply(Expr l, ExprTokenizer& tk) const {
      return Op::apply(l);
    }

    int BP() const {
      return tBP;
    }
      };

      template<int tBP>
      struct SkipToken : public LeftOperatorBase {
    Expr apply(Expr l, ExprTokenizer& tk) const {
      return l;
    }
    
    int BP() const {
      return tBP;
    }
      };

      template<int tBP>
      struct UnaryNegative : public LeftOperatorBase {
    struct Visitor : VisitorHelper<Visitor> {
      template<class T> Expr apply(const T& val) {
        return -val;
      }
    };
    
    Expr apply(Expr l, ExprTokenizer& tk) const {
      Visitor v;
      return l->visit(v);
    }
    
    int BP() const {
      return tBP;
    }
      };
      
      std::map<std::string, shared_ptr<LeftOperatorBase> > _left_operators;
      std::map<std::string, shared_ptr<RightOperatorBase> > _right_operators;

      Expr parseToken() {
    std::string token = next();
    consume();

    if (token.empty())
      stator_throw() << "Unexpected end of expression?\n" << parserLoc();

    //Parse numbers
    if (std::isdigit(token[0])) {
      std::stringstream ss;
      ss << token;
      double val;
      ss >> val;
      return Expr(val);
    }

    //Parse left operators
    auto it = _left_operators.find(token);
    if (it != _left_operators.end()) {
      return it->second->apply(parseExpression(it->second->BP()), *this);
    }

    //Its not a prefix operator or a number, if it is a single
    //alpha character, then assume its a variable!
    if ((token.size() == 1) && (std::isalpha(token[0])))
      return Expr(VarRT(token[0]));

    stator_throw() << "Could not parse as a valid token?\n" << parserLoc();
      }

      Expr parseExpression(int minLBP = 0) {
    //Grab the first token (should be either a unary/prefix
    //operator or a number/variable all of which may be a LHS of a
    //multi arg operator (which are handled in this
    //function). Unary/prefix operators are handled directly by
    //parseToken()
    Expr t = parseToken();
    
    //maxLBP is only allowed to decrease as it ensures the while
    //loop climbs down the precedence tree (up the AST) to the
    //root of the expression.
    int maxLBP = std::numeric_limits<int>::max();
    while (true) {
      std::string token = next();

      //Handle the special case of end of string
      if (token.empty()) break;

      //Determine the type of operator found
      auto it = _right_operators.find(token);

      //If there is no match, then return an error
      if (it == _right_operators.end())
        stator_throw() << "Expected right operator but got \""<< token << "\"?\n" << parserLoc();

      //If the operator has a lower binding power than what this
      //call can collect (as limited by minLBP), then return. If
      //an operator has already been collected and its next
      //binding power (stored in maxLBP) doesn't allow it to
      //collect this operator, then exit and allow the calling
      //function to handle this operator.
      if ((minLBP > it->second->LBP()) || (it->second->LBP() > maxLBP)) break;
      
      consume();
      t = it->second->apply(t, *this);
      maxLBP = it->second->NBP();
    }
    
    return t;
      }
      
    private:
    
      std::string _str;
      std::size_t _start;
      std::size_t _end;
    };
  }

  Expr::Expr(const std::string& str)
  {
    auto tokenizer = detail::ExprTokenizer(str);
    *this = simplify(tokenizer.parseExpression());

    //Check that the full string was parsed
    if (!tokenizer.empty())
      stator_throw() << "Parsing terminated unexpectedly early?\n" << tokenizer.parserLoc();
  }

  Expr::Expr(const char* str) : Expr(std::string(str)) {}
}