В первой части был написан лексер. Далее будет рассмотрена разработка парсера.
Парсер
Парсер будет реализован по алгоритму сортировочной станции, так как он достаточно прост и не нуждается в рекурсии. Сам алгоритм таков:
В начале даются пустой выходной поток и пустой стек. Начнём читать токены из входного потока по очереди.
- Если это число, то передать его в выходной поток.
- Если это лево ассоциативный оператор, то выталкиваем токены из стека в выходной поток до тех пор, пока он не опустеет, либо не его вершине не встретится скобка, или оператор с более низким приоритетом.
- Если это открывающая скобка, то положить её в стек.
- Если это закрывающая скобка, то выталкиваем токены из стека в выходной поток до обнаружения открывающей скобки. Вытолкнуть открывающую скобку из стека, но не передавать её в выходной поток. Если стек опустел, и скобка не найдена, то генерируем ошибку.
После достижения конца входного потока, вытолкнуть все оставшиеся в стеке операторы в выходной поток. Если в нём найдено что-либо кроме операторов, то генерируем ошибку.
Прикинем, какие тесты могут понадобиться для начала.
- При получении пустого списка, возвращается пустой список.
- При получении списка с одним числом, возвращается список с этим числом.
- При получении [1 + 2], возвращается [1 2 +].
- При получении [1 + 2 + 3], возвращается [1 2 + 3 +], так как оператор + является лево ассоциативным.
- При получении [1 * 2 + 3], возвращается [1 2 * 3 +].
- При получении [1 + 2 * 3], возвращается [1 2 3 * +], так как оператор * имеет больший приоритет.
Со скобками и ошибками разберёмся позднее. Итак, напишем первый тест из списка.
TEST_CLASS(ParserTests) {
public:
TEST_METHOD(Should_return_empty_list_when_put_empty_list) {
Tokens tokens = Parser::Parse({});
Assert::IsTrue(tokens.empty());
}
};
Как и в прошлый раз, парсер будет представлять собой свободную функцию в пространстве имён Parser.
namespace Parser {
inline Tokens Parse(const Tokens &) { throw std::exception(); }
} // namespace Parser
Заставим тест проходить применив ({} → nil).
inline Tokens Parse(const Tokens &) {
return{};
}
Следующий тест почти аналогичен предыдущему.
TEST_METHOD(Should_parse_single_number) {
Tokens tokens = Parser::Parse({ Token(1) });
AssertRange::AreEqual({ Token(1) }, tokens);
}
Применив (constant → scalar) разберёмся и с ним.
inline Tokens Parse(const Tokens &tokens) {
return tokens;
}
-
При получении пустого списка, возвращается пустой список. -
При получении списка с одним числом, возвращается список с этим числом. - При получении [1 + 2], возвращается [1 2 +].
- …
Дальше интереснее, необходимо обработать сразу несколько токенов.
TEST_METHOD(Should_parse_num_plus_num) {
Tokens tokens = Parser::Parse({ Token(1), Token(Operator::Plus), Token(2) });
AssertRange::AreEqual({ Token(1), Token(2), Token(Operator::Plus) }, tokens);
}
Для начала слегка изменим функцию Parse не нарушая предыдущие тесты.
inline Tokens Parse(const Tokens &tokens) {
Tokens output;
for(const Token &token : tokens) {
output.push_back(token);
}
return output;
}
Теперь легко добавить стек для операций и заставить проходить тест.
inline Tokens Parse(const Tokens &tokens) {
Tokens output;
Tokens stack;
for(const Token &token : tokens) {
if(token.Type() == TokenType::Number) {
output.push_back(token);
}
else {
stack.push_back(token);
}
}
std::copy(stack.crbegin(), stack.crend(), std::back_inserter(output));
return output;
}
-
При получении [1 + 2], возвращается [1 2 +]. - При получении [1 + 2 + 3], возвращается [1 2 + 3 +], так как оператор + является лево ассоциативным.
- …
TEST_METHOD(Should_parse_two_additions) {
Tokens tokens = Parser::Parse({ Token(1), Token(Operator::Plus), Token(2), Token(Operator::Plus), Token(3) });
AssertRange::AreEqual({ Token(1), Token(2), Token(Operator::Plus), Token(3), Token(Operator::Plus) }, tokens);
}
Тест не проходит, так как все операторы располагаются в конце списка. Будем перекидывать всё из стека в выходной список при каждом обнаружении оператора.
inline Tokens Parse(const Tokens &tokens) {
Tokens output, stack;
auto popAll = [&]() { while(!stack.empty()) {
output.push_back(stack.back());
stack.pop_back();
}};
for(const Token &token : tokens) {
if(token.Type() == TokenType::Operator) {
popAll();
stack.push_back(token);
continue;
}
output.push_back(token);
}
popAll();
return output;
}
Разберёмся с приоритетом операторов. Добавим тест на функцию, которая будет определять приоритет переданного в неё оператора.
-
При получении [1 + 2 + 3], возвращается [1 2 + 3 +], так как оператор + является лево ассоциативным. - Пары операторов +- и */ должны иметь равные приоритеты.
- Приоритет операторов + и — должен быть меньше, чем у * и /
- …
TEST_METHOD(Should_get_same_precedence_for_operator_pairs) {
Assert::AreEqual(Parser::PrecedenceOf(Operator::Plus), Parser::PrecedenceOf(Operator::Minus));
Assert::AreEqual(Parser::PrecedenceOf(Operator::Mul), Parser::PrecedenceOf(Operator::Div));
}
Добавим метод PrecedenceOf в пространство имён Parser и применим ({} → nil).
inline int PrecedenceOf(Operator) { return 0; }
Тест проходит, переходим к следующему.
TEST_METHOD(Should_get_greater_precedence_for_multiplicative_operators) {
Assert::IsTrue(Parser::PrecedenceOf(Operator::Mul) > Parser::PrecedenceOf(Operator::Plus));
}
Применим (unconditional → if).
inline int PrecedenceOf(Operator op) {
return (op == Operator::Mul || op == Operator::Div) ? 1 : 0;
}
-
Пары операторов +- и */ должны иметь равные приоритеты. -
Приоритет операторов + и — должен быть меньше, чем у * и / - При получении [1 * 2 + 3], возвращается [1 2 * 3 +].
- При получении [1 + 2 * 3], возвращается [1 2 3 * +], так как оператор * имеет больший приоритет.
Начнём с последнего теста, так как он кажется более простым.
TEST_METHOD(Should_parse_add_and_mul) {
Tokens tokens = Parser::Parse({ Token(1), Token(Operator::Plus), Token(2), Token(Operator::Mul), Token(3) });
AssertRange::AreEqual({ Token(1), Token(2), Token(3), Token(Operator::Mul), Token(Operator::Plus) }, tokens);
}
Он не проходит, так как парсер не должен выталкивать из стека операторы с меньшим приоритетом. Добавим в лямбду, выталкивающую операции из стека, предикат, определяющий, когда нужно остановиться.
inline Tokens Parse(const Tokens &tokens) {
Tokens output, stack;
auto popToOutput = [&output, &stack](auto whenToEnd) {
while(!stack.empty() && !whenToEnd(stack.back())) {
output.push_back(stack.back());
stack.pop_back();
}};
for(const Token ¤t : tokens) {
if(current.Type() == TokenType::Operator) {
popToOutput([&](Operator top) { return PrecedenceOf(top) < PrecedenceOf(current); });
stack.push_back(current);
continue;
}
output.push_back(current);
}
popToOutput([](auto) { return false; });
return output;
}
Для проверки алгоритма добавим последний тест, немного его усложнив. Попробуем обработать сложное выражение с несколькими операциями.
TEST_METHOD(Should_parse_complex_experssion) {
// 1 + 2 / 3 - 4 * 5 = 1 2 3 / + 4 5 * -
Tokens tokens = Parser::Parse({
Token(1), Token(Operator::Plus), Token(2), Token(Operator::Div), Token(3),
Token(Operator::Minus), Token(4), Token(Operator::Mul), Token(5)
});
AssertRange::AreEqual({
Token(1), Token(2), Token(3), Token(Operator::Div), Token(Operator::Plus),
Token(4), Token(5), Token(Operator::Mul), Token(Operator::Minus)
}, tokens);
}
Он сразу же проходит. Прохождение тестов без написания какого-либо кода, является сомнительной практикой, но иногда полезно для поведения, в котором ты не уверен полностью. Функция Parse, написанная в функциональном стиле, конечно, коротка и лаконична, но плохо расширяема. Как и в прошлый раз, выделим отдельный класс в пространство имён Detail и перенесём в него всю функциональность парсера, оставив функцию Parse в качестве фасада. Проделать это достаточно легко, так как не нужно бояться что-либо сломать.
inline Tokens Parse(const Tokens &tokens) {
Detail::ShuntingYardParser parser(tokens);
parser.Parse();
return parser.Result();
}
Класс Detail::ShuntingYardParser
namespace Detail {
class ShuntingYardParser {
public:
ShuntingYardParser(const Tokens &tokens) : m_current(tokens.cbegin()), m_end(tokens.cend()) {}
void Parse() {
for(; m_current != m_end; ++m_current) {
ParseCurrentToken();
}
PopToOutputUntil(StackIsEmpty);
}
const Tokens &Result() const { return m_output; }
private:
static bool StackIsEmpty() { return false; }
void ParseCurrentToken() {
switch(m_current->Type()) {
case TokenType::Operator:
ParseOperator();
break;
case TokenType::Number:
ParseNumber();
break;
default:
throw std::out_of_range("TokenType");
}
}
void ParseOperator() {
PopToOutputUntil([this]() { return PrecedenceOf(m_stack.back()) < PrecedenceOf(*m_current); });
m_stack.push_back(*m_current);
}
void ParseNumber() {
m_output.push_back(*m_current);
}
template<class T>
void PopToOutputUntil(T whenToEnd) {
while(!m_stack.empty() && !whenToEnd()) {
m_output.push_back(m_stack.back());
m_stack.pop_back();
}
}
Tokens::const_iterator m_current;
Tokens::const_iterator m_end;
Tokens m_output;
Tokens m_stack;
};
} // namespace Detail
Добавим поддержку скобок. Составим список тестов, начиная с самого простого для реализации.
- При получении [(1)], возвращается [1].
- При получении [(1 + 2) * 3], возвращается [1 2 + 3 *].
- При получении [1)], генерируется исключение.
- При получении [(1], генерируется исключение.
Добавим первый тест.
TEST_METHOD(Should_skip_paren_around_number) {
Tokens tokens = Parser::Parse({ Token(Operator::LParen), Token(1), Token(Operator::RParen) });
AssertRange::AreEqual({ Token(1) }, tokens);
}
Так как в данный момент мы не отличаем скобки от других операторов, то он не проходит. Внесём небольшое изменение (unconditional → if) в метод ParseOperator.
void ParseOperator() {
const Operator currOp = *m_current;
switch(currOp) {
case Operator::LParen:
break;
case Operator::RParen:
break;
default:
PopToOutputUntil([&]() { return PrecedenceOf(m_stack.back()) < PrecedenceOf(currOp); });
m_stack.push_back(*m_current);
break;
}
}
Перед тем, как добавить следующий тест, сделаем рефакторинг написанных на данный момент тестов. Создадим статические экземпляры токенов для операторов и некоторых чисел. Это значительно уменьшит количество кода в тестах.
static const Token plus(Operator::Plus), minus(Operator::Minus);
static const Token mul(Operator::Mul), div(Operator::Div);
static const Token pLeft(Operator::LParen), pRight(Operator::RParen);
static const Token _1(1), _2(2), _3(3), _4(4), _5(5);
В итоге следующий тест будет выглядеть гораздо компактнее и понятнее.
TEST_METHOD(Should_parse_expression_with_parens_in_beginning) {
Tokens tokens = Parser::Parse({ pLeft, _1, plus, _2, pRight, mul, _3 });
AssertRange::AreEqual({ _1, _2, plus, _3, mul }, tokens);
}
Изменим метод ParseOperator класса ShuntingYardParser таким образом, чтобы он соответствовал описанному выше алгоритму.
void ParseOperator() {
switch(*m_current) {
case Operator::LParen:
m_stack.push_back(*m_current);
break;
case Operator::RParen:
PopToOutputUntil([this]() { return LeftParenOnTop(); });
m_stack.pop_back();
break;
default:
PopToOutputUntil([this]() { return LeftParenOnTop() || OperatorWithLessPrecedenceOnTop(); });
m_stack.push_back(*m_current);
break;
}
}
bool OperatorWithLessPrecedenceOnTop() const {
return PrecedenceOf(m_stack.back()) < PrecedenceOf(*m_current);
}
bool LeftParenOnTop() const {
return static_cast<Operator>(m_stack.back()) == Operator::LParen;
}
У нас отсутствует какая-либо проверка на соответствие закрывающих скобок открывающим. Для тестирования генерации исключений, в классе Assert есть специальный метод ExpectException, принимающий в качестве параметра шаблона тип исключения, которое должно быть сгенерировано.
TEST_METHOD(Should_throw_when_opening_paren_not_found) {
Assert::ExpectException<std::logic_error>([]() {Parser::Parse({ _1, pRight }); });
}
Добавим проверку на наличие открывающий скобки при обработке закрывающей скобки.
…
case Operator::RParen:
PopToOutputUntil([this]() { return LeftParenOnTop(); });
if(m_stack.empty() || m_stack.back() != Operator::LParen) {
throw std::logic_error("Opening paren not found.");
}
m_stack.pop_back();
break;
Теперь тест на отсутствие закрывающей скобки.
TEST_METHOD(Should_throw_when_closing_paren_not_found) {
Assert::ExpectException<std::logic_error>([]() {Parser::Parse({ pLeft, _1 }); });
}
Данную ситуацию можно определить по наличию открывающий скобки в стеки на конец разбора.
void Parse() {
for(; m_current != m_end; ++m_current) {
ParseCurrentToken();
}
PopToOutputUntil([this]() {
if(m_stack.back() == Token(Operator::LParen)) {
throw std::logic_error("Closing paren not found.");
}
return false;
});
}
Итак, все тесты проходят, можно привести код в классе ShuntingYardParser в порядок.
Класс ShuntingYardParser после рефакторинга
class ShuntingYardParser {
public:
ShuntingYardParser(const Tokens &tokens) : m_current(tokens.cbegin()), m_end(tokens.cend()) {}
void Parse() {
for(; m_current != m_end; ++m_current) {
ParseCurrentToken();
}
PopToOutputUntil([this]() {return StackHasNoOperators(); });
}
const Tokens &Result() const { return m_output; }
private:
void ParseCurrentToken() {
switch(m_current->Type()) {
case TokenType::Operator:
ParseOperator();
break;
case TokenType::Number:
ParseNumber();
break;
default: throw std::out_of_range("TokenType");
}
}
bool StackHasNoOperators() const {
if(m_stack.back() == Token(Operator::LParen)) {
throw std::logic_error("Closing paren not found.");
}
return false;
}
void ParseOperator() {
switch(*m_current) {
case Operator::LParen:
PushCurrentToStack();
break;
case Operator::RParen:
PopToOutputUntil([this]() { return LeftParenOnTop(); });
PopLeftParen();
break;
default:
PopToOutputUntil([this]() { return LeftParenOnTop() || OperatorWithLessPrecedenceOnTop(); });
PushCurrentToStack();
break;
}
}
void PushCurrentToStack() {
return m_stack.push_back(*m_current);
}
void PopLeftParen() {
if(m_stack.empty() || m_stack.back() != Operator::LParen) {
throw std::logic_error("Opening paren not found.");
}
m_stack.pop_back();
}
bool OperatorWithLessPrecedenceOnTop() const {
return PrecedenceOf(m_stack.back()) < PrecedenceOf(*m_current);
}
bool LeftParenOnTop() const {
return static_cast<Operator>(m_stack.back()) == Operator::LParen;
}
void ParseNumber() {
m_output.push_back(*m_current);
}
template<class T>
void PopToOutputUntil(T whenToEnd) {
while(!m_stack.empty() && !whenToEnd()) {
m_output.push_back(m_stack.back());
m_stack.pop_back();
}
}
Tokens::const_iterator m_current, m_end;
Tokens m_output, m_stack;
};
Для уверенности можно написать тест на разбор сложного выражения.
TEST_METHOD(Should_parse_complex_experssion_with_paren) {
// (1+2)*(3/(4-5)) = 1 2 + 3 4 5 - / *
Tokens tokens = Parser::Parse({ pLeft, _1, plus, _2, pRight, mul, pLeft, _3, div, pLeft, _4, minus, _5, pRight, pRight });
AssertRange::AreEqual({ _1, _2, plus, _3, _4, _5, minus, div, mul }, tokens);
}
Он сразу проходит, что и было ожидаемо.
Весь код на данный момент:
Interpreter.h
#pragma once;
#include <vector>
#include <wchar.h>
#include <algorithm>
namespace Interpreter {
enum class Operator : wchar_t {
Plus = L'+',
Minus = L'-',
Mul = L'*',
Div = L'/',
LParen = L'(',
RParen = L')',
};
inline std::wstring ToString(const Operator &op) {
return{ static_cast<wchar_t>(op) };
}
enum class TokenType {
Operator,
Number
};
inline std::wstring ToString(const TokenType &type) {
switch(type) {
case TokenType::Operator:
return L"Operator";
case TokenType::Number:
return L"Number";
default:
throw std::out_of_range("TokenType");
}
}
class Token {
public:
Token(Operator op) :m_type(TokenType::Operator), m_operator(op) {}
Token(double num) :m_type(TokenType::Number), m_number(num) {}
TokenType Type() const {
return m_type;
}
operator Operator() const {
if(m_type != TokenType::Operator) {
throw std::logic_error("Should be operator token.");
}
return m_operator;
}
operator double() const {
if(m_type != TokenType::Number) {
throw std::logic_error("Should be number token.");
}
return m_number;
}
friend inline bool operator==(const Token &left, const Token &right) {
if(left.m_type == right.m_type) {
switch(left.m_type) {
case Interpreter::TokenType::Operator:
return left.m_operator == right.m_operator;
case Interpreter::TokenType::Number:
return left.m_number == right.m_number;
default:
throw std::out_of_range("TokenType");
}
}
return false;
}
private:
TokenType m_type;
union {
Operator m_operator;
double m_number;
};
};
inline std::wstring ToString(const Token &token) {
switch(token.Type()) {
case TokenType::Number:
return std::to_wstring(static_cast<double>(token));
case TokenType::Operator:
return ToString(static_cast<Operator>(token));
default:
throw std::out_of_range("TokenType");
}
}
typedef std::vector<Token> Tokens;
namespace Lexer {
namespace Detail {
class Tokenizer {
public:
Tokenizer(const std::wstring &expr) : m_current(expr.c_str()) {}
void Tokenize() {
while(!EndOfExperssion()) {
if(IsNumber()) {
ScanNumber();
}
else if(IsOperator()) {
ScanOperator();
}
else {
MoveNext();
}
}
}
const Tokens &Result() const {
return m_result;
}
private:
bool EndOfExperssion() const {
return *m_current == L'';
}
bool IsNumber() const {
return iswdigit(*m_current) != 0;
}
void ScanNumber() {
wchar_t *end = nullptr;
m_result.push_back(wcstod(m_current, &end));
m_current = end;
}
bool IsOperator() const {
auto all = { Operator::Plus, Operator::Minus, Operator::Mul, Operator::Div, Operator::LParen, Operator::RParen };
return std::any_of(all.begin(), all.end(), [this](Operator o) {return *m_current == static_cast<wchar_t>(o); });
}
void ScanOperator() {
m_result.push_back(static_cast<Operator>(*m_current));
MoveNext();
}
void MoveNext() {
++m_current;
}
const wchar_t *m_current;
Tokens m_result;
};
} // namespace Detail
inline Tokens Tokenize(const std::wstring &expr) {
Detail::Tokenizer tokenizer(expr);
tokenizer.Tokenize();
return tokenizer.Result();
}
} // namespace Lexer
namespace Parser {
inline int PrecedenceOf(Operator op) {
return (op == Operator::Mul || op == Operator::Div) ? 1 : 0;
}
namespace Detail {
class ShuntingYardParser {
public:
ShuntingYardParser(const Tokens &tokens) : m_current(tokens.cbegin()), m_end(tokens.cend()) {}
void Parse() {
for(; m_current != m_end; ++m_current) {
ParseCurrentToken();
}
PopToOutputUntil([this]() {return StackHasNoOperators(); });
}
const Tokens &Result() const {
return m_output;
}
private:
void ParseCurrentToken() {
switch(m_current->Type()) {
case TokenType::Operator:
ParseOperator();
break;
case TokenType::Number:
ParseNumber();
break;
default:
throw std::out_of_range("TokenType");
}
}
bool StackHasNoOperators() const {
if(m_stack.back() == Token(Operator::LParen)) {
throw std::logic_error("Closing paren not found.");
}
return false;
}
void ParseOperator() {
switch(*m_current) {
case Operator::LParen:
PushCurrentToStack();
break;
case Operator::RParen:
PopToOutputUntil([this]() { return LeftParenOnTop(); });
PopLeftParen();
break;
default:
PopToOutputUntil([this]() { return LeftParenOnTop() || OperatorWithLessPrecedenceOnTop(); });
PushCurrentToStack();
break;
}
}
void PushCurrentToStack() {
return m_stack.push_back(*m_current);
}
void PopLeftParen() {
if(m_stack.empty() || m_stack.back() != Operator::LParen) {
throw std::logic_error("Opening paren not found.");
}
m_stack.pop_back();
}
bool OperatorWithLessPrecedenceOnTop() const {
return PrecedenceOf(m_stack.back()) < PrecedenceOf(*m_current);
}
bool LeftParenOnTop() const {
return static_cast<Operator>(m_stack.back()) == Operator::LParen;
}
void ParseNumber() {
m_output.push_back(*m_current);
}
template<class T>
void PopToOutputUntil(T whenToEnd) {
while(!m_stack.empty() && !whenToEnd()) {
m_output.push_back(m_stack.back());
m_stack.pop_back();
}
}
Tokens::const_iterator m_current;
Tokens::const_iterator m_end;
Tokens m_output;
Tokens m_stack;
};
} // namespace Detail
inline Tokens Parse(const Tokens &tokens) {
Detail::ShuntingYardParser parser(tokens);
parser.Parse();
return parser.Result();
}
} // namespace Parser
} // namespace Interpreter
InterpreterTests.cpp
#include "stdafx.h"
#include "CppUnitTest.h"
#include "Interpreter.h"
#pragma warning(disable: 4505)
namespace InterpreterTests {
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
using namespace Interpreter;
using namespace std;
namespace AssertRange {
template<class T, class ActualRange>
static void AreEqual(initializer_list<T> expect, const ActualRange &actual) {
auto actualIter = begin(actual);
auto expectIter = begin(expect);
Assert::AreEqual(distance(expectIter, end(expect)), distance(actualIter, end(actual)), L"Size differs.");
for(; expectIter != end(expect) && actualIter != end(actual); ++expectIter, ++actualIter) {
auto message = L"Mismatch in position " + to_wstring(distance(begin(expect), expectIter));
Assert::AreEqual<T>(*expectIter, *actualIter, message.c_str());
}
}
} // namespace AssertRange
static const Token plus(Operator::Plus), minus(Operator::Minus);
static const Token mul(Operator::Mul), div(Operator::Div);
static const Token pLeft(Operator::LParen), pRight(Operator::RParen);
static const Token _1(1), _2(2), _3(3), _4(4), _5(5);
TEST_CLASS(LexerTests) {
public:
TEST_METHOD(Should_return_empty_token_list_when_put_empty_expression) {
Tokens tokens = Lexer::Tokenize(L"");
Assert::IsTrue(tokens.empty());
}
TEST_METHOD(Should_tokenize_single_plus_operator) {
Tokens tokens = Lexer::Tokenize(L"+");
AssertRange::AreEqual({ plus }, tokens);
}
TEST_METHOD(Should_tokenize_single_digit) {
Tokens tokens = Lexer::Tokenize(L"1");
AssertRange::AreEqual({ _1 }, tokens);
}
TEST_METHOD(Should_tokenize_floating_point_number) {
Tokens tokens = Lexer::Tokenize(L"12.34");
AssertRange::AreEqual({ 12.34 }, tokens);
}
TEST_METHOD(Should_tokenize_plus_and_number) {
Tokens tokens = Lexer::Tokenize(L"+12.34");
AssertRange::AreEqual({ plus, Token(12.34) }, tokens);
}
TEST_METHOD(Should_skip_spaces) {
Tokens tokens = Lexer::Tokenize(L" 1 + 12.34 ");
AssertRange::AreEqual({ _1, plus, Token(12.34) }, tokens);
}
TEST_METHOD(Should_tokenize_complex_experssion) {
Tokens tokens = Lexer::Tokenize(L"1+2*3/(4-5)");
AssertRange::AreEqual({ _1, plus, _2, mul, _3, div, pLeft, _4, minus, _5, pRight }, tokens);
}
};
TEST_CLASS(TokenTests) {
public:
TEST_METHOD(Should_get_type_for_operator_token) {
Token opToken(Operator::Plus);
Assert::AreEqual(TokenType::Operator, opToken.Type());
}
TEST_METHOD(Should_get_type_for_number_token) {
Token numToken(1.2);
Assert::AreEqual(TokenType::Number, numToken.Type());
}
TEST_METHOD(Should_get_operator_code_from_operator_token) {
Token token(Operator::Plus);
Assert::AreEqual<Operator>(Operator::Plus, token);
}
TEST_METHOD(Should_get_number_value_from_number_token) {
Token token(1.23);
Assert::AreEqual<double>(1.23, token);
}
};
TEST_CLASS(ParserTests) {
public:
TEST_METHOD(Should_return_empty_list_when_put_empty_list) {
Tokens tokens = Parser::Parse({});
Assert::IsTrue(tokens.empty());
}
TEST_METHOD(Should_parse_single_number) {
Tokens tokens = Parser::Parse({ _1 });
AssertRange::AreEqual({ _1 }, tokens);
}
TEST_METHOD(Should_parse_num_plus_num) {
Tokens tokens = Parser::Parse({ _1, plus, _2 });
AssertRange::AreEqual({ _1, _2, plus }, tokens);
}
TEST_METHOD(Should_parse_two_additions) {
Tokens tokens = Parser::Parse({ _1, plus, _2, plus, _3 });
AssertRange::AreEqual({ _1, _2, plus, _3, plus }, tokens);
}
TEST_METHOD(Should_get_same_precedence_for_operator_pairs) {
Assert::AreEqual(Parser::PrecedenceOf(Operator::Plus), Parser::PrecedenceOf(Operator::Minus));
Assert::AreEqual(Parser::PrecedenceOf(Operator::Mul), Parser::PrecedenceOf(Operator::Div));
}
TEST_METHOD(Should_get_greater_precedence_for_multiplicative_operators) {
Assert::IsTrue(Parser::PrecedenceOf(Operator::Mul) > Parser::PrecedenceOf(Operator::Plus));
}
TEST_METHOD(Should_parse_add_and_mul) {
Tokens tokens = Parser::Parse({ _1, plus, _2, mul, _3 });
AssertRange::AreEqual({ _1, _2, _3, mul, plus }, tokens);
}
TEST_METHOD(Should_parse_complex_experssion) {
Tokens tokens = Parser::Parse({ _1, plus, _2, div, _3, minus, _4, mul, _5 });
AssertRange::AreEqual({ _1, _2, _3, div, plus, _4, _5, mul, minus }, tokens);
}
TEST_METHOD(Should_skip_parens_around_number) {
Tokens tokens = Parser::Parse({ pLeft, _1, pRight });
AssertRange::AreEqual({ _1 }, tokens);
}
TEST_METHOD(Should_parse_expression_with_parens_in_beginning) {
Tokens tokens = Parser::Parse({ pLeft, _1, plus, _2, pRight, mul, _3 });
AssertRange::AreEqual({ _1, _2, plus, _3, mul }, tokens);
}
TEST_METHOD(Should_throw_when_opening_paren_not_found) {
Assert::ExpectException<std::logic_error>([]() {Parser::Parse({ _1, pRight }); });
}
TEST_METHOD(Should_throw_when_closing_paren_not_found) {
Assert::ExpectException<std::logic_error>([]() {Parser::Parse({ pLeft, _1 }); });
}
TEST_METHOD(Should_parse_complex_experssion_with_paren) {
// (1+2)*(3/(4-5)) = 1 2 + 3 4 5 - / *
Tokens tokens = Parser::Parse({ pLeft, _1, plus, _2, pRight, mul, pLeft, _3, div, pLeft, _4, minus, _5, pRight, pRight });
AssertRange::AreEqual({ _1, _2, plus, _3, _4, _5, minus, div, mul }, tokens);
}
};
}
Код к статье на GitHub. Названия коммитов и их порядок соответствуют тестам и рефакторингам, описанным выше. Окончанию первой части соответствует коммит «ParserTests Should_parse_complex_experssion_with_paren».
В следующий части будет рассмотрена разработка вычислителя и фасада для всего интерпретатора, а также рефакторинг всего кода для устранения дублирования.
Автор: Unrul
