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

Здравствуйте.
Смотрю я, что у вас неделя 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: Перенес в Ненормальное программирование
Share post

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 35

    +13
    Темы с очередными интерпретаторами Brainfuck уже выебали мозг больше, чем сам Brainfuck
    • UFO just landed and posted this here
      +5
      Напишите уже ктонить интерпретатор C# на brainfuck, а не наоборот *irony*
        +7
        Теги code рулят.
          0
          Как пропатчить kde2 под freebsd?
            +3
            Это канал о Брейнфаке, Вам в соседний.
            +1
            Brainfuck week at Habrahabr has already fucked my brain.
              0
              астрологи объявили неделю брейнфака. количест^W ну вы поняли…
              +3
              Может хватит?
                0
                жду брэйнфак на брэйнфаке
                +1
                /me бурчит
                А аккумулятор на текущую операцию?
                Я понимаю, что пост получился бы длиннее, но это можно было бы реализовать в сорцах, на которые вы дали ссылку.

                  0
                  BrainF#? Даешь полную интеграцию с CLR! :-)
                    +1
                    А в памяти сборку можно запустить, не сохраняя на диск? Этакий JIT бы получился…
                      0
                      Качество кода… ну это просто нечто!

                        0
                        Особенно понравилось MTB_IL.Emit(OpCodes.Stsfld,FDB_2);

                        Я даже врагу не пожелаю с такими именами дело иметь
                        –2
                        Блять, напишите уже компилятор/интерпретатор Brainfuck на Brainfuck и успокойтесь…
                        • UFO just landed and posted this here
                            +1
                            Вроде бы неделя уже закончилась
                              +1
                              brain# .NET
                                0
                                Хочу еще увидеть замеры в приросте производительности. Насколько быстрее будет работать скомпилированная программа от интерпритатора. Сколько съест памяти.

                                  +1
                                  Компилятор Brainfuck…

                                  Not this shit again…
                                    +2
                                    Компилятор это интересно. Только не совсем понятно, чем обусловлено ограничение в 30000 байт? Оно же не дос-приложение создает, где сегмент кода ограничен 64Kb… Не знаю, из-за этого ли, но мой любимый тест на скорость выполнения:
                                    >+>+>+>+>++<[>[<+++>-
                                     >>>>>
                                     >+>+>+>+>++<[>[<+++>-
                                       >>>>>
                                       >+>+>+>+>++<[>[<+++>-
                                         >>>>>
                                         >+>+>+>+>++<[>[<+++>-
                                           >>>>>
                                           +++[->+++++<]>[-]<
                                           <<<<<
                                         ]<<]>[-]
                                         <<<<<
                                       ]<<]>[-]
                                       <<<<<
                                     ]<<]>[-]
                                     <<<<<
                                    ]<<]>.

                                    Трапнулся:

                                    Можно как-то поправить, чтоб заработало? Интересно таки сравнить скорость откомпилированного теста и интерпретируемого.
                                    И еще пожелание — чтобы имя файла с кодом на брейнфаке передавать в первом параметре, а не ждать ввода вручную. Чтобы запускать так: BrainFuckCompiler.NET.exe <имя файла.bf>
                                      0
                                      А, еще забыл совсем — при выводе символа не нужно переводить каретку на новую строку. А то из простого Hello World! получается такое:
                                      H
                                      e
                                      l
                                      l
                                      o

                                      w
                                      o
                                      r
                                      l
                                      d
                                      !
                                        0
                                        А что она делает? Штук 5 brainfuck online interpreters тупо зависали…
                                          +1
                                          Если в кратце — просто гоняет много вложенных друг в друга циклов. В конце работы выводит символ ╩
                                            +1
                                            Да, спасибо, уже проверил. Моя реализация на mercury гоняла его 4мин 42 сек, не знаю, на сколько это хороший/плохой результат )
                                              +1
                                              Ну сравните ради эксперимента с моим JIT (или AOT)-интерпретатором: rghost.ru/4249797
                                              Так, на моей рабочей лошадке AMD 64 3000+ (немного разогнан до 2,2Ghz) этот код выполняется за 2-3 секунды.
                                                0
                                                Весьма интересно. Надо попробовать в мою программу добавить похожие оптимизации.
                                    • UFO just landed and posted this here
                                        +2
                                        я написал транслятор брейнфака в nasm, скормил ему dbfi:

                                        disk.tom.ru/g48ssfe
                                        usage:
                                        $ nasm -f elf dbfi.asm
                                        $ ld -s -o dbfi dbfi.o
                                        $ ./dbfi 
                                        ++++++++++[>+++++++>++++++++++>+++>+\
                                        <<<<-]>++.>+.+++++++..+++.>++.<<+++++++++\
                                        ++++++.>.+++.------.--------.>+.>.!
                                        Hello World!
                                        $
                                        • UFO just landed and posted this here
                                            0
                                            обращайтесь, если что =)

                                      Only users with full accounts can post comments. Log in, please.