diff options
author | Egor Tensin <Egor.Tensin@gmail.com> | 2019-12-07 03:36:21 +0300 |
---|---|---|
committer | Egor Tensin <Egor.Tensin@gmail.com> | 2019-12-07 03:36:21 +0300 |
commit | 00863566ec4601c65c435b74e575d49546a1c707 (patch) | |
tree | 479a0a6e96aba8191c7a65ea9bee2f4d5e3a4aba /server/parser | |
parent | add stress_test.py (diff) | |
download | math-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.txt | 2 | ||||
-rw-r--r-- | server/parser/error.hpp | 16 | ||||
-rw-r--r-- | server/parser/operator.hpp | 79 | ||||
-rw-r--r-- | server/parser/parser.hpp | 89 |
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; +}; + +} |