BFコンパイラー in Python DouKaku?

「どう書く?」でまだ出ていないのが不思議なお題。それがBF処理系。ここでは、BFで書かれたソースを、同じ言語に変換するコンパイラーを募集します。

私自身、すでにPerlとJavaScriptに関しては http://blog.livedoor.jp/dankogai/archives/50545151.html でやっているのですが、他の言語バージョンも是非見たいので。

Dan the Brainf.ucker

ひねり無し。
python bf.py -o hello.py hello.bf  みたいな感じで使います。

import sys
from getopt import getopt

def encode(bfcode):
    depth = code = 0
    pycode = []
    stack = []
    
    f = file(default['-o'], 'w')
    
    pycode.append('import sys')
    pycode.append('tape, ptr, code = {}, 0, 0')
    
    while code != len(bfcode):
        c = bfcode[code]
        
        if c == '>':
            pycode.append('\t' * depth + 'ptr += 1')
        elif c == '<':
            pycode.append('\t' * depth + 'ptr -= 1')
        elif c == '+':
            pycode.append('\t' * depth + 'tape[ptr] = tape.get(ptr, 0) + 1')
        elif c == '-':
            pycode.append('\t' * depth + 'tape[ptr] = tape.get(ptr, 0) - 1')
        elif c == ',':
            pycode.append('\t' * depth + 'tape[ptr] = sys.stdin.read(1)')
        elif c == '.':
            pycode.append('\t' * depth + 'sys.stdout.write(chr(tape.get(ptr, 0)))')
        elif c == '[':
            pycode.append('\t' * depth + 'while tape.get(ptr, 0):')
            stack.append(depth)
            depth += 1
        elif c == ']':
            depth = stack.pop()
        
        code += 1
    
    file(default['-o'], 'w').write('\n'.join(pycode))


if __name__ == '__main__':
    default = {'-o': 'a.py'}
    optlist, args = getopt(sys.argv[1:], 'o:', [])
    if args:
        default.update(optlist)
        encode(''.join(file(args[0]).readlines()))

これまたifの羅列をHashに置き換え。ただし、pythonの場合、[]は少し特別扱いが必要。こちらはindent不要とは行かないので。あと、関数名やインターフェースも好みにあわせて変えました。

Dan the Novice Snake Tamer

#!/usr/bin/env python
import sys
from getopt import getopt

def bf2py(bfcode):
    depth = 0
    opcode = {
        '>':'ptr += 1',
        '<':'ptr -= 1',
        '+':'tape[ptr] = tape.get(ptr, 0) + 1',
        '-':'tape[ptr] = tape.get(ptr, 0) - 1',
        ',':'tape[ptr] = sys.stdin.read(1)',
        '.':'sys.stdout.write(chr(tape.get(ptr, 0)))',
        '[':'while tape.get(ptr, 0):',
        ']':'pass'
    }
    pycode = []
    stack = []
    
    pycode.append('import sys')
    pycode.append('tape, ptr = {}, 0')
    
    for c in bfcode:
        if opcode.has_key(c):
            pycode.append( '\t' * depth + opcode[c])
            if c == '[':
                stack.append(depth)
                depth += 1
            elif c == ']':
                depth = stack.pop()
     
    return '\n'.join(pycode)

if __name__ == '__main__':
    defout = 'a.py'
    optlist, args = getopt(sys.argv[1:], 'o:', [])
    if args:
        pysrc = bf2py(''.join(file(args[0]).readlines()));
        file(defout or ops['-o'], 'w').write(pysrc)

せっかくなので++++がbf.inc(4)に置き換わるような設計にしてみました。

この程度の規模なら正規表現でも十分いけるんじゃないかと思いつつ勉強がてらにlexとyaccを使いました。

PLY (Python Lex-Yacc)

あとインデントうんぬんを考慮しないといけないのはそもそも直接while文を使うからなので式で表現しました。

,+[-.,+]を入力するとbf.get()or bf.inc(1)or bf.loop(lambda: bf.inc(-1)or bf.put()or bf.get()or bf.inc (1))と出力されます。

下のFizzBuzzコードを食わせると2638バイトの出力で、処理時間はあっという間でした。 http://d.hatena.ne.jp/n_shuyo/20070516/fizzbuzz

from ply import lex, yacc
import sys

# lex
tokens = "PLUS MINUS LEFT RIGHT WHILE WEND PUT GET COMMENT".split()

t_WHILE = "\["
t_WEND = "]"
t_PUT = "\."
t_GET = ","

def t_PLUS(t):
    "\++"
    t.value = len(t.value)
    return t

def t_MINUS(t):
    "-+"
    t.value = len(t.value)
    return t

def t_LEFT(t):
    "<+"
    t.value = len(t.value)
    return t

def t_RIGHT(t):
    ">+"
    t.value = len(t.value)
    return t

def t_COMMENT(t):
    '[^[\]><+-,.]' # return nothing

def t_error(t): pass
    
# yacc
"""*** grammar definition
sequence : sequence command
         | command

command : PLUS
        | MINUS
        | LEFT
        | RIGHT
        | PUT
        | GET
        | loop

loop : WHILE sequence WEND
"""

def p_sequence(p):
    "sequence : sequence command"
    p[0] = p[1] + "or " + p[2]

def p_sequence_command(p):
    "sequence : command"
    p[0] = p[1]

def p_command_PLUS(p):
    "command : PLUS"
    p[0] = "bf.inc(%s)" % p[1]

def p_command_MINUS(p):
    "command : MINUS"
    p[0] = "bf.inc(%s)" % -p[1]

def p_command_LEFT(p):
    "command : LEFT"
    p[0] = "bf.mov(%s)" % -p[1]

def p_command_RIGHT(p):
    "command : RIGHT"
    p[0] = "bf.mov(%s)" % p[1]

def p_command_PUT(p):
    "command : PUT"
    p[0] = "bf.put()"

def p_command_GET(p):
    "command : GET"
    p[0] = "bf.get()"

def p_command_loop(p):
    "command : loop"
    p[0] = p[1]
    
def p_loop(p):
    "loop : WHILE sequence WEND"
    p[0] = "bf.loop(lambda: %s)" % p[2]

def p_error(p): pass

# input and parse
data = sys.stdin.read()
lex.lex()
yacc.yacc()
result = yacc.parse(data)

# output
print """
from collections import defaultdict
import sys
class BF(object):
    mem = defaultdict(int)
    cur = 0
    def inc(self, n):
        self.mem[self.cur] += n
        self.mem[self.cur] %= 256
    def mov(self, n):
        self.cur += n
    def put(self):
        c = chr(self.mem[self.cur])
        sys.stdout.write(c)
    def get(self):
        c = sys.stdin.read(1)
        self.mem[self.cur] = ord(c)
    def loop(self, seq):
        while self.mem[self.cur]:
            seq()

bf = BF()
"""

print result

こんなもの dict にするのがいいに決まっている、と思ったら Dan さんに先こされているし。
仕方がないので、インデント情報も dict に突っ込んだやつを。

from __future__ import with_statement
import sys

def brainfuck_compile(source):
    try:
        from cStringIO import StringIO
    except:
        from StringIO import StringIO

    actions = {
        '>': ('pointer += 1', 0),
        '<': ('pointer -= 1', 0),
        '+': ('tape[pointer] = tape.get(pointer, 0) + 1', 0),
        '-': ('tape[pointer] = tape.get(pointer, 0) - 1', 0),
        '.': ('sys.stdout.write(chr(tape.get(pointer, 0)))', 0),
        ',': ('tape[pointer] = sys.stdin.read(1)', 0),
        '[': ('while tape.get(pointer, 0):', 1),
        ']': ('', -1),
    }

    generated = StringIO()
    print >>generated, 'import sys'
    print >>generated, 'tape, pointer = dict(), 0'
    indent = 0
    for c in source:
        if c.isspace(): continue
        stmt, indent_diff = actions[c]
        print >>generated, '%*s%s' % (indent, '', stmt)
        indent += indent_diff

    return generated.getvalue()

def iterchar(fp):
    for line in fp:
        for c in line: yield c

def main(args):
    if args:
        for arg in args:
            with file(arg) as fp:
                code = brainfuck_compile(iterchar(fp))
                print code
    else:
        code = brainfuck_compile(iterchar(sys.stdin))
        print code

if __name__ == '__main__':
    main(sys.argv[1:])

コードを張り忘れたので。

def p_sequence(p):
    "sequence : sequence command"
    p[0] = p[1] + p[2]

def p_sequence_command(p):
    "sequence : command"
    p[0] = p[1]

def p_command_PLUS(p):
    "command : PLUS"
    p[0] = "\nmem[cur] = (mem[cur] + %s) %% 256" % p[1]

def p_command_MINUS(p):
    "command : MINUS"
    p[0] = "\nmem[cur] = (mem[cur] - %s) %% 256" % p[1]

def p_command_LEFT(p):
    "command : LEFT"
    p[0] = "\ncur -= %s" % p[1]

def p_command_RIGHT(p):
    "command : RIGHT"
    p[0] = "\ncur += %s" % p[1]

def p_command_PUT(p):
    "command : PUT"
    p[0] = "\nsys.stdout.write(chr(mem[cur]))"

def p_command_GET(p):
    "command : GET"
    p[0] = "\nmem[cur] = ord(sys.stdin.read(1))"

def p_command_RESET(p):
    "command : RESET"
    p[0] = "\nmem[cur] = 0"

def p_command_loop(p):
    "command : loop"
    p[0] = p[1]
    
def p_loop(p):
    "loop : WHILE sequence WEND"
    p[0] = "\nwhile mem[cur]:%s" % p[2].replace("\n", "\n    ")

def p_error(p): pass

# input and parse
data = sys.stdin.read()
lex.lex()
yacc.yacc()
result = yacc.parse(data)

# output
print """
from collections import defaultdict
import sys
mem = defaultdict(int)
cur = 0
"""

print result

DouKaku?

BFコンパイラー

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq