GoでBrainf**kコンパイラを作ってみた

かかった時間

5.5時間

完成したもの

Brainf**kコンパイラ

Brainf**kコンパイラ完成！ pic.twitter.com/weWCTqCdhs

— ゆん (@yn0014) August 31, 2019

言語・環境

• 使用言語 : Golang
• OS : MacOS Mojave 10.14.5
• GCC : gcc (Homebrew GCC 8.2.0) 8.2.0
• Golang : go1.12.4 darwin/amd64

工程

1. ベースを作る

とりあえずベースを作ってどんどん拡張していくことに決める。
吐き出すアセンブリのヘッダー/フッター部分を出力する関数を作った。

2. 便利系関数を作る

続する文字の数を数える、エラーを出力するなどの関数を作った。

3. >, < 記号実装

ポインタ位置をインクリメント/デクリメントする記号「<」「>」を実装した。
(途中まで「+」「-」と勘違いしていたのでコミットメッセージが若干おかしい…) この時点でParse関数とAsmBody関数のベースも完成していたのでこの後の実装作業が格段に楽になった。

4. +, - 記号実装

ポインタの指す値をインクリメント/デクリメントする記号「+」「-」を実装した。
同時にメモリ確保関連の処理も実装した。

5. [, ] 記号実装

ループを表す記号「[」「]」を実装した。
対応する記号にIDを降って、対応したラベルを出力するような感じにした。

        cmp byte ptr [レジスタ], 0
        je __loop_end_0
__loop_start_0:
.
.
        cmp byte ptr [レジスタ], 0
        jne __loop_start_0
__loop_end_0:

6. バグ修正

ここで色々バグが見つかり出したので修正作業をした。
アドレス計算のミスが目立ったのでもっと精進したい…。

7. . 記号実装

ポインタの示す値をASCIIコードとして呼んで出力する記号「.」を実装した。manページのwriteを読みつつ実装した。

8. , 記号実装

1バイト標準入力からデータを受け取ってポインタが指す場所に保存する記号「,」を実装した。この記号もmanページのreadを読みつつ実装した。

9. テストプログラム

HelloWorldを出力する定番プログラムと、入力された内容をそのまま出力するプログラムを書いた。
どちらのプログラムも正常に動作することを確認した👍

// hello world
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++.>

// 3byte input
,>,>,<<.>.>.>++++++++++.>

10. 完成

やったーーーーーーー〜！！！！

動作具合

このBrainf**kコードをコンパイルすると…

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

以下のようなアセンブリを吐き出す。

.intel_syntax  noprefix
.global       _main

_main:
header:
        push rbp
        mov rbp, rsp
        mov rdi, 0
__init_stack:
        push 0
        add rdi, 1
        cmp rdi, 5
        jb __init_stack
        mov rdi, 0

body:
        mov rdx, rbp
        sub rdx, 8
        add byte ptr [rdx], 5
        mov rdx, rbp
        sub rdx, 8
        cmp byte ptr [rdx], 0
        je __loop_end_0
__loop_start_0:
        mov rdx, rbp
        sub rdx, 16
        add byte ptr [rdx], 13
        mov rdx, rbp
        sub rdx, 8
        add byte ptr [rdx], -1
        mov rdx, rbp
        sub rdx, 8
        cmp byte ptr [rdx], 0
        jne __loop_start_0
__loop_end_0:
        mov rax, 0x2000004
        mov rdi, 1
        mov rsi, rbp
        sub rsi, 16
        mov rdx, 1
        syscall
        mov rdx, rbp
        sub rdx, 16
        add byte ptr [rdx], 1
        mov rax, 0x2000004
        mov rdi, 1
        mov rsi, rbp
        sub rsi, 16
        mov rdx, 1
        syscall
        mov rdx, rbp
        sub rdx, 16
        add byte ptr [rdx], 1
        mov rax, 0x2000004
        mov rdi, 1
        mov rsi, rbp
        sub rsi, 16
        mov rdx, 1
        syscall
        mov rdx, rbp
        sub rdx, 24
        add byte ptr [rdx], 2
        mov rdx, rbp
        sub rdx, 24
        cmp byte ptr [rdx], 0
        je __loop_end_1
__loop_start_1:
        mov rdx, rbp
        sub rdx, 32
        add byte ptr [rdx], 5
        mov rdx, rbp
        sub rdx, 24
        add byte ptr [rdx], -1
        mov rdx, rbp
        sub rdx, 24
        cmp byte ptr [rdx], 0
        jne __loop_start_1
__loop_end_1:
        mov rax, 0x2000004
        mov rdi, 1
        mov rsi, rbp
        sub rsi, 32
        mov rdx, 1
        syscall
        mov rdx, rbp
        sub rdx, 40
        movzx rax, byte ptr [rdx]

footer:
        mov rsp, rbp
        pop rbp
        ret

冗長な部分が多いので時間が空いた時に直していきたい…！

---

ちなみに上のコードの出力は…

ABC

こんな感じ。

本家と違うところ

• >\<+_[]., 以外の入力は全てエラーになる
• 最終的なポインタの指す値がそのまま返り値になる

今後やっていくこと

• 吐き出すアセンブリの量を少なくする
• ポインタ位置決め打ちでコンパイルしているのを直す
• 自分なりに拡張していく

まとめ

Cコンパイラ入門で少しずつ学んでいることが1つ実った形になってとても嬉しい！！！
簡単な命令の復習、システムコールの確認も出来たのでとても良かった！！終わり！！！

ソースコード

Githubにあります。
本名・学校バレがあるのでこの記事には貼りませんれません。Publicにはなっているので探してください…。