aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/server/parser
diff options
context:
space:
mode:
authorEgor Tensin <Egor.Tensin@gmail.com>2019-12-07 03:36:21 +0300
committerEgor Tensin <Egor.Tensin@gmail.com>2019-12-07 03:36:21 +0300
commit00863566ec4601c65c435b74e575d49546a1c707 (patch)
tree479a0a6e96aba8191c7a65ea9bee2f4d5e3a4aba /server/parser
parentadd stress_test.py (diff)
downloadmath-server-00863566ec4601c65c435b74e575d49546a1c707.tar.gz
math-server-00863566ec4601c65c435b74e575d49546a1c707.zip
split server into multiple components
In a vague attempt to make header files more readable, split server/ into a number of components. Also, refactor the unit tests to use the "Data-driven test cases" of Boost.Test.
Diffstat (limited to 'server/parser')
-rw-r--r--server/parser/CMakeLists.txt2
-rw-r--r--server/parser/error.hpp16
-rw-r--r--server/parser/operator.hpp79
-rw-r--r--server/parser/parser.hpp89
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;
+};
+
+}