Интерпретатор Brainfuck с помощью нормальных алгоритмов Маркова

Под катом вы найдете самую ненормальную реализацию интерпетатора Brainfuck с помощью нормальных алгоритмов Маркова. В этой реализации все операторы Brainfuckа и сам интерпретатор являются нормальными алгоритмами Маркова. Целью этого поста было рассмотреть Brainfuck с точки зрения классической теории алгоритмов и привести его реализацию с помощью какого-либо классического уточнения понятия алгоритма. Кто не боится причинить своему мозгу вред столь ненормальным программированием добро пожаловать (под катом много текста, иногда сложного для понимания если не знаком с теорией алгоритмов, но в конце поста есть ссылка на реализацию этого интерперетатора, который можно попробовать в действии). Его быстродействие, по понятным причинам не очень высоко, но с точки зрения понимания алгоритмов работы он очень наглядный.

Как родилась такая идея

Все началось с того, что масса постов о Brainfuck на хабре подбила меня все же выучить что это такое. Кроме того на этот пост меня натолкнул мой друг, тоже программист, который сказал что-то вроде:«Раз ты мучаешь студентов в универе этой теорией алгоритмов, то опиши интерпретатор Brainfuck с помощью примитивно рекурсивной функции». Эта фраза и плохая погода и настроение и подтолкнула к тому, что получилось. Поскольку хабр ИТ а не математический ресурс, то вместо реализации с помощью рекурсивных функций мне показалось более правильным сделать реализацию с помощью нормальных алгоритмов Маркова.
Чтобы познакомиться с основными понятиями, которые будут встречаться можно почитать:
Brainfuck;
Рекурсивные функции;
Нормальный алгоритм Маркова.

Собственно полнейший Brainfuck

Как известно, Brainfuck является Тьюринг полным языком, что теоретически позволяет реализовать с его помощью любой алгоритм. Давайте посмотрим чем же является Brainfuck с точки зрения теории алгоритмов. Наиболее точно можно охарактеризовать его как некий гибрид машины Тьюринга и машины с натуральнозначными регистрами. Поскольку Brainfuck является Тьюринг полным, то значит его можно реализовать как на машине с натуральнозначными регистрами так и на машине Тьюринга, рекурсивных функциях, алгоритмах Маркова(чем я и занялся).
И так, что реализовано:

Команда Brainfuck	Описание команды	Реализовано?
>	перейти к следующей ячейке	Реализовано.
<	перейти к предыдущей ячейке	Реализовано.
+	увеличить значение в текущей ячейке на 1	Реализовано.
-	уменьшить значение в текущей ячейке на 1	Реализовано.
.	напечатать значение из текущей ячейки	Реализовано.
,	ввести извне значение и сохранить в текущей ячейке	Не реализовано, так эта операция не представляет особого интереса с точки зрения алгоритмов Маркова
[	если значение текущей ячейки нуль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей ] (с учётом вложенности)	Реализовано.
]	если значение текущей ячейки не нуль, перейти назад по тексту программы на символ [ (с учётом вложенности)	Реализовано.

Что нужно для реализации интерпретатора на нормальных алгоритмах Маркова: строка, в которую будем вводить код на брейнфаке(без оператора "," ), строка выполняющая роль ленту памяти, строка буффера(для вывода результата), строка для вывода результата.

При начале работе интерпретатора строка-лента должна иметь вид
._…
Количество точек — это количество доступных ячеек памяти, символ _ — указатель на текущую ячейку.
Продукции алгорима Маркова будем задавать в виде двух массивов строк одинаковой длины: первый — левые части продукций, второй — правые. Если правая часть продукции заканчивается на FIN, то это значит что эта продукция будет финальной.
Начнем с того, что проще — реализация операций брейнфака алгоритмами Маркова.

Команда Brainfuck	Реализация алгоритмом Маркова
>	В строке-ленте: string[] left = new string[5] { "|_.", "@_|", "@_.", "_..", "_.|" }; string[] right = new string[5] { "|.@_", "|@_", "_.FIN", "._.FIN", ".@_" };
<	В строке-ленте: string[] left = new string[2] { "|_", "._" }; string[] right = new string[2] { "_|", "_.FIN" };
+	В строке-ленте: string[] left = new string[1] { "_"}; string[] right = new string[1] { "|_FIN"};
-	В строке-ленте: string[] left = new string[1] { "|_" }; string[] right = new string[1] { "_FIN" };
.	В строке-буффере: | > .a a. >.a .. >. .aaaaaaaaaa > a,. ,a > a, .aaaaaaaaa > 9 .aaaaaaaa > 8 .aaaaaaa > 7 .aaaaaa > 6 .aaaaa >5 .aaaa > 4 .aaa > 3 .aa > 2 .a > 1 . > 0 , > a > .a тут печатаем в строку OUT символ с номером из буфера 1>0 2>0 3>0 4>0 5>0 6>0 7>0 8>0 9>0 00>0
[	В строке-исходнике(учитывает вложенность []) string[] left = new string[10] { "_+", "_-", "_.", "_,", "_<", "_>","_[","_]","**","]*" }; string[] right = new string[10] { "+_", "-_", "._", ",_", "<_", ">_","[__","]*","_","]_FIN" };
]	В строке-исходнике(учитывает вложенность []) string[] left = new string[11] { "+_", "-_", "._", ",_", "<_", ">_", "]_", "[_", "*_","[**", "[*" }; string[] right = new string[11] { "_+", "_-", "_.", "_,", "_<", "_>", "__]", "[*","**", "_[", "_[FIN" };

Ну и теперь собственно нормальный алгоритм-интерпретатор. Выполняется на строке-исходнике, после каждой продукции вызывается подалгоритм из таблицы операций(см. выше).

Что заменить	На что заменить	Вызываемый подалгоритм
_+	+_	+
_-	-_	-
_[	[_	[
_>	>_	>
_<	<_	<
_]	Если на строке-ленте можно выполнить продукцию ._. на ._.FIN, то ]_ иначе вызов подалгоритма ]	]
_.	._	.

У Вас есть возможность выполнить всю программу сразу или выполнять ее шаг за шагом. Реализация на С#, так что для ее работы нужен установленный .NET 2.0.
Демонстарция работа классического Hello World! на Brainfuck на этом интерпретаторе.


P.S. Надеюсь это было хоть кому-нибудь интересно. Старался уложится в максимально небольшой объем текста.
Реализация интерпретатора. Можете попробовать этого монстрика в работе.