Хочу рассказать о том, как сделать интерпретатор с помощью библиотеки Graph-talk. В качестве примера будет использоваться замечательный язык Brainfuck.

Грамматика языка

Всего в языке имеется 8 команд:

• «>» — переход к следующей ячейке памяти;
• «<» — переход к предыдущей ячейке памяти;
• «+» — увеличить значение в текущей ячейке на 1;
• «-» — уменьшить значение в текущей ячейке на 1;
• «.» — вывести значение текущей ячейки;
• «,» — ввести значение извне в текущую ячейку
• «[» — начало цикла, выполнить содержимое внутри цикла, если в текущей ячейке не 0;
• «]» — конец цикла, вернуться на начало с учетом вложенности.

Собственно, это все. Изначально имеется 30 000 ячеек памяти. «Hello, World!» на этом милейшем языке выглядит так:

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
——.———.>+.>.

 

Основные понятия graph-talk

Graph-talk изначально проектировалась как библиотека для операций разбиения на лексемы, парсинга и интерпретации текстов, написанных на формальных языках.

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

Есть 4 типа понятий:

1. Простое понятие — лист дерева с некоторым названием (класс Notion);
2. Активное понятие — простое понятие, которое вызывает некоторую функцию при его обработке (ActionNotion);
3. Составное понятие — содержит в себе несколько других понятий в указанном порядке (ComplexNotion);
4. Выборочное понятие — аналог оператора «select», составное понятие, которое содержит в себе одно из нескольких понятий (SelectiveNotion).

Понятия связаны между собой отношениями 4-х типов:

1. Простая связь — соединяет вместе два понятия, одно из которых называется Subject, а другое — Object (класс Relation);
2. Направленная связь — позволяет переходить от одного понятия к другому, если выполняется заданное условие (NextRelation);
3. Активная связь — направленная связь, которая вызывает функцию при ее обработке (ActionRelation);
4. Распознающая связь — направленная связь, которая «поглощает» обработанный текст, если он совпадает с ее условием (ParsingRelation);
5. Циклическая связь — направленная связь, которая повторяет выбранное понятие указанное число раз (LoopRelation);

Для обработки используется несколько типов процессов (Process) с разными возможностями. Для данного примера нам будет нужен процесс распознавания (ParsingProcess). ParsingProcess получает на вход текст и стартовую вершину графа для обработки. Затем он начинает обход графа, передавая имеющуюся у него информацию о тексте элементам графа. В зависимости от типа элемента он получает «ответы» с указаниями о дальнейших действиях, например: перейти к следующему элементу, выполнить функцию, обработать кусок текста и так далее. В конечном итоге весь входной текст оказывается обработан при помощи распознающих связей.

Моделирование процесса интерпретации

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

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

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

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

Как видно из рисунка, сам процесс интерпретации («Interpreter») состоит из обработки исходного кода («Source», будет одинаковым для всех программ на языке Brainfuck) и результирующей программы («Program»).

Исходный код состоит из команд («Commands»), которых может быть сколько угодно и которые мы будем продолжать искать до тех пор, пока текст не кончится. Каждая команда может быть одной из 8 команд языка, пробелом или чем-то другим (то есть ошибкой). Выбор команды осуществляется при помощи выборочного понятия («Command») и распознающих связей (ParsingRelation), каждая из которых «съедает» соответствующий текст при совпадении условия. Распознающие связи ведут к активным понятиям, функции которых помещают новые активные понятия, которые будут выполнять функции языка, в граф результирующей программы.

Несколько интересных моментов:

1. Связь «пробел» в качестве условия использует регулярное выражение. При наличии символов пробела все они будут удалены из текста.
2. Связь «ошибка» помечена как связь по умолчанию («default») для понятия «Command». Это означает, что процесс перейдет на нее только в том случае, если все другие связи не сработают.
3. Для поддержки вложенности циклов необходимо «прикреплять» новые команды не к самому верхнему понятию программы, а к понятию «Top», которое зависит от уровня цикла. Для этого используется стек понятий «Top», при создании нового цикла в него помещается новый элемент, а при окончании цикла элемент извлекается и новые команды начинают подключаться на уровень выше.

Полный код примера находится здесь.

Кроме интерпретатора, в нем приводится модель процесса преобразования кода на Brainfuck в код на Python, что значительно упрощает чтение текстов на этом эзотерическом языке.