one-file-projects/brainfuck.py

#!/usr/bin/env python
from sys import stdout,stdin,argv

class State:
    def __init__(self):
        self.data = [0]
        self.ptr = 0

    def prev(self):
        if self.ptr == 0:
            self.data.insert(0,0)
        else:
            self.ptr-=1

    def next(self):
        if self.ptr == len(self.data)-1:
            self.data.append(0)
        self.ptr+=1

    def get(self):
        return self.data[self.ptr]

    def set(self,val):
        self.data[self.ptr] = val


class Instruction:
    def run(self,state):
        raise NotImplementedError

    def __repr__(self):
        return self.__class__.__name__

class NextInstruction(Instruction):
    def run(self,state):
        state.next()

class PrevInstruction(Instruction):
    def run(self,state):
        state.prev()

class IncInstruction(Instruction):
    def run(self,state):
        state.set(state.get() + 1)

class DecInstruction(Instruction):
    def run(self,state):
        state.set(state.get() - 1)

class PutInstruction(Instruction):
    def run(self,state):
        stdout.write(chr(state.get()))
        stdout.flush()

class GetInstruction(Instruction):
    def run(self,state):
        state.set(ord(stdin.read(1)))

class BlockInstruction(Instruction):
    def __init__(self):
        self.instructions = []

    def prepend(self, inst):
        self.instructions.insert(0, inst)

    def run(self,state):
        for inst in self.instructions:
            inst.run(state)

    def __repr__(self):
        return  ", ".join(map(repr,self.instructions))

class LoopInstruction(Instruction):
    def __init__(self,block):
        self.block = block

    def run(self,state):
        while state.get() != 0:
            self.block.run(state)

    def __repr__(self):
        return "[ %s ]" % (repr(self.block))

Inext = NextInstruction()
Iprev = PrevInstruction()
Iinc = IncInstruction()
Idec = DecInstruction()
Iput = PutInstruction()
Iget = GetInstruction()

class Token:
    NEXT = "T_NEXT"
    PREV = "T_PREV"
    INC = "T_INC"
    DEC = "T_DEC"
    PUT = "T_PUT"
    GET = "T_GET"
    LOOP_START = "T_LOOP_START"
    LOOP_END = "T_LOOP_END"
    EOF = "T_EOF"

def lex(it):
    if type(it) == str:
        it = iter(it)
    END = object()
    c = next(it,END)

    while c != END:
        if c == ">":
            yield Token.NEXT
        elif c == "<":
            yield Token.PREV
        elif c == "+":
            yield Token.INC
        elif c == "-":
            yield Token.DEC
        elif c == ".":
            yield Token.PUT
        elif c == ",":
            yield Token.GET
        elif c == "[":
            yield Token.LOOP_START
        elif c == "]":
            yield Token.LOOP_END

        c = next(it,END)

    yield Token.EOF

class DefaultDict:
    def __init__(self,value):
        self.value = value

    def __contains__(self,key):
        return True

    def __getitem__(self,key):
        return self.value

def parse(it):
    NTS_S = object()
    NTS_B = object()

    r = object()
    s = object()
    a = object()

    table = [
        {
            Token.NEXT: (s,5),
            Token.PREV: (s,6),
            Token.INC: (s,7),
            Token.DEC: (s,8),
            Token.PUT: (s,9),
            Token.GET: (s,10),
            Token.LOOP_START: (s,2)
        },
        {
            Token.NEXT: (s,5),
            Token.PREV: (s,6),
            Token.INC: (s,7),
            Token.DEC: (s,8),
            Token.PUT: (s,9),
            Token.GET: (s,10),
            Token.LOOP_START: (s,2),
            Token.LOOP_END: (r,3),
            Token.EOF: (r,3)
        },
        {
            Token.NEXT: (s,5),
            Token.PREV: (s,6),
            Token.INC: (s,7),
            Token.DEC: (s,8),
            Token.PUT: (s,9),
            Token.GET: (s,10),
            Token.LOOP_START: (s,2)
        },
        {
            Token.LOOP_END: (s,4)
        },
        DefaultDict( (r,10) ),
        DefaultDict( (r,4) ),
        DefaultDict( (r,5) ),
        DefaultDict( (r,6) ),
        DefaultDict( (r,7) ),
        DefaultDict( (r,8) ),
        DefaultDict( (r,9) ),
        DefaultDict( (r,2) ),
        DefaultDict( (a,0) )
    ]

    goto = [
        { NTS_S: 12, NTS_B: 1 },
        { NTS_S: 11, NTS_B: 1 },
        { NTS_S: 3, NTS_B: 1 },
        {},
        {},
        {},
        {},
        {},
        {},
        {},
        {},
        {},
        {},
    ]

    state = [0]
    data = []
    c = next(it)

    while True:
        op, dat = table[state[-1]][c]
        if op == s:
            data.append(c)
            c = next(it)
            state.append(dat)
        elif op == a:
            return data[0]
        elif op == r:
            if dat == 2:
                S = data.pop()
                B = data.pop()
                state.pop()
                state.pop()

                S.prepend(B)
                data.append(S)

                state.append( goto[state[-1]][NTS_S] )
            elif dat == 3:
                B = data.pop()
                state.pop()

                S = BlockInstruction()
                S.prepend(B)
                data.append(S)

                state.append( goto[state[-1]][NTS_S] )
            elif dat == 4:
                data.pop()
                state.pop()

                data.append( Inext )

                state.append( goto[state[-1]][NTS_B] )
            elif dat == 5:
                data.pop()
                state.pop()

                data.append( Iprev )

                state.append( goto[state[-1]][NTS_B] )
            elif dat == 6:
                data.pop()
                state.pop()

                data.append( Iinc )

                state.append( goto[state[-1]][NTS_B] )
            elif dat == 7:
                data.pop()
                state.pop()

                data.append( Idec )

                state.append( goto[state[-1]][NTS_B] )
            elif dat == 8:
                data.pop()
                state.pop()

                data.append( Iput )

                state.append( goto[state[-1]][NTS_B] )
            elif dat == 9:
                data.pop()
                state.pop()

                data.append( Iget )

                state.append( goto[state[-1]][NTS_B] )
            elif dat == 10:
                data.pop()
                S = data.pop()
                data.pop()
                state.pop()
                state.pop()
                state.pop()

                B = LoopInstruction(S)
                data.append(B)

                state.append( goto[state[-1]][NTS_B] )


if __name__ == '__main__':

    if len(argv) > 1:
        fd = open(argv[1],"r")
        contents = fd.read()
        fd.close()
    else:
        contents = ",[.,]"

    ast = parse(lex(contents))

    state = State()
    ast.run(state)