最近在 ptt Gossiping 版的jserv 的一篇回文
https://www.ptt.cc/bbs/Gossiping/M.1555612071.A.14C.html
得知 Brainfuck 也是個程式語言，於是小編自己也來寫一個 Brainfuck interpreter。先來了解 Brainfuck 的指令吧。
Brainfuck指令說明
============底下文字從
https://en.wikipedia.org/wiki/Brainfuck 節錄出來：============
| Character | Meaning |
|---|
> | increment the data pointer (to point to the next cell to the right). |
< | decrement the data pointer (to point to the next cell to the left). |
+ | increment (increase by one) the byte at the data pointer. |
- | decrement (decrease by one) the byte at the data pointer. |
. | output the byte at the data pointer. |
, | accept one byte of input, storing its value in the byte at the data pointer. |
[ | if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command. |
] | if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command. |
brainfuck指令與C語言對照表：
| brainfuck command | C equivalent |
|---|
| (Program Start) | char array[30000] = {0};
char *ptr=array; |
> | ++ptr; |
< | --ptr; |
+ | ++*ptr; |
- | --*ptr; |
. | putchar(*ptr); |
, | *ptr=getchar(); |
[ | while (*ptr) { |
] | } |
============以上文字從
https://en.wikipedia.org/wiki/Brainfuck 節錄出來：============
其中，[ 與 ] 這兩個指令需要注意有巢狀的情況，而測試的 Brainfuck 程式碼如下：
hello.bf (
https://github.com/pablojorge/brainfuck/blob/master/programs/hello.bf)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| +++++ +++++ initialize counter (cell #0) to 10
[ use loop to set the next four cells to 70/100/30/10
> +++++ ++ add 7 to cell #1
> +++++ +++++ add 10 to cell #2
> +++ add 3 to cell #3
> + add 1 to cell #4
<<<< - decrement counter (cell #0)
]
> ++ . print 'H'
> + . print 'e'
+++++ ++ . print 'l'
. print 'l'
+++ . print 'o'
> ++ . print ' '
<< +++++ +++++ +++++ . print 'W'
> . print 'o'
+++ . print 'r'
----- - . print 'l'
----- --- . print 'd'
> + . print '!'
> . print '\n'
|
費式數列 fibonacci.bf (
https://github.com/pablojorge/brainfuck/blob/master/programs/fibonacci.bf)
1
2
3
4
5
6
7
8
9
| >++++++++++>+>+[
[+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[
[-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-
[>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>
]<<<
]
This program doesn't terminate; you will have to kill it.
Daniel B Cristofani (cristofdathevanetdotcom)
http://www.hevanet.com/cristofd/brainfuck/
|
圓周率 pi.bf (
https://copy.sh/brainfuck/prog/yapi.b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| [ yet another pi calculation program in bf
Just like for pi16.b the accuracy of the result depends on the cellsize:
- using 8 bit cells causes an overflow after 4 digits
- using 16 bit cells causes an overflow after 537 digits
- using 32 bit cells causes an overflow after several millions of digits
It's about ~38 times shorter than pi16.b, ~364 times faster and works with
not-wrapping (bignum) implementations.
by Felix Nawothnig (felix.nawothnig@t-online.de) ]
> +++++ +++++ +++++ (15 digits)
[<+>>>>>>>>++++++++++<<<<<<<-]>+++++[<+++++++++>-]+>>>>>>+[<<+++[>>[-<]<[>]<-]>>
[>+>]<[<]>]>[[->>>>+<<<<]>>>+++>-]<[<<<<]<<<<<<<<+[->>>>>>>>>>>>[<+[->>>>+<<<<]>
>>>>]<<<<[>>>>>[<<<<+>>>>-]<<<<<-[<<++++++++++>>-]>>>[<<[<+<<+>>>-]<[>+<-]<++<<+
>>>>>>-]<<[-]<<-<[->>+<-[>>>]>[[<+>-]>+>>]<<<<<]>[-]>+<<<-[>>+<<-]<]<<<<+>>>>>>>
>[-]>[<<<+>>>-]<<++++++++++<[->>+<-[>>>]>[[<+>-]>+>>]<<<<<]>[-]>+>[<<+<+>>>-]<<<
<+<+>>[-[-[-[-[-[-[-[-[-<->[-<+<->>]]]]]]]]]]<[+++++[<<<++++++++<++++++++>>>>-]<
<<<+<->>>>[>+<<<+++++++++<->>>-]<<<<<[>>+<<-]+<[->-<]>[>>.<<<<[+.[-]]>>-]>[>>.<<
-]>[-]>[-]>>>[>>[<<<<<<<<+>>>>>>>>-]<<-]]>>[-]<<<[-]<<<<<<<<]++++++++++.
|
自然數 e.bf (
http://www.hevanet.com/cristofd/brainfuck/e.b)
1
2
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
| [e.b -- compute e
(c) 2016 Daniel B. Cristofani
http://brainfuck.org/]
>>>>++>+>++>+>>++<+[
[>[>>[>>>>]<<<<[[>>>>+<<<<-]<<<<]>>>>>>]+<]>-
>>--[+[+++<<<<--]++>>>>--]+[>>>>]<<<<[<<+<+<]<<[
>>>>>>[[<<<<+>>>>-]>>>>]<<<<<<<<[<<<<]
>>-[<<+>>-]+<<[->>>>[-[+>>>>-]-<<-[>>>>-]++>>+[-<<<<+]+>>>>]<<<<[<<<<]]
>[-[<+>-]]+<[->>>>[-[+>>>>-]-<<<-[>>>>-]++>>>+[-<<<<+]+>>>>]<<<<[<<<<]]<<
]>>>+[>>>>]-[+<<<<--]++[<<<<]>>>+[
>-[
>>[--[++>>+>>--]-<[-[-[+++<<<<-]+>>>>-]]++>+[-<<<<+]++>>+>>]
<<[>[<-<<<]+<]>->>>
]+>[>>>>]-[+<<<<--]++<[
[>>>>]<<<<[
-[+>[<->-]++<[[>-<-]++[<<<<]+>>+>>-]++<<<<-]
>-[+[<+[<<<<]>]<+>]+<[->->>>[-]]+<<<<
]
]>[<<<<]>[
-[
-[
+++++[>++++++++<-]>-.>>>-[<<<----.<]<[<<]>>[-]>->>+[
[>>>>]+[-[->>>>+>>>>>>>>-[-[+++<<<<[-]]+>>>>-]++[<<<<]]+<<<<]>>>
]+<+<<
]>[
-[
->[--[++>>>>--]->[-[-[+++<<<<-]+>>>>-]]++<+[-<<<<+]++>>>>]
<<<<[>[<<<<]+<]>->>
]<
]>>>>[--[++>>>>--]-<--[+++>>>>--]+>+[-<<<<+]++>>>>]<<<<<[<<<<]<
]>[>+<<++<]<
]>[+>[--[++>>>>--]->--[+++>>>>--]+<+[-<<<<+]++>>>>]<<<[<<<<]]>>
]>
]
This program computes the transcendental number e, in decimal. Because this is
infinitely long, this program doesn't terminate on its own; you will have to
kill it. The fact that it doesn't output any linefeeds may also give certain
implementations trouble, including some of mine.
|
C語言程式碼：
1
2
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
| #include <stdlib.h>
#include <stdio.h>
static int cells[30000] = {0};
unsigned int dp = 0; // data pointer
void bfExe(char *cmds)
{
int i, nestedLoop, curCmd;
for(i = 0; cmds[i] != 0; i++)
{
curCmd = cmds[i];
switch(curCmd)
{
case '>':
++dp;
break;
case '<':
--dp;
break;
case '+':
++cells[dp];
break;
case '-':
--cells[dp];
break;
case '.':
putchar(cells[dp]);
break;
case ',':
cells[dp] = getchar();
break;
case '[':
if(!cells[dp])
{
nestedLoop = 1;
while(nestedLoop)
{
i++;
if(cmds[i] == '[') nestedLoop++;
if(cmds[i] == ']') nestedLoop--;
}
}
break;
case ']':
if(cells[dp])
{
nestedLoop = 1;
while(nestedLoop)
{
i--;
if(cmds[i] == ']') nestedLoop++;
if(cmds[i] == '[') nestedLoop--;
}
}
break;
}
}
}
int main(int argc, char* argv[]) {
if(argc < 2) exit(1);
FILE *f = fopen(argv[1], "r");
fseek(f, 0, SEEK_END);
long fsize = ftell(f);
fseek(f, 0, SEEK_SET);
int *bfCmd = malloc(fsize + 1);
fread(bfCmd, 1, fsize, f);
fclose(f);
bfCmd[fsize] = 0;
bfExe(bfCmd);
return 0;
}
|
而在 stackoverflow 上有高手寫了底下的C程式碼(
https://stackoverflow.com/questions/9147357/brainfuck-interpreter)：
1
2
3
4
5
6
7
8
9
10
| #include <stdlib.h>
char m[9999], *n[99], *r = m, *p = m + 5000, **s = n, d, c;
main()
{
for (read(0, r, 4000); c = *r; r++)
c - ']' || (d > 1 ||
(r = *p ? *s : (--s, r)), !d || d--), c - '[' || d++ ||
(*++s = r), d || (*p += c == '+', *p -= c == '-', p += c == '>',
p -= c == '<', c - '.' || write(2, p, 1), c - ',' || read(2, p, 1));
}
|
C語言果然很特別！！！
底下為其他語言實作出來的 brainfuck interpreters 與模擬實驗資料。
https://github.com/pablojorge/brainfuck
若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。
If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.
