本気で sed で brainf*ck コンパイラ

前回、 bf => asm なコンパイラを sed で書いたのですが、「bf のコンパイラとは bf の逆アセンブラのこと」であるという主張を読んで、ああ全くその通りだなぁうまいこと言うなぁと思うと同時に、じゃあ実行できるバイナリ吐けば単なる逆アセ扱いされないよね☆ということで根性で作りました。

http://shinh.skr.jp/koneta/bfx.sed

i@u ~/wrk/bf> time ./bfx.sed < hello.bf > hello
./bfx.sed < hello.bf > hello  4.29s user 0.03s system 98% cpu 4.390 total
i@u ~/wrk/bf> chmod 755 hello
i@u ~/wrk/bf> ./hello
Hello World!
i@u ~/wrk/bf> time ./bfx.sed < echo.bf > echo
./echo./bfx.sed < echo.bf > echo  18.81s user 0.03s system 99% cpu 18.932 total
i@u ~/wrk/bf> chmod 755 echo
i@u ~/wrk/bf> ./echo
abcDEFgh123
abcdefgh123

見ての通り、本気でコンパイル遅いです。 Hello world に 4秒かかるのは GHC にタメをはれるどころかそれより遅い自信があります。えへん。 echo.bf は k.inabaさん作 のものです。自作のヤツだと負の数を [-] でリセットしてる部分があったので、これは 255 でループかましてない処理系だとすんごい遅いので。まぁそのくらい実装はラクなのですが、実に飽きたのでもう終わりです…

あと普通のコンパイラにできて sed にできないことが一つありまして、なんと chmod ができません！これはとても残念なことです。

実装方針はですね…

• めげない
• バイナリ入ってる文字列置換をやろうとすると、途中で変な挙動したり改行入ったりと大変なので、まずASCIIで処理して、最後にまとめてバイナリに置換するといい。あと s/NUMFF/\xff/g が何故か終わらない処理になったのでループでごまかした。
• あと別にプレースホルダはいらんかった。
• アドレス計算必要な部分が3個所ある。プログラムヘッダのファイルサイズを記述する部分と、 [ の飛び先、 ] の戻り先。
  • まず [ が出てきたら適当に決めた CmpJ@FFF7 とかを埋めておく。あとファイルサイズの部分もヘッダとかを足した数値である CmpJ@0169 とかを埋めておく。
  • />$/ s/.$/Add3/ などとして、 > があったら Add3 とかに置換する。 3 は命令サイズ。
  • 前回書いた足し算処理の要領でアドレスを加算。要はさっきセットした 3 が 0 になるまでループしつつ全部の CmpJ@xxxx 。 の xxxx 部分をインクリメントしていく。
  • ] が出てきたらさあ大変。一番ケツの CmpJ@xxxx を CmpJexxxx に変えて、 xxxx をケツにくっつける。そんでからケツにくっつけた xxxx を引き算しながら、戻るべきアドレスを計算する。
• とかごちゃごちゃやってから最後に ASCII をバイナリに変換してやる。

もう sed は金輪際さわらん。

ちなみに実行ファイルサイズは非常に小さいです。

i@u ~/wrk/bf> LA hello
-rwxr-xr-x 1 i i 1060  9月 22 17:11 hello
i@u ~/wrk/bf> LA echo
-rwxr-xr-x 1 i i 1406  9月 22 17:12 echo