Хочу рассказать о том, как сделать интерпретатор с помощью библиотеки Graph-talk. В качестве примера будет использоваться замечательный язык Brainfuck.
Грамматика языка
Всего в языке имеется 8 команд:
- «>» — переход к следующей ячейке памяти;
- «<» — переход к предыдущей ячейке памяти;
- «+» — увеличить значение в текущей ячейке на 1;
- «-» — уменьшить значение в текущей ячейке на 1;
- «.» — вывести значение текущей ячейки;
- «,» — ввести значение извне в текущую ячейку
- «[» — начало цикла, выполнить содержимое внутри цикла, если в текущей ячейке не 0;
- «]» — конец цикла, вернуться на начало с учетом вложенности.
Собственно, это все. Изначально имеется 30 000 ячеек памяти. «Hello, World!» на этом милейшем языке выглядит так:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
——.———.>+.>.
Основные понятия graph-talk
Graph-talk изначально проектировалась как библиотека для операций разбиения на лексемы, парсинга и интерпретации текстов, написанных на формальных языках.
Формальные языки и процессы обработки в ней представляются в виде графов, которые, в свою очередь, состоят из вершин (понятий) и дуг (связей или отношений между ними).
Есть 4 типа понятий:
- Простое понятие — лист дерева с некоторым названием (класс Notion);
- Активное понятие — простое понятие, которое вызывает некоторую функцию при его обработке (ActionNotion);
- Составное понятие — содержит в себе несколько других понятий в указанном порядке (ComplexNotion);
- Выборочное понятие — аналог оператора «select», составное понятие, которое содержит в себе одно из нескольких понятий (SelectiveNotion).
Понятия связаны между собой отношениями 4-х типов:
- Простая связь — соединяет вместе два понятия, одно из которых называется Subject, а другое — Object (класс Relation);
- Направленная связь — позволяет переходить от одного понятия к другому, если выполняется заданное условие (NextRelation);
- Активная связь — направленная связь, которая вызывает функцию при ее обработке (ActionRelation);
- Распознающая связь — направленная связь, которая «поглощает» обработанный текст, если он совпадает с ее условием (ParsingRelation);
- Циклическая связь — направленная связь, которая повторяет выбранное понятие указанное число раз (LoopRelation);
Для обработки используется несколько типов процессов (Process) с разными возможностями. Для данного примера нам будет нужен процесс распознавания (ParsingProcess). ParsingProcess получает на вход текст и стартовую вершину графа для обработки. Затем он начинает обход графа, передавая имеющуюся у него информацию о тексте элементам графа. В зависимости от типа элемента он получает «ответы» с указаниями о дальнейших действиях, например: перейти к следующему элементу, выполнить функцию, обработать кусок текста и так далее. В конечном итоге весь входной текст оказывается обработан при помощи распознающих связей.
Моделирование процесса интерпретации
Программа представляет собой набор команд. С помощью графа можно представить это следующим образом:

Программа — это составное понятие, которое будет состоять из нескольких активных понятий в том порядке, в котором они встречаются в программе.
Для того чтобы реализовать цикл, его тело помещается внутрь соответствующего составного понятия, которое будет повторять содержимое до тех пор, пока значение текущей ячейки будет не 0. Это реализуется с помощью циклической связи (LoopRelation). На рисунке внизу показан цикл, который будет печатать содержимое текущей ячейки до тех пор, пока оно больше нуля:

Для непосредственного выполнения команд реализуются соответствующие функции, которые будут затем исполняться виртуальной машиной Brainfuck. После распознавания команды вызов функции помещается в граф программы как активное понятие. Когда входной текст полностью обработан, процесс обхода переходит на граф программы и начинает его выполнение. Вот как будет выглядеть граф программы «,[-.]» — ввода и печати содержимого ячейки, пока оно больше 0:

Как видно из рисунка, сам процесс интерпретации («Interpreter») состоит из обработки исходного кода («Source», будет одинаковым для всех программ на языке Brainfuck) и результирующей программы («Program»).
Исходный код состоит из команд («Commands»), которых может быть сколько угодно и которые мы будем продолжать искать до тех пор, пока текст не кончится. Каждая команда может быть одной из 8 команд языка, пробелом или чем-то другим (то есть ошибкой). Выбор команды осуществляется при помощи выборочного понятия («Command») и распознающих связей (ParsingRelation), каждая из которых «съедает» соответствующий текст при совпадении условия. Распознающие связи ведут к активным понятиям, функции которых помещают новые активные понятия, которые будут выполнять функции языка, в граф результирующей программы.
Несколько интересных моментов:
- Связь «пробел» в качестве условия использует регулярное выражение. При наличии символов пробела все они будут удалены из текста.
- Связь «ошибка» помечена как связь по умолчанию («default») для понятия «Command». Это означает, что процесс перейдет на нее только в том случае, если все другие связи не сработают.
- Для поддержки вложенности циклов необходимо «прикреплять» новые команды не к самому верхнему понятию программы, а к понятию «Top», которое зависит от уровня цикла. Для этого используется стек понятий «Top», при создании нового цикла в него помещается новый элемент, а при окончании цикла элемент извлекается и новые команды начинают подключаться на уровень выше.
Полный код примера находится здесь.
Кроме интерпретатора, в нем приводится модель процесса преобразования кода на Brainfuck в код на Python, что значительно упрощает чтение текстов на этом эзотерическом языке.