diff options
| -rw-r--r-- | src/__init__.py | 24 | ||||
| -rw-r--r-- | src/front/ast.py | 282 | ||||
| -rw-r--r-- | src/front/lexer.py | 25 | ||||
| -rw-r--r-- | src/front/parser.py | 59 | ||||
| -rw-r--r-- | src/front/scope.py | 20 |
5 files changed, 238 insertions, 172 deletions
diff --git a/src/__init__.py b/src/__init__.py index ad0278b..89bcdc6 100644 --- a/src/__init__.py +++ b/src/__init__.py @@ -1,26 +1,12 @@ from front.lexer import Lexer from front.parser import Parser +from front.scope import Scope +import sys def main(): - source = '''fun fib[a] - if a < 2 - @1 - end - @( call fib[a-1] + call fib[a-2] ) -end - -# main function -fun main[] - sum = 0 - i = 0 - while (i < 10) - sum = sum + call fib[i] - i = i + 1 - end - @sum -end''' - - print Parser(Lexer(source)).parse() + ast = Parser(Lexer(sys.stdin.read())).parse() + scope = Scope() + ast.generate() if __name__ == "__main__": main() diff --git a/src/front/ast.py b/src/front/ast.py index d6d4a3f..f221440 100644 --- a/src/front/ast.py +++ b/src/front/ast.py @@ -1,57 +1,128 @@ from back.tac import * +import sys class Node(object): - pass + labels = 0 + + def newlabel(self): + Node.labels += 1 + return Node.labels + + def emitlabel(self, i): + sys.stdout.write("L" + str(i) + ":") + sys.stdout.flush() + + def emit(self, s): + sys.stdout.write("\t" + s + "\n") + sys.stdout.flush() + + def debug(self, msg): + #sys.stdout.write("DEBUG: " + msg + "\n") + #sys.stdout.flush() + return class Program(Node): def __init__(self, functions, lineno = -1): self.functions = functions self.lineno = lineno - def eval(self,tacarray): + def generate(self): + self.debug("Program.generate(): functions = %s" % self.functions) for function in self.functions: - function = function.eval(tacarray) - - return 0 + function.generate() def __repr__(self): return "<Program: %s>" % self.functions class Function(Node): - def __init__(self, name, params, statements, lineno = -1): + def __init__(self, name, params, statement, lineno = -1): self.name = name self.params = params - self.statements = statements + self.statement = statement self.lineno = lineno - def __repr__(self): - return "<Function: %s(%s) at line %d: %s>" % (self.name, str(self.params), self.lineno, str(self.statements)) + def generate(self): + self.debug("Function.generate(): name = %s, params = %s, statement = %s" % (self.name, self.params, self.statement)) + print "%s:" % self.name + begin = self.newlabel() + after = self.newlabel() + self.emitlabel(begin) + self.statement.generate(begin, after) + self.emitlabel(after) + print - def eval(self,tacarray): - return tacarray.append(te) + def __repr__(self): + return "<Function: %s(%s) at line %d: %s>" % (self.name, str(self.params), self.lineno, str(self.statement)) class Statement(Node): pass +class Sequence(Statement): + def __init__(self, s1, s2, lineno = -1): + self.s1 = s1 + self.s2 = s2 + self.lineno = lineno + + def generate(self, before, after): + self.debug("Sequence.generate(before = %d, after = %d): s1 = %s, s2 = %s" % (before, after, self.s1, self.s2)) + if not self.s1: + self.s2.generate(before, after) + elif not self.s2: + self.s1.generate(before, after) + else: + label = self.newlabel() + self.s1.generate(before, label) + self.emitlabel(label) + self.s2.generate(label, after) + + def __repr__(self): + return "<Sequence at line %d: %s, %s>" % (self.lineno, self.s1, self.s2) + class IfStatement(Statement): - def __init__(self, expression, true_statements, false_statements, lineno = -1): + def __init__(self, expression, true_statement, false_statement, lineno = -1): self.expression = expression - self.true_statements = true_statements - self.false_statements = false_statements + self.true_statement = true_statement + self.false_statement = false_statement self.lineno = lineno + def generate(self, before, after): + self.debug("IfStatement.generate(before = %d, after = %d): expression = %s, true = %s, false = %s" % (before, after, self.expression, self.true_statement, self.false_statement)) + + x = self.expression.reduce() + + if self.false_statement: + true_label = self.newlabel() + false_label = self.newlabel() + self.emit("iffalse %s goto L%d" % (x, false_label)) + self.emitlabel(true_label) + self.true_statement.generate(true_label, after) + self.emit("goto 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.emitlabel(true_label) + self.true_statement.generate(true_label, after) + def __repr__(self): return "<IfStatement at line %d>" % self.lineno - def eval(self,tacarray): - return tacarray.append(te) - class WhileStatement(Statement): - def __init__(self, expression, statements, lineno = -1): + def __init__(self, expression, statement, lineno = -1): self.expression = expression - self.statements = statements + self.statement = statement self.lineno = lineno + 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)) + label = self.newlabel() + self.emitlabel(label) + self.statement.generate(label, before) + self.emit("goto L%d" % before) + def __repr__(self): return "<WhileStatement at line %d>" % self.lineno @@ -63,144 +134,135 @@ class ReturnStatement(Statement): self.expression = expression self.lineno = lineno + 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()) + def __repr__(self): return "<ReturnStatement at line %d>" % self.lineno - def eval(self,tacarray): - - if isinstance(expression,Node): - expression = expression.eval(tacarray) - - te = TacElem(Op.RETURN,expression) - return tacarray.append(te) - class AssignStatement(Statement): def __init__(self, ident, expression, lineno = -1): self.ident = ident self.expression = expression self.lineno = lineno + 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())) + def __repr__(self): return "<AssignStatement for %s at line %d>" % (self.ident, self.lineno) - def eval(self,tacarray): - if isinstance(expression,Node): - expression = expression.eval(tacarray) - yield self.expression - - class FunctionCall(Statement): def __init__(self, ident, arguments = [], lineno = -1): self.ident = ident self.arguments = arguments self.lineno = lineno + def generate(self): + self.debug("FunctionCall.generate(): ident = %s, arguments = %s" % (self.ident, self.arguments)) + self.emit("call %s" % self.ident) + + def reduce(self): + self.debug("FunctionCall.reduce(): %s" % self) + t = Temporary() + self.emit("%s = call %s%s" % (t, self.ident, self.arguments)) + return t + def __repr__(self): return "<FunctionCall for %s at line %d>" % (self.ident, self.lineno) - def eval(self,tacarray): - """ Function call will be seperated in all the Op.PARAMs first, and the - Op.CALL afterwards""" - - # XXX can there be arguments with multiple expressions bla((x+y-3),z)? - # -> have to look into that, when it comes to param-number - # for every parameter create a TacElem - #for argument in self.arguments: - # if isinstance(argument,Node): - # argument = argument.eval(tacarray) - # TacElem(Op.PARAM,argument) - - # in the end create the CALL-TacElem with the number of parameters - te = TacElem(Op.CALL,self.ident,len(self.arguments)) - return tacarray.append(te) +class Expression(Node): + def __init__(self, op, lineno = -1): + self.op = op + self.lineno = -1 + def generate(self): + return self -class Expression(Node): - pass + def reduce(self): + return self -class UnaryExpression(Expression): - """ Unary expressions are !x or -x ...""" - def __init__(self, op, right, lineno = -1): - self.op = op - self.right = right - self.lineno = lineno + def __str__(self): + return str(self.op) def __repr__(self): - return "<UnaryExpression: %s(%s) at line %d>" % (self.op, self.right, self.lineno) + return "<Expression at line %d>" % self.lineno - def eval(self,tacarray): - right = self.right - op = None +class Operation(Expression): + def __init__(self, op, lineno = -1): + super(Operation, self).__init__(op, lineno) - if (self.op == "not"): - op = Op.NOT - if (self.op == "minus"): - op = Op.MINUS + def reduce(self): + self.debug("Operation.reduce(): %s" % self) + x = self.generate() + t = Temporary() + self.emit("%s = %s" % (t, x)) + return t - if op == None: - return None + def __repr__(self): + return "<Operation at line %d>" % self.lineno - if isinstance(right,Node): - right = right.eval(tacarray) +class UnaryExpression(Operation): + """ Unary expressions are !x or -x ...""" + def __init__(self, op, right, lineno = -1): + super(UnaryExpression, self).__init__(op, lineno) + self.right = right - te = TacElem(op,right) - return tacarray.append(te) + def generate(self): + self.debug("UnaryExpression.generate(): op = %s, right = %s" % (self.op, self.right)) + return UnaryExpression(self.op, self.right.reduce()) + def __str__(self): + return "%s %s" % (str(self.op), str(self.right)) -class BinaryExpression(Expression): + def __repr__(self): + return "<UnaryExpression: %s(%s) at line %d>" % (self.op, self.right, self.lineno) + +class BinaryExpression(Operation): """ Biary expression are x+y, x-y, ... """ def __init__(self, left, op, right, lineno = -1): + super(BinaryExpression, self).__init__(op, lineno) self.left = left - self.op = op self.right = right - self.lineno = lineno - def __repr__(self): - return "<BinaryExpression: %s(%s, %s) at line %d>" % (self.op, self.left, self.right, self.lineno) + 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 __str__(self): + return "%s %s %s" % (str(self.left), str(self.op), str(self.right)) - def eval(self,tacarray): - op = None - if (self.op == "+"): - op = Op.ADD - if (self.op == "-"): - op = Op.SUB - if (self.op == "*"): - op= Op.MUL - if (self.op == "/"): - op= Op.DIV - if (self.op == "%"): - op= Op.MOD - if (self.op == "and"): - op= Op.AND - if (self.op == "or"): - op= Op.OR - - if op == None: - return None - - if isinstance(left,Node): - left = left.eval(tacarray) - - if isinstance(right,Node): - right = right.eval(tacarray) - - te = TacElem(op,left,right) - return tacarray.append(te) - + def __repr__(self): + return "<BinaryExpression: %s(%s, %s) at line %d>" % (self.op, self.left, self.right, self.lineno) class Variable(Expression): def __init__(self, name, lineno = -1): - self.name = name - self.lineno = lineno + super(Variable, self).__init__(name, lineno) def __repr__(self): - return "<Variable: %s at line %d>" %(self.name, self.lineno) + return "<Variable: %s at line %d>" %(self.op, self.lineno) class Constant(Expression): def __init__(self, value, lineno = -1): - self.value = value - self.lineno = lineno + super(Constant, self).__init__(value, lineno) + + def jumping(self, true_label, false_label): + if self.op and true_label != 0: + self.emit("goto L%d" % true_label) + elif not self.op and false_label != 0: + self.emit("goto L%d" % false_label) def __repr__(self): - return "<Variable: %d at line %d>" %(self.value, self.lineno) + return "<Constant: %d at line %d>" %(self.op, self.lineno) + +class Temporary(Expression): + count = 0 + + def __init__(self): + self.number = Temporary.count + Temporary.count += 1 + + def __str__(self): + return "t%d" % self.number diff --git a/src/front/lexer.py b/src/front/lexer.py index 53ccaec..e6eb172 100644 --- a/src/front/lexer.py +++ b/src/front/lexer.py @@ -4,10 +4,10 @@ from token import * class Lexer: def __init__(self, source): - self.source = (source + "\n\n").splitlines() + self.source = (source + "\n").splitlines() self.source.reverse() self.line = 0 - self.doubleNewlineCheck = False + self.lastWasNewline = True self.currentLine = '' # reservierte Wörter initialisieren @@ -31,31 +31,32 @@ class Lexer: return def scan(self): + # leerzeichen entfernen + self.currentLine = self.currentLine.strip() + # wenn in der aktuellen Zeile nichts mehr steht - if (len(self.currentLine) == 0): + if len(self.currentLine) == 0: # wenn source zuende, dann None zurückgeben - if (len(self.source) <= 0): + if len(self.source) <= 0: return None # nächste Zeile auslesen self.line = self.line + 1 self.currentLine = self.source.pop() - # newline zurückgeben - if self.doubleNewlineCheck: - self.doubleNewlineCheck = False - return Token(Tag.NEWLINE) + # nur ein newline zurückgeben + if self.lastWasNewline: + return self.scan() - # leerzeichen entfernen - self.currentLine = self.currentLine.strip() + self.lastWasNewline = True + return Token(Tag.NEWLINE) # bei Kommentar, Rest der Zeile ignorieren if self.currentLine.startswith('#'): self.currentLine = '' return self.scan() - # keine doppelten Newlines - self.doubleNewlineCheck = True + self.lastWasNewline = False # Token parsen if self.currentLine.startswith('@'): diff --git a/src/front/parser.py b/src/front/parser.py index 610a5bb..511e929 100644 --- a/src/front/parser.py +++ b/src/front/parser.py @@ -1,37 +1,41 @@ # -*- coding: utf-8 -*- from ast import * -from lexer import * -from token import * +from token import Tag +from scope import Scope + +class ParseError(Exception): + pass class Parser: - def __init__(self, lex): - self.lexer = lex - self.token = lex.scan() - self.count = 1 #debug - return + def __init__(self, lexer): + self.lexer = lexer + self.scope = Scope() + self.move() def parse(self): return self.program() def move(self): - print self.count, self.token #debug - self.count += 1 #debug self.token = self.lexer.scan() - return + #print "move(): %s" % self.token def error(self, msg): - raise Exception(msg) + raise ParseError(msg) - def match(self, tag): + def _match(self, tag): if self.token == None: self.error("Unexpected end of file.") - if self.token.tag != tag: self.error("match: expected %s got %s\n" %(tag, self.token.tag)) val = self.token.value self.move() return val + def match(self, tag, *tags): + for t in (tag,) + tags: + res = self._match(t) + return res + # boolean = join { "||" join }. def boolean(self): res = self.join() @@ -94,8 +98,7 @@ class Parser: # function_call = "call" ident "[" [ expression_list ] "]". def function_call(self): - self.match(Tag.CALL) - name = self.match(Tag.IDENT) + name = self.match(Tag.CALL, Tag.IDENT) self.match(Tag.LBRAK) args = [] if self.token.tag == Tag.RBRAK else self.expression_list() self.match(Tag.RBRAK) @@ -126,23 +129,20 @@ class Parser: # statement_list = statement { statement }. def statement_list(self): - stat = [self.statement()] - while self.token.tag not in [Tag.END, Tag.ELSE]: - stat.append(self.statement()) - return stat + if self.token.tag in [Tag.END, Tag.ELSE]: + return None + return Sequence(self.statement(), self.statement_list(), self.lexer.line) # function = "fun" ident "[" [ ident_list ] "]" nl statement_list "end" nl. def function(self): line = self.lexer.line - self.match(Tag.FUN) - name = self.match(Tag.IDENT) + name = self.match(Tag.FUN, Tag.IDENT) self.match(Tag.LBRAK) args = [] if self.token.tag == Tag.RBRAK else self.ident_list() - self.match(Tag.RBRAK) - self.match(Tag.NEWLINE) + self.match(Tag.RBRAK, Tag.NEWLINE) + self.scope.new(name, args) block = self.statement_list() - self.match(Tag.END) - self.match(Tag.NEWLINE) + self.match(Tag.END, Tag.NEWLINE) return Function(name, args, block, line) # statement = [ if_statement | while_statement | assign_statement | return_statement | function_call ]. @@ -161,13 +161,12 @@ class Parser: condition = self.boolean() self.match(Tag.NEWLINE) true_case = self.statement_list() - else_case = [] + else_case = None if self.token.tag == Tag.ELSE: self.move() self.match(Tag.NEWLINE) else_case = self.statement_list() - self.match(Tag.END) - self.match(Tag.NEWLINE) + self.match(Tag.END, Tag.NEWLINE) return IfStatement(condition, true_case, else_case, line) # while_statement = "while" boolean nl statement_list "end" nl. @@ -177,8 +176,7 @@ class Parser: condition = self.boolean() self.match(Tag.NEWLINE) body = self.statement_list() - self.match(Tag.END) - self.match(Tag.NEWLINE) + self.match(Tag.END, Tag.NEWLINE) return WhileStatement(condition, body, line) # return_statement = "@" boolean nl. @@ -196,6 +194,7 @@ class Parser: self.match(Tag.ASSIGNMENT) exp = self.boolean() self.match(Tag.NEWLINE) + self.scope.add(name) return AssignStatement(name, exp, line) # program = function_list. diff --git a/src/front/scope.py b/src/front/scope.py index 0df8729..a15ed1d 100644 --- a/src/front/scope.py +++ b/src/front/scope.py @@ -1,6 +1,24 @@ class Scope(object): __shared_state = {} - functions = {} + __current_function = None + __functions = {} def __init__(self): self.__dict__ = self.__shared_state + + def new(self, name, symbols = []): + if getattr(self.__functions, name, None): + raise ScopeError("multiple definitions of %s" % name) + self.__functions[name] = [] + self.__current_function = name + self.add(symbols) + + def add(self, symbols): + if type(symbols) != type([]): + symbols = [symbols] + for symbol in symbols: + if symbol not in self.__functions[self.__current_function]: + self.__functions[self.__current_function].append(symbol) + + def __str__(self): + return "<Scope: %s>" % str(self.__functions) |