aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/server/parser
diff options
context:
space:
mode:
authorEgor Tensin <Egor.Tensin@gmail.com>2020-01-01 02:52:39 +0300
committerEgor Tensin <Egor.Tensin@gmail.com>2020-01-01 03:20:14 +0300
commitb0f9a8bee0736990bdd58667be3d7deea66b399e (patch)
tree8771be0c9331383aab2c52c146d69cff4e00eec3 /server/parser
parentparser: support unary + (diff)
downloadmath-server-b0f9a8bee0736990bdd58667be3d7deea66b399e.tar.gz
math-server-b0f9a8bee0736990bdd58667be3d7deea66b399e.zip
parser: make ^ operator higher priority than unary -
Diffstat (limited to 'server/parser')
-rw-r--r--server/parser/operator.hpp8
-rw-r--r--server/parser/parser.hpp39
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 ')'"};
}