Unrul Aug 4 2014 at 17:36

Пишем простой интерпретатор на C++ с помощью TDD, часть 2

16 min

14K

Tutorial

В первой части был написан лексер. Далее будет рассмотрена разработка парсера.

Парсер

Парсер будет реализован по алгоритму сортировочной станции, так как он достаточно прост и не нуждается в рекурсии. Сам алгоритм таков:

В начале даются пустой выходной поток и пустой стек. Начнём читать токены из входного потока по очереди.

Если это число, то передать его в выходной поток.
Если это лево ассоциативный оператор, то выталкиваем токены из стека в выходной поток до тех пор, пока он не опустеет, либо не его вершине не встретится скобка, или оператор с более низким приоритетом.
Если это открывающая скобка, то положить её в стек.
Если это закрывающая скобка, то выталкиваем токены из стека в выходной поток до обнаружения открывающей скобки. Вытолкнуть открывающую скобку из стека, но не передавать её в выходной поток. Если стек опустел, и скобка не найдена, то генерируем ошибку.

После достижения конца входного потока, вытолкнуть все оставшиеся в стеке операторы в выходной поток. Если в нём найдено что-либо кроме операторов, то генерируем ошибку.

Прикинем, какие тесты могут понадобиться для начала.

При получении пустого списка, возвращается пустой список.
При получении списка с одним числом, возвращается список с этим числом.
При получении [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 &current : 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'\0';
    }

    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. Названия коммитов и их порядок соответствуют тестам и рефакторингам, описанным выше. Окончанию второй части соответствует метка «Конец_второй_части»

В следующий части будет рассмотрена разработка вычислителя и фасада для всего интерпретатора, а также рефакторинг всего кода для устранения дублирования.

Tags:

Hubs: