summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/__init__.py4
-rw-r--r--src/back/generator.py10
-rw-r--r--src/back/tac.py103
-rw-r--r--src/front/__init__.py0
-rw-r--r--src/front/ast.py121
-rw-r--r--src/front/parser.py6
-rw-r--r--src/front/scope.py3
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)