Рубрика «интерпретатор» - 3

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

Вычислитель

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

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

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

• Если на входе пустой список, возвращаем 0.
• Если на входе список с одним числом, возвращаем это число.
• Если на входе [1 2 +], возвращаем 3.

Создадим новый тестовый класс и добавим первый тест.

TEST_CLASS(EvaluatorTests) {
public:
    TEST_METHOD(Should_return_zero_when_evaluate_empty_list) {
        double result = Evaluator::Evaluate({});
        Assert::AreEqual(0.0, result);
    }
};

Читать полностью »

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

Парсер

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

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

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

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

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

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

Читать полностью »

Введение

Многие 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» и удостоверимся, что всё компилируется.
Читать полностью »