Пишем простой интерпретатор на C++ с помощью TDD, часть 1
Введение
Многие C++ программисты слышали про разработку через тестирование. Но почти все материалы по данной теме касаются более высокоуровневых языков и сосредоточены больше на общей теории, чем на практике. Итак, в данной статье я попробую привести пример пошаговой разработки через тестирование небольшого проекта на C++. А именно, как можно предположить из названия, простого интерпретатора математических выражений. Такой проект также является неплохой code kata, так как на его выполнение затрачивается не более часа (если не писать параллельно статью об этом).Архитектура
Несмотря на то, что при использовании TDD архитектура приложения постепенно проявляется сама собой, начальная её проработка всё же необходима. Благодаря этому может значительно снизиться общее время, затраченное на реализацию. Это особенно эффективно в тех случаях, когда существуют готовые примеры подобных систем, которые можно взять за образец. В данном случае, существует вполне устоявшееся мнение о том, как должны быть устроены компиляторы и интерпретаторы, чем и можно воспользоваться.Для начала, составим список того, что должен уметь наш простой интерпретатор, в порядке убывания приоритета:
Вычислять значение математического выражения, состоящего из чисел с плавающий точкой и математических операторов (-+/*). Учёт приоритета операторов. Учёт скобок. Унарные плюс и минус. Вычисление нескольких выражений, разделённых точкой с запятой (;). Встроенные константы (pi, e). Создание собственных констант с помощью оператора присваивания (=). Встроенные функции с переменным числом аргументов. Задание новых функций. В данной статье будет реализация только первых трёх пунктов. Сам проект концептуально будет состоять из четырёх частей: Лексический анализатор. Преобразовывает входную строку в последовательность токенов. Синтаксический анализатор. Строит из токенов синтаксическое представление в виде постфиксной нотации. Делать это будем без рекурсии и таблиц, с помощью алгоритма сортировочной станции. Вычислитель. Вычисляет результат выражения на стековой машине. Собственно, интерпретатор. Служит фасадом для вышеперечисленных частей. Инструментарий Программа будет писаться в Visual Studio 2013 с установленным Visual C++ Compiler Nov 2013 CTP. Тесты будут на основе встроенного в студию тестового фреймворка для C++ проектов CppUnitTestFramework. Он предоставляет минимальную поддержку для написания модульных тестов (по сравнению с Boost.Test, или CppUTest), но, с другой стороны, хорошо интегрирован в среду разработки.Итак, создадим новый проект типа «Native Unit Test Project» и удостоверимся, что всё компилируется.
Лексер
Начнём с разработки лексера. Будем следовать привычному для TDD циклу Red-Green-Refactor: Написать тест и заставить его падать (Red).
Заставить его пройти (Green).
Улучшить дизайн (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
#pragma once;
#include
namespace Interpreter {
struct Token {};
typedef std: vector
namespace Lexer { inline Tokens Tokenize (std: string expr) { throw std: exception (); } } // namespace Lexer } // namespace Interpreter Сейчас проект компилируется, но тест, что было ожидаемо, падает. Для определения того, что же писать дальше, можно воспользоваться техникой The Transformation Priority Premise (TPP) авторства Роберта Мартина. Трансформации являются аналогами рефакторингов, но, в отличии от них, используются для изменения поведения кода, тогда как рефакторинг к изменению поведения не приводит. Каждая трансформация ведёт к изменению кода от более конкретного к более общему. Главная их особенность в том, что они имеют разные приоритеты, в зависимости от которых выбирается то, какой код писать для прохождения теста и какой будет следующий тест. А именно, те трансформации, которые проще (располагаются выше в списке) должны быть более предпочтительны, чем те, которые снизу. При намерении создать новый тест, выбирается такой, что для его прохождения нужно применить более простую трансформацию. Это не является строгим правилом, но следование TPP может вести к более простому коду за меньшее количество шагов.Сам список трансформаций:
({} → nil) Заменить отсутствие кода на код, использующий нулевое значение.
(nil → constant) Заменить нулевое значение константой.
(constant → constant+) Заменить простую константу более сложной (строку из одной буквы на строку из нескольких букв, к примеру).
(constant → scalar) Заменить константу на переменную, или аргумент.
(statement → statements) Добавить безусловный оператор (break, continue, return и подобное).
(unconditional → if) Разбить поток выполнения с помощью условного оператора.
(scalar → array) Заменить переменную/аргумент массивом.
(array → container) Заменить массив более сложным контейнером.
(statement → recursion) Заменить выражение рекурсией.
(if → while) Заменить условный оператор циклом.
(expression → function) Заменить выражение функцией.
(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
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
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
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
void ScanOperator () {
m_result.push_back (static_cast
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
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
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
typedef std: vector
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
void ScanOperator () {
m_result.push_back (static_cast
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
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
} // 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
TEST_METHOD (Should_get_number_value_from_number_token) {
Token token (1.23);
Assert: AreEqual
} Код к статье на GitHub. Названия коммитов и их порядок соответствуют тестам и рефакторингам, описанным выше. Окончанию первой части соответствует коммит «LexerTests Should_tokenize_complex_experssion».Разработка парсера будет рассмотрена во второй части. Разработка вычислителя и фасада для парсера, а также рефакторинг всего кода будут рассмотрены в третьей части.
