From b0f9a8bee0736990bdd58667be3d7deea66b399e Mon Sep 17 00:00:00 2001
From: Egor Tensin <Egor.Tensin@gmail.com>
Date: Wed, 1 Jan 2020 02:52:39 +0300
Subject: parser: make ^ operator higher priority than unary -

---
 server/parser/operator.hpp |  8 +++++---
 server/parser/parser.hpp   | 39 +++++++++++++++++++++++----------------
 2 files changed, 28 insertions(+), 19 deletions(-)

(limited to 'server')

diff --git a/server/parser/operator.hpp b/server/parser/operator.hpp
index 86b9eb1..fd45aa2 100644
--- a/server/parser/operator.hpp
+++ b/server/parser/operator.hpp
@@ -42,8 +42,8 @@ public:
 
     static constexpr unsigned min_precedence() { return 0; }
 
-    unsigned get_precedence() const {
-        switch (m_type) {
+    static unsigned get_precedence(Type type) {
+        switch (type) {
             case Type::PLUS:
             case Type::MINUS:
                 return min_precedence();
@@ -53,13 +53,15 @@ public:
                 return min_precedence() + 1;
 
             case Type::CARET:
-                return min_precedence() + 2;
+                return min_precedence() + 3;
 
             default:
                 throw ParserError{"internal: undefined operator precedence"};
         }
     }
 
+    unsigned get_precedence() const { return get_precedence(m_type); }
+
     bool is_right_associative() const {
         switch (m_type) {
             case Type::CARET:
diff --git a/server/parser/parser.hpp b/server/parser/parser.hpp
index fb2a5ff..0a8c761 100644
--- a/server/parser/parser.hpp
+++ b/server/parser/parser.hpp
@@ -17,6 +17,8 @@ namespace math::server {
 
 class Parser {
 public:
+    using Type = lexer::Token::Type;
+
     // I did simple recursive descent parsing a long time ago (see
     // https://github.com/egor-tensin/simple-interpreter), this appears to be
     // a finer algorithm for parsing arithmetic expressions.
@@ -27,7 +29,7 @@ public:
     { }
 
     double exec() {
-        const auto result = exec_expr();
+        const auto result = exec_dmas();
         if (m_lexer.has_token()) {
             throw ParserError{"expected a binary operator"};
         }
@@ -35,19 +37,25 @@ public:
     }
 
 private:
-    double exec_expr() {
-        return exec_expr(exec_factor(), parser::BinaryOp::min_precedence());
+    // DMAS as in Division, Multiplication, Addition and Subtraction
+    double exec_dmas() {
+        return exec_binary_op(exec_factor(), parser::BinaryOp::min_precedence());
+    }
+
+    // Exponentiation operator
+    double exec_exp() {
+        return exec_binary_op(exec_atom(), parser::BinaryOp::get_precedence(Type::CARET));
     }
 
-    double exec_expr(double lhs, unsigned min_prec) {
-        for (auto op = peek_operator(); op.has_value() && op->get_precedence() >= min_prec;) {
+    double exec_binary_op(double lhs, unsigned min_prec) {
+        for (auto op = peek_operator(min_prec); op.has_value();) {
             const auto prev = *op;
             const auto prev_prec = prev.get_precedence();
 
             m_lexer.drop_token();
             auto rhs = exec_factor();
 
-            for (op = peek_operator(); op.has_value(); op = peek_operator()) {
+            for (op = peek_operator(min_prec); op.has_value(); op = peek_operator(min_prec)) {
                 const auto next = *op;
                 const auto next_prec = next.get_precedence();
 
@@ -61,7 +69,7 @@ private:
                     }
                 }
 
-                rhs = exec_expr(rhs, next_prec);
+                rhs = exec_binary_op(rhs, next_prec);
             }
 
             lhs = prev.exec(lhs, rhs);
@@ -69,28 +77,29 @@ private:
         return lhs;
     }
 
-    std::optional<parser::BinaryOp> peek_operator() {
+    std::optional<parser::BinaryOp> peek_operator(unsigned min_prec) {
         const auto token = m_lexer.peek_token();
         if (!token.has_value() || !parser::BinaryOp::is(*token)) {
             return {};
         }
-        return parser::BinaryOp::from_token(*token);
+        const auto op = parser::BinaryOp::from_token(*token);
+        if (op.get_precedence() < min_prec) {
+            return {};
+        }
+        return op;
     }
 
     double exec_factor() {
         if (!m_lexer.has_token()) {
             throw ParserError{"expected '-', '+', '(' or a number"};
         }
-
-        using Type = lexer::Token::Type;
-
         if (m_lexer.drop_token_of_type(Type::MINUS).has_value()) {
             return -exec_factor();
         }
         if (m_lexer.drop_token_of_type(Type::PLUS).has_value()) {
             return exec_factor();
         }
-        return exec_atom();
+        return exec_exp();
     }
 
     double exec_atom() {
@@ -98,10 +107,8 @@ private:
             throw ParserError{"expected '-', '+', '(' or a number"};
         }
 
-        using Type = lexer::Token::Type;
-
         if (m_lexer.drop_token_of_type(Type::LEFT_PAREN).has_value()) {
-            const auto inner = exec_expr();
+            const auto inner = exec_dmas();
             if (!m_lexer.has_token() || !m_lexer.drop_token_of_type(Type::RIGHT_PAREN).has_value()) {
                 throw ParserError{"missing closing ')'"};
             }
-- 
cgit v1.2.3