aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/server/parser
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--server/parser.hpp168
-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
5 files changed, 186 insertions, 168 deletions
diff --git a/server/parser.hpp b/server/parser.hpp
deleted file mode 100644
index a9e5f54..0000000
--- a/server/parser.hpp
+++ /dev/null
@@ -1,168 +0,0 @@
-#pragma once
-
-#include "error.hpp"
-#include "lexer.hpp"
-
-#include <optional>
-#include <string>
-#include <string_view>
-
-namespace math::server {
-namespace parser {
-
-class Error : public server::Error {
-public:
- explicit Error(const std::string& what)
- : server::Error{"parser error: " + what}
- { }
-};
-
-class BinaryOp {
-public:
- static bool is(const lexer::Token& token) {
- using Type = lexer::Token::Type;
- 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 lexer::Token& token) {
- if (!is(token)) {
- throw Error{"internal: token is not a binary operator"};
- }
- return BinaryOp{token};
- }
-
- static constexpr unsigned min_precedence() { return 0; }
-
- unsigned get_precedence() const {
- using Type = lexer::Token::Type;
- switch (m_type) {
- case Type::PLUS:
- case Type::MINUS:
- return min_precedence();
-
- case Type::ASTERISK:
- case Type::SLASH:
- return min_precedence() + 1;
-
- default:
- throw Error{"internal: undefined operator precedence"};
- }
- }
-
- double exec(double lhs, double rhs) const {
- using Type = lexer::Token::Type;
- 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 Error{"division by zero"};
- }
- return lhs / rhs;
- default:
- throw Error{"internal: unsupported operator"};
- }
- }
-
-private:
- explicit BinaryOp(const lexer::Token& token)
- : m_type{token.get_type()}
- { }
-
- lexer::Token::Type m_type;
-};
-
-}
-
-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() {
- m_lexer.parse_token();
- const auto result = exec_expr();
- if (m_lexer.has_token()) {
- throw parser::Error{"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 parser::Error{"expected '-', '(' or a number"};
- }
-
- using Type = lexer::Token::Type;
-
- if (m_lexer.drop_token_if(Type::MINUS).has_value()) {
- return -exec_primary();
- }
-
- if (m_lexer.drop_token_if(Type::LEFT_PAREN).has_value()) {
- const auto inner = exec_expr();
- if (!m_lexer.has_token() || !m_lexer.drop_token_if(Type::RIGHT_PAREN).has_value()) {
- throw parser::Error{"missing closing ')'"};
- }
- return inner;
- }
-
- if (const auto token = m_lexer.drop_token_if(Type::NUMBER); token.has_value()) {
- return token.value().get_number_value();
- }
-
- throw parser::Error{"expected '-', '(' or a number"};
- }
-
- Lexer m_lexer;
-};
-
-}
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;
+};
+
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-10 10:10:43 +0000