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. if语句
  2. switch语句
  3. 嵌套循环