diff options
author | Egor Tensin <Egor.Tensin@gmail.com> | 2020-01-01 02:52:39 +0300 |
---|---|---|
committer | Egor Tensin <Egor.Tensin@gmail.com> | 2020-01-01 03:20:14 +0300 |
commit | b0f9a8bee0736990bdd58667be3d7deea66b399e (patch) | |
tree | 8771be0c9331383aab2c52c146d69cff4e00eec3 | |
parent | parser: support unary + (diff) | |
download | math-server-b0f9a8bee0736990bdd58667be3d7deea66b399e.tar.gz math-server-b0f9a8bee0736990bdd58667be3d7deea66b399e.zip |
parser: make ^ operator higher priority than unary -
-rw-r--r-- | server/parser/operator.hpp | 8 | ||||
-rw-r--r-- | server/parser/parser.hpp | 39 |
2 files changed, 28 insertions, 19 deletions
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 ')'"}; } |