golang実装brainfuck解釈器

8212 ワード

brainfuck  極めて簡略化されたesotericプログラミング言語で、卵痛プログラミング言語に訳すことができるかもしれないが、8つの命令しかない.これを使ってプロジェクトをすれば、アセンブリプログラミングよりも卵が痛いはずだが、トゥーリンは完全だという.ハローワールドはこうです
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

コード全体は+,-,>,<,,,,[,],で構成されている.
Character Meaning
>データポインタの追加 (現在の右側のメモリセルを指す).
<データポインタを減らす(現在の左メモリセルを指す).
+現在のメモリセルに1を追加 
-       現在のメモリセルに対して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
", 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>
", os.Args[0]) os.Exit(1) } c, err := ioutil.ReadFile(os.Args[1]) if err != nil { fmt.Printf("read brainfuck file failed!
") 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