Сразу предупреждаю, те, кто учили CS в ВУЗе могут дальше не читать, интересно не будет. Статья больше для программистов-самоучек без формального образования (вроде меня самого), которые не против узнать какой-нибудь интересный факт из теоретической computer science.
Все наверняка слышали об алгоритмически-неразрешимых задачах. Эти задачи многие воспринимают как что-то очень далёкое и очень теоретическое. Между тем наткнуться на одну из них в обычной жизни не так уж и сложно.
Одним холодным майским днем от скуки решил я таки приступить к изучению этого удивительного языка — Brainfuck'a.
Его интерпретаторы публиковали на Хабре уже очень много раз.
Но мне хотолось изучить поглубже сам язык и алгоритмы на нем, а не писать очередной интерпретатор. Поэтому было решено сделать из мухи слона компилятор какого-нибудь высокоуровневого языка в brainfuck.
Однако очень быстро начался реальный brainfuck: отсутствие оператора if, отсутствие произвольного доступа к ячейкам и куча других проблем сразу свалилась на меня. Пришлось повременить с высокоуровневым языком и сделать для начала ассемблер, в который и будет компилироваться высокоуровневый язык.
О реализации ассемблера под катом.
Читать полностью »
