diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/__init__.py | 4 | ||||
| -rw-r--r-- | src/back/generator.py | 10 | ||||
| -rw-r--r-- | src/back/tac.py | 103 | ||||
| -rw-r--r-- | src/front/__init__.py | 0 | ||||
| -rw-r--r-- | src/front/ast.py | 121 | ||||
| -rw-r--r-- | src/front/parser.py | 6 | ||||
| -rw-r--r-- | src/front/scope.py | 3 |
7 files changed, 157 insertions, 90 deletions
diff --git a/src/__init__.py b/src/__init__.py index 89bcdc6..bbe2e28 100644 --- a/src/__init__.py +++ b/src/__init__.py @@ -1,12 +1,16 @@ from front.lexer import Lexer from front.parser import Parser from front.scope import Scope +from back.tac import TACList import sys def main(): ast = Parser(Lexer(sys.stdin.read())).parse() scope = Scope() ast.generate() + print scope + sys.stdout.write(repr(TACList())) + sys.stdout.flush() if __name__ == "__main__": main() diff --git a/src/back/generator.py b/src/back/generator.py new file mode 100644 index 0000000..851149b --- /dev/null +++ b/src/back/generator.py @@ -0,0 +1,10 @@ +class Register(object): + __shared_state = {} + count = 0 + + def __init__(self): + self.__dict__ = self.__shared_state + + def new(self): + self.count += 1 + return self.count diff --git a/src/back/tac.py b/src/back/tac.py index fc072d9..23ba1db 100644 --- a/src/back/tac.py +++ b/src/back/tac.py @@ -10,60 +10,71 @@ class Op(object): def __repr__(self): return """<Operator: "%s">""" % self -# arg1 arg2 -Op.ADD = Op("ADD") # x + y -> x y -Op.SUB = Op("SUB") # x - y -> x y -Op.MUL = Op("MUL") # x * y -> x y -Op.DIV = Op("DIV") # x / y -> x y -Op.MOD = Op("MOD") # x % y -> x y -Op.AND = Op("AND") # x AND y -> x y -Op.OR = Op("OR") # x OR y -> x y - -Op.NOT = Op("NOT") # !x -> x -Op.MINUS = Op("MINUS") # -x -> x - -Op.ASSIGN = Op("ASSIGN") # x = y -> x y - -Op.JMP = Op("JMP") # "goto" x -> x -Op.BEQ = Op("EQ") # "if x == y" -> x y -Op.BNE = Op("NE") # "if x != y" -> x y -Op.LE = Op("LE") # ... -Op.GE = Op("GE") -Op.LT = Op("LT") -Op.GT = Op("GT") - -Op.PARAM = Op("PARAM") # param x -> x -Op.CALL = Op("CALL") # fun x (y-args..) -> x y -Op.RETURN = Op("RETURN") # return x -> x - -# maybe in the future -#Op.ARRAYGET = Op("ARRAYGET") # x = y[i] -> i -#Op.ARRAYSET = Op("ARRAYSET") # x[i] = y -> y i - - -class TacElem: - +Op.ADD = Op("ADD") # x = x + y +Op.SUB = Op("SUB") # x = x - y +Op.MUL = Op("MUL") # x = x * y +Op.DIV = Op("DIV") # x = x / y +Op.MOD = Op("MOD") # x = x % y +Op.AND = Op("AND") # x = x AND y +Op.OR = Op("OR") # x = x OR y + +Op.NOT = Op("NOT") # x = !x +Op.MINUS = Op("MINUS") # x = -x + +Op.STORE = Op("STORE") # MEM[x] = y +Op.LOAD = Op("LOAD") # y = MEM[x] +Op.MOV = Op("MOV") # x = y + +Op.CMP = Op("CMP") # Z = x == y, N = x < y + +Op.EQ = Op("EQ") # x = Z +Op.NE = Op("NE") # x = !Z +Op.LT = Op("LT") # x = N +Op.LE = Op("LE") # x = Z || N +Op.GE = Op("GE") # x = !N +Op.GT = Op("GT") # x = !Z && !N + +Op.BEQ = Op("BEQ") # if x goto y +Op.JMP = Op("JMP") # goto x + +Op.PARAM = Op("PARAM") # param x +Op.CALL = Op("CALL") # call x return in y +Op.RETURN = Op("RETURN") # return x + +class TAC(object): def __init__(self,op,arg1=None,arg2=None): self.op = op self.arg1 = arg1 self.arg2 = arg2 def __repr__(self): - return "<TacElem, Op: %s, Arg1: %s, Arg2: %s>" % (self.op,self.arg1,self.arg2) + if self.arg2: + return "<TAC, op: %s, arg1: %s, arg2: %s>" % (self.op,self.arg1,self.arg2) + return "<TAC, op: %s, arg1: %s>" % (self.op,self.arg1) -class TacArray: - def __init__(self): - self.liste = [] +class Label(object): + def __init__(self, name): + self.name = name + + def __repr__(self): + return "<Label, name: %s>" % self.name - def append(self,arg): - self.liste.append(arg) - return len(self.liste)-1 +class FunctionLabel(Label): + def __repr__(self): + return "<FunctionLabel, name: %s>" % self.name + +class TACList(object): + __shared_state = {} + __tac_list = [] - def createList(self): - i = 1 - output = "" - for item in self.liste: - print "%08d | %s\t%s\t%s" % (i,item.op,item.arg1,item.arg2) - i = i+1 + def __init__(self): + self.__dict__ = self.__shared_state + def add(self, tac): + self.__tac_list.append(tac) + def __repr__(self): + res = "" + for i in range(len(self.__tac_list)): + res += "%04d: %s\n" % (i, repr(self.__tac_list[i])) + return res diff --git a/src/front/__init__.py b/src/front/__init__.py new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/src/front/__init__.py diff --git a/src/front/ast.py b/src/front/ast.py index f221440..99ccbee 100644 --- a/src/front/ast.py +++ b/src/front/ast.py @@ -1,4 +1,5 @@ from back.tac import * +from back.generator import Register import sys class Node(object): @@ -9,12 +10,14 @@ class Node(object): return Node.labels def emitlabel(self, i): - sys.stdout.write("L" + str(i) + ":") - sys.stdout.flush() + TACList().add(Label("L%d" % i)) - def emit(self, s): - sys.stdout.write("\t" + s + "\n") - sys.stdout.flush() + def emitfunction(self, name): + TACList().add(FunctionLabel(name)) + + def emit(self, op, arg1=None, arg2=None): + self.debug("emit(): op = %s, arg = %s, arg2 = %s" % (op, arg1, arg2)) + TACList().add(TAC(op, arg1, arg2)) def debug(self, msg): #sys.stdout.write("DEBUG: " + msg + "\n") @@ -43,13 +46,13 @@ class Function(Node): def generate(self): self.debug("Function.generate(): name = %s, params = %s, statement = %s" % (self.name, self.params, self.statement)) - print "%s:" % self.name + self.emitfunction(self.name) begin = self.newlabel() after = self.newlabel() self.emitlabel(begin) self.statement.generate(begin, after) self.emitlabel(after) - print + self.emit(Op.RETURN, 0) def __repr__(self): return "<Function: %s(%s) at line %d: %s>" % (self.name, str(self.params), self.lineno, str(self.statement)) @@ -93,15 +96,15 @@ class IfStatement(Statement): if self.false_statement: true_label = self.newlabel() false_label = self.newlabel() - self.emit("iffalse %s goto L%d" % (x, false_label)) + self.emit(Op.BEQ, x, "L%d" % false_label) self.emitlabel(true_label) self.true_statement.generate(true_label, after) - self.emit("goto L%d" % after) + self.emit(Op.JMP, "L%d" % after) self.emitlabel(false_label) self.false_statement.generate(false_label, after) else: true_label = self.newlabel() - self.emit("iffalse %s goto L%d" % (x, after)) + self.emit(Op.BEQ, x, "L%d" % after) self.emitlabel(true_label) self.true_statement.generate(true_label, after) @@ -116,19 +119,15 @@ class WhileStatement(Statement): def generate(self, before, after): self.debug("WhileStatement.generate(before = %d, after = %d): expression = %s, statement = %s" % (before, after, self.expression, self.statement)) - x = self.expression.reduce() - self.emit("iffalse %s goto L%d" % (x, after)) + self.emit(Op.BEQ, self.expression.reduce(), "L%d" % after) label = self.newlabel() self.emitlabel(label) self.statement.generate(label, before) - self.emit("goto L%d" % before) + self.emit(Op.JMP, "L%d" % before) def __repr__(self): return "<WhileStatement at line %d>" % self.lineno - def eval(self,tacarray): - return tacarray.append(te) - class ReturnStatement(Statement): def __init__(self, expression, lineno = -1): self.expression = expression @@ -136,7 +135,7 @@ class ReturnStatement(Statement): def generate(self, before, after): self.debug("ReturnStatement.generate(before = %d, after = %d): expression = %s" % (before, after, self.expression)) - self.emit("return %s" % self.expression.reduce()) + self.emit(Op.RETURN, self.expression.reduce()) def __repr__(self): return "<ReturnStatement at line %d>" % self.lineno @@ -149,7 +148,7 @@ class AssignStatement(Statement): def generate(self, before, after): self.debug("AssignStatement.generate(before = %d, after = %d): ident = %s, expression = %s" % (before, after, self.ident, self.expression)) - self.emit("%s = %s" % (self.ident, self.expression.reduce())) + self.emit(Op.STORE, self.ident, self.expression.reduce()) def __repr__(self): return "<AssignStatement for %s at line %d>" % (self.ident, self.lineno) @@ -162,13 +161,17 @@ class FunctionCall(Statement): def generate(self): self.debug("FunctionCall.generate(): ident = %s, arguments = %s" % (self.ident, self.arguments)) - self.emit("call %s" % self.ident) + for argument in self.arguments: + self.emit(Op.PARAM, argument.reduce()) + self.emit(Op.CALL, self.ident, len(self.arguments)) def reduce(self): self.debug("FunctionCall.reduce(): %s" % self) - t = Temporary() - self.emit("%s = call %s%s" % (t, self.ident, self.arguments)) - return t + for argument in self.arguments: + self.emit(Op.PARAM, argument.reduce()) + r = Register().new() + self.emit(Op.CALL, self.ident, r) + return r def __repr__(self): return "<FunctionCall for %s at line %d>" % (self.ident, self.lineno) @@ -178,12 +181,6 @@ class Expression(Node): self.op = op self.lineno = -1 - def generate(self): - return self - - def reduce(self): - return self - def __str__(self): return str(self.op) @@ -194,13 +191,6 @@ class Operation(Expression): def __init__(self, op, lineno = -1): super(Operation, self).__init__(op, lineno) - def reduce(self): - self.debug("Operation.reduce(): %s" % self) - x = self.generate() - t = Temporary() - self.emit("%s = %s" % (t, x)) - return t - def __repr__(self): return "<Operation at line %d>" % self.lineno @@ -210,9 +200,15 @@ class UnaryExpression(Operation): super(UnaryExpression, self).__init__(op, lineno) self.right = right - def generate(self): + def reduce(self): self.debug("UnaryExpression.generate(): op = %s, right = %s" % (self.op, self.right)) - return UnaryExpression(self.op, self.right.reduce()) + op = { + "!": Op.NOT, + "-": Op.MINUS, + }[self.op] + r = self.right.reduce() + self.emit(op, r) + return r def __str__(self): return "%s %s" % (str(self.op), str(self.right)) @@ -227,9 +223,36 @@ class BinaryExpression(Operation): self.left = left self.right = right - def generate(self): - self.debug("BinaryExpression.generate(): left = %s, op = %s, right = %s" % (self.left, self.op, self.right)) - return BinaryExpression(self.left.reduce(), self.op, self.right.reduce()) + def reduce(self): + self.debug("BinaryExpression.reduce(): left = %s, op = %s, right = %s" % (self.left, self.op, self.right)) + arith_op = { + "+": Op.ADD, + "-": Op.SUB, + "*": Op.MUL, + "/": Op.DIV, + "%": Op.MOD, + } + + logic_op = { + "==": Op.EQ, + "!=": Op.NE, + "<": Op.LT, + "<=": Op.LE, + ">=": Op.GE, + ">": Op.GT, + } + + try: + op = arith_op[self.op] + r = self.left.reduce() + self.emit(op, r, self.right.reduce()) + except KeyError: + op = logic_op[self.op] + r = Register().new() + self.emit(Op.CMP, self.left.reduce(), self.right.reduce()) + self.emit(op, r) + + return r def __str__(self): return "%s %s %s" % (str(self.left), str(self.op), str(self.right)) @@ -241,6 +264,12 @@ class Variable(Expression): def __init__(self, name, lineno = -1): super(Variable, self).__init__(name, lineno) + def reduce(self): + self.debug("Variable.reduce(): name = %s" % self.op) + r = Register().new() + self.emit(Op.LOAD, self.op, r) + return r + def __repr__(self): return "<Variable: %s at line %d>" %(self.op, self.lineno) @@ -250,9 +279,15 @@ class Constant(Expression): def jumping(self, true_label, false_label): if self.op and true_label != 0: - self.emit("goto L%d" % true_label) + self.emit(Op.JMP, "L%d" % true_label) elif not self.op and false_label != 0: - self.emit("goto L%d" % false_label) + self.emit(Op.JMP, "L%d" % false_label) + + def reduce(self): + self.debug("Constant.reduce(): value = %s" % self.op) + r = Register().new() + self.emit(Op.MOV, r, self.op) + return r def __repr__(self): return "<Constant: %d at line %d>" %(self.op, self.lineno) @@ -265,4 +300,4 @@ class Temporary(Expression): Temporary.count += 1 def __str__(self): - return "t%d" % self.number + return "r%d" % self.number diff --git a/src/front/parser.py b/src/front/parser.py index 511e929..53818bc 100644 --- a/src/front/parser.py +++ b/src/front/parser.py @@ -93,7 +93,11 @@ class Parser: self.move() return Constant(0, self.lexer.line) if self.token.tag == Tag.IDENT: - return Variable(self.match(Tag.IDENT), self.lexer.line) + line = self.lexer.line + name = self.match(Tag.IDENT) + if not self.scope.contains(name): + raise SyntaxError("%s is not declared in line %d" % (name, line)) + return Variable(name, line) return self.function_call() # function_call = "call" ident "[" [ expression_list ] "]". diff --git a/src/front/scope.py b/src/front/scope.py index a15ed1d..533497d 100644 --- a/src/front/scope.py +++ b/src/front/scope.py @@ -20,5 +20,8 @@ class Scope(object): if symbol not in self.__functions[self.__current_function]: self.__functions[self.__current_function].append(symbol) + def contains(self, name): + return name in self.__functions[self.__current_function] + def __str__(self): return "<Scope: %s>" % str(self.__functions) |