※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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


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

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



解説

プログラム列の読み込み


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

プログラムをひとつ読み込むたびに次のように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 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バイトぐらいでこれよりも処理の速いコードが存在する)