timmeh

import sysclass operator:    all_ops = {}    def __init__(self, symbol, precedence, mnemonic):        self.sym = symbol        self.prec = precedence        self.mnem = mnemonic        if operator.all_ops.has_key(symbol):            raise SyntaxError, 'Operator already assigned'        operator.all_ops[symbol] = self        operator('=', 50 , 'POP')operator('+', 100, 'ADD')operator('-', 100, 'SUB')operator('*', 200, 'MUL')operator('/', 200, 'DIV')operator('^', 300, 'POW')operator('@', 50 , 'END')eq = 0ay = 1by = 2precedence_table =  [#                       +   -   *   /   ^   (   )   @                    [   by, by, ay, ay, ay, ay, by, by ],   # +                    [   by, by, ay, ay, ay, ay, by, by ],   # -                    [   by, by, by, by, by, ay, by, by ],   # *                    [   by, by, by, by, by, ay, by, by ],   # /                    [   by, by, by, by, by, ay, by, by ],   # ^                    [   ay, ay, ay, ay, ay, ay, eq, by ],   # (                    [   by, by, by, by, by, eq, by, by ],   # )                    [   ay, ay, ay, ay, ay, ay, ay, eq ],   # @                    ]def get_precedence(a, b):    mapping = {'+': 0, '-': 1, '*': 2, '/': 3, '^': 4, '{': 5, ')': 6, '@': 7 }    return precedence_table[mapping[a]][mapping[b]]class lex:    '''Class to hold lexer related variables'''    digits = '0123456789'    alpha = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'    ident = alpha + digits + '_'    ops = '+-*/^'    newline = ';'    addsub = ['+', '-']    muldiv = ['*', '/']    boolops = ['<', '>', '==', '!=']    unknown = 0    number = 1    ident = 2    operator = 3    def __init__(self, code):        self.pos = 0        self.char = code[0]        self.code = code        self.count = len(code)        self.col = 1        self.sym = None        self.symtype = None        self.linebuf = ''        self.line = 1        self.end = False        self.next_symbol()    def isdigit(self):        if self.char in lex.digits:            return True        return False    def isnumber(self):        if sum([1 for i in self.sym if i in lex.digits]) < len(self.sym):            return False        return True    def isalpha(self):        if self.char in lex.alpha:            return True        return False    def isident(self):        if self.char in lex.ident:            return True        return False    def isidentifier(self):        if self.sym[0] in lex.alpha and sum([1 for i in self.sym[1:] if i in lex.ident]) == len(self.sym) - 1:            return True        return False    def isop(self):        if self.char in lex.ops:            return True        return False    def next_char(self):        #print self.char        char = self.char        self.pos += 1        self.col += 1        if self.pos >= self.count:            self.end = True            return        self.char = self.code[self.pos]        self.linebuf += self.char    def next_symbol(self):        while(1):            if self.end:                self.sym = 'END'                return            if self.char in '''	 ''':                self.next_char()                continue            elif self.char is lex.newline:                self.line += 1                self.col = 1                self.linebuf = ''                self.next_char()           #for when there is more than 1 line            elif self.isdigit():                num = ''                while(1):                    num += self.char                    self.next_char()                    if not self.isdigit():                        self.sym = num                        self.symtype = lex.number                        return            elif self.isalpha():                ident = ''                while(1):                    ident += self.char                    self.next_char()                    if not self.isident():                        self.sym = ident                        self.symtype = lex.ident                        return            elif self.isop():                op = ''                while(1):                    op += self.char                    self.next_char()                    if not self.isop():                        self.sym = op                        self.symtype = lex.operator                        return            else:                self.sym = self.char                self.symtype = lex.unknown                self.next_char()                returnclass bottom_up:        def __init__(self, out_strm, lexer):        self.op_prec = operator.all_ops        self.out = out_strm        self.lexer = lexer        self.lineidx = 0        self.lblidx = 0    def isnum(self, char):        if char in '0123456789':            return 1        return 0    def isop(self, char):        if char in self.op_prec.keys():            return 1        return 0    def output(self, out):        self.lineidx += 1        self.out.write('''%04d 		 %s''' % (self.lineidx, out))        def evaluate(self):                #print some stats        print 'Expression : %s' % self.lexer.code        print 'Expression Length : %s' % len(self.lexer.code)        print ''        #stack for operations        ops = ['@']        #loops through all 'tokens'        while(self.lexer.sym <> 'END'):            sym = self.lexer.sym            stype = self.lexer.symtype            #all numbers are immediately output            if stype == lex.number:                self.output('PUSH #%s' % sym)            #if the current operator has a precedence less than the last            #operator put on the stack, pop the last operator and output            #it.  push all operators onto the stack            elif stype == lex.operator:                prec = get_precedence(ops[-1], sym)                if prec == ay or prec == eq:                    ops.append(sym)                else:                    while(get_precedence(ops[-1], sym) == by):                        self.output(operator.all_ops[ops.pop()].mnem)                    ops.append(sym)            self.lexer.next_symbol()        #any left over operators on the stack need to be popped to the        #output        #print ops        while(len(ops) <> 0):            self.output(self.op_prec[ops.pop()].mnem)        #more stats        print ''        print 'Lines Output : %s' % self.lineidximport timelexer = lex('3*4*6*5;')parser = bottom_up(sys.stdout, lexer)start = time.clock()parser.evaluate()end = time.clock()print 'Start : %s' % startprint 'End   : %s' % endprint 'Time  : %s' % str(end - start)