Brainfuck interpreter in Ruby's Regexp

Ruby の正規表現だけで Brainfuck インタプリタを作ることができました。正規表現の実行は =~ だけなので、ループなども正規表現の内部で実行してます。

https://github.com/shinh/hack/blob/master/bf_rb_reg/bf.rb

つまりどういうことができるかというと、 BF_REG という Regexp と BF_SUFFIX という文字列定数があって、 bf という文字列に格納された Brainfuck のコードを

BF_REG =~ bf + BF_SUFFIX

で実行することができます。出力は $~['o0'], $~['o1'], ... に入っているので、

output = ''
256.times do |i|
 o = $~["o#{i}"]
 break if !o
 output += o
end

的なコードで取り出すことができます。入力は ! の後に続いてる文字列を入力とする形式。Ruby の正規表現は Turing 完全でないので、無限ループはできないようになっています。

仕様の一覧を並べると

• 8bit Brainfuck
• 入力の終端は -1
• メモリは255番地まで
• 出力文字数は256まで
• 入力文字数は256まで
• Brainfuck命令以外の文字があると正規表現がマッチに失敗する
• 無限ループがあると正規表現がマッチに失敗する(正確には1つのループが256回連続回ったら止まるという仕様なので、本当は止まるコードもマッチ失敗することがありえます)

など。256まで、という制限は実装をラクにするためなので、本質的な制限ではないです、が無限にはできないです(入力文字数は無限にできるかも?)。この程度の制限があっても十分に実用的(?)で、例えば cal.bf も動いています。

$ echo 2016 10 | time ruby bf.rb cal.bf
                   1
 2  3  4  5  6  7  8
 9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
ruby bf.rb cal.bf  1147.54s user 0.26s system 99% cpu 19:07.91 total

ただすごく遅くて、 cal.bf の実行に19分とかかかってました。1命令10msとかその程度だと思います。 + とか - が実に遅い。

こんなことできるとはつい最近まで思ってなかったのですが、 HITCON CTF で正規表現力の研鑽を積んだ結果、なんかできるような気がしてきて、やってみたらできました。

今思うに、一番重要なことは後方参照を更新できる、ということだったのかなと思います。 \g で呼び出された中にある後方参照は、呼び出されるたびに値が変わっていくという。