Как написать интерпретатор на c

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

Многие 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:

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

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

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 namespace Interpreter < struct Token <>; typedef std::vector Tokens; 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<>; >

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

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

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

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

AssertRange

namespace AssertRange < templatestatic void AreEqual(initializer_list 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(token) >; >

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

inline Tokens Tokenize(std::wstring expr) < if(expr.empty()) < return<>; > return< static_cast(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)

Он не проходит. Примени трансформацию (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::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(1.23, token); >

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

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(token)); case TokenType::Operator: return ToString(static_cast(token)); default: return "Unknown token."; > >

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

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

 if(expr[0] >= '0' && expr[0] ; > return< static_cast(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(*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(*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(*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(Operator::Plus)) < result.push_back(static_cast(*current)); ++current; > else < ++current; >>

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

inline Tokens Tokenize(const std::wstring &expr)

Класс 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(Operator::Plus); > void ScanOperator() < m_result.push_back(static_cast(*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) (o); >); >

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

Interpreter.h

#pragma once; #include #include #include 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(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(token)); case TokenType::Operator: return ToString(static_cast(token)); default: throw std::out_of_range("TokenType"); > > typedef std::vector 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) ); > void ScanOperator() < m_result.push_back(static_cast(*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 < templatestatic void AreEqual(initializer_list 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 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::Plus, token); > TEST_METHOD(Should_get_number_value_from_number_token) < Token token(1.23); Assert::AreEqual(1.23, token); > >; >

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

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

c++
TDD
интерпретатор
test driven development
разработка через тестирование
рефакторинг
юнит-тесты

Учебники. Программирование для начинающих.

Programm.ws — это сайт, на котором вы можете почитать литературу по языкам программирования , а так-же посмотреть примеры работающих программ на С++, ассемблере, паскале и много другого..

Программирование — в обычном понимании, это процесс создания компьютерных программ.
В узком смысле (так называемое кодирование) под программированием понимается написание инструкций — программ — на конкретном языке программирования (часто по уже имеющемуся алгоритму — плану, методу решения поставленной задачи). Соответственно, люди, которые этим занимаются, называются программистами (на профессиональном жаргоне — кодерами), а те, кто разрабатывает алгоритмы — алгоритмистами, специалистами предметной области, математиками.
В более широком смысле под программированием понимают весь спектр деятельности, связанный с созданием и поддержанием в рабочем состоянии программ — программного обеспечения ЭВМ. Более точен современный термин — «программная инженерия» (также иначе «инженерия ПО»). Сюда входят анализ и постановка задачи, проектирование программы, построение алгоритмов, разработка структур данных, написание текстов программ, отладка и тестирование программы (испытания программы), документирование, настройка (конфигурирование), доработка и сопровождение.

Си для профессионалов

Глава 6. Интерпретаторы языка

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

Интерпретаторы важны по трем очень важным причинам. Во-первых, они могут обеспечивать удобную интерактивную среду (как доказательство — интерпретатор стандартного языка BASIC, которыми снабжаются большинство персональных компьтеров). Многие пользователи-новички находят, что интерактивная среда более удобна, чем компилятор. Во-вторых, интерпретаторы языка обеспечивают превосходные интерактивные отладочные возможности. Даже ветераны-программисты при отладке трудных программ прибегают к помощи интерпретатора языка, потому что он позволяет динамично устанавливать значения переменных и условий. В-третьих, большинство языков запросов к базе данных работают в режиме интерпретации.

В этой главе будет разработан интерпретатор для подмножества языка BASIC, который еще называют «SMALL BASIC». BASIC выбран вместо Cи, потому что BASIC легче интерпретируется, чем Cи или другой структурный язык. Интерпретатор для структурного языка, такого как Cи более труден, чем для BASIC из-за автономных функций с локальными переменными, которые обеспечивают интерпретатору многозначность. Принципы, используемые в интерпретаторе BASIC, применимы и для других языков, и вы можете использовать написанные программы в качестве отправной точки. Прежде, чем начать работу, необходимо изучить сущность языковой интерпретации, особенно перед тем, как браться за интерпетацию такого сложного языка, как Cи. Если вы не знаете BASIC, не беспокойтесь, команды используемые в SMALL BASIC очень легкие для понимания.

Мы начинаем с сердца любого интерпретатора: синтаксического анализатора выражений.

Наиболее важной частью интерпретатора языка является синтактический анализатор выражений, который преобразует числовые выражения, такие как (10-X)/23, в такую форму, чтобы компьютер мог понять ее и вычислить. В книге по языку Cи: The Complete Reference (Osborne/McGraw-uill, 1987) вступительная глава посвящена синтаксическому анализу выражений. Подобного же рода синтаксический анализ, основанный на принципах, изложенных в вышеупомянутой книге, (правда, с небольшими изменениями) будет использоваться для построения интерпретатора SMALL BASIC в данной главе нашей книги. (Так как эта глава содержит только краткие сведения о синтаксическом анализе выражений, то для более детального изучения этой проблемы советуем вам обратиться к источнику: The Compelete Reference.

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

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

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

Символ ‘^’ означает экспоненту, а символ ‘=’ используется как оператор присваивания, а также как знак равенства в операциях сравнения. Элементы выражения можно комбинировать согласно правилам алгебры.

Вот некоторые примеры выражений:

Что касается языка BASIC, старшинство операторов не определено. В процессе работы синтаксический анализатор присваивает операторам следующие приоритеты:

Операторы равного приоритета выполняются слева направо.

Синтаксис языка SMALL BASIC предполагает, что все переменные обозначаются одной буквой. Это позволяет оперировать в программе двадцати шестью переменными (буквы от A до Z). Хотя интерпретаторы языка BASIC поддерживают обычно большее число символов в определении переменной, (например, переменные типа Х27), но для простоты изложения основных принципов построения интерпретаторов наш интерпретатор языка SMALL BASIC этого делать не будет. Будем считать также, что переменные разных регистров не отличаются друг от друга и, поэтому, переменные «a» и «A» будут трактоваться как одна и та же переменная. Условимся, что все числа являются целыми, хотя вы без особого труда можете написать

программы для манипулирования другими типами чисел. Хотя

символьные переменные в нашей версии языка и не поддерживаются,

будем считать, что возможен вывод ограниченных символьных

констант на экран в виде различных сообщений.

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

Перед тем, как построить синтаксический анализатор, разбирающий значения выражений, вы должны иметь несколько вариантов разбиения строки, содержащей выражение, на составляющие части. Например, выражение

содержит компоненты «А», «*», «В», «-«, «(«, «W», «+», «10» и

«)». Каждый компонент представляет собой неделимый элемент

выражения. Такой компонент или независимая часть выражения

называется лексемой. Функция, разбивающая выражение на составные

части, должна решать четыре задачи: (1) игнорировать пробелы и

символы табуляции, (2) извлекать каждую лексему из текста, (3)

если необходимо, преобразовывать лексему во внутренний формат,

(4) определять тип лексемы.

Каждая лексема имеет два формата: внешний и внутренний. Внешний формат — это символьная строка, с помощью которой вы пишите программы на каком-либо языке программирования. Например, «PRINT» — это внешняя форма команды PRINT языка BASIC. Можно построить интерпретатор из расчета, что каждая лексема используется во внешнем формате, но это типичное решение проблемы программистом-непрофессионалом, который лишь два часа назад оторвался от материной юбки и час назад увидел настоящий компьютер. Настоящие мужчины ориентируются на внутренний формат лексемы, который является просто числом, и разрабатывают интерпретаторы исходя из этой профессиональной точки зрения на проблему. Поясним этот подход. Например, команда PRINT может иметь порядковый внутренний номер 1, команда INPUT — 2 и т.д. Преимущество внутреннего формата заключается в том, что программы, обрабатывающие числа, более быстродействующие, чем программы, обрабатывающие строки. Для реализации такого подхода необходима функция, которая берет из входного потока данных очередную лексему и преобразует ее из внешнего формата во внутренний. Помните, что не все лексемы имеют разные форматы. Например, операторы не подлежат преобразованию потому, что они могут трактоваться как символы или числа в своих внешних форматах.

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

Функция, которая возвращает следующую лексему в выражении, называется get_token( ). Она работает из расчета того, что в языке SMALL BASIC, программа хранится как одна строка, ограниченная в конце символом завершения строки (