import re import sys import pretty class token: unknown = 0 number = 1 mnemonic = 2 label = 3 address = 4 identifier = 5 line = 6 def __init__(self, tok_type, tok_val): self.ttype = tok_type self.val = tok_val def __str__(self): return ' %s' % (self.ttype, self.val) class opcode: pretty_printer = pretty.pretty_printer([0, 10, 20, 30, 50]) def __init__(self, opcode, operands, line=None, debug=None): self.opcode = opcode self.operand = operands self.line = line self.debug = debug def __str__(self): return opcode.pretty_printer.pprint([self.line, self.opcode, self.operand, self.debug]) #return '%s %s @ line %s => %s' % (self.opcode, self.operand, self.line, self.debug) class lexical_analyser: def __init__(self, input_stream): self.end = False self.instr = input_stream self.idx = 0 self.tokens = self.instr.split() self.line_re = re.compile('[0-9]') self.identifier_re = re.compile('[A-Za-z]:?') self.number_re = re.compile('#[0-9]+') self.address_re = re.compile('\[[0-9]+\]') self.keywords = ['PUSH', 'ADD', 'SUB', 'MUL', 'DIV', 'POW', 'PRINT', 'POP', 'NEG', 'JMP',] def get_next_token(self): self.idx += 1 if self.idx >= len(self.tokens): self.end = True tok = self.tokens[self.idx-1] if self.number(tok): return token(token.number, int(tok[1:])) elif self.address(tok): return token(token.address, int(tok[1:-1])) elif self.line(tok): return token(token.line, tok) elif self.identifier(tok): return token(token.identifier, tok) elif self.label(tok): return token(token.label, tok) else: return token(token.unknown, tok) def get_line_token(self): tok = self.get_next_token() if tok.ttype <> token.line: raise SyntaxError, 'Expected number, got %s' % tok.ttype tok.val = int(tok.val[1:]) return tok def get_mnemonic_token(self): tok = self.get_next_token() if tok.ttype == token.identifier and tok.val in self.keywords: return token(token.mnemonic, tok.val) raise SyntaxError, 'Expected keyword' def get_label_token(self): tok = self.get_next_token() if tok.ttype == token.identifier and tok.val[-1] == ':': return token(token.label, tok.val[:-1]) raise SyntaxError, 'Expected label' def get_label_or_mnemonic(self): tok = self.get_next_token() if tok.ttype == token.identifier and tok.val in self.keywords: return token(token.mnemonic, tok.val) elif tok.ttype == token.identifier and tok.val[-1] == ':': return token(token.label, tok.val[:-1]) raise SyntaxError, 'Expected label or mnemonic' def line(self, token): if self.line_re.match(token): return 1 return 0 def label(self, token): if self.identifier_re.match(token): return 1 return 0 def identifier(self, token): if self.identifier_re.match(token): return 1 return 0 def number(self, token): if self.number_re.search(token): return 1 return 0 def address(self, token): if self.address_re.search(token): return 1 return 0 class assembly_parser: def __init__(self, lexer, output): self.lexer = lexer self.out = output self.line = 1 self.labels = {} self.vars = {} def output(self, command): self.out.append(command) #sys.stdout.write(command) #print command def parse(self): while(1): if self.lexer.end: break line = self.lexer.get_line_token() token = self.lexer.get_label_or_mnemonic() if token.ttype is token.label: self.labels[token.val] = line.val - 1 label = token mnemonic = self.lexer.get_mnemonic_token() if hasattr(self, mnemonic.val): getattr(self, mnemonic.val)() else: raise SyntaxError, 'Incorrect syntax' else: if hasattr(self, token.val): getattr(self, token.val)() self.line += 1 def PUSH(self): operand = self.lexer.get_next_token() if operand.ttype == token.identifier: self.output(opcode(1001, operand.val, self.line, 'PUSH %s' % operand.val)) elif operand.ttype == token.number: self.output(opcode(1002, operand.val, self.line, 'PUSH #%s' % operand.val)) elif operand.ttype == token.address: self.output(opcode(1003, operand.val, self.line, 'PUSH [%s]' % operand.val)) def ADD(self): self.output(opcode(1004, None, self.line, 'ADD')) def SUB(self): self.output(opcode(1005, None, self.line, 'SUB')) def MUL(self): self.output(opcode(1006, None, self.line, 'MUL')) def DIV(self): self.output(opcode(1007, None, self.line, 'DIV')) def POW(self): self.output(opcode(1008, None, self.line, 'POW')) def POP(self): operand = self.lexer.get_next_token() if not operand.ttype == token.identifier: raise SyntaxError, 'Expected identifier' self.output(opcode(1009, operand.val, self.line, 'POP %s' % operand.val)) def NEG(self): self.output(opcode(1010, None, self.line, 'NEG')) def JMP(self): operand = self.lexer.get_next_token() self.output(opcode(2001, operand.val, self.line, 'JMP %s' % operand.val)) def PRINT(self): self.output(opcode(3001, None, self.line, 'PRINT')) class virtual_machine: def __init__(self, input_stream, output_stream): self.input = input_stream self.output = output_stream def run(self): pretty_printer = pretty.pretty_printer([0, 10, 20, 30, 50, 60]) pretty_printer.output(['Line', 'Opcode', 'Operand', 'Debug', 'Stack']) print '-' * 70 stack = [] variables = {} ip = 0 while(1): opcode = self.input[ip] op = opcode.opcode if op == 1001: # push identifier if not variables.has_key(opcode.operand): raise SyntaxError, 'Variable reference before assignment' stack.append(variables[opcode.operand]) elif op == 1002: # push number on stack stack.append(opcode.operand) elif op == 1003: # push address on stack # not sure whether this will be useful yet pass elif op == 1004: # add stack.append(stack.pop() + stack.pop()) elif op == 1005: #sub stack.append(-stack.pop() + stack.pop()) elif op == 1006: #mul stack.append(stack.pop() * stack.pop()) elif op == 1007: #div a = stack.pop() b = stack.pop() stack.append(b/a) elif op == 1008: #pow a = stack.pop() b = stack.pop() stack.append(b**a) elif op == 1009: #pop variables[opcode.operand] = stack.pop() elif op == 1010: #neg stack[-1] *= -1 elif op == 2001: if self.labels.has_key(opcode.operand): ip = self.labels[opcode.operand] elif op == 3001: print '\t\tOutput:\t\t%s' % stack.pop() ip += 1 if ip >= len(self.input): break pretty_printer.output([opcode.line, opcode.opcode, opcode.operand, opcode.debug, stack]) print '-' * 70 if __name__ == '__main__': test_program = ''' 0000 PUSH #1 0001 JMP L3 0002 L1: PUSH #2 0003 PUSH #3 0004 ADD 0005 L2: PUSH #7 0006 POW 0007 PUSH #7 0008 MUL 0009 ADD 0010 JMP L4 0011 L3: NEG 0012 JMP L1 0013 L4: POP answer 0014 PUSH answer 0015 PRINT ''' lex = lexical_analyser(test_program) parser = assembly_parser(lex, []) parser.parse() vm = virtual_machine(parser.out, sys.stdout) vm.labels = parser.labels vm.run()