Как стать автором
Обновить

Компилятор Brainfuck в .NET

Время на прочтение 5 мин
Количество просмотров 7.6K
Здравствуйте.
Смотрю я, что у вас неделя BrainFuck-а и я решил написать компилятор, тем более, что в комментариях к этой статье просили рассказать поподробнее про динамические методы. В этой статье мы рассмотрим этот метод компиляции кода и попробуем сделать компилятор самого нормального простого языка

Вступление


Для того, чтобы скомпилировать любой исходный код в платформе .NET необходимо сделать 3 вещи:
  1. Создать новый проект и подключить к нему пространства имен System.Reflection и System.Reflection.Emit
  2. Обеспечить ввод и проверку исходного кода
  3. Скомпилировать этот код в исполняемый файл

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

Итак, проверка исходного кода


Для того, чтобы проверить исходный код на правильность нам необходимо знать из каких операндов он состоит. Их всего 8:
  1. > — перейти к следующей ячейке
  2. < — перейти к предыдущей ячейке
  3. + — увеличить значение в текущей ячейке на 1
  4. — — уменьшить значение в текущей ячейке на 1
  5. . — напечатать значение из текущей ячейки
  6. , — ввести извне значение и сохранить в текущей ячейке
  7. [ — если значение текущей ячейки нуль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей ] (с учётом вложенности)
  8. ] — если значение текущей ячейки не нуль, перейти назад по тексту программы на символ [ (с учётом вложенности)


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

Напишем функцию, проверяющую код:

public bool CheckSource()
{
if (Src.Length == 0) throw new ArgumentException("Исходный код имеет нулевую длину");
int State = 0;
for (int i = 0; i < Src.Length; i++)
{
if (Src[i] == '[') State++;
if (Src[i] == ']') State--;
//Выкидываем ошибку, если код неправильный.
if (State < 0) throw new ArgumentException(String.Format("Исходный код не соответствует правилам построения. Позиция: {0}", i++));
}
if (State != 0) Console.WriteLine("Исходный код не соответствует правилам построения.");
return State == 0;
}


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

Компиляция


Сразу оговорюсь, что реализовывать будем компилятор с ограничением памяти 30000 байт. Каждая ячейка имеет размер 1 байт.

Для того, чтобы компилировать в уме сделать компилятор, необходимо разобраться с классом AssemblyBuilder.
Результатом операций над ним становится исполняемый файл или библиотека.
AssemblyBuilder ASM = AppDomain.CurrentDomain.DefineDynamicAssembly(new AssemblyName("BrainFuck Compiled Program"), AssemblyBuilderAccess.RunAndSave); //Создаем сборку
ASM.Save(Filename);

Этот код не создаст пустую сборку. Для того, чтобы эта сборка не была пустой, ее надо наполнить модулями.
ModuleBuilder MDB = ASM.DefineDynamicModule(Filename); //Создаем модуль в сборке

Этот код создаст модуль с именем равным имени сборки.
И создадим в нем класс Program
TypeBuilder TPB = MDB.DefineType("Program", TypeAttributes.Class); //Создаем класс в модуле
TPB.CreateType(); //Завершаем класс

Теперь у нас есть класс. Все операции будем производить в нем.
Нам необходим массив – память и указатель в ней.
FieldBuilder FDB_1 = TPB.DefineField("Memory", typeof(byte[]), FieldAttributes.Private); // private byte[] Memory; //Память для операций.
FieldBuilder FDB_2 = TPB.DefineField("Point", typeof(int), FieldAttributes.Private); //private int Point; //Указатель в памяти.

Вся программа будет в Main.
Ну что ж, напишем Main и сделаем его точкой входа:
MethodBuilder MTB = TPB.DefineMethod("Main", MethodAttributes.Static, CallingConventions.Any); //static void Main() //Main Procedure
ASM.SetEntryPoint(MTB.GetBaseDefinition());

Теперь необходимо инициализировать переменные, заведенные ранее. MSDN говорит, что это делается так:
ILGenerator MTB_IL=MTB.GetILGenerator();
MTB_IL.Emit(OpCodes.Ldc_I4,30000); //Загружаем в стек 30000 - длина нового массива памяти
MTB_IL.Emit(OpCodes.Newarr,typeof(byte)); //Создаем массив 30000 байтов
MTB_IL.Emit(OpCodes.Stsfld, FDB_1); //Ставим указатель Memory на созданный массив


Потом описываем все действия: (куча кода, но прокомментированная)
foreach (var t in Src) //Так как каждый оператор самодостаточен, то можно просто записывать каждый.
{
switch (t)
{
case '>':
{
MTB_IL.Emit(OpCodes.Ldsfld,FDB_2); //Помещаем в стек поле POINT
MTB_IL.Emit(OpCodes.Ldc_I4_1); //Помещаем в стек 1
MTB_IL.Emit(OpCodes.Add); //Плюс
MTB_IL.Emit(OpCodes.Stsfld,FDB_2); //Выполняем операцию с Point то есть сдвигаем указатель вправо
break;
}
case '<':
{
MTB_IL.Emit(OpCodes.Ldsfld, FDB_2);//Помещаем в стек поле POINT
MTB_IL.Emit(OpCodes.Ldc_I4_1); //Помещаем в стек 1
MTB_IL.Emit(OpCodes.Sub); //Минус
MTB_IL.Emit(OpCodes.Stsfld, FDB_2); //Выполняем операцию с Point то есть сдвигаем указатель вправо
break;
}
case '+':
{
MTB_IL.Emit(OpCodes.Ldsfld, FDB_1);//Помещаем в стек поле MEMORY
MTB_IL.Emit(OpCodes.Ldsfld, FDB_2);//Помещаем в стек поле POINT
MTB_IL.Emit(OpCodes.Ldelema, typeof(byte)); //Помещаем в стек элемент MEMORY[POINT]
MTB_IL.Emit(OpCodes.Dup);
MTB_IL.Emit(OpCodes.Ldobj, typeof(byte));
MTB_IL.Emit(OpCodes.Ldc_I4_1);
MTB_IL.Emit(OpCodes.Add); //Плюс
MTB_IL.Emit(OpCodes.Conv_U1);
MTB_IL.Emit(OpCodes.Stobj, typeof(byte));//Сохраняем
break;
}
case '-':
{
MTB_IL.Emit(OpCodes.Ldsfld, FDB_1);//Помещаем в стек поле MEMORY
MTB_IL.Emit(OpCodes.Ldsfld, FDB_2);//Помещаем в стек поле POINT
MTB_IL.Emit(OpCodes.Ldelema, typeof(byte));//Помещаем в стек элемент MEMORY[POINT]
MTB_IL.Emit(OpCodes.Dup);
MTB_IL.Emit(OpCodes.Ldobj, typeof(byte));
MTB_IL.Emit(OpCodes.Ldc_I4_1);
MTB_IL.Emit(OpCodes.Sub); //Минус
MTB_IL.Emit(OpCodes.Conv_U1);
MTB_IL.Emit(OpCodes.Stobj, typeof(byte));//Сохраняем
break;
}
case '[':
{
var Lbl = MTB_IL.DefineLabel(); //Объявляем метку
MTB_IL.MarkLabel(Lbl); //И помечаем ей то место куда будем возвращаться, то есть начало цикла
Scopes.Push(Lbl); //В стек. Иначе не узнаем куда :)
break;
}
case ']':
{
MTB_IL.Emit(OpCodes.Ldsfld, FDB_1); //Конструкция из этих 3х элементов
MTB_IL.Emit(OpCodes.Ldsfld, FDB_2); //загружает в стек значение из массива
MTB_IL.Emit(OpCodes.Ldelem_U1); //FDB_1 по адресу FDB_2
MTB_IL.Emit(OpCodes.Ldc_I4_0); //Загружаем в стек 0
MTB_IL.Emit(OpCodes.Ceq); // Если текущая ячейка=0
MTB_IL.Emit(OpCodes.Brtrue,5); //Переход на послеследующую инструкцию
MTB_IL.Emit(OpCodes.Br,Scopes.Pop()); //Иначе на начало цикла. Занимает 5 байт.
break;
}
case '.':
{
MTB_IL.Emit(OpCodes.Ldsfld, FDB_1);//Помещаем в стек поле MEMORY
MTB_IL.Emit(OpCodes.Ldsfld, FDB_2);//Помещаем в стек поле POINT
MTB_IL.Emit(OpCodes.Ldelem_U1);//Помещаем в стек элемент MEMORY[POINT]
MTB_IL.EmitCall(OpCodes.Call,typeof(Console).GetMethod("WriteLine",new[] {typeof(char)}),new[] {typeof(char)}); //Console.WriteLine(MEMORY[POINT]);
MTB_IL.Emit(OpCodes.Nop);
break;
}
case ',':
{
MTB_IL.Emit(OpCodes.Ldsfld, FDB_1);//Помещаем в стек поле MEMORY
MTB_IL.Emit(OpCodes.Ldsfld, FDB_2);//Помещаем в стек поле POINT
MTB_IL.EmitCall(OpCodes.Call, typeof(Console).GetMethod("ReadLine"), new[] { typeof(string) }); //Console.ReadLine();
MTB_IL.Emit(OpCodes.Call,typeof(Convert).GetMethod("ToByte",new[] {typeof(string)})); //Конвертация в байт.
MTB_IL.Emit(OpCodes.Stelem_I1); //Сохраняем
break;
}
}
}


И все!

MTB_IL.Emit(OpCodes.Ret); //Заканчиваем
TPB.CreateType(); //Завершаем класс
ASM.Save(Filename); //Сохраняем сборку


Для желающих, здесь исходный код + .sln для VS2010

UPD: Перенес в Ненормальное программирование
Теги:
Хабы:
+20
Комментарии 35
Комментарии Комментарии 35

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн
PG Bootcamp 2024
Дата 16 апреля
Время 09:30 – 21:00
Место
Минск Онлайн
EvaConf 2024
Дата 16 апреля
Время 11:00 – 16:00
Место
Москва Онлайн