挑战 | Brainfuck语言解释器

Copyright 2019 HisenZhang

1993年被提出的Brainfuck(以下简称BF)是一种极小化的语言, 全部使用的符号只有八种. 下面是BF的例程Hello World.

++++++++++ [>+++++++ >++++++++++ >+++>+<<<<-]
>++.>+.+++++++ ..+++.>++.<<+++++++++++++++ .
>.+++.------ .-------- .>+.>.

BF的工作原理模拟了一台简单的图灵机Turing Machine. 这个在1936年由图灵提出的计算模型描述了在一条无限长的纸带上, 机器的读写头不停的移动或读写以完成计算任务.

虽然图灵模型看上去简单, 但是图灵机可以解决大多数计算问题. 今天常用的计算机正是按照图灵机模型设计的. 因此, 理解了BF的工作原理, 也就很大程度上理解了现代计算机的数学原理和一些简单的计算理论Computation Theory.

在这个挑战里, 你需要编写一个解释器来运行BF语言.

样例

输入样例 1

++++++++++ [>+++++++ >++++++++++ >+++>+<<<<-]
>++.>+.+++++++ ..+++.>++.<<+++++++++++++++ .
>.+++.------ .-------- .>+.>.

输出样例 1

Hello World!

输入样例 2

+++++++++++
>+>>>>++++++++++++++++++++++++++++++++++++++++++++
>++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
<-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<
-]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]
>[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++
+++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++
++++++++++++++++++++++++++++++++++++++++++++.[-]<<
<<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
[-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]

输出样例 2

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

完成度

本挑战的完成度分为三个等级

1. 可以解析+,-,<,>四种操作
2. 可以解析.,,两种操作
3. 可以解析循环

目标

1. 学习图灵计算模型
2. 学习ASCII编码
3. 强化四则运算的编程
4. 强化条件/循环语句
5. 理解编程语言的本质

材料

访问OneDrive以获取相关材料

1. 中文维基百科:
   • brainfuck.pdf
   • turing_machine.pdf
   • ascii.pdf
2. 视频 & 英语字幕:
   • How Brainfuck Work.mp4
   • How Brainfuck Works.ass
3. 在线 Brainfuck Visualizer
   • https://fatiherikli.github.io/brainfuck-visualizer/