娱乐一下,介绍一种语言——brainfuck

Question

语言一共只有8个符号
+-><.,[]
brainfuck的程序全部都由这8个符号构成
初始化的时候，有一个连续的两个方向都无限长的内存，内存的每个字节值是0。
有一个指针p，指向其中一个字节。
每个符号的意义如下：
+  指针指向的这个字节自加
-   指针指向的这个字节自减
>  指针向右移一个字节
<  指针向左移一个字节
.   输出指针指向的这个字节
,   输入这个字节，存在指针指向的这个字节
[   如果指针指向的这个字节，则进入循环节
]   回到匹配的[（比如[--.[++>.[+]---].-]，^指着的两个是匹配的]）
                               ^              ^

以下程序输出我的ID

2. ++++++++++[>++++++++++[>+<-]<-]>>-.+++++++.---------.++++++++.
3. >>++++[<++++[<+>-]>-]<<+.-------..

复制代码

自举编译器在39楼
C语言写的解释器在42楼

[ 本帖最后由 cjaizss 于 2008-6-9 17:05 编辑 ]

Answer 1

以下是用sed写的一个编译器：

1. #! /bin/sed -f
2. s/[^][+<>.,-]//g
3. s/\([-+]\)/\1\1*p;/g
4. s/</p--;/g
5. s/>/p++;/g
6. s/\./putchar(*p);/g
7. s/,/*p=getchar();/g
8.      s/\[/while (*p) {/g
9.      s/\]/}/g
10.      1s/^/#include <stdio.h>\
11.      int main(void){char *p=calloc(1,10000);/
12.      $s/$/}/
14.      /./!d
16. # Here is an example BF program
17. #
18. # +[>>+++++[<++++++>-]<[>++++[>++++++++<-]<[->+>.<<]>[-<+>]+++++
19. # [>+++++<-]>+++.-.<+++[>------<-]>.---------.<+++++[>++++++<-]>
20. # .--.[-]++++++++++.[-]<<-]>+++++[<++++++>-]>>[-]<<<[>++++[>++++
21. # ++++<-]>>[<.>>+<-]>[-<+>]<+<<+++++[->++++++<]>.--.<++++[>-----
22. # --<-]>.++++++++.<+++[>++++++<-]>.++++.[-]++++++++++.[-]<<-]<]

复制代码

Answer 2

我写的C语言解释器:

2. /*bf.c*/
3. #include <stdio.h>
4. #include <stdlib.h>
5. char s[30000]={0};
6. char code[100000];
7. int len = 0;
8. int  stack[100];
9. int stack_len=0;
10. int main(int argc,char**argv)
11. {
12.         char c;
13.         int i=0,j,k,x=0;
14.         FILE* f;
15.         char* p=s+10000;
16.         if(argc==2) {
17.                 f=fopen(argv[1],"r");
18.                 if(f==NULL) {
19.                         perror("fopen");
20.                                 return 1;
21.                 }
22.                 while(fread(&code[len],1,1,f)==1) {
23.                         len++;
24.                 }
25.         } else {
26.                 fprintf(stderr,"%s:%d\n",__FILE__,__LINE__);
27.                 return 2;
28.         }
29.         setbuf(stdout,NULL);
30.         while(i<len) {
31.                 switch(code[i]) {
32.                         case '+':
33.                                 (*p)++;
34.                                 break;
35.                         case '-':
36.                                 (*p)--;
37.                                 break;
38.                         case '>':
39.                                 p++;
40.                                 break;
41.                         case '<':
42.                                 p--;
43.                                 break;
44.                         case '.':
45.                                 putchar((int)(*p));
46.                                 //printf("put:%hd\n",*p);
47.                                 break;
48.                         case ',':
49.                                 *p=getchar();
50.                                 break;
51.                         case '[':
52.                                 if(*p) {
53.                                         stack[stack_len++]=i;
54.                                 } else {
55.                                         for(k=i,j=0;k<len;k++) {
56.                                                 code[k]=='['&&j++;
57.                                                 code[k]==']'&&j--;
58.                                                 if(j==0)break;
59.                                         }
60.                                         if(j==0)
61.                                                 i=k;
62.                                         else {
63.                                                 fprintf(stderr,"%s:%d\n",__FILE__,__LINE__);
64.                                                 return 3;
65.                                         }
66.                                 }
67.                                 break;
68.                         case ']':
69.                                 i=stack[stack_len-- - 1]-1;
70.                                 break;
71.                         default:
72.                                 break;
73.                 }
74.                 i++;
75.                 //x++;
76.                 //printf("%d : i=%d\n",x,i);
77.         }
78.         return 0;
79. }

复制代码
[ 本帖最后由 cjaizss 于 2008-6-7 12:36 编辑 ]

Answer 3

准备写个brainfuck自举编译器，但是写的过程中才意识到并非那么容易。要解决一个看起来其实很微小的东西——分支，但是想不出如何解决，今天放弃，明天继续

[ 本帖最后由 cjaizss 于 2008-6-1 04:19 编辑 ]

Answer 4

终于写成了一个，可是我并不是很满意。我写的这个程序只接受bf语言的8个符号，如果有别的符号过来，编译的结果会是错误的，即使进来的字符是\n,\t和空格
另外就是编译器实际所需内存与源码长度成正比（在规则如此简单的语言里不应该存在这种问题，但我暂时只能想到这个办法）
假如把我那个C语言的bf解释器编译之后定为/usr/local/bin/mybf
以下编译器文件为/usr/local/bin/bf2c.bf
源文件为1.bf
则编译1.bf为1.c的命令为
bf2c.bf <1.bf >1.c
如果1.bf中含有8个符号之外的符号，一般编译则可以如下：
cat 1.bf|tr -dC '<>[]+.,-'| bf2c.bf >1.c
则bf的自举编译器如下：

2. #!/usr/local/bin/mybf
3. +++++++++++++++++++++++++++++++++++.
4. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
5. +++++.
6. -----------.
7. +++++++++.
8. +++++++++.
9. -----------------.
10. +.
11. ---------------------------------------------------------------------.
12. ++++++++++++++++++++++++++++.
13. +++++++++++++++++++++++++++++++++++++++++++++++++++++++.
14. +.
15. ----------------.
16. +++++.
17. ++++++.
18. -----------------------------------------------------------------.
19. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
20. ------------------------------------------.
21. ----------------------------------------------------.
22. +++++++++++++++++++++++++.
23. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
24. +++++.
25. -----------.
26. +++++++++.
27. +++++++++.
28. -----------------.
29. +.
30. ---------------------------------------------------------------------.
31. ++++++++++++++++++++++++++++.
32. +++++++++++++++++++++++++++++++++++++++++++++++++++++++.
33. +.
34. ----------------.
35. ++++++++.
36. ---.
37. -------.
38. ----------------------------------------------------.
39. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
40. ------------------------------------------.
41. ----------------------------------------------------.
42. +++++++++++++++++++++++++.
43. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
44. +.
45. +.
46. +++.
47. +++++.
48. ---------.
49. ---------------------------------------------------------------------.
50. +++++++++++++++++++++++++++++++++.
51. ---------------------------------.
52. +++++++++++..
53. -.
54. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
55. -----------------------------------------------------.
56. -------------------------------------------------.
57. +++++++++++++++++++++++++.
58. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
59. +.
60. +.
61. +++.
62. +++++.
63. ---------.
64. ---------------------------------------------------------------------.
65. ++++++++++++++++++++++++++++++++++.
66. ----------------------------------.
67. ++++++++++.
68. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
69. ---------------------------------------------------.
70. ++++++++++++++++++++++++++++++++++++++++++.
71. --.
72. +++++++++++++++.
73. -----------------.
74. +++++.
75. -------.
76. +++++++++++++++++.
77. --------------------------------------------------------------------------.
78. +.
79. ++++++++++++++++++.
80. -------------------------------------------------.
81. +++++++++++++++++++++++++.
82. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
83. +.
84. +.
85. +++.
86. +++++.
87. ---------.
88. ---------------------------------------------------------------------.
89. +++++++++++++++++++++++++++++++++++.
90. -----------------------------------.
91. +++++++++++++..
92. ---.
93. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
94. -----------------------------------------------------.
95. -------------------------------------------------.
96. +++++++++++++++++++++++++.
97. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
98. +.
99. +.
100. +++.
101. +++++.
102. ---------.
103. ---------------------------------------------------------------------.
104. ++++++++++++++++++++++++++++++++++++.
105. ------------------------------------.
106. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
107. +++++.
108. -.
109. -----------------.
110. +++++.
111. -------.
112. +++++++++++++++++.
113. --------------------------------------------------------------------------.
114. ++.
115. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
116. -----------------------------------------------------------------------.
117. ++++++++++++++++++.
118. -------------------------------------------------.
119. +++++++++++++++++++++++++.
120. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
121. +.
122. +.
123. +++.
124. +++++.
125. ---------.
126. ---------------------------------------------------------------------.
127. ++++++++++++++++++++++++++++++++++++++++++++++++++.
128. --------------------------------------------------.
129. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
130. -------------------------------------------------------------------..
131. ++++++++++++++.
132. -------------------------------------------------.
133. +++++++++++++++++++++++++.
134. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
135. +.
136. +.
137. +++.
138. +++++.
139. ---------.
140. ---------------------------------------------------------------------.
141. ++++++++++++++++++++++++++++++++++++++++++++++++++++.
142. ----------------------------------------------------.
143. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
144. ---------------------------------------------------------------------..
145. ++++++++++++++++.
146. -------------------------------------------------.
147. +++++++++++++++++++++++++.
148. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
149. +.
150. +.
151. +++.
152. +++++.
153. ---------.
154. ---------------------------------------------------------------------.
155. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
156. ---------------------------------------------------------------------------------.
157. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
158. ---------------.
159. +.
160. +++.
161. -------.
162. -------------------------------------------------------------.
163. ++.
164. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
165. -----------------------------------------------------------------------.
166. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
167. -----------------------------------------------------------------------------------------------------------------.
168. +++++++++++++++++++++++++.
169. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
170. +.
171. +.
172. +++.
173. +++++.
174. ---------.
175. ---------------------------------------------------------------------.
176. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
177. -----------------------------------------------------------------------------------.
178. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
179. -------------------------------------------------------------------------------------------------------------------.
180. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
181. +++++.
182. -------.
183. +++++++++++++++++.
184. ----------------------------------------------------------------------------------.
185. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
186. -----------------------.
187. ---------------------------------------.
188. ----....
189. +++++++++++++++++++++++++++++++++++++++++++++.
190. --------------------------------.
191. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
192. ---------------------------------------------------------------------------.
193. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
194. ------------------------------------------------------------------.
195. ++++++++++++++++++++++++++++++++++++++++++++++.
196. +++++.
197. ++++++.
198. ------------------------------------------------------------------------------------.
199. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
200. ------------.
201. ++++++++.
202. +++++.
203. ----------------------------------------------------------------------.
204. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
205. -------.
206. ------.
207. -----.
208. -----------------------------------------------------------.
209. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
210. ------------------------.
211. +++++.
212. -------.
213. +++++++++++++++++.
214. ------------------------------------------------------------------------.
215. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
216. ---------------------------------------------------.
217. +++++++++++++++++++++++++++++++++++++++++++++++++++++.
218. -----------------------------------------------------------------------.
219. ++++++.
220. -....
221. +++++++++++.
222. -------------------------------------------------..
225. /////////////////////////////cjaizss compile////////////////////////
226. >
227. +
228. [
229.         [-]+
230.         >
231.         ,
232.         +
233.         [
234.                 +++++++++++++++++++++.
235.                 [-]
236.                 ++++++++++.
237.                 [-]
238.                 >
239.         ]
240.         <
241.         -
242. ]
243. ////////////////////////////////////////////////////////////////
246. [-]
247. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
248. -------------.
249. +++++++++++++++.
250. +.
251. ---.
252. ----.
253. ------------------------------------------------------------------------------.
254. ++++++++++++++++.
255. +++++++++++.
256. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
257. [-]
258. ++++++++++.

复制代码
[ 本帖最后由 cjaizss 于 2008-6-7 19:24 编辑 ]

Answer 5

c版在深入计算理论？

Answer 6

呵呵，做这个纯属娱乐

Answer 7

优化之后的bf解释器程序bf

2. /*bf.c*/
3. #include <stdio.h>
4. #include <stdlib.h>
5. char s[30000]={0};
6. char code[100000];
7. int len = 0;
8. int  stack[100];
9. int stack_len=0;
10. int main(int argc,char**argv)
11. {
12.         char c;
13.         int i,j,k,x=0;
14.         int m,n;
15.         FILE* f;
16.         char* p=s+10000;
17.         if(argc==2) {
18.                 f=fopen(argv[1],"r");
19.                 if(f==NULL) {
20.                         perror("fopen");
21.                                 return 1;
22.                 }
23.                 while(fread(&code[len],1,1,f)==1) {
24.                         len++;
25.                 }
26.         } else return 2;
27.        
28.         /*optimization*/
29.         /*We can prove that n is never greater than m.So we can use the same memory*/
30.         for(m=0,n=0,c=0,j=0;m<len;m++) {
31.                 switch(code[m]) {
32.                         case '+':
33.                                 switch (j) {
34.                                         case 1:
35.                                                 code[n++]='>';
36.                                                 break;
37.                                         case -1:
38.                                                 code[n++]='<';
39.                                                 break;
40.                                         case 0:
41.                                                 break;
42.                                         default:
43.                                                 code[n++]='p';
44.                                                 code[n++]=j;
45.                                                 break;
46.                                 }
47.                                 j=0;
48.                                 c++;
49.                                 break;
50.                         case '-':
51.                                 switch (j) {
52.                                         case 1:
53.                                                 code[n++]='>';
54.                                                 break;
55.                                         case -1:
56.                                                 code[n++]='<';
57.                                                 break;
58.                                         case 0:
59.                                                 break;
60.                                         default:
61.                                                 code[n++]='p';
62.                                                 code[n++]=j;
63.                                                 break;
64.                                 }
65.                                 j=0;
66.                                 c--;
67.                                 break;
68.                         case '>':
69.                                 switch (c) {
70.                                         case ((char)1):
71.                                                 code[n++]='+';
72.                                                 break;
73.                                         case ((char)(-1)):
74.                                                 code[n++]='-';
75.                                                 break;
76.                                         case ((char)0):
77.                                                 break;
78.                                         default:
79.                                                 code[n++]='a';
80.                                                 code[n++]=c;
81.                                                 break;
82.                                 }
83.                                 c=0;
84.                                 j++;
85.                                 if(j==0x7f) {
86.                                         code[n++]='p';
87.                                         code[n++]=0x7f;
88.                                         j=0;
89.                                 }
90.                                 break;
91.                         case '<':
92.                                 switch (c) {
93.                                         case ((char)1):
94.                                                 code[n++]='+';
95.                                                 break;
96.                                         case ((char)(-1)):
97.                                                 code[n++]='-';
98.                                                 break;
99.                                         case ((char)0):
100.                                                 break;
101.                                         default:
102.                                                 code[n++]='a';
103.                                                 code[n++]=c;
104.                                                 break;
105.                                 }
106.                                 c=0;
107.                                 j--;
108.                                 if(j==-128) {
109.                                         code[n++]='p';
110.                                         code[n++]=-128;
111.                                         j=0;
112.                                 }
113.                                 break;
114.                         case '.':
115.                         case ',':
116.                         case '[':
117.                                 switch (c) {
118.                                         case ((char)1):
119.                                                 code[n++]='+';
120.                                                 break;
121.                                         case ((char)(-1)):
122.                                                 code[n++]='-';
123.                                                 break;
124.                                         case ((char)0):
125.                                                 break;
126.                                         default:
127.                                                 code[n++]='a';
128.                                                 code[n++]=c;
129.                                                 break;
130.                                 }
131.                                 c=0;
132.                                 switch (j) {
133.                                         case 1:
134.                                                 code[n++]='>';
135.                                                 break;
136.                                         case -1:
137.                                                 code[n++]='<';
138.                                                 break;
139.                                         case 0:
140.                                                 break;
141.                                         default:
142.                                                 code[n++]='p';
143.                                                 code[n++]=j;
144.                                                 break;
145.                                 }
146.                                 j=0;
147.                                 code[n++]=code[m];
148.                                 break;
149.                         case ']':
150.                                 switch (c) {
151.                                         case ((char)1):
152.                                                 code[n++]='+';
153.                                                 break;
154.                                         case ((char)(-1)):
155.                                                 code[n++]='-';
156.                                                 break;
157.                                         case ((char)0):
158.                                                 break;
159.                                         default:
160.                                                 code[n++]='a';
161.                                                 code[n++]=c;
162.                                                 break;
163.                                 }
164.                                 c=0;
165.                                 switch (j) {
166.                                         case 1:
167.                                                 code[n++]='>';
168.                                                 break;
169.                                         case -1:
170.                                                 code[n++]='<';
171.                                                 break;
172.                                         case 0:
173.                                                 break;
174.                                         default:
175.                                                 code[n++]='p';
176.                                                 code[n++]=j;
177.                                                 break;
178.                                 }
179.                                 j=0;
180.                                 if(n-1>=0&&n-2>=0&&code[n-2]=='['&&(code[n-1]=='+'||code[n-2]=='-')) {
181.                                         code[n-2]='0';
182.                                         n--;
183.                                 } else {
184.                                         code[n++]=code[m];
185.                                 }
186.                                 break;
187.                         default:
188.                                 break;
189.                 }
190.         }
191.         len=n;
192.         setbuf(stdout,NULL);
193. #if 0
194.         for(i=0;i<len;i++)
195.                 putchar(code[i]);
196.         return 0;
197. #endif
198.         i=0;
199.         while(i<len) {
200.                 switch(code[i]) {
201.                         case '0':
202.                                 *p=0;
203.                                 break;
204.                         case 'a':
205.                                 i++;
206.                                 *p+=code[i];
207.                                 break;
208.                         case 'p':
209.                                 i++;
210.                                 p+=code[i];
211.                                 break;
212.                         case '+':
213.                                 (*p)++;
214.                                 break;
215.                         case '-':
216.                                 (*p)--;
217.                                 break;
218.                         case '>':
219.                                 p++;
220.                                 break;
221.                         case '<':
222.                                 p--;
223.                                 break;
224.                         case '.':
225.                                 putchar((int)(*p));
226.                                 //printf("put:%hd\n",*p);
227.                                 break;
228.                         case ',':
229.                                 *p=getchar();
230.                                 break;
231.                         case '[':
232.                                 if(*p) {
233.                                         stack[stack_len++]=i;
234.                                 } else {
235.                                         for(k=i,j=0;k<len;k++) {
236.                                                 if(code[k]=='a'||code[k]=='p') {
237.                                                         k++;
238.                                                         continue;
239.                                                 }
240.                                                 code[k]=='['&&j++;
241.                                                 code[k]==']'&&j--;
242.                                                 if(j==0)break;
243.                                         }
244.                                         if(j==0)
245.                                                 i=k;
246.                                         else {
247.                                                 fprintf(stderr,"%s:%d\n",__FILE__,__LINE__);
248.                                                 return 3;
249.                                         }
250.                                 }
251.                                 break;
252.                         case ']':
253.                                 i=stack[stack_len-- - 1]-1;
254.                                 break;
255.                         default:
256.                                 break;
257.                 }
258.                 i++;
259.                 //x++;
260.                 //printf("%d : i=%d\n",x,i);
261.         }
262.         return 0;
263. }

复制代码
[ 本帖最后由 cjaizss 于 2008-6-7 12:37 编辑 ]

Answer 8

楼主的工作很棒！

Answer 9

cjaizss真是牛X啊！不愧版主，呵呵