summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/__init__.py24
-rw-r--r--src/front/ast.py282
-rw-r--r--src/front/lexer.py25
-rw-r--r--src/front/parser.py59
-rw-r--r--src/front/scope.py20
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)