暮鼓晨钟-河工论坛

 找回密码
 立即入住
查看: 1523|回复: 8

[程序设计] [娱乐]BrainF**k语言解释器一枚&简单分析

[复制链接]

16

主题

2

听众

5752

积分

伴坛终老

鸟人

Rank: 3Rank: 3

签到天数: 12 天

[LV.3]大三老生

在线时间
950 小时
最后登录
2012-3-3
威望
5566 点
金钱
23956 HGB
注册时间
2011-2-4
积分
5752
记录
0
日志
0
帖子
520
精华
0
好友
25
鲜花(5) 鸡蛋(0)
发表于 2011-7-23 13:38:13 |显示全部楼层
本帖最后由 愤怒的菜鸟 于 2011-7-23 13:45 编辑

Brainfuck(google,wiki),是一种极小化的计算机语言,它是由Urban Müller1993年创建的。由于fuck英语中是脏话,这种语言有时被称为brainf*ckbrainf***,甚至被简称为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) {
]        }

上面这些都是从wiki上copy过来的,算是一个BF简介。可见,BF是一个很fuck很简单的语言,好在它是图灵等价的,“理论上”是可以实现很多功能的。



潜规则是这么说的,了解一个语言之前,先要看看hello world怎么讲。hello world 在这里讲的很凌乱,如下:

  1. ++++++++++[>+++++++>++++++++++>+++>+<<<<-]
  2. >++.>+.+++++++..+++.>++.<<+++++++++++++++.
  3. >.+++.------.--------.>+.>.
复制代码





再回过来看指令含义的表格,可以发现,除了"["和"]"两种指令涉及到流程控制,其他的指令都可以很简单地实现。而即使是这两种相对复杂的操作,它的实现起来的复杂度也会唱会场得低。

所以直接上代码,逐块解释。



首先是BF-机的定义:

  1. typedef struct
  2. {
  3.     int ip;
  4.     int dp;
  5.     char *mem;
  6.     char *code;
  7.     int stack[128];
  8.     int sp;
  9. }BF_machine;
复制代码


定义里,可以看到,数据空间和指令空间是分开的。这是一种叫做哈佛结构的储存器结构,现在很多的单片机、大名鼎鼎的安腾系列和ARM9、10、11都是用的哈佛结构。与之对应的是常见的叫做冯诺依曼结构的储存器结构,又被叫做普林斯顿结构。你面前的x86、x86_64,路由器里的mips,mp4里的arm7,都是冯诺依曼结构的机器。
结构里的mem指针,指向的是数据内存的地址。
code指针。指向的是指令内存的地址。
ip用作指令计数器,总是指向要执行的下一条地址。
dp用作数据计数器,是当前的数据指针地址。
另外,这里还定义了一个深度为128的栈,sp作为栈顶指针使用。128的深度貌似有点大,几乎户可能被用到,但既然程序是在不缺内存的电脑上运行,这128个整数可以忽略不计了。


之后是正经的代码了,首先初始化一个BF-解释器。

  1.         BF_machine t;
  2.         t.mem=(char *)malloc(4096);
  3.         t.code=(char *)malloc(4096);
  4.         t.ip=0;
  5.         t.dp=0;
  6.         t.sp=128;
  7.         for(i=0;i<4096;i++)
  8.         {
  9.                 t.mem[i]=0;
  10.                 t.code[i]=0;
  11.         }
复制代码

代码很简单,可以看出来。分配内存并清零,各种指针清零。因为栈这里用向下伸展地方法,所以栈顶指针初始化成了128。


然后就是把代码读入code内存。

  1. fp=fopen(argv[1],"r");
  2.         while(!feof(fp))
  3.         {
  4.                 fscanf(fp,"%s",tmp);
  5.                 sprintf(t.code,"%s%s",t.code,tmp);
  6.         }
  7.         fclose(fp);
复制代码

很简单没什么可说的,打开文件,读入。错误处理?懒人,嗯,算了吧。


然后就是程序最主要的部分了,解释循环:

  1. while(t.code[t.ip])
  2.         {
  3.                 switch(t.code[t.ip])
  4.                 {
  5.                 case '>':
  6.                         t.dp++;
  7.                         break;
  8.                 case '<':
  9.                         t.dp--;
  10.                         break;
  11.                 case '+':
  12.                         t.mem[t.dp]++;
  13.                         break;
  14.                 case '-':
  15.                         t.mem[t.dp]--;
  16.                         break;
  17.                 case '.':
  18.                         putchar(t.mem[t.dp]);
  19.                         fflush(stdout);
  20.                         break;
  21.                 case ',':
  22.                         t.mem[t.dp]=getchar();
  23.                         break;
  24.                 case '[':
  25.                         if (t.mem[t.dp]==0)
  26.                         {
  27.                                 while(t.code[t.ip]!=']')
  28.                                         t.ip++;
  29.                         }
  30.                         else
  31.                         {
  32.                                 t.sp--;
  33.                                 t.stack[t.sp]=t.ip;
  34.                         }
  35.                         break;
  36.                 case ']':
  37.                         t.ip=t.stack[t.sp]-1;
  38.                         t.sp++;
  39.                         break;
  40.                 default:
  41.                         fprintf(stderr,"[BrainFuck]systax error:\n[BrainFuck]\tip=%d code=%c\n",t.ip,t.code[t.ip]);
  42.                         break;
  43.                 }
  44.                 t.ip++;
  45.         }
复制代码

相比来说,这段代码要长多了。
我们拆开来看:

  1.         while(t.code[t.ip])
  2.         {
  3.                 switch(t.code[t.ip])
  4.                 { ... }
  5.                t.sp++;
  6.         }
复制代码

外围的循环很简单,插一句,这里我们把字符0x00看作是停机指令。所以,代码的结束就导致了自然的停机。
指令计数器遵循简单的原则,每执行一个指令增一,去执行下一个指令。

从'>'到','指令,都是很简单的操作,按照要求改写dp或改写mem[dp]或输入输出即可。
  1. case '>':
  2.                         t.dp++;
  3.                         break;
  4.                 case '<':
  5.                         t.dp--;
  6.                         break;
  7.                 case '+':
  8.                         t.mem[t.dp]++;
  9.                         break;
  10.                 case '-':
  11.                         t.mem[t.dp]--;
  12.                         break;
  13.                 case '.':
  14.                         putchar(t.mem[t.dp]);
  15.                         fflush(stdout);
  16.                         break;
  17.                 case ',':
  18.                         t.mem[t.dp]=getchar();
  19.                         break;
复制代码


putchar这里强制刷新了输出,免得存在缓存里看不到结果。

需要解释的是有流程控制的'['和']'指令。

  1.                 case '[':
  2.                         if (t.mem[t.dp]==0)
  3.                         {
  4.                                 while(t.code[t.ip]!=']')
  5.                                         t.ip++;
  6.                         }
  7.                         else
  8.                         {
  9.                                 t.sp--;
  10.                                 t.stack[t.sp]=t.ip;
  11.                         }
  12.                         break;
  13.                 case ']':
  14.                         t.ip=t.stack[t.sp]-1;
  15.                         t.sp++;
  16.                         break;
复制代码

指令'['需要进行判断,判断当前数据指针指向的位置是不是零。这是上面的表格里写到的。
假如当前指针是0的话,那么把ip向后移动到']'即可,在执行t.ip++时,指令指针恰好地指向了下一个要执行的指令。
如果当前的指针不是0,这段代码就需要循环执行了 。这里代码把ip压入堆栈,等到执行到']'的时候,再将ip出栈并-1。这样ip就又一次的指向了'[',循环得以进行。

Everything that has a begin has an end.

假如代码没有问题的话,他总要有个结束条件的,对于BF语言,明显写出的代码的结束亦即代码的结束。
所以在while结束之后,程序打印了如下语句并return 0。over
  1. fprintf(stderr,"\n\n[BrainFuck]machine halt.\n");
复制代码



下面是一个运行的实例,执行的是上面写到的hello world的例子:
bf 解释器.png




哈哈,看到想要的结果了。






C源码、程序以及brainf**k的hello world打包如下:
bf_machine.rar (8.54 KB, 下载次数: 6)


已有 1 人评分威望 金钱 收起 理由
Pegasas + 30 + 300 原创内容

总评分: 威望 + 30  金钱 + 300   查看全部评分

Ooh-Oh, And I'm just waiting till the firing stopped
Ooh-Oh, And I'm just waiting till the shine wears off

187

主题

14

听众

5万

积分

管理员

Super Richard is me

Rank: 9Rank: 9Rank: 9

签到天数: 105 天

[LV.6]研二僵尸

在线时间
3077 小时
最后登录
2018-6-23
威望
40817 点
金钱
93256 HGB
注册时间
2010-7-18
积分
55638
记录
0
日志
0
帖子
4181
精华
2
好友
62

老不死勋章 大富翁

鲜花(104) 鸡蛋(7)
发表于 2011-7-23 16:00:25 |显示全部楼层
学习了~~~~~~~~~

25

主题

1

听众

6614

积分

伴坛终老

Rank: 3Rank: 3

该用户从未签到

在线时间
957 小时
最后登录
2016-3-11
威望
11315 点
金钱
38846 HGB
注册时间
2009-11-24
积分
6614
记录
1
日志
2
帖子
457
精华
0
好友
9
鲜花(71) 鸡蛋(0)
发表于 2011-7-25 23:34:29 |显示全部楼层
少见的技术贴
解释器是很好的东西啊

16

主题

2

听众

5752

积分

伴坛终老

鸟人

Rank: 3Rank: 3

签到天数: 12 天

[LV.3]大三老生

在线时间
950 小时
最后登录
2012-3-3
威望
5566 点
金钱
23956 HGB
注册时间
2011-2-4
积分
5752
记录
0
日志
0
帖子
520
精华
0
好友
25
鲜花(5) 鸡蛋(0)
发表于 2011-7-25 23:47:03 |显示全部楼层
3# exat500g
唉,技术贴都是用来沉的
Ooh-Oh, And I'm just waiting till the firing stopped
Ooh-Oh, And I'm just waiting till the shine wears off

3

主题

2

听众

55

积分

注册看看

Rank: 1

该用户从未签到

在线时间
12 小时
最后登录
2012-7-11
威望
30 点
金钱
374 HGB
注册时间
2010-7-24
积分
55
记录
0
日志
0
帖子
5
精华
0
好友
0
鲜花(0) 鸡蛋(0)
发表于 2011-7-26 11:51:05 |显示全部楼层
年轻人总是想改变世界,我高中时也在写basic解释器,想追赶Gates的脚步。这个没前途的,真的没前途

16

主题

2

听众

5752

积分

伴坛终老

鸟人

Rank: 3Rank: 3

签到天数: 12 天

[LV.3]大三老生

在线时间
950 小时
最后登录
2012-3-3
威望
5566 点
金钱
23956 HGB
注册时间
2011-2-4
积分
5752
记录
0
日志
0
帖子
520
精华
0
好友
25
鲜花(5) 鸡蛋(0)
发表于 2011-7-26 12:45:15 |显示全部楼层
您言重了,改变世界没想过,相比之下我更想改变自己的生活。
况且这只是个带有技术成分的娱乐贴,不指望靠这个挣什么前途。
至于做成just in time 编译器,也只是实现曾有过的想法,没追随谁的意思。
Ooh-Oh, And I'm just waiting till the firing stopped
Ooh-Oh, And I'm just waiting till the shine wears off

16

主题

2

听众

5752

积分

伴坛终老

鸟人

Rank: 3Rank: 3

签到天数: 12 天

[LV.3]大三老生

在线时间
950 小时
最后登录
2012-3-3
威望
5566 点
金钱
23956 HGB
注册时间
2011-2-4
积分
5752
记录
0
日志
0
帖子
520
精华
0
好友
25
鲜花(5) 鸡蛋(0)
发表于 2011-7-26 12:51:31 |显示全部楼层
至于gates和他的软件帝国,和他的basic,或者别的谁谁。说句比较冷的话,他们关我鸟事
Ooh-Oh, And I'm just waiting till the firing stopped
Ooh-Oh, And I'm just waiting till the shine wears off

107

主题

1

听众

4万

积分

版主

我只在午夜灌水。

Rank: 6Rank: 6

签到天数: 1 天

[LV.1]大一新生

在线时间
1671 小时
最后登录
2019-3-7
威望
33901 点
金钱
112746 HGB
注册时间
2005-10-24
积分
40115
记录
6
日志
0
帖子
5339
精华
3
好友
44

老不死勋章

鲜花(2) 鸡蛋(0)
发表于 2011-8-12 15:42:26 |显示全部楼层
呵呵,这个好,
以前也写过类似的东西。
虽然没什么实际意义,不过还是挺好玩的
徘徊陆离,人影迷乱.

16

主题

2

听众

5752

积分

伴坛终老

鸟人

Rank: 3Rank: 3

签到天数: 12 天

[LV.3]大三老生

在线时间
950 小时
最后登录
2012-3-3
威望
5566 点
金钱
23956 HGB
注册时间
2011-2-4
积分
5752
记录
0
日志
0
帖子
520
精华
0
好友
25
鲜花(5) 鸡蛋(0)
发表于 2011-8-12 18:29:02 |显示全部楼层
8# 田园的拾荒者
嗯,纯属自娱自乐玩的
Ooh-Oh, And I'm just waiting till the firing stopped
Ooh-Oh, And I'm just waiting till the shine wears off
您需要登录后才可以回帖 登录 | 立即入住

手机版|Archiver|河北工业大学非官方社区 ( 津ICP备15003977号-1 )

GMT+8, 2020-3-28 19:32

Powered by Discuz! X2.5

© 2001-2012 Comsenz Inc.

回顶部