Stork: Как создать язык программирования на C++

Часть 1: Токенизатор

В этой серии мы разработаем новый язык сценариев и шаг за шагом опишем этот процесс.

Первым вопросом, который спонтанно приходит в голову любому заинтересованному читателю, скорее всего, будет: «Действительно ли нам нужен новый язык программирования?»

Действительно ли нам нужен новый язык программирования?

Чтобы ответить на этот вопрос, позволю себе небольшое отступление.

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

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

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

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

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

Полный исходный код всего, что здесь описано, находится в свободном доступе на GitHub.

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

Маленькие помощники Tokenizer

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

Мне нужен контейнер ключ-значение, который должен быстро извлекать значения за логарифмическое время. Однако после инициализации контейнера я не хочу добавлять в него новые значения. Таким образом, std::map<Key, Value> (или std::unordered_map<Key, Value> ) является излишним, так как он также позволяет быструю вставку.

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

Второй вариант — std::vector<std::pair<Key,Value> > , отсортированный после вставок. Единственная проблема с этим подходом — меньшая читабельность кода, поскольку нам нужно помнить, что вектор отсортирован, поэтому я разработал небольшой класс, обеспечивающий это ограничение.

(Все функции, классы и т. д. объявлены в пространстве имен stork . Я буду опускать это пространство имен для удобства чтения.)

 template <typename Key, typename Value> class lookup { public: using value_type = std::pair<Key, Value>; using container_type = std::vector<value_type>; private: container_type _container; public: using iterator = typename container_type::const_iterator; using const_iterator = iterator; lookup(std::initializer_list<value_type> init) : _container(init) { std::sort(_container.begin(), _container.end()); } lookup(container_type container) : _container(std::move(container)) { std::sort(_container.begin(), _container.end()); } const_iterator begin() const { return _container.begin(); } const_iterator end() const { return _container.end(); } template <typename K> const_iterator find(const K& key) const { const_iterator it = std::lower_bound( begin(), end(), key, [](const value_type& p, const K& key) { return p.first < key; } ); return it != end() && it->first == key ? it : end(); } size_t size() const { return _container.size(); } };

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

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

 using get_character = std::function<int()>;

Я буду использовать известные соглашения из потоковых функций в стиле C, таких как getc , которая возвращает int вместо char , а также отрицательное число, сигнализирующее о конце файла.

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

 class push_back_stream { private: const get_character& _input; std::stack<int> _stack; size_t _line_number; size_t _char_index; public: push_back_stream(const get_character& input); int operator()(); void push_back(int c); size_t line_number() const; size_t char_index() const; };

Для экономии места я опущу детали реализации, которые вы можете найти на моей странице GitHub.

Как видите, push_back_stream инициализируется из функции get_character . Перегруженный operator() используется для извлечения следующего символа, а push_back используется для возврата символа обратно в поток. line_number и char_number — это удобные методы, используемые для отчетов об ошибках.

Имейте в виду, что char_index — это не индекс символа в текущей строке, а общий; в противном случае нам пришлось бы хранить все прошлые символы в каком-то контейнере, чтобы правильно реализовать функцию push_back .

Зарезервированные токены

Токенизатор — это компонент компилятора самого низкого уровня. Он должен считывать входные и «выплевываемые» токены. Нас интересуют четыре типа токенов:

• Зарезервированные токены
• Идентификаторы
• Числа
• Струны

Комментарии нас не интересуют, поэтому токенизатор их просто «съест», никого не уведомив.

Чтобы обеспечить привлекательность и планетарную популярность этого языка, мы будем использовать хорошо известный Си-подобный синтаксис. Он неплохо работал для C, C++, JavaScript, Java, C# и Objective-C, поэтому он должен работать и для Stork. Если вам нужен курс повышения квалификации, вы можете обратиться к одной из наших предыдущих статей, посвященных учебным ресурсам C/C++.

Вот перечисление зарезервированных токенов:

 enum struct reserved_token { inc, dec, add, sub, concat, mul, div, idiv, mod, bitwise_not, bitwise_and, bitwise_or, bitwise_xor, shiftl, shiftr, assign, add_assign, sub_assign, concat_assign, mul_assign, div_assign, idiv_assign, mod_assign, and_assign, or_assign, xor_assign, shiftl_assign, shiftr_assign, logical_not, logical_and, logical_or, eq, ne, lt, gt, le, ge, question, colon, comma, semicolon, open_round, close_round, open_curly, close_curly, open_square, close_square, kw_if, kw_else, kw_elif, kw_switch, kw_case, kw_default, kw_for, kw_while, kw_do, kw_break, kw_continue, kw_return, kw_var, kw_fun, kw_void, kw_number, kw_string, };

Элементы перечисления с префиксом «kw_» являются ключевыми словами. Мне пришлось добавить к ним префикс, поскольку они обычно совпадают с ключевыми словами C++. Те, что без префикса, являются операторами.

Почти все они следуют соглашению C. Те, что нет:
- concat и concat_assign ( .. и ..= ), которые будут использоваться для конкатенации
- idiv и idiv_assign ( \ и \= ), которые будут использоваться для целочисленного деления
- kw_var для объявления переменной
- kw_fun для объявления функции
- kw_number для числовых переменных
- kw_string для строковых переменных

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

Есть одно новое ключевое слово, которое заслуживает описания: kw_elif . Я твердо верю, что блоки из одного оператора (без фигурных скобок) того не стоят. Я ими не пользуюсь (и не чувствую, что чего-то не хватает), за исключением двух случаев:

1. Когда я случайно нажимаю точку с запятой сразу после for , while или if перед блоком. Если мне повезет, он вернет ошибку времени компиляции, но иногда это приводит к фиктивному оператору if и всегда выполняющемуся блоку. К счастью, с годами я научился на своих ошибках, поэтому такое случается очень редко. Со временем собака Павлова тоже научилась.
2. Когда у меня есть «цепочка» операторов if, то есть блок if, затем один или несколько блоков else-if и, необязательно, блок else. Технически, когда я пишу else if , это блок else только с одним оператором, которым является оператор if.

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

Есть две вспомогательные функции, которые возвращают зарезервированные токены:

 std::optional<reserved_token> get_keyword(std::string_view word); std::optional<reserved_token> get_operator(push_back_stream& stream);

Функция get_keyword возвращает необязательное ключевое слово из переданного слова. Это «слово» представляет собой последовательность букв, цифр и знаков подчеркивания, начинающуюся с буквы или знака подчеркивания. Он вернет reserved_token , если слово является ключевым словом. В противном случае токенизатор будет считать, что это идентификатор.

Функция get_operator пытается прочитать как можно больше символов, если последовательность является допустимым оператором. Если он прочитает больше, он удалит все лишние символы, прочитанные после самого длинного распознанного оператора.

Для эффективной реализации этих двух функций нам нужны два поиска между string_view и reserved_keyword словом.

 const lookup<std::string_view, reserved_token> operator_token_map { {"++", reserved_token::inc}, {"--", reserved_token::dec}, {"+", reserved_token::add}, {"-", reserved_token::sub}, {"..", reserved_token::concat}, /*more exciting operators*/ }; const lookup<std::string_view, reserved_token> keyword_token_map { {"if", reserved_token::kw_if}, {"else", reserved_token::kw_else}, {"elif", reserved_token::kw_elif}, {"switch", reserved_token::kw_switch}, {"case", reserved_token::kw_case}, {"default", reserved_token::kw_default}, {"for", reserved_token::kw_for}, {"while", reserved_token::kw_while}, {"do", reserved_token::kw_do}, {"break", reserved_token::kw_break}, {"continue", reserved_token::kw_continue}, {"return", reserved_token::kw_return}, {"var", reserved_token::kw_var}, {"fun", reserved_token::kw_fun}, {"void", reserved_token::kw_void}, {"number", reserved_token::kw_number}, {"string", reserved_token::kw_string} };

Реализация get_keyword абсолютно проста, но для get_operator нам нужен специальный компаратор, который будет сравнивать заданный символ с операторами-кандидатами, принимая во внимание только n-й символ.

 class maximal_munch_comparator{ private: size_t _idx; public: maximal_munch_comparator(size_t idx) : _idx(idx) { } bool operator()(char l, char r) const { return l < r; } bool operator()( std::pair<std::string_view, reserved_token> l, char r ) const { return l.first.size() <= _idx || l.first[_idx] < r; } bool operator()( char l, std::pair<std::string_view, reserved_token> r ) const { return r.first.size() > _idx && l < r.first[_idx]; } bool operator()( std::pair<std::string_view, reserved_token> l, std::pair<std::string_view, reserved_token> r ) const { return r.first.size() > _idx && ( l.first.size() < _idx || l.first[_idx] < r.first[_idx] ); } };

Это обычный лексический компаратор, который учитывает только символ в позиции idx , но если строка короче, он обрабатывает ее так, как если бы она имела нулевой символ в позиции idx , что меньше любого другого символа.

Это реализация get_operator , которая должна сделать класс maximal_munch_operator более понятным:

 std::optional<reserved_token> get_operator(push_back_stream& stream) { auto candidates = std::make_pair( operator_token_map.begin(), operator_token_map.end() ); std::optional<reserved_token> ret; size_t match_size = 0; std::stack<int> chars; for (size_t idx = 0; candidates.first != candidates.second; ++idx) { chars.push(stream()); candidates = std::equal_range( candidates.first, candidates.second, char(chars.top()), maximal_munch_comparator(idx) ); if ( candidates.first != candidates.second && candidates.first->first.size() == idx + 1 ) { match_size = idx + 1; ret = candidates.first->second; } } while (chars.size() > match_size) { stream.push_back(chars.top()); chars.pop(); } return ret; }

По сути, мы рассматриваем всех операторов как кандидатов в начале. Затем мы читаем символ за символом и фильтруем текущих кандидатов, вызывая equal_range , сравнивая только n-й символ. Нам не нужно сравнивать предшествующие символы, поскольку они уже сравнены, и мы не хотим сравнивать последующие символы, поскольку они все еще не имеют значения.

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

Токенизатор

Поскольку токены неоднородны, токен — это удобный класс, который обертывает std::variant разные типы токенов, а именно:

• Зарезервированный токен
• Идентификатор
• Количество
• Нить
• Конец файла

 class token { private: using token_value = std::variant<reserved_token, identifier, double, std::string, eof>; token_value _value; size_t _line_number; size_t _char_index; public: token(token_value value, size_t line_number, size_t char_index); bool is_reserved_token() const; bool is_identifier() const; bool is_number() const; bool is_string() const; bool is_eof() const; reserved_token get_reserved_token() const; std::string_view get_identifier() const; double get_number() const; std::string_view get_string() const; size_t get_line_number() const; size_t get_char_index() const; };

identifier — это просто класс с одним членом типа std::string . Это сделано для удобства, так как, на мой взгляд, std::variant чище, если все его альтернативы относятся к разным типам.

Теперь мы можем написать токенизатор. Это будет одна функция, которая примет push_back_stream и вернет следующий токен.

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

• Если мы прочитаем символ конца файла, мы вернемся из функции.
• Если мы прочитаем пробел, мы его пропустим.
• Если мы прочитаем буквенно-цифровой символ (букву, цифру или знак подчеркивания), мы прочитаем все последующие символы этого типа (мы также прочитаем точки, если первым символом является цифра). Затем, если первый символ — цифра, мы попытаемся разобрать последовательность как число. В противном случае мы будем использовать функцию get_keyword , чтобы проверить, является ли это ключевым словом или идентификатором.
• Если мы прочитаем кавычку, мы будем рассматривать ее как строку, удаляя из нее экранированные символы.
• Если мы прочитаем символ косой черты ( / ), мы проверим, является ли следующий символ косой чертой или звездочкой ( * ), и в этом случае мы пропустим комментарий строки/блока.
• В противном случае мы будем использовать функцию get_operator .

Вот реализация функции токенизации. Я опущу детали реализации функций, которые он вызывает.

 token tokenize(push_back_stream& stream) { while (true) { size_t line_number = stream.line_number(); size_t char_index = stream.char_index(); int c = stream(); switch (get_character_type(c)) { case character_type::eof: return {eof(), line_number, char_index}; case character_type::space: continue; case character_type::alphanum: stream.push_back(c); return fetch_word(stream); case character_type::punct: switch (c) { case '"': return fetch_string(stream); case '/': { char c1 = stream(); switch(c1) { case '/': skip_line_comment(stream); continue; case '*': skip_block_comment(stream); continue; default: stream.push_back(c1); } } default: stream.push_back(c); return fetch_operator(stream); } break; } } }

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

Исключения

В одной из своих тирад против исключений мой брат однажды сказал:

«Есть два типа людей: те, кто бросает исключения, и те, кто должен их ловить. Я всегда нахожусь в этой грустной, второй группе».

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

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

Вот реализация исключения:

 class error: public std::exception { private: std::string _message; size_t _line_number; size_t _char_index; public: error(std::string message, size_t line_number, size_t char_index) noexcept; const char* what() const noexcept override; size_t line_number() const noexcept; size_t char_index() const noexcept; };

Однако я обещаю перехватывать все исключения в коде верхнего уровня. Я даже добавил line_number и char_index для красивой печати и функцию, которая это делает:

 void format_error( const error& err, get_character source, std::ostream& output );

Подведение итогов

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

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

Дальнейшее чтение в блоге Toptal Engineering:

• Как подойти к написанию интерпретатора с нуля