В наше время программирование стало очень доступным из-за развития инструментов и языков. Написать «привет, мир» может практически каждый, а количество фреймворков для JavaScript уже воспевается в шутках. Теперь, чтобы выделиться и впечатлить друзей и коллег, нужно спускаться глубже. Придумаем свой язык шуточный программирования!
В этой статье кратко рассмотрим базу компиляторов и мемные эзотерические языки программирования. В конце придумаем свой язык и попробуем его реализовать.
Это упрощенная статья, которая расширит ваш кругозор, а у некоторых вызовет интерес и любопытство погрузиться в тему.
Оглавление
Введение
В начале необходимо изучить (или повторить) основы. Может быть скучно, но это важно для понимания.
Язык программирования — это формальный язык со своими правилами (синтаксисом), который позволяет записывать инструкции (команды) для вычислителя. Люди придумали тысячи языков программирования, но ни один из них в своем оригинальном виде не является «понятным» для компьютеров, которые понимают только машинные инструкции. «Переложением» языка программирования в полезные действия занимаются специальные программы: компиляторы и интерпретаторы.
Машинный код — это представление программы в бинарном виде, которое может быть выполнено процессором.
Компилятор — это программа, которая переводит исходный код в машинные инструкции, байт-код или другой язык программирования. Компиляторов существует несколько видов.
Традиционные компиляторы. Конвертируют исходный код в машинные инструкции. На выходе получается бинарный исполняемый файл, который может быть исполнен. Среди традиционных компиляторов выделяют кросс-компиляторы, которые позволяют собирать программы для других архитектур и операционных систем. Например, компиляция программ для Linux на Windows является кросс-компиляцией. К традиционным компилятором относятся компиляторы языков C, C++, Pascal.
Компиляторы в байт-код. Конвертируют исходный код в байт-код, понятный виртуальным машинам. Таковыми являются компиляторы языков Java и C#: компилятор создает команды не для центрального процессора, а для виртуальных машин JVM (Java Virtual Machine) или CLR (Common Language Runtime).
Just-In-Time (JIT) компиляторы. Компиляторы, которые принимают байт-код виртуальной машины и конвертируют его в команды, которые понимает текущий используемый процессор. Такие компиляторы используются «под капотом» в JVM и CLR и не видны обычным программистам.
Транспилеры. Конвертеры одного языка программирования в другой. Транспилеры чаще встречаются в веб-технологиях. Например, популярен компилятор Babel, который транслирует типизированный TypeScript и все новые особенности ECMAScript в «старый» JavaScript, который поддерживается браузерами.
Компиляция состоит из нескольких этапов, на каждом из которых исходный код проверяется и превращается в представление, удобное для следующего этапа компиляции.
Препроцессинг. Обработка директив препроцессора: подстановка макросов, включение содержимого других файлов.
Компиляция. Превращение каждого файла исходного кода в ассемблерный код — человекочитаемую интерпретацию машинного кода.
Ассемблирование. Превращение ассемблерного кода в машинный код — объектный файл.
Компоновка. Связывание нескольких объектных файлов между собой и с функциями и библиотеками, доступными на целевой платформе.
Почти все виды компиляторов «видят» весь исходный код и полностью «переводят» программу с языка программирования в машинные инструкции. Кроме JIT-компиляторов. Они поверхностно проверяют целостность и корректность байт-кода, созданного «предшественником», но сам байт-код переводится в машинные инструкции только если он будет выполнен в ближайшем будущем. Машинные инструкции не сохраняются между запусками и при следующем запуске JIT-компилятору снова придется поработать.
В виртуальной машине JVM каждая функция при первом вызове выполняется чуть дольше: сначала JIT-компилятор создает машинный код, потом этот код выполняется. Поэтому существует термин «прогрев JVM» — выполнение небольшого нагрузочного тестирования, чтобы скомпилировать как можно больше функций и вывести программу на продуктовый режим работы.
Интерпретатор — это программа, которая «на лету» построчно анализирует исходный код и выполняет команды. В отличие от компилятора, интерпретатор не обрабатывает полностью весь исходный код, а только проверяет синтаксическую корректность, а правильность проверяет только когда это «попадается» при исполнении. Это значит, что ошибки, такие как использование необъявленной переменной или несоответствие типов, выясняются, когда интерпретатор дойдет до команды с ошибкой.
Теперь у нас есть упрощенное знание основ и мы можем приступить к разработке своего языка. Но технологий и процессов так много, с чего начать?
Язык программирования на препроцессоре
Обратимся к этапам компиляции. В первую очередь происходит препроцессинг — раскрытие макросов, то в том числе замена имен макросов на их значения. Возможно, вы видели в программах на С и С++ такие строки:
#include <iostream> #define TRUE 1
Первый макрос указывает, что в начало текущего файла нужно вставить содержимое файла iostream, а второй макрос определяет, что последовательность символов TRUE должна быть заменена на цифру 1. Препроцессор заменяет одни последовательности на другие, а значит можно сделать свой «язык программирования», заменив все ключевые слова в уже существующем языке. В качестве примера приведу отредактированный «чёткий» код из мема более чем десятилетней давности.
#include <iostream> #define ярусский setlocale(LC_CTYPE, "Russian") #define б ; #define нифига int #define факт bool #define базарь cout<< #define спроси cin>> #define зашибись 1 #define если if( #define то ) #define собака == #define иначе else #define типа { #define слыш } #define ану_иди_сюда using namespace #define сказал std #define стопе main() ану_иди_сюда сказал б нифига стопе типа ярусский б типа факт СЕМКИ б базарь "Семки есть, слыш?" б спроси СЕМКИ б если СЕМКИ собака зашибись то типа базарь "Красава" б слыш иначе типа базарь "Нарываешься?" б слыш слыш слыш
Достоинства:
Очень простая реализация, которая не требует специфических знаний.
Недостатки:
Нужен компилятор с поддержкой препроцессинга.
Синтаксис оригинального языка заставляет придумывать непрактичные решения. В примере компактные фигурные скобки превращаются в более объемные «типа» и «слыш», а точка с запятой — в ругательство.
Нужен словарь замен, который должен появляться в начале каждого файла. Это достигается либо директивой
#include, которую никак не изменить, либо использовать аргумент-includeпри компиляции.
Решение хорошее, чтобы сделать скриншот работоспособной программы и показать друзьям. Но словарь языка — это часть программы, а компиляция требует от пользователя дополнительных действий. Эти действия можно и нужно автоматизировать: переходим от препроцессора к транспилеру.
Создайте веб-приложение и получите бонусы на его деплой в облако
В новом бесплатном курсе по JavaScript.
Четкий транспилер
Если код на С++ был только картинкой-шуткой, то в 2016 году появился язык программирования YoptaScript. Оригинальная идея была возведена в абсолют: при создании ключевых слов использовался словарь блатного жаргона.
В JavaScript нет препроцессора, поэтому автор реализовал программу на TypeScript, которая заменяет не только ключевые слова языка, но и названия встроенных модулей и функций. Этот язык программирования использует настолько много непечатной лексики, что лучше не выносить примеры кода в статью, чем пытаться отредактировать. Однако, если любопытство зовет и вы не боитесь ругательств, то в репозитории есть каталог с примерами: чистый JavaScript и та же программа на YoptaScript.
Достоинства:
В рамках веб-технологий это самостоятельный компилятор-транспилер, который конвертирует жаргонный исходный код в JavaScript.
В отличие от решения на препроцессоре, этот транспилер позволяет выполнить преобразование в обе стороны: из оригинального языка в шуточный и наоборот.
Недостатки:
Как и ранее, язык построен на основе замен, что снижает ценность: это все тот же JavaScript, но с излишней словесной нагрузкой.
Вывод: решение более сложное, для мемов годится, но можно лучше. Продолжаем наше движение дальше и ищем оригинальный язык программирования.
Простейший интерпретатор — Brainfuck
В 1993 году Урбан Мюллер придумал эзотерический язык программирования Brainfuck, который состоит из восьми команд, каждая из которых записывается одним символом. Интерпретатор содержит 30 000 ячеек памяти, а программа представляется как лента с последовательностью символов.
> — перейти к следующей ячейке памяти;
< — перейти к предыдущей ячейке памяти;
+ — увеличить значение в текущей ячейке памяти на 1;
- — уменьшить значение в текущей ячейке памяти на 1;
. — напечатать значение из текущей ячейки памяти;
, — ввести извне числовое значение и сохранить в текущей ячейке памяти;
[ — если значение текущей ячейки ноль, перейти вперед по тексту программы на символ, следующий за соответствующей ] (с учетом вложенности);
] — если значение текущей ячейки не ноль, перейти назад по тексту программы на символ [ (с учетом вложенности).
Язык настолько прост, что написание собственного интерпретатора или транспилера Brainfuck — это неплохая задача для новичков в программировании. Чем меньше синтаксического сахара в языке программирования — тем проще реализация интерпретатора и тем сложнее писать на таком языке программы. Обычный «Hello, World» выглядит так:
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
Если вам интересно, сколько внимания уделяли люди языку Brainfuck, то советую посетить Brainfuck Archive, в котором можно найти библиотеки функций, а также интерпретаторы и транспилеры на разных языках, включая компилятор Brainfuck на Brainfuck. Отдельного внимания стоят чемпионаты по лаконичному решению задач.
Следующим по сложности я отмечу другой эзотерический язык программирования, Whitespace. Для написания кода используются всего три символа: перенос строки, пробел и табуляция.
В этом языке 24 команды, включая арифметические операции, работу со стеком и кучей, а также команды управления потоком исполнения: условные и безусловные переходы к метке. Так как в языке всего три символа, то каждая команда кодируется уникальной последовательностью символов. Интересная особенность Whitespace — возможность прятать исходный код программы внутри файлов с «обычным» исходным кодом.
Достоинства:
Легко реализовать интерпретатор для языков с простой структурой. Для этого требуются базовые навыки программирования без специфических знаний.
Язык придуман «с нуля», следовательно, не нужны «костыли» для обыгрывания существующего синтаксиса, как это было описано ранее.
Недостатки:
Чем меньше команд в языке — тем сложнее на нем писать программы.
Но это только начало пути.
Эксперты шокированы: изобретен кликбейтный язык программирования
В 2021 году Линус Ли (Linus Lee), похоже, сильно устал от кликбейтных заголовков в интернете и решил сделать шуточный язык программирования, в котором каждый оператор — это громкий заголовок. Так появился Tabloid. Программа для вычисления чисел Фибоначчи:
DISCOVER HOW TO fibonacci WITH a, b, n RUMOR HAS IT WHAT IF n SMALLER THAN 1 SHOCKING DEVELOPMENT b LIES! RUMOR HAS IT YOU WON'T WANT TO MISS b SHOCKING DEVELOPMENT fibonacci OF b, a PLUS b, n MINUS 1 END OF STORY END OF STORY EXPERTS CLAIM limit TO BE 10 YOU WON'T WANT TO MISS 'First 10 Fibonacci numbers' EXPERTS CLAIM nothing TO BE fibonacci OF 0, 1, limit PLEASE LIKE AND SUBSCRIBE
Язык полностью оправдывает свою кликбейтную задумку: заголовок функции объявляется выражением «DISCOVER HOW TO имя WITH аргументы», что можно примерно перевести как как «СТАЛО ИЗВЕСТНО, КАК имя ПРИ ПОМОЩИ аргументы». Каждая переменная объявляется в этом языке исключительно при участии экспертов: «EXPERTS CLAIM имя TO BE значение». В языке несколько недоработок: отсутствие приоритетов для математических операций, отсутствие комментариев и циклов.
Для нас интересно то, что язык заявляет поддержку переменных, функций и использует разные области видимости. Это требует более «взрослого» подхода c лексером, парсером и абстрактным синтаксическим деревом.
Объяснять чужой код — занятие неблагородное. Возьмем реализацию Tabloid за эталон и напишем свой интерпретатор нового языка.
Машинный язык
Просто переводить Tabloid на русский язык не хочется: это оригинальная идея, а заимствование переводов из комментариев — это нечестно. Поэтому я решил придумать свой простой интерпретируемый язык в стиле Адептус Механикус — Литания. Для отличия от Tabloid введем особенность языка: при старте интерпретатор просит представиться, а доступность функций зависит от ранга пользователя.
Для разработки я буду использовать Python 3.12.
Составление грамматики
Для описания грамматик языков используется нотация Бэкуса-Наура. Составление грамматики — первый шаг в разработке языка программирования. Человеку привычен естественный язык, но машине нужно строгое описание.
Грамматика состоит из двух типов символов.
Терминальные символы — это конкретные, конечные символы языка (буквы, цифры, знаки), из которых состоят итоговые строки.
Нетерминальные символы — это абстрактные синтаксические конструкции (переменные), которые заменяются по правилам грамматики в процессе вывода грамматики.
В нашем случае необходимо все терминальные символы свести в один, который описывает программу. Имена нетерминальных символов в «уголках».
Сперва определим базовые единицы языка: числа, идентификаторы и константы.
<ЦИФРА> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <ЧИСЛО> ::= <ЦИФРА> | <ЧИСЛО><ЦИФРА> <БУКВА> ::= *алфавит русского языка* <ИДЕНТИФИКАТОР> ::= <БУКВА> | <ИДЕНТИФИКАТОР><БУКВА> | <ИДЕНТИФИКАТОР><ЦИФРА> <ИСТИНА> ::= ИСТИНА <ЛОЖЬ> ::= ЛОЖЬ | ЕРЕСЬ <КОНСТАНТА> ::= <ЧИСЛО> | <ИСТИНА> | <ЛОЖЬ> <РАНГ> ::= послушник | техножрец | магос | архимагос <СИМВОЛ> ::= <СИМВОЛ><СИМВОЛ> | <ЦИФРА> | <БУКВА> <СТРОКА> ::= "<СИМВОЛ>"
Затем определим базовые арифметические и логические выражения.
<УНАРНОЕ> ::= <ИДЕНТИФИКАТОР> | <ЧИСЛО> | <СТРОКА> | НЕ <УНАРНОЕ> | <ВЫЗОВ_ФУНКЦИИ> <СУММА> ::= <ВЫРАЖЕНИЕ> + <ВЫРАЖЕНИЕ> // Аналогично для всех операций. Опущено для краткости <ВЫРАЖЕНИЕ> ::= (<ВЫРАЖЕНИЕ>) | <УНАРНОЕ> | <СУММА> | <РАЗНОСТЬ> | <ПРОИЗВЕДЕНИЕ> | <ДЕЛЕНИЕ> | <ЛОГИЧЕСКОЕ И> | <ЛОГИЧЕСКОЕ ИЛИ>
Затем определим операторы и функции:
<ВЫЗОВ ФУНКЦИИ> ::= вызвать <ИДЕНТИФИКАТОР> параметры <АРГУМЕНТЫ> <АРГУМЕНТЫ> ::= <ВЫРАЖЕНИЕ> | <АРГУМЕНТЫ>,<ВЫРАЖЕНИЕ> <ОБЪЯВЛЕНИЕ ФУНКЦИИ> ::= ритуал <ИДЕНТИФИКАТОР> принимает <АРГУМЕНТЫ> требует <РАНГ> <БЛОК> завершить ритуал <БЛОК> ::= <ОПЕРАТОР> | <БЛОК><ОПЕРАТОР> <ПРИСВОЕНИЕ ПЕРЕМЕННОЙ> ::= да будет <ИДЕНТИФИКАТОР> равен <УНАРНОЕ> <ВОЗВРАТ> ::= вернуть <УНАРНОЕ> <УСЛОВНЫЙ> ::= если выражение <ВЫРАЖЕНИЕ> верно <БЛОК> конец условия | если выражение <ВЫРАЖЕНИЕ> верно <БЛОК> иначе <БЛОК> конец условия <ВЫВОД> ::= вывод <ВЫРАЖЕНИЕ> <ОПЕРАТОР> ::= <ОБЪЯВЛЕНИЕ ПЕРЕМЕННОЙ> | <ПРИСВОЕНИЕ ПЕРЕМЕННОЙ> | <ВОЗВРАТ> | <УСЛОВНЫЙ> | <ВЫЗОВ ФУНКЦИИ> | <ВЫВОД> <ПРОГРАММА> ::= <ОПЕРАТОР> | <ПРОГРАММА><ОПЕРАТОР> | <ПРОГРАММА><ОБЪЯВЛЕНИЕ ФУНКЦИИ>
«Корневой» нетерминальный символ грамматики — <ПРОГРАММА>. Если грамматика составлена верно, то код синтаксически верной программы можно свернуть в этот символ, следуя заданным правилам.
Составление грамматики может быть скучным и нудным процессом, но это обязательный этап, который позволяет заключить естественный язык в рамки, упрощающие написание кода. Более того, наличие записанной грамматики позволяет выделить ключевые слова языка.
В «нормальных» языках программирования редко допускают составные ключевые слова и используют пробел как удобный разделитель. В моем языке для объявления переменной используется два слова — «да будет». Это несколько усложнит лексер, но не более.
Теперь у нас есть грамматика, переходим к написанию кода.
Лексер
Первый обязательный этап компилятора — лексер. Компилятору на вход подается программа в виде строки. Минимальная единица информации в строке — символ, что избыточно для компилятора.
Лексер преобразует программу-строку в массив токенов. Токен — это структура данных, которая содержит последовательность из оригинальной строки и мета-информацию, полезную на следующем этапе. В нашем случае отдельными токенами становятся:
Ключевые слова: «ритуал», «да», «будет», «конец», «условия» и так далее. Каждое слово имеет свое уникальное внутреннее представление, которое используется на следующих этапах.
Числа.
Строки — последовательность любых символов, заключенная в кавычки.
Лексер не проверяет синтаксическую правильность программы, он лишь выделяет ключевые слова, константы и идентификаторы.
Написание лексера — это рутинная задача, которую мало кто хочет делать своими руками. В образовательных целях, конечно, можно потр��тить несколько часов времени, но хорошим тоном будет использовать существующие инструменты. Вот, например, статья про генератор лексера flex от 2010 года. Задача настолько не нова, что генератор лексеров lex появился более 50 лет назад.
Для языка программирования Python существует библиотека ply (Python Lex-Yacc), которая реализует генераторы lex и yacc в терминах Python. Генератор лексеров требует список внутренних идентификаторов для каждого токена, а также регулярное выражение, соответствующее токену в строке.
from ply import lex # Ключевое слово: токен reserved = { # Присвоение "ДА": "ASSIGN_P1", "БУДЕТ": "ASSIGN_P2", "РАВЕН": "ASSIGN_P3", # Список продолжается… } class LitaniaLexer: def __init__(self, **kwargs): self.lexer = lex.lex(module=self, **kwargs) # Список имён токенов. Обязательно для генератора! tokens = [ 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN', 'ID', 'STRING', 'COMMA', ] + list(reserved.values()) def t_ID(self, t): r'[a-zA-Z_а-яА-Я][a-zA-Z_а-яА-Я0-9]*' val = t.value.strip() # Если есть в словаре, то берем его представление. # Иначе это идентификатор (переменная/имя функции) t.type = reserved.get(val, 'ID') return t def t_STRING(self, t): r'".*"' t.value = t.value.strip('"') return t t_PLUS = r'\+' t_MINUS = r'-' t_TIMES = r'\*' t_DIVIDE = r'/' t_LPAREN = r'\(' t_RPAREN = r'\)' t_COMMA = r',' def t_NUMBER(self, t): r'\d+' t.value = int(t.value) return t # Считаем строки def t_newline(self, t): r'\n+' t.lexer.lineno += len(t.value) # Символы, которые игнорируются t_ignore = ' \t' # Обработка ошибок def t_error(self, t): print("Недопустимый сим��ол '%s'" % t.value[0]) t.lexer.skip(1) # Test it output def test(self, data): self.lexer.input(data) while True: tok = self.lexer.token() if not tok: break print(tok)
С подробным разбором функций лексера ply можно ознакомиться в этой статье от 2013 года. Несмотря на то, что прошло уже 13 лет, принципы работы ply практически не изменились. Я лишь ограничил область работы лексера классом, а не модулем, как это описывалось в статье.
Для маленькой программы «Привет, мир» с вычислением простого выражения будет такой результат работы лексера.
ВЫВОД "Привет, мир" ВЫВОД 2+2*2
LexToken(OUTPUT,'ВЫВОД',1,0) LexToken(STRING,'Привет, мир',1,6) LexToken(OUTPUT,'ВЫВОД',2,20) LexToken(NUMBER,2,2,26) LexToken(PLUS,'+',2,27) LexToken(NUMBER,2,2,28) LexToken(TIMES,'*',2,29) LexToken(NUMBER,2,2,30)
Ознакомиться с полным исходным кодом лексера можно на GitHub.
Результат работы лексера передается на следующий этап.
Парсер
Парсер — это следующий этап обработки исходного текста. Одномерный массив токенов превращается в иерархическую структуру — абстрактное синтаксическое дерево.
На этом этапе проверяется синтаксическая корректность программы, то есть следование формальной грамматике, описанной ранее.
Однако есть одна проблема: грамматика, описанная в форме Бэкуса-Наура позволяет нам смешивать терминальные и нетерминальные символы. Парсер же такого не позволяет, он оперирует токенами, которые определены в лексере. Идея, однако, остается аналогичной: в классе определяются функции, внутри которых описано правило грамматики.
import ply.yacc as yacc class LitaniaParser: tokens = [] # Приоритет операций можно задать в парсере # Это исправляет проблему Tabloid минимальными усилиями precedence = ( ('left', 'LOGICAL_OR', 'LOGICAL_AND'), ('left', 'GT', 'LT', 'EQ'), ('left', 'PLUS', 'MINUS'), ('left', 'TIMES', 'DIVIDE'), ('right', 'UMINUS'), ) def __init__(self, lexer): self.lexer = lexer self.tokens = lexer.tokens def p_expr_math(self, p): """EXPR : EXPR TIMES EXPR | EXPR DIVIDE EXPR | EXPR PLUS EXPR | EXPR MINUS EXPR | EXPR GT EXPR | EXPR LT EXPR | EXPR EQ EXPR | EXPR LOGICAL_OR EXPR | EXPR LOGICAL_AND EXPR""" p[0] = NodeBinaryOperation( type=p[2], left=p[1], right=p[3], ) # Парсер проверяет составные ключевые слова # ЕСЛИ (IF_P1) УТВЕРЖДЕНИЕ (IF_P2) def p_if(self, p): """IF_STATEMENT : IF_P1 IF_P2 EXPR IF_P3 CODE ENDIF_P1 ENDIF_P2""" p[0] = NodeIfStatement( condition=p[3], # EXPR branch_true=p[5], # CODE branch_false=[], ) def build(self, **kwargs): self.parser = yacc.yacc(module=self, start="PROG", **kwargs)
Каждое правило парсера принимает один аргумент, который позволяет по индексу получить представление токена. В каждом правиле нужно заполнить нулевой элемент представления.
Я сразу использую эту возможность для построения синтаксического дерева. Например, бинарные операции помещаются в узел, который содержит тип, а также два операнда. Синтаксическое дерево выглядит так.
[ { "val": { "val": "Привет, мир", "node_type": "const" }, "node_type": "output" }, { "val": { "type": "+", "left": { "val": 2, "node_type": "const" }, "right": { "type": "*", "left": { "val": 2, "node_type": "const" }, "right": { "val": 2, "node_type": "const" }, "node_type": "binary_op" }, "node_type": "binary_op" }, "node_type": "output" } ]
Ознакомиться с полным исходным кодом парсера можно на GitHub.
Внимательно вглядитесь в эту структуру данных. Мы все ближе к машинному представлению. Остался последний шаг — интерпретатор.
Интерпретатор
Абстрактное синтаксическое дерево состоит из узлов, которые описывают действия и операнды. Взгляните еще раз в пример в предыдущем разделе.
Верхний уровень — это массив из двух объектов. По одному на каждую строчку программы.
Первая команда состоит из узла типа «output», который в качестве операнда содержит константу.
Вторая команда содержит «output» с двумя вложенными бинарными операциями.
Идея проста: берем первый узел дерева и вычисляем значение всех операндов, то есть спускаемся на уровень ниже. Повторяем так до тех пор, пока не обойдем все дерево. Минимальный вариант интерпретатора, который выполняет арифметические операции, выглядит так.
class LitaniaInterpreter: def __init__(self, parser): self.parser = parser op = { "+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b, "/": lambda a, b: a / b, "БОЛЬШЕ": lambda a, b: 1 if a > b else 0, "МЕНЬШЕ": lambda a, b: 1 if a < b else 0, "РАВНО": lambda a, b: 1 if a == b else 0, "И": lambda a, b: 1 if a and b else 0, "ИЛИ": lambda a, b: 1 if a or b else 0, } def eval_list(self, node_list: list[BaseNode]): for node in node_list: self.eval(node) def eval(self, node: BaseNode): if isinstance(node, NodeConst): # Для констант возвращаем значение return node.val elif isinstance(node, NodeUnaryMinus): # Унарный минус e = self.eval(node.val) return -e elif isinstance(node, NodeBinaryOperation): # Для бинарных операций вычисляем операнды, # потом применяем операцию l = self.eval(node.left) r = self.eval(node.right) return self.op[node.type](l, r) elif isinstance(node, NodeOutput): # Выводим значение операнда e = self.eval(node.val) print(e) else: raise RuntimeError(f"Неизвестный узел дерева: {node}") def run(self, data): self.parser.build() ast: list[BaseNode] = self.parser.test(data) self.eval_list(ast)
Для хранения значения переменных в интерпретатор вводится массив словарей vars, а для хранения функций — словарь funcs. Единственным нетривиальным моментом является именно вызов описанных функций.
Функция может объявлять свои переменные, которые могут совпадать по имени с уже существующими переменными. Исключить пересечение можно с помощью области видимости: при входе в функцию создается новый словарь в массиве vars, с которым работает запускаемая функция.
Функция может прервать свое исполнение в любой момент оператором возврата. В интерпретаторе это сделано генерацией исключения ReturnException.
Ознакомиться с полным исходным кодом интерпретатора можно на GitHub.
Пример программ на Литании
Вычисление чисел Фибоначчи.
РИТУАЛ фибоначчи ПРИНИМАЕТ первое, второе, всего ТРЕБУЕТ ПОСЛУШНИК ВЫВОД первое + второе ЕСЛИ УТВЕРЖДЕНИЕ всего РАВНО 0 ВЕРНО ВЕРНУТЬ первое + второе КОНЕЦ УСЛОВИЯ ДА БУДЕТ результат РАВЕН ВЫПОЛНИТЬ фибоначчи ПАРАМЕТРЫ второе, первое + второе, всего - 1 ВЕРНУТЬ результат ЗАВЕРШИТЬ РИТУАЛ ВЫПОЛНИТЬ фибоначчи ПАРАМЕТРЫ 0, 1, 10
Получился какой-то странный диалект известного российского языка программирования.
Заключение
Написать свой интерпретируемый язык программирования — не самая сложная задача, которая, тем не менее, требует очень скрупулезного подхода. Вероятно, материала данной статьи хватит, чтобы за вечер написать интерпретатор калькулятора или игрушечный язык программирования, аналогичный Литании или Таблоиду.
Для разработки более серьезных проектов нужно погружаться в теорию и более сложные инструменты.
Я лишь поверхностно коснулся темы формальных языков и грамматик и их классификации.
В статье не рассматривалась тема оптимизации кода.
Если интерпретируемые языки кажутся вам «фальшью», то у проекта LLVM есть многостраничный туториал по созданию фронтенда компилятора*, который позволяет создавать нативный код. Там все по-взрослому.
* В терминах LLVM «фронтенд» — это программа, которая транслирует язык программирования в байт-код LLVM IR. Затем «бэкэнд» транслирует LLVM IR в машинный код для заданной архитектуры.
Исходный код проекта доступен на GitHub.
Подписывайтесь на мой Telegram‑канал — там можно увидеть заметки по статьям, над которыми работаю, публикую небольшие познавательные посты, а по пятницам традиционно выкладываю мемы.
