Closed18

Brainfuck のコンパイラを作ってみる

inukayinukay

以下の順でやってみる

  1. BF のインタプリタをとりあえず作る
  2. BF の実行環境の詳細を決める
  3. BF の詳細なインタプリタを作る
  4. BF を効率的に実行する、中間言語を設計する
  5. BF を中間言語にコンパイルし実行する
  6. BF を拡張してみる（これはやるかどうか未定）
inukayinukay

BF の実行環境の詳細を決める。
移植性を考慮する仕様書 と今回の実装を確認しながら決めた

  • 用意するバッファは以下とする
    • 1変数が取りうる範囲は 0 ～ 255 (すなわち、符号なし8bit整数 ) である。
    • 配列の長さは 65536 (= 2^{16}) までとする。
    • ポインタが取りうる範囲は、上記のバッファサイズからわかるように 符号なし16bit整数 の範囲
  • 加算減算について配列、変数ともにオーバーフロー時とアンダーフロー時ともに同様の処理をする
    • 最大値に 1 を足した値は、 0 とする
    • 0 から 1 と引いた値は、 最大値とする
  • 入力命令で標準入力から入力がない場合、一定時間経過後何もせずプログラムの実行を続ける
    • すなわち、 , 命令で、一定時間経過までに標準入力がないと変数の書き換え等をしない
  • ループの開始と終了の対応状態が違う場合（すなわち、[ に対応する ] がない、またはその逆のとき）、コンパイルしない
inukayinukay

元の実装では、バッファ配列の長さ関連と標準入力関連を変更する必要がありそう。

inukayinukay

勝手にプログラムコードのサイズを決めてた。
rust の usize なので、 符号なし64bit整数 になってる。

inukayinukay

なんとなく、 [ ] 関連をスタックできればうまくいくのは分かった。

inukayinukay

多分これで問題ないと思う。

番号 名前 引数 説明
0 NOP なし(常に0) 何もしない
1 ADD 変化量 引数分ポイントが指し示す値を加算する
2 SUB 変化量 引数分ポイントが指し示す値を減算する
3 INC 変化量 引数分ポイントを加算して動かす
4 DEC 変化量 引数分ポイントを減算して動かす
5 OUT なし(常に0) ポイントが指し示す値を出力する
6 IN なし(常に0) ポイントが指し示す値に入力する
7 JMP 実行ポイント 引数にジャンプ
8 JE 実行ポイント ポイントが指し示す値が 0 なら引数にジャンプ

とりあえずこれで行く。
バイナリの表現はまた書く。

inukayinukay

32bit (4octet) で表現することにする。

1 octet 目は、命令番号
2-4 octet 目は、引数（ビッグエンディアン）

これで行く

inukayinukay

ジャンプ命令計算めんどくさい
どこに飛べばいいのか調べるので一苦労しそう

inukayinukay
struct CompiledBf {
    r: Vec<Instruction>,
    l: Vec<Box<CompiledBf>>,
}

こんな感じに、 CompiledBf を定義して、これの配列って形で処理すればいいことは分かった。

inukayinukay

わけわからん説明になってるので、細くすると、

BF は、
[ と ] を含まないBFコード（いったん、 「ジャンプなしコード」と呼ぶ）
と
[ と ] の内部のコード（「内部コード」）
が繰り返していると考えられる。
「内部コード」は素の BF コードなので、上記が再帰的に繰り返されている。
そのため、上記の構造体を作成すればよい。

「ジャンプなしコード」と「内部コード」をうまいことすれば、ジャンプ先を計算できる。
これによりコードができる。

inukayinukay

全く持ってまとまってないけど打来たと思う。（コミットはしてない）
テストコード書かないとうまく動いているのかわからない。

このスクラップは2023/11/05にクローズされました