妖怪少女のための Brainf*ck インタプリタ

こんにちは。人類は古来から、プログラムを書く際の力試しとして、Quine*1やBrainf*ck*2処理系を書く傾向にあります。 そのような傾向があり、やはり傾向であるので、書きました。

github.com

ちなみに文法チェックはしていません。

構文木を作る

構文木といっても生成しているのはただの入れ子リストです。 [] が来たらリストを入れ子にしてそれっぽくします。

def _generate_tree(program, ptr):
    tree = []
    while ptr < len(program):
        if program[ptr] == '[':
            leaf, nptr = _generate_tree(program, ptr + 1)
            tree.append(leaf + [']'])
            ptr = nptr
        elif program[ptr] == ']':
            return tree, ptr
        else:
            tree.append(program[ptr])
        ptr += 1
    return tree, 0


def parse(program):
    program = re.sub(r'[^\.,\+\-><\[\]]', '', program)
    return _generate_tree(program, 0)[0]

いま読み出してる文字列の位置を引数と返り値でやりとりしています。 見返してみるとクラスにしたほうがよかったとか思いますが忘れましょう。 我々は一時の誤ちに弱いし、なにより注意しないと設計のミスに気づかずいってしまうのです。気づきを高めるなどしていきましょう。

動かす

あとは生成した構文木をループで回すだけです。

def _run(tree, memory, ptr):
    output = ''
    for ch in tree:
        if isinstance(ch, list):
            ptr, a = _run(ch, memory, ptr)
            output += a
        elif ch == '+':
            memory[ptr] += 1
        elif ch == '-':
            memory[ptr] -= 1
        elif ch == '>':
            ptr += 1
            if ptr >= len(memory):
                memory.append(0)
        elif ch == '<':
            ptr -= 1
        elif ch == '.':
            output += chr(memory[ptr])
        elif ch == ',':
            try:
                memory[ptr] = ord(sys.stdin.read(1))
            except TypeError:
                memory[ptr] = 0
        elif ch == ']':
            if memory[ptr] != 0:
                return _run(tree, memory, ptr)
            else:
                return ptr, output
    return 0, output


def run(tree):
    return _run(tree, [0], 0)[1]

リストにしておくとループに投げられて便利ですね。

まとめ

Brainf*ck インタプリタは、やっていることは意外に壮大だけど、ちょっとコードが書けるようになったらわりと書けるので、どんどん書いていきましょう。 コンパイラなどもよいですね。

*1:自身のソースコードを出力するプログラム

*2:命令が8個しかないプログラミング言語