Python で Brainf*ck のインタプリタを実装してみる
Brainf*ck は有名な難解プログラミング言語の一つ。 使える命令は ><+-.,[] のわずか 8 種類しかない。 今回は試しにそのインタプリタを Python で実装してみた。
#!/usr/bin/env python # -*- coding: utf-8 -*- from __future__ import print_function import sys class InvalidTokenException(BaseException): pass class CursorUnderflowException(BaseException): pass class Brainfuck(object): INITIAL_SIZE = 10000 DELTA = 1000 def __init__(self): self._token_mappings = { '>': self._increment, '<': self._decrement, '+': self._increment_pointer, '-': self._decrement_pointer, '.': self._write, ',': self._read, '[': self._loop_start, ']': self._loop_end, } self._brace_mappings = {} self._pointer = 0 self._cells = [0] * self.INITIAL_SIZE # > def _increment(self, _cursor): self._pointer += 1 if len(self._cells) < self._pointer: self._cells += [0] * self.DELTA # < def _decrement(self, _cursor): self._pointer -= 1 if self._pointer < 0: msg = 'ポインタは負の値を取れません' raise CursorUnderflowException(msg) # + def _increment_pointer(self, _cursor): self._cells[self._pointer] += 1 # - def _decrement_pointer(self, _cursor): self._cells[self._pointer] -= 1 # . def _write(self, _cursor): c = chr(self._cells[self._pointer]) print(c, end='') # , def _read(self, _cursor): d = ord(sys.stdin.read(1)) self._cells[self._pointer] = d # [ def _loop_start(self, cursor): if self._cells[self._pointer] != 0: return pair_brace_position = self._brace_mappings[cursor] return pair_brace_position # ] def _loop_end(self, cursor): if self._cells[self._pointer] == 0: return pair_brace_position = self._brace_mappings[cursor] return pair_brace_position def evaluate(self, code): self._initialize_brace_mappings(code) cursor = 0 end = len(code) while cursor < end: c = code[cursor] command = self._token_mappings.get(c) if command is None: msg = '不正な命令が含まれます: {token}'.format(token=c) raise InvalidTokenException(msg) index = command(cursor) cursor = index if index is not None else cursor + 1 def _initialize_brace_mappings(self, code): start_brace_positions = [] for i, token in enumerate(code): if token not in ['[', ']']: # '[' と ']' 以外は無視する continue if token == '[': # '[' のあった位置をスタックにプッシュする start_brace_positions.append(i) else: # 直近の ']' の場所をスタックから取り出す start_brace_position = start_brace_positions.pop() # 上記の ']' に対応する '[' の場所 end_brace_position = i # ']' の場所から対応する '[' の場所を引けるようにする self._brace_mappings[start_brace_position] = end_brace_position # 反対方向も self._brace_mappings[end_brace_position] = start_brace_position def main(): lines = [ line.strip('\r\n').replace(' ', '') for line in sys.stdin.readlines() ] code = ''.join(lines) interpreter = Brainfuck() try: interpreter.evaluate(code) except InvalidTokenException as e: print(e, file=sys.stderr) except CursorUnderflowException as e: print(e, file=sys.stderr) if __name__ == '__main__': main()
Hello, world! のプログラムを入力してみる。 入力が終わったら Ctrl-D で実行できる。
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-. ------------.<++++++++.--------.+++.------.--------.>+.^D Hello, world!
めでたしめでたし。
