4 files changed, 186 insertions, 0 deletions
diff --git a/server/parser/CMakeLists.txt b/server/parser/CMakeLists.txt
new file mode 100644
index 0000000..2490e57
--- /dev/null
+++ b/server/parser/CMakeLists.txt
@@ -0,0 +1,2 @@
+add_library(parser INTERFACE)
+target_link_libraries(parser INTERFACE common lexer)
diff --git a/server/parser/error.hpp b/server/parser/error.hpp
new file mode 100644
index 0000000..1ba29ed
--- /dev/null
+++ b/server/parser/error.hpp
@@ -0,0 +1,16 @@
+#pragma once
+
+#include "../common/error.hpp"
+
+#include <string>
+
+namespace math::server {
+
+class ParserError : public Error {
+public:
+    explicit ParserError(const std::string& what)
+        : Error{"parser error: " + what}
+    { }
+};
+
+}
diff --git a/server/parser/operator.hpp b/server/parser/operator.hpp
new file mode 100644
index 0000000..4226078
--- /dev/null
+++ b/server/parser/operator.hpp
@@ -0,0 +1,79 @@
+#pragma once
+
+#include "error.hpp"
+
+#include "../lexer/token.hpp"
+#include "../lexer/token_type.hpp"
+
+namespace math::server::parser {
+
+class BinaryOp {
+public:
+    using Token = lexer::Token;
+    using Type = Token::Type;
+
+    static bool is(const Token& token) {
+        switch (token.get_type()) {
+            case Type::PLUS:
+            case Type::MINUS:
+            case Type::ASTERISK:
+            case Type::SLASH:
+                return true;
+
+            default:
+                return false;
+        }
+    }
+
+    static BinaryOp from_token(const Token& token) {
+        if (!is(token)) {
+            throw ParserError{"internal: token is not a binary operator"};
+        }
+        return BinaryOp{token};
+    }
+
+    static constexpr unsigned min_precedence() { return 0; }
+
+    unsigned get_precedence() const {
+        switch (m_type) {
+            case Type::PLUS:
+            case Type::MINUS:
+                return min_precedence();
+
+            case Type::ASTERISK:
+            case Type::SLASH:
+                return min_precedence() + 1;
+
+            default:
+                throw ParserError{"internal: undefined operator precedence"};
+        }
+    }
+
+    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;
+            default:
+                throw ParserError{"internal: unsupported operator"};
+        }
+    }
+
+private:
+    explicit BinaryOp(const Token& token)
+        : m_type{token.get_type()}
+    { }
+
+    Type m_type;
+};
+
+}
diff --git a/server/parser/parser.hpp b/server/parser/parser.hpp
new file mode 100644
index 0000000..1197c31
--- /dev/null
+++ b/server/parser/parser.hpp
@@ -0,0 +1,89 @@
+#pragma once
+
+#include "error.hpp"
+#include "operator.hpp"
+
+#include "../lexer/lexer.hpp"
+
+#include <optional>
+#include <string_view>
+
+namespace math::server {
+
+class Parser {
+public:
+    // 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.
+    // Reference: https://en.wikipedia.org/wiki/Operator-precedence_parser
+
+    explicit Parser(const std::string_view& input)
+        : m_lexer{input}
+    { }
+
+    double exec() {
+        const auto result = exec_expr();
+        if (m_lexer.has_token()) {
+            throw ParserError{"expected a binary operator"};
+        }
+        return result;
+    }
+
+private:
+    double exec_expr() {
+        return exec_expr(exec_primary(), parser::BinaryOp::min_precedence());
+    }
+
+    double exec_expr(double lhs, unsigned min_prec) {
+        for (auto op = peek_operator(); op.has_value() && op->get_precedence() >= min_prec;) {
+            const auto lhs_op = *op;
+            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()) {
+                rhs = exec_expr(rhs, op->get_precedence());
+            }
+
+            lhs = lhs_op.exec(lhs, rhs);
+        }
+        return lhs;
+    }
+
+    std::optional<parser::BinaryOp> peek_operator() {
+        const auto token = m_lexer.peek_token();
+        if (!token.has_value() || !parser::BinaryOp::is(*token)) {
+            return {};
+        }
+        return parser::BinaryOp::from_token(*token);
+    }
+
+    double exec_primary() {
+        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_primary();
+        }
+
+        if (m_lexer.drop_token_of_type(Type::LEFT_PAREN).has_value()) {
+            const auto inner = exec_expr();
+            if (!m_lexer.has_token() || !m_lexer.drop_token_of_type(Type::RIGHT_PAREN).has_value()) {
+                throw ParserError{"missing closing ')'"};
+            }
+            return inner;
+        }
+
+        if (const auto token = m_lexer.drop_token_of_type(Type::NUMBER); token.has_value()) {
+            return token.value().as_number();
+        }
+
+        throw ParserError{"expected '-', '(' or a number"};
+    }
+
+    Lexer m_lexer;
+};
+
+}