brainf*ckでbrainf*ckインタプリタ

brainfckでbrainfckインタプリタ

brainfuckでbrainfuckのインタプリタを書いてみた.
入力の最初からNULL文字(ASCII文字コード:0x00)を読み込むまでをbrainfuckプログラム,NULL文字以降を標準入力とみなす.
注意：激重(このインタプリタを噛まさない場合に比べておよそ数百xプログラムの長さ倍時間がかかる) !!!処理系によっては一生終わらない!!!

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

Gist にも置いた.

解説

プログラム列の読み込み

>>>>,[>+>>,]<<[<<<]>>>-<

プログラムをひとつ読み込むたびに次のように3バイトのメモリを使う.

$C_i$

$F_i$

$S_i$

$C_i$ :命令記号(処理がめんどくさいので関係ない文字を弾く処理は入れていない)
$F_i$ :実行中フラグ　 $i$ 番目の命令が実行中ならば0,そうでないなら1にする.なぜこうするかは後で解説する.
$S_i$ :計算用領域　一時的な計算結果を格納したりするために使う.
メモリ上には0番地から次のようにデータが並ぶ

$S_{-1}$

$C_0$

$F_0$

$S_0$

$C_1$

$F_1$

$S_1$

...

プログラムは $C_1$ から格納されるが, $S_{-1}$ から $S_0$ までの領域は計算用領域として用いることがある. $F_0$ は決して実行されないが常に0である.
また,プログラムが格納された領域の後ろには,データの内容を格納するための領域が用意されている.
データ1バイトにつき次のように3バイトのメモリを使う.

$C_k$

$F_k$

$S_k$

$D_k$ :データ
$G_k$ :使用中フラグ　ポインタが $i$ 番目のデータを指しているか,未使用のデータ領域だったら0,そうでなければ1にする.なぜこうするかは後で解説する.
$S_{m+k+2}$ :計算用領域　一時的な計算結果を格納したりするために使う.
プログラムを格納する領域とデータを格納する領域は次のように繋がっている.

$S_{m-1}$

$S_m$

$F_m$

$S_m$

$0$

$S_{m+1}$

$D_0$

$G_0$

$S_{m+2}$

$D_1$

...

$S_m$ の次の0はプログラムの終わりを表す番兵として使う.また, $\{ S_n \}$ が3バイトごとに現れるようにすることでデータやプログラムの端でも計算領域を使うのに特別な配慮が不要になるうえに,プログラム領域とデータ領域を行き来するときにも処理が簡単になる.

命令の判定

$C_i$ が〜だったら○○というコードを単純に+-,.<>[]の8種類それぞれについて行なっている.
たとえば,プログラム冒頭の

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

であれば, $C_i$ が+なら $D_k$ を1増やすという操作を行う.
また,[と]の命令記号では順番にプログラムメモリ上を進みながら[と]の数を数えて括弧の数が対応するまで移動するという事を繰り返す.

命令の実行

命令を実行するにはプログラムを格納している領域とデータを格納する領域を,適切な場所(プログラム領域なら今実行している場所,データ領域ならポインタの指している場所)の間を行き来しなければならない.このときに $F_i,G_k$ が役に立つ.
まず,プログラム領域からデータ領域に移動するときには, $F_{i+1}$ まで移動してから

[>>>]>>>[>>>]

で $G_k$ まで移動できる.逆に,データ領域からプログラム領域に移動するときには, $G_{k-1}$ まで移動してから,

[<<<]<<<[<<<]

で $F_i$ まで移動できる.

今後改善すべき点

非常に遅いので高速化したバージョンを作る
もっとコードの短いバージョンを作る(400バイトぐらいでこれよりも処理の速いコードが存在する)

「brainf*ckでbrainf*ckインタプリタ」をウィキ内検索

最終更新：2013年08月07日 03:37

projectpn brainfckでbrainfckインタプリタ

メニュー

数学の部屋

その他

更新履歴