implement three-address-code objects instead of printf

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)