golang 实现brainfuck 解释器
浏览数：45 /
时间：2015年06月10日
brainfuck 是极为简化esoteric 编程语言，或许可以翻作蛋疼编程语言，仅有八条指令，如果用这玩意搞项目，应该比汇编编程还蛋疼，不过据说是图灵完全。它的hello world 是这样的：
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
整个代码都是由+，-，>, <, . , [, ], , 组成。
Character Meaning
> 增加数据指针 (使其指向当前右边内存单元).
< 减少数据指针(使其指向当前左边内存单元).
+ 对当前内存单元加 1
- 对当前内存单元减 1
. 输出当内存单元
, 接受一个字节的输入，将其放到当前数据指针指向的内存单元
[ 如果当前数据指针指向的单元，值为非0， 进入循环，执行紧靠 [ 后面的指令；否则，向前跳转到与此 [ 匹配的 ] 之后开始执行
] 如果当前数据指针指向的单元，值为非0，向后跳转，回到与此 ] 匹配的 [ 后面执行， 否则，正常流程，继续向下执行
brainfuck 命令 c语言等价操作
(Program Start) char array[infinitely large size] = {0};
char *ptr=array;
> ++ptr;
< --ptr;
+ ++*ptr;
- --*ptr;
. putchar(*ptr);
, *ptr=getchar();
[ while (*ptr) {
] }
package main
import (
"fmt"
"io/ioutil"
"os"
)
//表达brainfuck使用的机器模型，连续字节内存块
type tape struct {
mem []byte
pos int
}
func TapeNew() *tape {
t := new(tape)
t.mem = make([]byte, 4096)
return t
}
//.操作， putchar(*ptr)
func (t *tape) get() byte { return t.mem[t.pos] }
//,操作， *ptr = getchar()
func (t *tape) set(val byte) { t.mem[t.pos] = val }
//+操作， ++*ptr
func (t *tape) inc() { t.mem[t.pos]++ }
//-操作， --*ptr
func (t *tape) dec() { t.mem[t.pos]-- }
//>操作, ++ptr
func (t *tape) forward() {
t.pos++
if len(t.mem) <= t.pos {
t.mem = append(t.mem, 0)
}
}
//<操作，--ptr
func (t *tape) backward() { t.pos-- }
func interpret(prog string, whilemap map[int]int) {
pc := 0
tape := TapeNew()
var tmp byte
for pc < len(prog) {
switch prog[pc] {
case '>':
tape.forward()
case '<':
tape.backward()
case '+':
tape.inc()
case '-':
tape.dec()
case '.':
c := tape.get()
fmt.Printf("%c", c)
case ',':
fmt.Scanf("%c", &tmp)
tape.set(tmp)
case '[':
if tape.get() == 0 {
pc = whilemap[pc]
}
case ']':
if tape.get() != 0 {
pc = whilemap[pc]
}
}
pc++
}
}
func parse(prog string) (string, map[int]int) {
parsed := make([]byte, 0)
pcstack := make([]int, 0)
//记录[,对应的],索引(指令)位置
whilemap := make(map[int]int, 128)
pc := 0
for _, char := range prog {
//fmt.Printf("got char: %c\n", char)
switch char {
case '>', '<', '+', '-', '.', ',', '[', ']':
parsed = append(parsed, byte(char))
if char == '[' {
pcstack = append(pcstack, pc)
} else if char == ']' {
last := len(pcstack) - 1
left := pcstack[last]
pcstack = pcstack[:last]
right := pc
whilemap[right] = left
whilemap[left] = right
}
pc++
}
}
return string(parsed), whilemap
}
func main() {
if len(os.Args) < 2 {
fmt.Printf("Usage: %s <brainfuck source file>\n", os.Args[0])
os.Exit(1)
}
c, err := ioutil.ReadFile(os.Args[1])
if err != nil {
fmt.Printf("read brainfuck file failed!\n")
os.Exit(2)
}
interpret(parse(string(c)))
}
hello.b:
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. ./brainfuck hello.b Hello World! add.b: >> + [- >,>+< ----- ----- ----- ----- ; checking with ascii 43 ie plus symbol ----- ----- ----- ----- --- [ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++ < ] >> ] ; first input is over and terminated by a 'plus' symbol <->>>>>+ [- >,>+< ----- ----- ----- ----- ; checking with ascii 61 ie = symbol ----- ----- ----- ----- ----- ----- ----- ------ [ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ ++++++ < ] >> ] ; second input is over and terminated by an = symbol ; now the array looks like 0 0 0 49 0 50 0 0 0 0 0 0 0 0 49 0 53 0 0 1 0 ; for an input 12'plus'15= <<<< [<+<] ; filled with 1's in between + [<+>-<<[>-]>] ; This is a special loop to traverse LEFT through indefinite no of 0s ; Lets call it left traverse << [<+<] >[>]< ; now the array looks like ; 0 0 1 49 1 50 0 0 0 0 0 0 0 1 49 1 53 0 0 1 for eg:12plus15 [ [->+> + [>+<->>[<-]<] ; Right traverse >>[>]<+ [<] + [<+>-<<[>-]>] ; Left traverse <<-< ] + [>+<->>[<-]<] >> [>] <<-<[<] + [<+>-<<[>-]>] <<-< ] ; now actual addition took place ; ie array is 00000000000000 98 0 103 0 0 1 + [>+<->>[<-]<] >> [ ----- ----- ----- ----- ----- ----- ----- ----- ----- --- >>] ; minus 48 to get the addition correct as we add 2 ascii numbers >-< ; well an undesired 1 was there 2 place after 103 right ? just to kill it ; now the array is 00000 00000 0000 50 0 55 ; now comes the biggest task Carry shifting << [<<] +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++ [>>] ; we added a 48 before all the digits in case there is an overall carry ; to make the size n plus 1 ; array : 00000 00000 00 48 0 50 0 55 << << [ [>>->[>]>+>>>> >>>+<<<< <<<<<[<]><<] >+[>]>- [-<<[<]>+[>]>] >>>>>+>>> +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++ < ; comparison loop: 0 1 0 a b 0 ; (q) (p) (num) (58) [->-[>]<<] ; comparison loop to check each digit with 58: greater means ; we need to minus 10 and add 1 to next significant digit <[- ; n greater than or equal to 58 (at p) <<<< <<< [<]+ > ----- ----- ; minus 10 to that digit <<+ ; plus 1 to next digit > [>] >>>>>> ] < [-< ; n less than 58 (at q) <<<<<< [<]+ [>] >>>>> ] ; at (q) >>>[-]>[-] <<<<< <<<<< [<]> << ] ; Its all over now : something like 0 48 0 52 0 66 ( ie 0 4 18 ) ; will turn into 0 48 0 53 0 56 (ie 0 5 8) >> ----- ----- ----- ----- ----- ----- ----- ----- ----- --- ; here we are just checking first digit is 48 or not ; its weird to print 0 ahead but it is defenitely needed ; if it is 49 ie 1 [ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++ . [-] ] >> [.>>] +++++ +++++ . ; to print nextline : ascii 10
./brainfuck add.b
1234+0001=
1235
fib.b:
>++++++++++>+>+[
[+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[
[-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-
[>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>
]<<<
]
./brainfuck fib.b
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
