diff options
| author | Teddy <ted.sybil@gmail.com> | 2013-07-31 20:46:43 +0800 |
|---|---|---|
| committer | Teddy <ted.sybil@gmail.com> | 2013-07-31 20:46:43 +0800 |
| commit | afdc71eaeffc760e5ceea76d35402fc2404bc80d (patch) | |
| tree | ef535316c61ce69a9595110e75cfcec81ae396a5 /sketch.py | |
| parent | 19d260020ca4025cf5d7d987966579c5d6276056 (diff) | |
use a simple and elegant way to represent the AST
Diffstat (limited to 'sketch.py')
| -rwxr-xr-x | sketch.py | 270 |
1 files changed, 108 insertions, 162 deletions
@@ -88,40 +88,41 @@ def to_bool(obj): # Mark all children of pc as flag def _fill_marks(pc, flag): - pc = pc.chd - while pc: - pc.skip = flag - pc = pc.sib + pc = pc.cdr + while not (pc is empty_list): + pc.func.skip = flag + pc = pc.cdr class _builtin_if(SpecialOptObj): def prepare(self, pc): # TODO: check number of arguments # Evaluate the condition first self.state = 0 # Prepared - pc = pc.chd - pc.skip = False - pc.sib.skip = True - if pc.sib.sib: - pc.sib.sib.skip = True + pc = pc.cdr + pc.func.skip = False + pc.cdr.func.skip = True + if not (pc.cdr.cdr is empty_list): + pc.cdr.cdr.func.skip = True def pre_call(self, arg_list, pc, envt, cont): + pc = pc.car # Condition evaluated and the decision is made self.state = 1 if (to_bool(arg_list[0])).val: - pc = pc.chd - pc.skip = True - pc.sib.skip = False - if pc.sib.sib: + pc = pc.cdr + pc.func.skip = True + pc.cdr.func.skip = False + if not (pc.cdr.cdr is empty_list): # Eval the former - pc.sib.sib.skip = True + pc.cdr.cdr.func.skip = True return (None, True) # Re-eval else: - pc = pc.chd - pc.skip = True - pc.sib.skip = True - if pc.sib.sib: + pc = pc.cdr + pc.func.skip = True + pc.cdr.func.skip = True + if not (pc.cdr.cdr is empty_list): # Eval the latter - pc.sib.sib.skip = False + pc.cdr.cdr.func.skip = False return (None, True) # Re-eval def post_call(self, arg_list, pc, envt, cont): @@ -147,28 +148,26 @@ class _builtin_lambda(SpecialOptObj): _fill_marks(pc, True) def call(self, arg_list, pc, envt, cont): + pc = pc.car para_list = list() # paramter list - par = pc.chd # Switch to the first parameter - if par.obj.obj: # If there is at least one parameter - para_list.append(par.obj.obj) - if par.chd: # More paramters? - par = par.chd - while par: - para_list.append(par.obj) - par = par.sib + par = pc.cdr.car # Switch to the first parameter + if not (par is empty_list): # If there is at least one parameter + while not (par is empty_list): + para_list.append(par.car) + par = par.cdr # Clear the flag to avoid side-effects (e.g. proc calling) _fill_marks(pc, False) - pc = pc.chd.sib # Move pc to procedure body + pc = pc.cdr.cdr # Move pc to procedure body #TODO: check body body = list() # store a list of expressions inside <body> - while pc: + while not (pc is empty_list): body.append(pc) - pc.next = None # Make each expression a orphan - # in order to ease the exit checking - pc = pc.sib + pc.func.next = None # Make each expression a orphan + # in order to ease the exit checking + pc = pc.cdr return (ProcObj(body, envt, para_list), False) @@ -180,37 +179,39 @@ class _builtin_lambda(SpecialOptObj): class _builtin_define(SpecialOptObj): def prepare(self, pc): - if is_arg(pc.chd): # Simple value assignment - pc.chd.skip = True # Skip the identifier - pc.chd.sib.skip = False + if is_arg(pc.cdr): # Simple value assignment + pc.cdr.func.skip = True # Skip the identifier + pc.cdr.cdr.func.skip = False else: # Procedure definition _fill_marks(pc, True) # Skip all parts def call(self, arg_list, pc, envt, cont): + pc = pc.car # TODO: check identifier - if is_arg(pc.chd): # Simple value assignment - id = pc.chd.obj + if is_arg(pc.cdr): # Simple value assignment + id = pc.cdr.car obj = arg_list[0] else: # Procedure definition - id = pc.chd.obj.obj + id = pc.cdr.car.car para_list = list() # Parameter list - par = pc.chd - if par.chd: # If there's at least one parameter - par = par.chd - while par: - para_list.append(par.obj) - par = par.sib + par = pc.cdr.car + if not (par.cdr is empty_list): + # If there's at least one parameter + par = par.cdr + while not (par is empty_list): + para_list.append(par.car) + par = par.cdr # Clear the flag to avoid side-effects (e.g. proc calling) _fill_marks(pc, False) - pc = pc.chd.sib # Move pc to procedure body + pc = pc.cdr.cdr # Move pc to procedure body #TODO: check body body = list() # store a list of expressions inside <body> - while pc: + while not (pc is empty_list): body.append(pc) - pc.next = None - pc = pc.sib + pc.func.next = None + pc = pc.cdr obj = ProcObj(body, envt, para_list) @@ -225,12 +226,12 @@ class _builtin_define(SpecialOptObj): class _builtin_set(SpecialOptObj): def prepare(self, pc): # TODO: check number of arguments - pc = pc.chd - pc.skip = True # Skip the identifier - pc.sib.skip = False + pc.cdr.func.skip = True # Skip the identifier + pc.cdr.cdr.func.skip = False def call(self, arg_list, pc, envt, cont): - id = pc.chd.obj + pc = pc.car + id = pc.cdr.car if envt.has_obj(id): envt.add_binding(id, arg_list[0]) return (UnspecObj(), False) @@ -261,52 +262,36 @@ class Tokenizor(): return None return self.tokenized.pop(0) -class Node(object): # AST Node - def __init__(self, obj, sib): - self.obj = obj - self.sib = sib - self.skip = None # skip the current branch? (runtime) - self.next = sib # next instruction (runtime) +class Prog(object): + def __init__(self, skip = False, next = None): + self.skip = skip + self.next = next - def __str__(self): - return "#<AST Node>" - def __expr__(self): - return self.__str__() +class Data(object): + pass -class ArgNode(Node): # AST Node (Argument) - def __init__(self, obj, sib = None): - super(ArgNode, self).__init__(obj, sib) +class Cons(object): # Construction + def __init__(self, car, cdr, func = Data()): + self.car = car + self.cdr = cdr + self.func = func + def ext_repr(self): + return "#<Cons>" def __str__(self): - return "#<AST ArgNode>" - def __expr__(self): - return self.__str__() - + return self.ext_repr() def print_(self): - print \ - "======================" + "\n" + \ - "Obj: " + str(self.obj) + "\n" + \ - "Sib: " + str(self.sib) + "\n" + \ - "======================" - -class OptNode(Node): # AST Node (Operator) - def __init__(self, obj, sib = None, chd = None): - super(OptNode, self).__init__(obj, sib) - self.chd = chd + print "car: " + str(self.car) + "\n" + \ + "cdr: " + str(self.cdr) + "\n" +class EmptyList(object): + def ext_repr(self): + return "()" def __str__(self): - return "#<AST OptNode>" - def __expr__(self): - return self.__str__() + return self.ext_repr() - def print_(self): - print \ - "======================" + "\n" + \ - "Obj: " + str(self.obj) + "\n" + \ - "Sib: " + str(self.sib) + "\n" + \ - "Chd: " + str(self.chd) + "\n" + \ - "======================" - -class RetAddr(object): # Return Adress (Refers to an AST Node) +empty_list = EmptyList() + +class RetAddr(object): # Return Adress (Refers to an Cons) def __init__(self, addr): self.addr = addr def __str__(self): @@ -315,16 +300,11 @@ class RetAddr(object): # Return Adress (Refers to an AST Node) class ASTGenerator(EvalObj): # Abstract Syntax Tree Generator def to_obj(self, obj): # Try to convert a string to EvalObj - if isinstance(obj, Node): return obj try: return IntObj(obj) except Exception: try: return FloatObj(obj) except Exception: return IdObj(obj) - def to_node(self, obj): # Try to convert an EvalObj to AST Node - if isinstance(obj, Node): return obj - return ArgNode(obj) - def __init__(self, stream): self.stream = stream self.stack = list() # Empty stack @@ -333,7 +313,8 @@ class ASTGenerator(EvalObj): # Abstract Syntax Tree Generator stack = self.stack while True: if len(stack) > 0 and stack[0] != '(': - return self.to_node(stack.pop(0)) # An AST is constructed + return Cons(stack.pop(0), empty_list, Prog(0)) + # An AST is constructed token = self.stream.read() # Read a new token if token is None: return None # Feed me! if token == '(': @@ -344,25 +325,24 @@ class ASTGenerator(EvalObj): # Abstract Syntax Tree Generator lst = stack[-1:] + lst del stack[-1] if len(lst) > 0: # At least one elem - root = OptNode(lst[0]) # The operator in the list + root = Cons(lst[0], None, Prog()) # The operator in the list # Collect the operands - if len(lst) > 1: - root.chd = lst[1] - ref = root.chd - for i in lst[2:]: - ref.sib = i - ref.next = ref.sib - ref = ref.sib + ref = root + for i in lst[1:]: + ref.cdr = Cons(i, None, Prog()) + ref.func.next = ref.cdr + ref = ref.cdr + ref.cdr = empty_list stack[-1] = root else: # Null list - stack[-1] = OptNode(ArgNode(None)) + stack[-1] = empty_list else: - stack.append(ArgNode(self.to_obj(token))) # Found an EvalObj + stack.append(self.to_obj(token)) # Found an EvalObj def is_id(string): return isinstance(string, IdObj) -def is_arg(node): - return isinstance(node, ArgNode) +def is_arg(pc): + return isinstance(pc.car, EvalObj) def is_ret_addr(val): return isinstance(val, RetAddr) def is_builtin_proc(val): @@ -475,66 +455,32 @@ class Evaluator(object): self._add_builtin_routines(self.envt) def run_expr(self, prog): stack = [0] * 100 # Eval Stack - ostack = [0] * 100 # Operator to be evaluated - top = -1 # stack top - otop = -1 # ostack top pc = prog # pc register cont = None # continuation register envt = self.envt # environment register - def print_stack(): - print '++++++++++STACK++++++++' - if len(stack) > 0: - for i in range(0, top + 1): - print stack[i] - print '----------STACK--------' - - def next_addr(ret_addr, otop): # Get the next instruction (after returning) - notop = otop - if otop > -1 and ret_addr is ostack[notop]: - # If the operator is evaluated successfully - # pc should point to its operand - notop -= 1 - res = ostack[notop].chd - notop -= 1 - else: - # Normal situation: move to the next operand - res = ret_addr.next - return (res, notop) - - - def push(pc, top, otop): # Push EvalObj to the stack + def push(pc, top): # Push EvalObj to the stack ntop = top - notop = otop - if is_arg(pc): # Pure operand + if is_arg(pc): # Pure operand ntop += 1 - stack[ntop] = envt.get_obj(pc.obj) # Try to find the binding - npc = pc.next # Move to the next instruction + stack[ntop] = envt.get_obj(pc.car) # Try to find the binding + if is_special_opt(stack[ntop]): + stack[ntop].prepare(pc) + npc = pc.func.next # Move to the next instruction else: # Found an Operator ntop += 1 - stack[ntop] = RetAddr(pc) # Push return address - if is_arg(pc.obj): # Getting operator - ntop += 1 - stack[ntop] = envt.get_obj(pc.obj.obj) - if is_special_opt(stack[ntop]): - stack[ntop].prepare(pc) - npc = pc.chd - else: # Operator need to be evaluated - notop += 1 - ostack[notop] = pc - notop += 1 - ostack[notop] = pc.obj - npc = pc.obj - - return (npc, ntop, notop) - - (pc, top, otop) = push(pc, top, otop) + stack[ntop] = RetAddr(pc) # Push return address + npc = pc.car + + return (npc, ntop) + + (pc, top) = push(pc, top) while is_ret_addr(stack[0]): # Still need to evaluate - while pc and pc.skip: - pc = pc.next # Skip the masked branches + while pc and pc.func.skip: + pc = pc.func.next # Skip the masked branches if pc is None: # All arguments are evaluated, exiting arg_list = list() @@ -553,7 +499,7 @@ class Evaluator(object): if ncur == len(body): # All exps in the body are evaled stack[top] = arg_list[0] envt = cont.envt - (pc, otop) = next_addr(cont.pc, otop) + pc = cont.pc.func.next cont = cont.old_cont else: pc = body[ncur] # Load the next exp @@ -562,16 +508,16 @@ class Evaluator(object): if is_builtin_proc(opt): # Built-in Procedures stack[top] = opt.call(arg_list[1:]) - (pc, otop) = next_addr(ret_addr, otop) + pc = ret_addr.func.next elif is_special_opt(opt): # Sepecial Operations (res, flag) = opt.call(arg_list[1:], ret_addr, envt, cont) if flag: # Need to call again top += 1 - pc = ret_addr.chd # Invoke again + pc = ret_addr.car.func.next # Invoke again else: stack[top] = res # Done - (pc, otop) = next_addr(ret_addr, otop) + pc = ret_addr.func.next elif is_user_defined_proc(opt): # User-defined Procedures # Create a new continuation @@ -585,7 +531,7 @@ class Evaluator(object): stack[top] = RetAddr(False) # Continuation mark pc = opt.body[0] # Move to the proc entry point else: - (pc, top, otop) = push(pc, top, otop) + (pc, top) = push(pc, top) return stack[0] |