Code

#!/usr/bin/env python

import nodes

asts = []

class AST(object):
    END_CHARS = ")(r"
    RECURSE = "RECURSE"
    def setup(self, code, first = False):
        if first: asts[:] = []
        asts.append(self)
        self.first = first
        self.nodes = []
        while code != "" and (self.first or code[0] not in AST.END_CHARS):
            code, node = AST.add_node(code)
            self.nodes.append(node)
        #print self.nodes
        if code != "":
            if code[0] == "r":
                self.nodes.append(AST.RECURSE)
            if code[0] != "(":
                code = code[1:]
        return code

    def run(self, stack = None):
        if stack == None:
            self.stack = []
        else:
            self.stack = stack
        self.counter = 0
        while self.counter != len(self.nodes):
            cur_node = self.nodes[self.counter]
            if cur_node is AST.RECURSE:
                self.recurse()
                return self.stack
            #print(cur_node, stack)
            cur_node.prepare(self.stack)
            no_args = cur_node.args
            self.stack, args = self.stack[no_args:], self.stack[:no_args]
            self.stack = cur_node(args) + self.stack
            self.counter += 1
        return self.stack

    @staticmethod
    def add_node(code):
        accepting = []
        for name in nodes.nodes:
            node = nodes.nodes[name]
            new_code, new_node = node.accepts(code)
            if new_code is not None:
                assert(new_node is not None)
                accepting.append((node.char, new_code, new_node))
        if accepting == []:
            raise SyntaxError("No nodes will accept code: %r"%(code))
        return sorted(accepting, key = lambda i:len(i[0]))[0][1:]

    def recurse(self):
        for ast in asts[::-1]:
            ast.counter = len(ast.nodes)-1
        assert(ast.first)
        ast.stack = self.stack
        ast.counter = 0

def test_code(code, out_stack):
    ast = AST()
    ast.setup(code, first = True)
    rtn_stack = ast.run()
    assert(rtn_stack == out_stack)