brainf**kインタプリタを書いてみよう

処理系には30000バイトの byte型の配列があり、配列の要素はゼロで初期化される。 また、その配列の要素のひとつを指す暗黙のポインタがあり、ポインタは最初配列の先頭を指している。
実行可能な命令は次の8つのみである。

  • ">": ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
  • "<": ポインタをデクリメントする。C言語の「ptr--;」に相当。
  • "+": ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
  • "-": ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
  • ".": ポインタが指す値を出力する。C言語の「putchar(*ptr);」に相当。
  • ",": 1バイトを入力してポインタが指す値に代入する。C言語の「*ptr=getchar();」に相当。
  • "[": ポインタが指す値が0なら、対応する ] の直後までジャンプする。C言語の「while(*ptr){」に相当。
  • "]": ポインタが指す値が0でないなら、対応する [ にジャンプする。C言語の「}」に相当。
http://ja.wikipedia.org/wiki/Brainfuck

brainfuckなんて誰が書いても同じだろと思ってたけど、いざ自分が実装したものと、ググって出てきたものとを比べるとだいぶ違うのが出てきたのに驚きました。

自分がpythonでbf.pyを書いたのは以下の二通りです(ちなみにpython2/3双方で動作します)。

前者はソーススクリプトを直でたどるタイプで実装し、後者は一度パーザーで構文木を作ってから実行するタイプで実装しています。どちらも手続きの処理と環境へのコマンドとを分離して、一般的な言語実装っぽく作ってます。
検索でよく見る実装ではループをまわすだけで、こういうことをやってないのがほとんどのようですね。

ポインタの概念もあるし、やれる人なら実装も１，２時間で終わるだろうし、こういう言語を実装させるのも、プログラム能力を要求する採用などでの実演課題としてはありかもしれない。FizzBuzzと違って、設計系の議論もできるでしょうし。

パーザーを使う実装: bf.py

(手続き命令構築周りを若干きれいになるよう修正しました。)