brainfuck

brainfuck是一个图灵完备的语言,仅有8个操作,晦涩难懂,但能够像图灵机一样完成任何计算。本文主要讨论一下brainfuck的一些编程技巧。

brainfuck由8个操作,输入输出流,一块初始化为0的内存,以及一个全局指针ptr(默认指向内存块的开始)构成。八个操作分别为(这里采用c描述):

1
2
3
4
5
6
7
8
> ptr++
< ptr--
+ *ptr++
- *ptr--
, *ptr = getchar()
. putchar(*ptr)
[ while(*ptr){
] } // of while

马上就是新年了,下面这段程序可以输出HappyNewYear

1
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++.+++++++++++++++..+++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++.<--.++.>.----.+++++++++++++++++.

brainfuck由于语法简单,所以解释器也非常好实现,这里也实现了一个:Calvin’s brainfuck interpreter。由于写bf会导致+-<>比较多,解释器也提供了+(48)表示连续48个加号的糖,同时也可使用%作注释,使用#stk访问变量表。程序可以开启debug模式,可以使用#dbg和#cdb代码块局部开启或关闭debug模式。同时这边也附了一个贪心算法的实现,用比较短的bf代码打印字符串。
等我考完试再优化一下ლ(╹◡╹ლ)

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
# https://github.com/CalvinNeo/brainfuck/blob/master/print_gen.py
#coding:utf8
import sys
def naive_gen(ascii):
code = ''
for x in ascii:
code += '>' + '+' * ord(x) + '.'
return code
def greedy_gen(ascii):
current = []
code = ''
ptr = -1
for x in ascii:
if len(current) == 0:
code += '+' * ord(x) + '.'
ptr += 1
current.append(x)
else:
min_dist = 256
min_index = 0
for (index, y) in zip(range(len(current)), current):
if abs(ord(y)-ord(x)) < min_dist:
min_dist, min_index = abs(ord(y)-ord(x)), index
if min_dist < ord('A'):
if ord(current[min_index]) >= ord(x):
ptr_delta = '-' * ( ord(current[min_index]) - ord(x) )
else:
ptr_delta = '+' * ( ord(x) - ord(current[min_index]) )
if min_index >= ptr:
ptr_move = '>' * ( min_index - ptr )
else:
ptr_move = '<' * ( ptr - min_index )
code += ptr_move + ptr_delta + '.'
ptr = min_index
current[min_index] = x
else:
code += '>' * (len(current) - ptr) + '+' * ord(x) + '.'
current.append(x)
ptr = len(current) - 1
return code
if __name__ == '__main__':
ascii = raw_input()
print greedy_gen(ascii)

下面介绍一下brainfuck的常用技巧。

数学运算

  1. 乘法
    以下代码实现了两个一位数乘法:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    ,-(48)>,-(48) % read 2 integers
    [- % while $2--
    < % set ptr to $1
    [
    - % while $1--
    >>+ % $3++
    >+ % $4++
    <<< % set ptr back to $1
    ]
    >>> % set ptr to $4
    [ % copy $4 to $1
    - % while $4--
    <<<+ % $1++
    >>> % set ptr back to $4
    ]
    << % move ptr to $2 and continue
    ]
    >+(48). % print answer in $3

内存操作

  1. 清空存储区
    这里需要特别强调一下,brainfuck里面没有生存空间这样的概念,也就是它的ptr是全局的单例的,在使用[]嵌套循环的时候,要特别注意这一点。
    1
    2

语言结构

  1. if语句
  2. switch语句
  3. 嵌套循环