За основу я взял язык Brainfuck, он настолько мал, что можно немного расширив получить практически новый и достаточно функциональный язык программирования. И при этом не потерять изюминку исходного языка - мой язык будет все так же терзать мозг программиста, как и его родитель!
Итак, Brainfuck. Вкратце, идея такая, есть N регистров/ячеек. У программиста есть доступ к ним всем но перемещения по ним делаются явным образом. Т.е. из ячейки 2 нельзя перейти к ячейке 7 сразу, нужно последовательно.
"Ключевые слова" языка:
- > - перейти на ячейку вправо.
- < - перейти на ячейку влево.
- + - увеличить значение ячейки на единицу.
- - - уменьшить значение ячейки на единицу.
- , - прочесть значение в ячейку со стандартного устройства ввода.
- . - напечатать значение ячейки стандартным устройством вывода.
- [ - начать цикл while если значение текущей ячейки не равно 0 и перейти к следующей ячейке.
- ] - конец блока while. Продолжить цикл, если значение "условной" ячейки не равно 0 ("условная ячейка" - ячейка на которой начался цикл).
- $ - прочитать значение в ячейку как число (> переопределим как чтение в качестве ANCII символа)
- ! - напечатать как число
- { - начало функции, после начала идет имя функции (именем может служить любая последовательность букв между символами %<имя функции>%. Для любой функции создается копия ячеек, возвращаемое значение записывается в текущий регистр вызвавшего блока
- } - конец функции
- (- начало комментария
- ) - конец комментария
- @%<имя функции>% - вызов функции
- ^ - обнулить ячейку
Так как все множество ключевых слов состоит из ANCII символов, имеем:
// Искомые ключевые слова
const char bf_next = ">";
const char bf_prev = "<";
const char bf_incr = "+";
const char bf_decr = "-";
const char bf_prnt = ".";
const char bf_read = ",";
const char bf_wBeg = "[";
const char bf_wEnd = "]";
// Добавленные ключевые слова
const char bf_pNum = "!" ;
const char bf_rNum = "$";
const char bf_fBeg = "{";
const char bf_fEnd = "}";
const char bf_fNme = "%";
const char bf_comm= "(";
const char bf_call = "@";
const char bf_null = "^";
Без ограничения общности возьмем ограниченное количество ячеек, скажем 256 и в случае попытки перейти к недопустимой ячейке будем переходить к самой первой ячейке (если переход влево) или к самой последней (если переход вправо).
const unsigned long regSize = 256; // Количество регистров
long reg[ regSize ]; // Сами регистры
long stck[ regSize ]; // Стек, у каждой функции свой стек
void resetRegisters(); // Функция для обнуления регистров
void printRegistres(); // Показать состояние регистров
Теперь, скажем имеем test.bf, как входной файл, в котором находится код на моем языке или на родном Brainfuck. Интерпретатор должен обеспечивать "обратную совместимость".
Опять же, без ограничения общности, можем хранить весь код в некотором ограниченном массиве. Т.е. интепретатор будет работать с файлами ограниченного размера, скажем так:
const unsigned long maxCodeSize = 1024000; /* максимальный размер входного файла в символах */
unsigned long realCodeSize; // Размер кода в файле realCodeSize < maxCodeSize
char code; // Сам код
Интерпритатор читает весь код сразу. В один символьный массив, для этого будем использовать функцию readCode(). После прочтения не пустого текста m_realCodeSize будет содержать точное количество символов в коде, без учета комментариев, комментарии отбрасываются во время чтения.
int main(int argc, char** argv)
{
welcome();
resetRegisters();
readCode("test.bf ");
loop (0, realCodeSize - 1, regSize, reg);
return 0;
}
bool loop(unsigned long from,
unsigned long to,
unsigned long condRegIndx,
unsigned long currReg,
long* registers);
bool runFunction(unsigned long from,
unsigned int to,
unsigned int& retValue);
void copyRegistersTo(long* source, long* destination);
Первая будет выполнять цикл и вернет true если цикл выполнен без проблем, т.е. нет синтаксических ошибок.
Вторая собственно будет выполнять функцию, а возвращаемое значение запишется в retVal, которое в свою очередь присвоится регистру, на котором была вызвана функция. Возвращаемым значением будем считать первый регистр стека функции после ее окончания.
Кстати, о цикле while, в общем случае цикл может продолжаться бесконечно. Но, чтобы не столкнуться с проблемой зависания интерпретатора, введем переменную отвечающую за максимальное количество циклов.
const unsigned long maxLoopCycles = 999999;
Реализуем сначала обратную совместимость. Пусть пока наш интерпретатор сможет выполнять только код Brainfuck-а.
Нам понадобятся функции:
bool makeCommand(char command, long* registers, unsigned long currReg)
unsigned long findLoopEnd(const unsigned long from)
Второй и третий параметры первой функции обязательны. Третий параметр нужен для того, чтобы ориентироваться с какой ячейкой работать, второй нужен потому что регистры каждой функции отличаются, а операции над ними одинаковы.
Вторая функция исходя из названия находит конец цикла, т.е. символ соответствуюйщий "[".
Таким образом имеем интерпретатор для языка Brainfuck.
К записи прикрепил исходный код , моего интерпретатора с тестовым кодом
$[+<->]<<$>!<>>++++[++++++++++<->]<+++.++++++++++++++++++<<[<-<+>>]>>.<<
На код выше мой интерпретатор выведет сумму двух введённых чисел в виде а+b=c.
Удачного… программирования!
- 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:- Написать тест и заставить его падать (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
Сейчас проект компилируется, но тест, что было ожидаемо, падает. Для определения того, что же писать дальше, можно воспользоваться техникой 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 {
template
Также пришлось изменить определение токена и добавить перечисление 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
После этого тест компилируется, но не проходит, так как мы продолжаем возвращать пустую последовательность токенов. Исправим это, применив трансформацию (unconditional → if).
Inline Tokens Tokenize(std::wstring expr) {
if(expr.empty()) { return{}; }
return{ static_cast
- В ответ на пустое выражение должен возвращаться пустой список токенов.
- В ответ на строку с оператором должен возвращаться токен с оператором.
- В ответ на строку с цифрой должен возвращаться токен с числом.
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
Для удобства преобразования токена к нужному типу будем использовать оператор неявного приведения.
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
Так как в токене не может одновременно храниться и оператор, и число, то их поля можно объединить в 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
Все тесты, относящиеся к токену проходят, можно восстановить предыдущие тесты и убедиться, что ничего не сломалось. Последний тест всё так же не проходит. Приступим к его исправлению.
- В ответ на строку с цифрой должен возвращаться токен с числом.
- В ответ на строку с числом с плавающей точкой должен возвращаться токен с этим числом.
- В ответ на строку с простым выражением должен возвращаться список соответствующих токенов.
- Пробелы между числами и операторами должны игнорироваться.
If(expr >= "0" && expr <= "9") {
return{ (double) expr - "0" };
}
return{ static_cast
Выгладит пока что не очень симпатично, но тест проходит.
- В ответ на строку с цифрой должен возвращаться токен с числом.
- В ответ на строку с числом с плавающей точкой должен возвращаться токен с этим числом.
Вспомним, что в стандартной библиотеке 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
После этого можно приступить и к более сложным тестам. Попробуем обработать полюс и число одновременно.
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
Теперь заставить пройти тест довольно просто: применим трансформацию (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
Функция 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
На данном этапе проведём рефакторинг данной функции. Выделим логику в отдельный класс и разобьём на отдельный методы. Поместим этот класс в пространство имён 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
Как видно, извлечение класса сделало код гораздо понятнее. Без тестов такой рефакторинг был бы, как минимум, рискованным. Теперь добавим поддержку скобок и остальных операторов.
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(), (Operator o) {return *m_current == static_cast
Все тесты проходят и можно приступить к написанию парсера. Ниже приводится весь исходный код на данный момент.
Interpreter.h
#pragma once;
#include
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
От автора:
Тянулся нудный осенний вечер; делать как всегда было нечего... И вдруг, ни с того ни с сего, пришла мне в голову идея написать статью по созданию интерпретатора. «Делать тебе нечего... – иди лучше к коллоквиуму по вышке готовься», - раздался внутренний голос. И я уже было потянулся к розетке, чтобы вырубить мой компьютер, но внезапно вспомнил. Вспомнил, как я сам писал систему обработки сценариев. Вспомнил, сколько времени, усилий и нервов было впустую затрачено на поиск исчерпывающей информации по этой теме. Вспомнил бессонные ночи, проведенные за отладкой. И еще много чего вспомнил, а потом... послал свой внутренний голос и принялся за работу.
Введение:
Этот цикл статей предназначен, прежде всего, для читателя, не имеющего опыта работы в области написания интерпретаторов. Я постараюсь рассмотреть этот процесс настолько подробно, на сколько позволяют мои знания и опыт. Итак:
Тема работы: написание системы обработки сценариев на С++.
Цель работы:
1) ознакомление читателя с темой;
2) создание работоспособного интерпретатора с нуля;
3) его «внедрение» в какое-либо приложение.
Приборы и оборудование: базовые навыки владения С++, ООП и STL.
Ход работы:
Постановка задачи:
Написание полноценного интерпретатора какого-либо языка – дело сверхтрудоемкое и для меня непосильное. Поэтому я ограничил скриптовый язык подмножеством языка Си и, следуя принципу «достижения результатов наименьшими усилиями» внес в это подмножество кое-какие изменения. Итак, вот что получилось:
По существу, наша система обработки сценариев состоит из следующих основных компонентов:
- Lexer – преобразует входные данные (обычно, файл) в поток лексем (таких как ключевые слова, операторы и т.д.);
- Generator – генерирует байт код для последующего выполнения виртуальной машиной;
- Executor – выполняет байт код.
А вот наглядное изображение взаимодействия этих компонентов:
Термины и понятия:
Ниже я привожу словарь терминов и понятий, которые будут периодически использоваться в последующих статьях цикла. Все нижеперечисленные определения рассматриваются в контексте скриптов ESL.
аргумент (или параметр ) – это значение, передаваемое в функцию. Например в случае вызова функции IntToStr(123) аргументов является число 123.
выражение – это то, что приводит к некоторому значению. Например, как простая переменная, так и формула (x*n-1)/y2k являются выражениями. Любое выражение можно превратить в инструкцию, добавив после него «;». Операции присваивания также являются выражениями. Примеры выражений: x, y = x, func1(), y = func1().
идентификатор – это имя, определенное в скрипте. Любое слово в программе (за исключением комментариев и ключевых слов) является идентификатором. Все имена стандартных и игровых функций также являются идентификаторами.
инструкция – базовый элемент скрипта. Пример: for(...), if(...), a = b;.
ключевое слово – это имя, определенное в самом ESL. Сюда не включаются имена стандартных и программных функций, которые являются идентификаторами. Примеры: if, for, end.
Рассказывает программист Вильям В. Вольд
На протяжении последних шести месяцев я работал над созданием языка программирования (ЯП) под названием Pinecone. Я не рискну назвать его законченным, но использовать его уже можно - он содержит для этого достаточно элементов, таких как переменные, функции и пользовательские структуры данных. Если хотите ознакомиться с ним перед прочтением, предлагаю посетить официальную страницу и репозиторий на GitHub .
Введение
Я не эксперт. Когда я начал работу над этим проектом, я понятия не имел, что делаю, и всё еще не имею. Я никогда целенаправленно не изучал принципы создания языка - только прочитал некоторые материалы в Сети и даже в них не нашёл для себя почти ничего полезного.
Тем не менее, я написал абсолютно новый язык. И он работает. Наверное, я что-то делаю правильно.
В этой статье я постараюсь показать, каким образом Pinecone (и другие языки программирования) превращают исходный код в то, что многие считают магией. Также я уделю внимание ситуациям, в которых мне приходилось искать компромиссы, и поясню, почему я принял те решения, которые принял.
Текст точно не претендует на звание полноценного руководства по созданию языка программирования, но для любознательных будет хорошей отправной точкой.
Первые шаги
«А с чего вообще начинать?» - вопрос, который другие разработчики часто задают, узнав, что я пишу свой язык. В этой части постараюсь подробно на него ответить.
Компилируемый или интерпретируемый?
Компилятор анализирует программу целиком, превращает её в машинный код и сохраняет для последующего выполнения. Интерпретатор же разбирает и выполняет программу построчно в режиме реального времени.
Технически любой язык можно как компилировать, так и интерпретировать. Но для каждого языка один из методов подходит больше, чем другой, и выбор парадигмы на ранних этапах определяет дальнейшее проектирование. В общем смысле интерпретация отличается гибкостью, а компиляция обеспечивает высокую производительность, но это лишь верхушка крайне сложной темы.
Я хотел создать простой и при этом производительный язык, каких немного, поэтому с самого начала решил сделать Pinecone компилируемым. Тем не менее, интерпретатор у Pinecone тоже есть - первое время запуск был возможен только с его помощью, позже объясню, почему.
Прим. перев. Кстати, у нас есть краткий обзор - это отличное упражнение для тех, кто изучает Python.
Выбор языка
Своеобразный мета-шаг: язык программирования сам является программой, которую надо написать на каком-то языке. Я выбрал C++ из-за производительности, большого набора функциональных возможностей, и просто потому что он мне нравится.
Но в целом совет можно дать такой:
- интерпретируемый ЯП крайне рекомендуется писать на компилируемом ЯП (C, C++, Swift). Иначе потери производительности будут расти как снежный ком, пока мета-интерпретатор интерпретирует ваш интерпретатор;
- компилируемый ЯП можно писать на интерпретируемом ЯП (Python, JS). Возрастёт время компиляции, но не время выполнения программы.
Проектирование архитектуры
У структуры языка программирования есть несколько ступеней от исходного кода до исполняемого файла, на каждой из которых определенным образом происходит форматирование данных, а также функции для перехода между этими ступенями. Поговорим об этом подробнее.
Лексический анализатор / лексер
Строка исходного кода проходит через лексер и превращается в список токенов.
Первый шаг в большинстве ЯП - это лексический анализ . Говоря по-простому, он представляет собой разбиение текста на токены, то есть единицы языка: переменные, названия функций (идентификаторы), операторы, числа. Таким образом, подав лексеру на вход строку с исходным кодом, мы получим на выходе список всех токенов, которые в ней содержатся.
Обращения к исходному коду уже не будет происходить на следующих этапах, поэтому лексер должен выдать всю необходимую для них информацию.
Flex
При создании языка первым делом я написал лексер. Позже я изучил инструменты, которые могли бы сделать лексический анализ проще и уменьшить количество возникающих багов.
Одним из основных таких инструментов является Flex - генератор лексических анализаторов. Он принимает на вход файл с описанием грамматики языка, а потом создаёт программу на C, которая в свою очередь анализирует строку и выдаёт нужный результат.
Моё решение
Я решил оставить написанный мной анализатор. Особых преимуществ у Flex я в итоге не увидел, а его использование только создало бы дополнительные зависимости, усложняющие процесс сборки. К тому же, мой выбор обеспечивает больше гибкости - например, можно добавить к языку оператор без необходимости редактировать несколько файлов.
Синтаксический анализатор / парсер
Список токенов проходит через парсер и превращается в дерево.
Следующая стадия - парсер. Он преобразует исходный текст, то есть список токенов (с учётом скобок и порядка операций), в абстрактное синтаксическое дерево , которое позволяет структурно представить правила создаваемого языка. Сам по себе процесс можно назвать простым, но с увеличением количества языковых конструкций он сильно усложняется.
Bison
На этом шаге я также думал использовать стороннюю библиотеку, рассматривая Bison для генерации синтаксического анализатора. Он во многом похож на Flex - пользовательский файл с синтаксическими правилами структурируется с помощью программы на языке C. Но я снова отказался от средств автоматизации.
Преимущества кастомных программ
С лексером моё решение писать и использовать свой код (длиной около 200 строк) было довольно очевидным: я люблю задачки, а эта к тому же относительно тривиальная. С парсером другая история: сейчас длина кода для него - 750 строк, и это уже третья попытка (первые две были просто ужасны).
Тем не менее, я решил делать парсер сам. Вот основные причины:
- минимизация переключения контекста ;
- упрощение сборки;
- желание справиться с задачей самостоятельно.
В целесообразности решения меня убедило высказывание Уолтера Брайта (создателя языка D) в одной из его статей :
Я бы не советовал использовать генераторы лексических и синтаксических анализаторов, а также другие так называемые «компиляторы компиляторов». Написание лексера и парсера не займёт много времени, а использование генератора накрепко привяжет вас к нему в дальнейшей работе (что имеет значение при портировании компилятора на новую платформу). Кроме того, генераторы отличаются выдачей не релевантных сообщений об ошибках.
Абстрактный семантический граф
Переход от синтаксического дерева к семантическому графу
В этой части я реализовал структуру, по своей сути наиболее близкую к «промежуточному представлению» (intermediate representation) в LLVM. Существует небольшая, но важная разница между абстрактным синтаксическим деревом (АСД) и абстрактным семантическим графом (АСГ).
АСГ vs АСД
Грубо говоря, семантический граф - это синтаксическое дерево с контекстом. То есть, он содержит информацию наподобие какой тип возвращает функция или в каких местах используется одна и та же переменная. Из-за того, что графу нужно распознать и запомнить весь этот контекст, коду, который его генерирует, необходима поддержка в виде множества различных поясняющих таблиц.
Запуск
После того, как граф составлен, запуск программы становится довольно простой задачей. Каждый узел содержит реализацию функции, которая получает некоторые данные на вход, делает то, что запрограммировано (включая возможный вызов вспомогательных функций), и возвращает результат. Это - интерпретатор в действии.
Варианты компиляции
Вы, наверное, спросите, откуда взялся интерпретатор, если я изначально определил Pinecone как компилируемый язык. Дело в том, что компиляция гораздо сложнее, чем интерпретация - я уже упоминал ранее, что столкнулся с некоторыми проблемами на этом шаге.
Написать свой компилятор
Сначала мне понравилась эта мысль - я люблю делать вещи сам, к тому же давно хотел изучить язык ассемблера. Вот только создать с нуля кроссплатформенный компилятор - сложнее, чем написать машинный код для каждого элемента языка. Я счёл эту идею абсолютно не практичной и не стоящей затраченных ресурсов.
