Си компилятор для машины Тьюринга

[vak]

Собираем компилятор:

git checkout https://github.com/retrage/elvm.git
cd elvm
make tm

При сборке будет прогнана куча тестов, так что понадобятся три гигабайта места на диске. Результат окажется в каталоге out:

$ size out/8cc out/elc out/tm
   text	   data	    bss	    dec	    hex	filename
 150381	   3136	   5184	 158701	  26bed	out/8cc
 329064	  83328	  30696	 443088	  6c2d0	out/elc
   6687	    737	     56	   7480	   1d38	out/tm

Здесь 8сс преобразует исходник Си во внутреннее представление (ассемблер виртуальной машины). Затем elc генерит код для целевой архитектуры, в нашем случае для машины Тьюринга. Третий компонент tm это симулятор машины Тьюринга, он выполняет полученный код.

Компилируем и выполняем стандартный тест Hello World:

$ cat test/hello.c
#include <stdio.h>

int main() {
  const char* p = "Hello, world!\n";
  for (; *p; p++)
    putchar(*p);
  return 0;
}
$ out/8cc -S -Ilibc test/hello.c
$ out/elc -tm hello.s > hello.tm
$ out/tm -b -n -v hello.tm
running: steps=10000000 cells=34251
running: steps=20000000 cells=34251
...
running: steps=480000000 cells=34491
halt: accept=1 steps=482391152 cells=34491
Hello, world!

Программа выполняется за 482 миллиона шагов и занимает 34 тысячи ячеек ленты.

Формат кода машины Тьюринга описан в комментариях к симулятору: tm.c