diff options
-rw-r--r-- | server/lexer/token_type.cpp | 1 | ||||
-rw-r--r-- | server/lexer/token_type.hpp | 1 | ||||
-rw-r--r-- | server/parser/operator.hpp | 27 | ||||
-rw-r--r-- | server/parser/parser.hpp | 12 | ||||
-rw-r--r-- | test/unit_tests/lexer.cpp | 10 | ||||
-rw-r--r-- | test/unit_tests/parser.cpp | 8 |
6 files changed, 58 insertions, 1 deletions
diff --git a/server/lexer/token_type.cpp b/server/lexer/token_type.cpp index cafb403..6a42a3d 100644 --- a/server/lexer/token_type.cpp +++ b/server/lexer/token_type.cpp @@ -35,6 +35,7 @@ private: {Type::MINUS, "-"}, {Type::ASTERISK, "*"}, {Type::SLASH, "/"}, + {Type::CARET, "^"}, {Type::LEFT_PAREN, "("}, {Type::RIGHT_PAREN, ")"}, {Type::NUMBER, "number"}, diff --git a/server/lexer/token_type.hpp b/server/lexer/token_type.hpp index fba2abb..2040d28 100644 --- a/server/lexer/token_type.hpp +++ b/server/lexer/token_type.hpp @@ -18,6 +18,7 @@ enum class Type { MINUS, ASTERISK, SLASH, + CARET, LEFT_PAREN, RIGHT_PAREN, NUMBER, diff --git a/server/parser/operator.hpp b/server/parser/operator.hpp index f1c24de..86b9eb1 100644 --- a/server/parser/operator.hpp +++ b/server/parser/operator.hpp @@ -10,6 +10,8 @@ #include "../lexer/token.hpp" #include "../lexer/token_type.hpp" +#include <cmath> + namespace math::server::parser { class BinaryOp { @@ -23,6 +25,7 @@ public: case Type::MINUS: case Type::ASTERISK: case Type::SLASH: + case Type::CARET: return true; default: @@ -49,25 +52,49 @@ public: case Type::SLASH: return min_precedence() + 1; + case Type::CARET: + return min_precedence() + 2; + default: throw ParserError{"internal: undefined operator precedence"}; } } + bool is_right_associative() const { + switch (m_type) { + case Type::CARET: + return true; + + default: + return false; + } + } + + bool is_left_associative() const { + return !is_right_associative(); + } + double exec(double lhs, double rhs) const { switch (m_type) { case Type::PLUS: return lhs + rhs; + case Type::MINUS: return lhs - rhs; + case Type::ASTERISK: return lhs * rhs; + case Type::SLASH: // Trapping the CPU would be better? if (rhs == 0.) { throw ParserError{"division by zero"}; } return lhs / rhs; + + case Type::CARET: + return std::pow(lhs, rhs); + default: throw ParserError{"internal: unsupported operator"}; } diff --git a/server/parser/parser.hpp b/server/parser/parser.hpp index ac87fbe..596f84f 100644 --- a/server/parser/parser.hpp +++ b/server/parser/parser.hpp @@ -45,7 +45,17 @@ private: m_lexer.drop_token(); auto rhs = exec_primary(); - for (op = peek_operator(); op.has_value() && op->get_precedence() > lhs_op.get_precedence(); op = peek_operator()) { + for (op = peek_operator(); op.has_value(); op = peek_operator()) { + const auto op_prec = op->get_precedence(); + const auto lhs_prec = lhs_op.get_precedence(); + const auto ok_left_assoc = op->is_left_associative() && op_prec > lhs_prec; + const auto ok_right_assoc = op->is_right_associative() && op_prec == lhs_prec; + const auto ok = ok_left_assoc || ok_right_assoc; + + if (!ok) { + break; + } + rhs = exec_expr(rhs, op->get_precedence()); } diff --git a/test/unit_tests/lexer.cpp b/test/unit_tests/lexer.cpp index aa4011c..0f65979 100644 --- a/test/unit_tests/lexer.cpp +++ b/test/unit_tests/lexer.cpp @@ -53,6 +53,7 @@ BOOST_AUTO_TEST_CASE(test_parse_const_token) { // parse_* functions only consume a single token: BOOST_TEST(details::parse_const_token("+/*").value() == Type::PLUS); BOOST_TEST(details::parse_const_token("-").value() == Type::MINUS); + BOOST_TEST(details::parse_const_token("^^").value() == Type::CARET); BOOST_TEST(!details::parse_const_token("&+").has_value()); } @@ -63,6 +64,7 @@ const std::vector<std::string_view> input{ "", " + - ", "1+2", + ".5^-1 ^ 4", "1+2 * (3- 4e-2)", " 2 * (1 + 3 * (1 - -3)) ", }; @@ -93,6 +95,14 @@ const std::vector<Expected> expected{ Token{2}, }}, {{ + Token{.5}, + Token{Type::CARET}, + Token{Type::MINUS}, + Token{1}, + Token{Type::CARET}, + Token{4}, + }}, + {{ Token{1}, Token{Type::PLUS}, Token{2}, diff --git a/test/unit_tests/parser.cpp b/test/unit_tests/parser.cpp index 562c6b7..37d9e0a 100644 --- a/test/unit_tests/parser.cpp +++ b/test/unit_tests/parser.cpp @@ -30,6 +30,10 @@ const std::vector<std::string_view> input{ " 2 * (1 + 3) ", " 2 * (1 + 3 * (1 - -3)) ", " -2 * ---- (3 + -100e-1) ", // Looks weird, but also works in e.g. Python + "2 ^ 3 ^ 3", + "(2 ^ 3) ^ 3", // Power operator is right-associative + "(.5 ^ -1) ^ 4", + ".5 ^ -1 ^ 4", // Power operator has higher precedence than the unary minus }; const std::vector<double> expected{ @@ -39,6 +43,10 @@ const std::vector<double> expected{ 8, 26, 14, + 134217728, + 512, + 16, + 2, }; } |