返回列表

Brainfuck 世界上最小的图灵完备系统

默认分类 2014/08/19 09:20

今天从同学那里抢到了这个 很震惊地听说这门语言居然是图灵完备的。

Brainfuck是一种极小化的计算机语言,它是由Urban Müller在1993年创建的。 由于fuck在英语中是脏话,这种语言有时被称为brainf*ck或brainf***,甚至被简称为BF。 概述 Müller的目标是建立一种简单的、可以用最小的编译器来实现的、符合图灵完全思想的编程语言。 这种语言由八种状态构成,为Amiga机器编写的编译器(第二版)只有240个字节大小!

就象它的名字所暗示的,brainfuck程序很难读懂。 尽管如此,brainfuck图灵机一样可以完成任何计算任务。 虽然brainfuck的计算方式如此与众不同,但它确实能够正确运行。

这种语言基于一个简单的机器模型,除了指令,这个机器还包括: 一个以字节为单位、被初始化为零的数组、 一个指向该数组的指针(初始时指向数组的第一个字节)、 以及用于输入输出的两个字节流。

下面是这八种状态的描述,其中每个状态由一个字符标识:

字符 含义 
> 指针加一 
< 指针减一 
+ 指针指向的字节的值加一 
- 指针指向的字节的值减一 
. 输出指针指向的单元内容(ASCII码) 
, 输入内容到指针指向的单元(ASCII码) 
[ 如果指针指向的单元值为零,向前跳转到对应的]指令的次一指令处 
] 如果指针指向的单元值不为零,向后跳转到对应的[指令的次一指令处

Brainfuck程序可以用下面的替换方法翻译成C语言(假设ptr是char*类型):

Brainfuck C 
> ++ptr; 
< --ptr; 
+ ++*ptr; 
- --*ptr; 
. putchar(*ptr); 
, *ptr =getchar(); 
[ while (*ptr) { ] }

\--------------------------------------------------------------------------------

例子

\--------------------------------------------------------------------------------

Hello World!
一个在屏幕上打印"Hello World!"的程序: \++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>. \--------------------------------------------------------------------------------

当前位置清零
[-]
\--------------------------------------------------------------------------------

字符I/O
,. 从键盘读取一个字符并输出到屏幕上。
\--------------------------------------------------------------------------------

简单的循环
,[.,] 这是一个连续从键盘读取字符并回显到屏幕上的循环。注意,这里假定0表示输入结束,事实上有些系统并非如此。 以-1和"未改变"作为判断依据的程序代码分别是",+[-.,+]"和",[.[-],]"。
\--------------------------------------------------------------------------------

指针维护
\>,[.>,] 通过移动指针保存所有的输入,供后面的程序使用。
\--------------------------------------------------------------------------------

加法
[->+<] 把当前位置的值加到后面的单元中(破坏性的加,它导致左边的单元被归零)。
\--------------------------------------------------------------------------------

条件指令
\,----------[----------------------.,----------] 这个程序会把从键盘读来的小写字符转换成大写。按回车键退出程序。 首先,我们通过,读入第一个字符并把它减10(大多数情况下,brainfuck使用10作为换行符的值)。 如果用户按的是回车键,循环命令([)就会直接跳转到程序的结尾:因为这时第一个字节已经被减到了零。 如果输入的字符不是换行符(假设它是一个小写字符),程序进入循环。 在这里我们再减去剩下的22,这样总共减掉32:这是ASCII码中小写字符和大写字符的差值。

下面我们把它输出到屏幕。然后接收下一个输入字符,并减去10。如果它是换行符,退出循环; 否则,再回到循环的开始,减去22并输出……当循环退出时,因为后面已经没有其他的指令,程序也随之终止。
\--------------------------------------------------------------------------------

加法

,>++++++[<-------->-],,[<+>-]<.

这个程序对两个一位数做加法,并输出结果(如果结果也只有一位数的话):

4+3
7

(现在程序开始有点复杂了。我们要涉及到数组中单元的内容了,比如[0]、[1]、[2]之类。) 第一个输入的数字被放在在[0]中,从中减去48来把它从ASCII码值48到57转换为数值0到9: 这是通过在[1]中放入6,然后按照[1]中的次数让一个循环从[0]中多次减去8来完成的(当加上或减去一个大的数值时,这是常用的办法)。 下一步,加号被读入[1]中;然后,第二个数字被输入,覆盖掉加号。

下面的循环[<+>-]执行最重要的工作:通过把第二个数字移动到第一个里面让它们相加,并把[1]清空。 这里的每次循环都把[0]增一并从[1]中减一;最终,在[1]被置零的多次循环中,[1]中的值就被转移到了[0]中。 现在,[1]中是我们输入的换行符(这个程序里,我们没有设置对输入错误的检查机制)。

然后,指针被移回到指向[0],并输出它的内容([0]里面现在是 a + (b + 48) 的值, 因为我们没有修改b的值,这等于 (a + b) + 48,也就是我们想要输出的ASCII值)。 然后,把指针指向[1],里面保存着前面输入的换行符;输出换行符,程序结束。 \--------------------------------------------------------------------------------

乘法

\,>,,>++++++++[<------<------>>-]_<<[>[>+>+<<-]>>[<<+>>-]<<<-]_>>>++++++[<++++++++>-],<.>.  

和前一个程序类似,不过这次是乘法而不是加法。

第一个输入的数字被放入[0],星号和第二个数字被放入[1],然后两个数值都被校正:减去48。

现在,程序进入了主循环。我们的基本思想是:每次从[0]中减去一,同时把[1]的值加入到保存乘积的[2]中。 在实际操作中,第一个内层循环把[1]的值同时转移到[2]和[3]中,同时[1]清零(这是我们复制数字的基本方法)。 下一个内层循环把[3]中的值重新放回到[1],并清零[3]。然后从[0]中减一,结束外层循环。 在退出这个循环时,[0]中为零,[1]仍然是输入的第二个数值,[2]则是这两个数值的和。 (要是想保存第一个数,我们可以在外层循环中每次给[4]加一,最后把[4]移回[0]。) 在结果中加48,并把换行符读入[3],输出ASCII码的乘积,然后输出刚才保存的换行符。

附上这小子写的C语言实现

//brain_fuck_interpreter
//此版本支持键盘输入,即以互交方式运行.
/*
brain_fuck_instruction_sets

<   ptr := ptr + 1
>   ptr := ptr - 1
+   [ptr] := [ptr] + 1
-   [ptr] := [ptr] - 1
,   [ptr] := in
.   out := [ptr]
[   if( [ptr]==0 ) jmp lable:] + 1
]   if( [ptr]!=0 ) jmp lable:[ + 1

*/
#include<stdio.h>
#include<string.h>
#define BUFFERSIZE 65536
#define MEMORYSIZE 1024
char code[BUFFERSIZE];
char mem[MEMORYSIZE]="The language is called brain fuck...";
//'a':+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
//'A':+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
//'0':++++++++++++++++++++++++++++++++++++++++++++++++.
//Q:输出0123456789
//++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++<[>+.<-]
//
//Q:输出A-Z
//>+++++[>+++++<-]>+>++++++++[>++++++++<-]>+<<[>>.+<<-]
//
//Q:输出a-z
//>+++++[>+++++<-]>+>++++++++++[>++++++++++<-]>---<<[>>.+<<-]
//
//Q:实现echo
//,----------[++++++++++.,----------]
//
//Q:输入a,b输出a+b( a , b , a+b < 10 )
//,>++++++[<-------->-]
//,,[<+>-],<.>.
//
//Q:输入a,b输出a*b( a , b , a*b < 10 )
//,>,,>++++++++[<------<------>>-]
//<<[>[>+>+<<-]>>[<<+>>-]<<<-]
//>>>++++++[<++++++++>-],<.>.
//Q:求3 n + 1问题的循环次数
//>,[
//[
//----------[
//>>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<]
//++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<
//]>
//]>>>++>+>>[
//<<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>]
//>[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]]
//>[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>>
//]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<
//

void run(void)
{   int l=strlen(code),ip=0,si=0,err=0;

    for(int i=0;i<MEMORYSIZE;i++)mem[i]=0;
    while(ip<l&&err==0)
    {
        //printf(" STATUS: ip=%d si=%d cond=%d cur char:%c",ip,si,mem[si],code[ip]);

        switch (code[ip])
        {
            case '<':
                si--;
                if(si<0)err=2;
                break;
            case '>':
                si++;
                if(si>=MEMORYSIZE)err=2;
                break;
            case '+':
                if(mem[si]==127)err=4;
                mem[si]++;
                break;
            case '-':
                if(mem[si]==0)err=4;
                mem[si]--;
                break;
            case '.':
                printf("%c",mem[si]);
                break;
            case ',':
                scanf("%c",&mem[si]);
                break;
            case '[':
                if(mem[si]==0)
                {   while(ip<MEMORYSIZE)
                    {   ip++;
                        if(code[ip]==']'&&err==0)break;
                        if(code[ip]=='[')err++;
                        else if(code[ip]==']')err--;
                        if(ip>=l){err=8;break;}
                    }
                }
                break;
            case ']':
                if(mem[si]!=0)
                {   while(ip>=0)
                    {   ip--;
                        if(code[ip]=='['&&err==0)break;
                        if(code[ip]==']')err++;
                        else if(code[ip]=='[')err--;
                        if(ip<=0){err=8;break;}
                    }
                }
                break;
            case '/':
                break;
            default:
                err=1;
                break;
        }
        if(err==0)ip++;
    }
    switch(err)
    {   case 0:
            break;
        case 1:
            printf("-!--{%c}.%d is illegal char!",code[ip],ip);
            break;
        case 2:
            printf("-!-- slop over");
            break;
        case 4:
            printf("-!-- overflow");
            break;
        case 8:
            printf("-!-- logical error!");
            break;
        default:
            break;
    }
}
int main()
{   char tmp[BUFFERSIZE];
    printf("==== codes terminate by // , exit by '#' ==== bf_code:");
    while(gets(code)!=NULL)
    {   if(strcmp(code,"#")==0)break;
        while(gets(tmp)!=NULL)
        {   strcat(code,tmp);
            if(strcmp(tmp,"//")==0)break;
        }
        if(strcmp(code,"#//")==0)break;

        //printf("%s ",code);

        run();
        printf(" bf_code:");
    }
    printf("bye...");
    getchar();
    return 0;
}