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

  • Tutorial

Введение



Многие C++ программисты слышали про разработку через тестирование. Но почти все материалы по данной теме касаются более высокоуровневых языков и сосредоточены больше на общей теории, чем на практике. Итак, в данной статье я попробую привести пример пошаговой разработки через тестирование небольшого проекта на C++. А именно, как можно предположить из названия, простого интерпретатора математических выражений. Такой проект также является неплохой code kata, так как на его выполнение затрачивается не более часа (если не писать параллельно статью об этом).

Архитектура


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

Существует множество библиотек и инструментов, которые могут облегчить разработку интерпретаторов и компиляторов. Начиная от Boost.Spirit и заканчивая ANTLR и Bison. Можно даже запустить канал интерпретатора командной строки через popen и вычислить выражение через него. Целью данной статье является пошаговая разработка достаточно сложной системы с помощью TDD, поэтому будет использоваться только стандартная библиотека C++ и встроенный в IDE тестовый фреймворк.

Для начала, составим список того, что должен уметь наш простой интерпретатор, в порядке убывания приоритета:

  • Вычислять значение математического выражения, состоящего из чисел с плавающий точкой и математических операторов (-+/*).
  • Учёт приоритета операторов.
  • Учёт скобок.
  • Унарные плюс и минус.
  • Вычисление нескольких выражений, разделённых точкой с запятой (;).
  • Встроенные константы (pi, e).
  • Создание собственных констант с помощью оператора присваивания (=).
  • Встроенные функции с переменным числом аргументов.
  • Задание новых функций.

В данной статье будет реализация только первых трёх пунктов. Сам проект концептуально будет состоять из четырёх частей:

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

Инструментарий


Программа будет писаться в Visual Studio 2013 с установленным Visual C++ Compiler Nov 2013 CTP. Тесты будут на основе встроенного в студию тестового фреймворка для C++ проектов CppUnitTestFramework. Он предоставляет минимальную поддержку для написания модульных тестов (по сравнению с Boost.Test, или CppUTest), но, с другой стороны, хорошо интегрирован в среду разработки. Альтернативой может служить Eclipse с установленным плагином C/C++ Unit и настроенным Boost.Test, GTest, или QtTest. В такой конфигурации рекомендую использовать clang, так как он предоставляет несколько мощнейших compile- и runtime анализаторов, в результате чего, в связке с TDD, код становится совершенно неуязвимым для ошибок.

Итак, создадим новый проект типа «Native Unit Test Project» и удостоверимся, что всё компилируется.

Лексер


Начнём с разработки лексера. Будем следовать привычному для TDD циклу Red-Green-Refactor:

  1. Написать тест и заставить его падать (Red).
  2. Заставить его пройти (Green).
  3. Улучшить дизайн (Refactor).

Напишем первый тест, поместив его в класс LexerTests. Я буду пользоваться такой техникой, как список тестов, в который будут записываться те тесты, которые я планирую написать следующими. Также в него заносятся мысли о предстоящих тестах, которые часто возникают во время написания текущего теста и не могут быть реализованы сразу же:

  • В ответ на пустое выражение, должен возвращаться пустой список токенов.

Я привык писать названия тестов в BDD стиле. Каждый тест начинается со слова Should, в качестве субъекта подразумевается то, что упомянуто в названии класса. То есть Lexer … should … сделать A в ответ на B. Это фокусирует тест на небольшом аспекте поведения и не даёт ему расти в объёме.

TEST_CLASS(LexerTests) {
public:
    TEST_METHOD(Should_return_empty_token_list_when_put_empty_expression) {
        Tokens tokens = Lexer::Tokenize("");
        Assert::IsTrue(tokens.empty());
    }
};

В CppUnitTestFramework макрос TEST_CLASS генерирует класс, в котором будут размещаться тестовые методы. Макрос TEST_METHOD, соответственно, создаёт сам тестовый метод. Необходимо учесть, что экземпляр класса создаётся только один раз перед запуском всех находящихся в нём тестов. В Boost.Test, к примеру, экземпляр класса создаётся каждый раз заново перед запуском каждого теста. Следовательно, тот, код, который необходимо выполнить перед каждым тестом, будет помещаться в метод, объявленный с помощью макроса TEST_METHOD_INITIALIZE, а тот, который после, в TEST_METHOD_CLEANUP. Все методы утверждений являются статическими и располагаются в классе Assert. Их немного, но основную функциональность они покрывают.

Вернёмся к нашему тесту. Он не то, чтобы не проходит, он даже не компилируется. Создадим функцию Tokenize в пространстве имён Lexer, принимающую строку и возвращающую std::vector, скрытый для удобства за псевдонимом Tokens. Я решил пока что не создавать дополнительные классы и ограничиться обычной функцией.

#pragma once;
#include <vector>

namespace Interpreter {

struct Token {};
typedef std::vector<Token> Tokens;

namespace Lexer {
inline Tokens Tokenize(std::string expr) { throw std::exception(); }
} // namespace Lexer
} // namespace Interpreter

Сейчас проект компилируется, но тест, что было ожидаемо, падает. Для определения того, что же писать дальше, можно воспользоваться техникой The Transformation Priority Premise (TPP) авторства Роберта Мартина. Трансформации являются аналогами рефакторингов, но, в отличии от них, используются для изменения поведения кода, тогда как рефакторинг к изменению поведения не приводит. Каждая трансформация ведёт к изменению кода от более конкретного к более общему. Главная их особенность в том, что они имеют разные приоритеты, в зависимости от которых выбирается то, какой код писать для прохождения теста и какой будет следующий тест. А именно, те трансформации, которые проще (располагаются выше в списке) должны быть более предпочтительны, чем те, которые снизу. При намерении создать новый тест, выбирается такой, что для его прохождения нужно применить более простую трансформацию. Это не является строгим правилом, но следование TPP может вести к более простому коду за меньшее количество шагов.

Сам список трансформаций:

  1. ({} → nil) Заменить отсутствие кода на код, использующий нулевое значение.
  2. (nil → constant) Заменить нулевое значение константой.
  3. (constant → constant+) Заменить простую константу более сложной (строку из одной буквы на строку из нескольких букв, к примеру).
  4. (constant → scalar) Заменить константу на переменную, или аргумент.
  5. (statement → statements) Добавить безусловный оператор (break, continue, return и подобное).
  6. (unconditional → if) Разбить поток выполнения с помощью условного оператора.
  7. (scalar → array) Заменить переменную/аргумент массивом.
  8. (array → container) Заменить массив более сложным контейнером.
  9. (statement → recursion) Заменить выражение рекурсией.
  10. (if → while) Заменить условный оператор циклом.
  11. (expression → function) Заменить выражение функцией.
  12. (variable → assignment) Изменить значение переменной.

Применим первую трансформацию для прохождения написанного выше теста.

inline Tokens Tokenize(std::string expr) { return{}; }

Посмотрим, что должен уметь лексер для выполнения первого пункта требований. Занесём это в список тестов.

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

Отрефакторим код, заменив std::string на std::wstring. Это будет полезно для упрощения интеграции с тестовым фреймворком, так как он принимает только Unicode. Напишем тест из второго пункта.

    TEST_METHOD(Should_tokenize_single_plus_operator) {
        Tokens tokens = Lexer::Tokenize(L"+");
        AssertRange::AreEqual({ Operator::Plus }, tokens);
    }

Здесь AssertRange - это пространство имён, в которое я поместил функцию утверждения AreEqual, сравнивающую две последовательности, а точнее, список инициализации и последовательность.

AssertRange
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(*expectIter, *actualIter, message.c_str());
    }
}
} // namespace AssertRange


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

enum class Operator : wchar_t {
    Plus = L'+',
};
typedef Operator Token;

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

std::wstring ToString(const Token &)
inline std::wstring ToString(const Token &token) {
    return{ static_cast<wchar_t>(token) };
}


После этого тест компилируется, но не проходит, так как мы продолжаем возвращать пустую последовательность токенов. Исправим это, применив трансформацию (unconditional → if).

inline Tokens Tokenize(std::wstring expr) {
    if(expr.empty()) { return{}; }
    return{ static_cast<Operator>(expr[0]) };
}

  • В ответ на пустое выражение должен возвращаться пустой список токенов.
  • В ответ на строку с оператором должен возвращаться токен с оператором.
  • В ответ на строку с цифрой должен возвращаться токен с числом.

Теперь третий тест.

    TEST_METHOD(Should_tokenize_single_digit) {
        Tokens tokens = Lexer::Tokenize(L"1");
        AssertRange::AreEqual({ 1.0 }, tokens);
    }

Здесь возникает проблема представления токенов. С одной стороны, они должны хранить коды операторов, с другой - числа. Решений в данном случае, несколько:

  • Создать два класса токенов для операторов и числе, унаследовав их от общего класса Token. После этого приводить его с помощью dynamic_cast для извлечения кода числа, или кода оператора.
  • То же, что в варианте выше, но вместо каста использовать двойную диспетчеризацию.
  • В качестве токенов может быть std::function в которой будет храниться замыкание с необходимыми данными. Получать данные из замыкания можно с помощью посетителя.
  • Использовать Boost.Any, или что-либо подобное.
  • Использовать обычную структуру с полями для каждого вида данный и флагом типа.

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

  • Создать токен с оператором и получить его тип.
  • Создать токен с числом и получить его тип.
  • Создать токен с оператором и получить этот оператор.
  • Создать токен с числом и получить это число.

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

enum class TokenType {
    Operator,
    Number
};
class Token {
public:
    Token(Operator) {}

    TokenType Type() const { return TokenType::Operator; }
};
…
TEST_CLASS(TokenTests) {
public:
    TEST_METHOD(Should_get_type_for_operator_token) {
        Token opToken(Operator::Plus);
        Assert::AreEqual(TokenType::Operator, opToken.Type());
    }
};

Добавив метод ToString для перечисления TokenType и подправив аналогичный метод для самого токена, заставим всё компилироваться, а тесты проходить. Напишем следующий тест из списка.

    TEST_METHOD(Should_get_type_for_number_token) {
        Token numToken(1.2);
        Assert::AreEqual(TokenType::Number, numToken.Type());
    }

Он не проходит. Примени трансформацию (constant → scalar) для класса токена.

class Token {
public:
    Token(Operator) :m_type(TokenType::Operator) {}
    Token(double) :m_type(TokenType::Number) {}
    TokenType Type() const { return m_type; }
 
private:
    TokenType m_type;
};

  • Создать токен с оператором и получить его тип.
  • Создать токен с числом и получить его тип.
  • Создать токен с оператором и получить этот оператор.
  • Создать токен с числом и получить это число.

Теперь реализуем оставшиеся тесты.

    TEST_METHOD(Should_get_operator_code_from_operator_token) {
        Token token(Operator::Plus);
        Assert::AreEqual<Operator>(Operator::Plus, token);
    }

Для удобства преобразования токена к нужному типу будем использовать оператор неявного приведения.

class Token {
public:
    Token(Operator op) :m_type(TokenType::Operator), m_operator(op) {}
    operator Operator() const { return m_operator; }
    …
    Operator m_operator;
};

Аналогично напишем тест для числового токена.

    TEST_METHOD(Should_get_number_value_from_number_token) {
        Token token(1.23);
        Assert::AreEqual<double>(1.23, token);
    }

Так как в токене не может одновременно храниться и оператор, и число, то их поля можно объединить в union. Также добавим проверку на операцию приведения к неверному типу.

Token
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;
    }

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: return "Unknown token.";
    }
}


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

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

Для прохождения теста добавим ещё одно условное выражение:

    if(expr[0] >= '0' && expr[0] <= '9') {
        return{ (double) expr[0] - '0' };
    }
    return{ static_cast<Operator>(expr[0]) };

Выгладит пока что не очень симпатично, но тест проходит.

  • В ответ на строку с цифрой должен возвращаться токен с числом.
  • В ответ на строку с числом с плавающей точкой должен возвращаться токен с этим числом.

    TEST_METHOD(Should_tokenize_floating_point_number) {
        Tokens tokens = Lexer::Tokenize(L"12.34");
        AssertRange::AreEqual({ 12.34 }, tokens);
    }

Вспомним, что в стандартной библиотеке C есть такие функции, как isdigit, проверяющая, что данный символ является цифрой и atof, преобразующая строку в число, а также их аналоги для wchar_t. Применим (expression → function). После этого небольшого изменения данный тест также начал проходить.

inline Tokens Tokenize(std::wstring expr) {
    const wchar_t *current = expr.c_str();
    if(!*current) return{};
    if(iswdigit(*current)) return{ _wtof(current) };
    return{ static_cast<Operator>(*current) };
}

После этого можно приступить и к более сложным тестам. Попробуем обработать полюс и число одновременно.

    TEST_METHOD(Should_tokenize_plus_and_number) {
        Tokens tokens = Lexer::Tokenize(L"+12.34");
        AssertRange::AreEqual({ Token(Operator::Plus), Token(12.34) }, tokens);
    }

Тест не компилируется, так как не хватает оператора сравнения для токена. Исправим это, теперь тест просто не проходит. Для начала сделаем небольшой рефакторинг. Добавим переменную result, в которую будем помещать токены.

inline Tokens Tokenize(std::wstring expr) {
    Tokens result;
    const wchar_t *current = expr.c_str();
    if(!*current) return result;
    if(iswdigit(*current)) {
        result.push_back(_wtof(current));
    }
    else {
        result.push_back(static_cast<Operator>(*current));
    }
    return result;
}

Теперь заставить пройти тест довольно просто: применим трансформацию (if → while). Можно было бы использовать рекурсию, но я решил целенаправленно делать не рекурсивный алгоритм.

inline Tokens Tokenize(std::wstring expr) {
    Tokens result;
    const wchar_t *current = expr.c_str();
    while(*current) {
        if(iswdigit(*current)) {
            wchar_t *end = nullptr;
            result.push_back(wcstod(current, &end));
            current = end;
        }
        else {
            result.push_back(static_cast<Operator>(*current));
            ++current;
        }
    }
    return result;
}

Функция wcstod делает то же самое, что и _wtof, но также возвращает указатель на следующий за числом символ в строке. Так как все операторы на данный момент состоят из одного символа, то во втором случае просто передвигаем указатель на текущий символ на одну позицию вперёд. Как видим, теперь все тесты проходят.

  • В ответ на строку с простым выражением должен возвращаться список соответствующих токенов.
  • Пробелы между числами и операторами должны игнорироваться.

Разберёмся с пробелами.

    TEST_METHOD(Should_skip_spaces) {
        Tokens tokens = Lexer::Tokenize(L" 1 +  12.34  ");
        AssertRange::AreEqual({ Token(1.0), Token(Operator::Plus), Token(12.34) }, tokens);
    }

Применим (unconditional → if) добавив проверку на то, что символ является оператором.

    while(*current) {
        if(iswdigit(*current)) {
            wchar_t *end = nullptr;
            result.push_back(wcstod(current, &end));
            current = end;
        }
        else if(*current == static_cast<wchar_t>(Operator::Plus)) {
            result.push_back(static_cast<Operator>(*current));
            ++current;
        }
        else {
            ++current;
        }
    }

На данном этапе проведём рефакторинг данной функции. Выделим логику в отдельный класс и разобьём на отдельный методы. Поместим этот класс в пространство имён Detail чтобы не засорять публичный интерфейс лексера. Теперь функция Tokenize просто будет служить фасадом для модуля лексера.

inline Tokens Tokenize(const std::wstring &expr) {
    Detail::Tokenizer tokenizer(expr);
    tokenizer.Tokenize();
    return tokenizer.Result();
}

Класс Detail::Tokenizer
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 { return *m_current == static_cast<wchar_t>(Operator::Plus); }

    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


Как видно, извлечение класса сделало код гораздо понятнее. Без тестов такой рефакторинг был бы, как минимум, рискованным. Теперь добавим поддержку скобок и остальных операторов.

    TEST_METHOD(Should_tokenize_complex_experssion) {
        Tokens tokens = Lexer::Tokenize(L"1+2*3/(4-5)");
        AssertRange::AreEqual({
            Token(1), Token(Operator::Plus), Token(2), Token(Operator::Mul), Token(3), Token(Operator::Div),
            Token(Operator::LParen), Token(4), Token(Operator::Minus), Token(5), Token(Operator::RParen)
        }, tokens);
    }

Добавим необходимые операторы к перечислению Operator, чтобы заставить тест компилироваться.

enum class Operator : wchar_t {
    Plus = L'+',
    Minus = L'-',
    Mul = L'*',
    Div = L'/',
    LParen = L'(',
    RParen = L')',
};

Тест не проходит. Чтобы это исправить необходимо всего лишь изменить метод IsOperator класса Tokenizer.

    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); });
    }

Все тесты проходят и можно приступить к написанию парсера. Ниже приводится весь исходный код на данный момент.

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 Interpreter


InterpreterTests.cpp
#include "stdafx.h"
#include "CppUnitTest.h"
#include "Interpreter.h"

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

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({ Operator::Plus }, tokens);
    }

    TEST_METHOD(Should_tokenize_single_digit) {
        Tokens tokens = Lexer::Tokenize(L"1");
        AssertRange::AreEqual({ 1.0 }, 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({ Token(Operator::Plus), Token(12.34) }, tokens);
    }

    TEST_METHOD(Should_skip_spaces) {
        Tokens tokens = Lexer::Tokenize(L" 1 +  12.34  ");
        AssertRange::AreEqual({ Token(1.0), Token(Operator::Plus), Token(12.34) }, tokens);
    }

    TEST_METHOD(Should_tokenize_complex_experssion) {
        Tokens tokens = Lexer::Tokenize(L"1+2*3/(4-5)");
        AssertRange::AreEqual({
            Token(1), Token(Operator::Plus), Token(2), Token(Operator::Mul), Token(3), Token(Operator::Div),
            Token(Operator::LParen), Token(4), Token(Operator::Minus), Token(5), Token(Operator::RParen)
        }, 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);
    }
};

}


Код к статье на GitHub. Названия коммитов и их порядок соответствуют тестам и рефакторингам, описанным выше. Окончанию первой части соответствует метка "Конец_первой_части".

Разработка парсера будет рассмотрена во второй части. Разработка вычислителя и фасада для парсера, а также рефакторинг всего кода будут рассмотрены в третьей части.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 9

    +3
    Спасибо за содержательный пример TDD! Но раз уж пошла речь о интерпретации, рекомендую глянуть вот эту вот статью:
    epaperpress.com/lexandyacc/download/LexAndYaccTutorial.pdf
    В ней освещается хороший инструментарий, который уже имеет разделение на мощный лексер и мощный парсер, умеющий удобно разбирать грамматики, записанные в БНФ
      +1
      Благодарю за замечание. Я добавил в начало статьи параграф с объяснением, почему используется только возможности C++ и стандартной библиотеки.
        +1
        Однако, замечание вообще ценное.

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

        Хорошие инструменты позволяют тратить меньше времени на написание и тестирование парсеров, так как отлаживать необходимо только генератор парсеров и только его авторам. Пользователи могут считать, что генератор безошибочно переводит специфицикацию в код.

        Тем не менее, суть TDD не столько в самих тестах и корректности, сколько в разработке архитектуры под тестируемость. Так что в данном случае замечения не вполне уместно. Хотя да, лично мне было бы интереснее посмотреть на разработку более поздних этапов.
      0
      Вроде все хорошо, но почему строки по значению передаете?
      А большинство push_back можно заменить на emplace_back.
        0
        Ближе к концу строки передаются по константной ссылке, emplace_back также появляется немного позже.
        –2
        TDD и прочие практики экстремального программирования мне всегда казались извращением
          +1
          Рекомендую к прочтению книгу Agile!: The Good, the Hype and the Ugly Paperback – Bertrand Meyer, 2014. В ней как раз даётся разбор, что из XP хорохо, а что не очень. TDD не является серебряной пулей, но зачастую является очень полезной техникой.
          –5
          Программа будет писаться в Visual Studio 2013

          Дальше не читал…
            +3
            Всё то же самое можно сделать в Eclipse с установленным плагином C/C++ Unit, скачать Boost.Test, или GTest, скомпилировать их, прописать в путях проекта. Но в таком случае половина статьи будет касаться только настройки окружения. В Visual Studio 2012 и 2013 окружение, готовое к TDD создаётся за пару кликов. Хотя, для написания более сложных тесто, всё равно придётся ставить Boost.Test, или подобное.

          Only users with full accounts can post comments. Log in, please.