golang 实现brainfuck 解释器

yujian0231 · · 2450 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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


有疑问加站长微信联系(非本文作者)

本文来自:开源中国博客

感谢作者:yujian0231

查看原文:golang 实现brainfuck 解释器

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2450 次点击  
加入收藏 微博
1 回复  |  直到 2000-01-01 00:00:00
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传