diff --git a/Makefile b/Makefile index d803a96..b1db5a5 100755 --- a/Makefile +++ b/Makefile @@ -14,21 +14,33 @@ # Variables # Groupe -GROUP_NUMBER = 39 # remplacez ceci par votre numéro de groupe # +GROUP_NUMBER = 39 # remplacez ceci par votre numéro de groupe # GROUP = $(GROUP_NUMBER:%=compil%) -COMPILER_MAIN = zweic.AnalyzerTest +COMPILER_MAIN = zweic.GeneratorTest EXAMPLES_DIR = $(ROOT)/examples -TESTS_DIR = $(ROOT)/tests/4 +TESTS_DIR = $(ROOT)/tests/5 TO_ADDRESS = compilation@lampsun1.epfl.ch # Global ROOT = . +TARGETS += $(JC_TARGET) TARGETS += $(SC_TARGET) +SOURCES += $(JC_SOURCES) SOURCES += $(SC_SOURCES) OBJECTS += $(SC_OUTPUTDIR) +# Compilation Java +JC_COMMAND = javac +JC_FLAGS = -g -deprecation -source 1.4 +JC_OUTPUTDIR = $(ROOT)/classes +JC_CLASSPATH = $(JC_OUTPUTDIR) +JC_TARGET = .latest-jc + +JC_FILES += RISC +JC_SOURCES += $(JC_FILES:%=sources/zweic/%.java) + # Compilation Scala SC_COMMAND = scalac SC_FLAGS = @@ -52,6 +64,9 @@ SC_FILES += Type SC_FILES += Analyzer SC_FILES += AnalyzerTest +SC_FILES += Code +SC_FILES += Generator +SC_FILES += GeneratorTest SC_SOURCES += $(SC_FILES:%=sources/zweic/%.scala) # Execution Scala @@ -189,6 +204,14 @@ ############################################################################## # Règles +$(JC_TARGET) : $(JC_SOURCES) + @if [ ! -d $(JC_OUTPUTDIR) ]; then \ + $(call run,$(MKDIR) -p $(JC_OUTPUTDIR)); \ + fi + $(strip $(JC_COMMAND) $(JC_FLAGS) $(JC_OUTPUTDIR:%=-d %) \ + $(JC_CLASSPATH:%=-classpath %) $?) + $(TOUCH) $@ + $(SC_TARGET) : $(SC_SOURCES) @if [ ! -d $(SC_OUTPUTDIR) ]; then \ $(call run,$(MKDIR) -p $(SC_OUTPUTDIR)); \ diff --git a/build.properties b/build.properties index 2a25200..d226cd2 100755 --- a/build.properties +++ b/build.properties @@ -6,7 +6,7 @@ ############################################################################## # The two-digit number for your project group -group.number=39 +group.number= group=compil${group.number} # The mail addresses for submitting the project work @@ -31,7 +31,7 @@ tests5.dir=${basedir}/tests/5 # Default compiler phase -compiler.main=zweic.AnalyzerTest +compiler.main=zweic.GeneratorTest # List of ignored source files exclude.files= @@ -40,4 +40,4 @@ test.file=Factorial.zwei # Default test suite for task "tests" -tests.suite=tests4 +tests.suite=tests5 diff --git a/build.xml b/build.xml index fc0a33d..a8828fe 100755 --- a/build.xml +++ b/build.xml @@ -94,8 +94,7 @@ + includes="**/*.scala"/> diff --git a/script.sh b/script.sh index e3fd1df..e593d4d 100755 --- a/script.sh +++ b/script.sh @@ -685,3 +685,13 @@ $SEPARATOR +file="tests/4/paramredef.zwei" + +echo "Testing file $file : + Errors in file : * parameter defined twice +" + +$COMMAND $file + +$SEPARATOR + diff --git a/sources/zweic/Code.scala b/sources/zweic/Code.scala new file mode 100644 index 0000000..e74063c --- /dev/null +++ b/sources/zweic/Code.scala @@ -0,0 +1,210 @@ +/* zweic -- a compiler for zwei + * + * Stephane Micheloud & LAMP + * + * $Id$ + */ + +package zweic; + +import java.io.PrintWriter; + +class Code { + import RISC._; + + //######################################################################## + // Constants + + /** Index of first general-use register. */ + private val RC_MIN = 1; + /** Index of last general-use register. */ + private val RC_MAX = 29; + + //######################################################################## + // Instance variables + + /** Free registers */ + private val freeRegisters = new Array[Boolean](32); + + /** Already emitted instructions */ + private var code = List[Instruction](); + + /** Stack frame size */ + private var frameSize = 0; + + //######################################################################## + // Initialization + + Iterator.range(RC_MIN, RC_MAX+1) foreach { r => freeRegisters(r) = true }; + + //######################################################################## + // Methods - register allocation + + /** Allocate a register. */ + def getRegister(): Int = + Iterator.range(RC_MIN, RC_MAX+1) find { r => freeRegisters(r) } match { + case Some(r) => getRegister(r) + case None => throw new Error("no more free registers") + } + + /** + * Allocate the given register, which has to be free (otherwise an + * exception is thrown). + */ + def getRegister(r: Int): Int = { + if (! freeRegisters(r)) + throw new Error("attempt to allocate non-free register R" + r); + freeRegisters(r) = false; + r + } + + /** Free a register. */ + def freeRegister(r: Int): Unit = { + if (freeRegisters(r)) + throw new Error("attempt to free already-free register R" + r); + if (r < RC_MIN || r > RC_MAX) + throw new Error("attempt to free special register R" + r); + freeRegisters(r) = true + } + + /** + * Return the set of used registers as an array. If element at + * index I is true, this means that register R[i] is in use. + */ + def usedRegisters(): Array[Boolean] = { + val used = new Array[Boolean](freeRegisters.length); + for (val i <- Iterator.range(0, used.length)) + used(i) = (i >= RC_MIN) && (i <= RC_MAX) && !freeRegisters(i); + used + } + + //######################################################################## + // Methods - address handling + + /** Return address of next instruction. */ + def pc(): Int = WORD_SIZE * code.length; + + //######################################################################## + // Methods - frame handling + + /** Increment frame size by given value. */ + def incFrameSize(bytes: Int) = + frameSize = frameSize + bytes; + + /** Decrement frame size by given value. */ + def decFrameSize(bytes: Int): Unit = { + frameSize = frameSize - bytes; + assert(frameSize >= 0); + } + + /** Return current frame size. */ + def getFrameSize(): Int = frameSize; + + //######################################################################## + // Methods - code emitting + + def emit(opcode: Int): Unit = + emit(opcode, Integer.MIN_VALUE); + + def emit(opcode: Int, c: Int): Unit = + emit(opcode, Integer.MIN_VALUE, c); + + def emit(opcode: Int, c: Int, s: String): Unit = + emit(opcode, Integer.MIN_VALUE, Integer.MIN_VALUE, c, s); + + def emit(opcode: Int, l: Label): Unit = + emit(opcode, Integer.MIN_VALUE, l); + + def emit(opcode: Int, a: Int, c: Int): Unit = + emit(opcode, a, Integer.MIN_VALUE, c); + + def emit(opcode: Int, a: Int, l: Label): Unit = + if (l.isAnchored()) + emit(opcode, a, (l.getAnchor() - pc()) / WORD_SIZE); + else { + l.recordInstructionToPatch(pc()); + emit(opcode, a, Integer.MIN_VALUE, Integer.MIN_VALUE); + }; + + private def syscall2string(c: Int): String = c match { + case SYS_IO_RD_CHR => "SYS_IO_RD_CHR" + case SYS_IO_RD_INT => "SYS_IO_RD_INT" + case SYS_IO_WR_CHR => "SYS_IO_WR_CHR" + case SYS_IO_WR_INT => "SYS_IO_WR_INT" + case SYS_GC_INIT => "SYS_GC_INIT" + case SYS_GC_ALLOC => "SYS_GC_ALLOC" + case SYS_GET_TOTAL_MEM_SIZE => "SYS_GET_TOTAL_MEM_SIZE" + case SYS_EXIT => "SYS_EXIT" + case _ => Integer.toString(c) + }; + + def emit(opcode: Int, a: Int, b: Int, c: Int): Unit = { + val s = if (opcode == SYSCALL) syscall2string(c) else null; + emit(opcode, a, b, c, s) + } + + def emit(opcode: Int, a: Int, b: Int, c: Int, s: String): Unit = + code = new Instruction(opcode, a, b, c, s) :: code; + + //######################################################################## + // Methods - program printing. + + /** Print program. */ + def write(out: PrintWriter): Unit = { + val n = code.length; + var i:Int = 0; + while(i < n) { + var label = Integer.toString(WORD_SIZE * i); + while (label.length() < 4) label = '0' + label; + out.print("/* " + label + " */ "); + out.print(code(n - i - 1)); + out.println(); + i=i+1; + } + out.flush() + } + + //######################################################################## + // Labels + + def getLabel(): Label = new Label(); + + def anchorLabel(l: Label): Unit = l.setAnchor(pc()); + + class Label { + private var toPatch = List[Int](); + private var pc = -1; + + def setAnchor(pc: Int): Unit = { + this.pc = pc; + toPatch foreach { instrPC => + code((pc - instrPC) / WORD_SIZE - 1).c = (pc - instrPC) / WORD_SIZE; } + } + def getAnchor(): Int = pc; + def isAnchored(): Boolean = pc >= 0; + def recordInstructionToPatch(pc: Int): Unit = + toPatch = pc :: toPatch; + } + + //######################################################################## + // Instructions + + private case class Instruction(opcode: Int, a: Int, b: Int, _c: Int, s: String) { + var c = _c; + override def toString(): String = { + val buffer = new StringBuffer(); + buffer.append(mnemonics(opcode)); + if (a != Integer.MIN_VALUE) buffer.append(' ').append(a); + if (b != Integer.MIN_VALUE) buffer.append(' ').append(b); + if (c != Integer.MIN_VALUE) buffer.append(' ').append(c); + if (s != null) { + var i = buffer.length(); + while (i < 17) { buffer.append(' '); i = i + 1; } + buffer.append("/* ").append(s).append(" */"); + } + buffer.toString() + } + } + + //######################################################################## +} diff --git a/sources/zweic/Generator.scala b/sources/zweic/Generator.scala new file mode 100644 index 0000000..59d0a81 --- /dev/null +++ b/sources/zweic/Generator.scala @@ -0,0 +1,206 @@ +/* zweic -- a compiler for zwei + * + * Stephane Micheloud & LAMP + * + * $Id$ + */ + +package zweic; +import Operators._; + +class Generator(analyzer: Analyzer) { + import RISC._; + import scala.collection.mutable.{Map, HashMap}; + + val code = new Code(); + + private def genTmp(gen: Int => Unit) = { + val tmpReg = code.getRegister(); + gen(tmpReg); + code.freeRegister(tmpReg); + } + + def emitLoadConstant(r: Int, value: Int) = { + code.emit(ADDI, r, ZERO, value, value.toString()); + //TODO: immediats bigger than 2^16 have to be shifted + } + + def gen(tree: Tree): Unit = tree match { + case Program(classes, main) => + val init = code.getLabel(); + code.emit(BEQ,ZERO,init); + + // go initialize the VMTs + // ... � compl�ter ... + + // generate class and function definitions + // ... � compl�ter ... + + // generate main expression + val start = code.getLabel(); + code.anchorLabel(start); + genTmp { tmpReg => genLoad(main, tmpReg) } + + // exit + code.emit(RET, ZERO); + + // the following code is placed here because the space that + // it occupies can be used after initialization. + + code.anchorLabel(init); + // initialise stack pointer + code.emit(SYSCALL, SP, 0, SYS_GET_TOTAL_MEM_SIZE); + // initialise garbage collector: + // the heap starts at init and + // its size is 2/3 * (total_mem_size - init) words + val r1 = code.getRegister(); + val r2 = code.getRegister(); + val r3 = code.getRegister(); + emitLoadConstant(r1,init.getAnchor()); + code.emit(SUB,r2,SP,r1); + code.emit(DIVIU,r2,r2,3*WORD_SIZE); + code.emit(LSHI,r2,r2,1); // r2 now contains the size of the heap + emitLoadConstant(r3,SP << 27); + code.emit(ADD, r2, r2, r3); + code.emit(SYSCALL, r1, r2, SYS_GC_INIT); + code.freeRegister(r3); + code.freeRegister(r2); + code.freeRegister(r1); + + // populate VMTs + // ... � compl�ter ... + + // jump to main expression + code.emit(BEQ, ZERO, start); + + case ClassDef(_, _, members) => + // ... � compl�ter ... + + //TODO: case FieldDecl(_, _) => ; + case FieldDecl(_) => ; + + case method @ MethodDef(name, params, _, body) => + // ... � compl�ter ... + + case While(cond, stats) => + // ... � compl�ter ... + + case Var(varname, _, init) => + // ... � compl�ter ... + + case Set(name, expr) => + // ... � compl�ter ... + + case Do(expr) => + Console.println("DO"); + genTmp { tempReg => + genLoad(tree.asInstanceOf[Expr], tempReg) + } + + case PrintInt(expr) => + genTmp { tmpReg => + genLoad(expr, tmpReg); + code.emit(SYSCALL, tmpReg, ZERO, SYS_IO_WR_INT, "printInt"); + code.emit(SYSCALL, ZERO, ZERO, SYS_IO_FLUSH, "flush"); + } + + case PrintChar(expr) => + genTmp { tempReg => + genLoad(expr, tempReg); + code.emit(SYSCALL, tempReg, ZERO, SYS_IO_WR_CHR, "printChar"); + // TODO: do we flush all day long? + code.emit(SYSCALL, ZERO, ZERO, SYS_IO_FLUSH, "flush"); + } + + case _ => + Console.println("gen __________________________________"); + + } // def gen(Tree): Unit + + def genLoad(tree: Expr, targetReg: Int): Unit = { + def caseDefault(tree: Expr): Unit = genLoad( + new If(tree, new IntLit(1), new IntLit(0)), + targetReg); + + assert(code.usedRegisters()(targetReg), + "invariant violated: target register R" + + targetReg + " not allocated"); + + tree match { + case NullLit() => + // ... � compl�ter ... + + case IntLit(value) => + emitLoadConstant(targetReg, value) + + case ReadInt() => + code.emit(SYSCALL, targetReg, ZERO, SYS_IO_RD_INT, "readInt") + + case ReadChar() => + code.emit(SYSCALL, targetReg, ZERO, SYS_IO_RD_CHR, "readChar") + + case Unop(op, expr) => + op match { + case NOT => + //TODO + + case NEG => + genTmp { tmpReg => + genLoad(expr, tmpReg); + code.emit(SUB, targetReg, ZERO, tmpReg, "-"); + } + + case _ => + Console.println("unop _________"); + } + + case Binop(op, left, right) => + // ... � compl�ter ... + + case Block(stats, main) => + // ... � compl�ter ... + + case If(cond, thenp, elsep) => + // ... � compl�ter ... + + case Ident(name) => + // ... � compl�ter ... + + case New(name, args) => + // ... � compl�ter ... + + case Select(prefix, selector) => + // ... � compl�ter ... + + case Call(receiver, method, args) => + // ... � compl�ter ... + + case _ => + Console.println("LoadGen________________"); + // ... � compl�ter ... + } + } // genLoad + + + + /** + * Generates code for conditions, that is constructs + * which jump somewhere on the result of a test. + */ + private def genCond(tree: Expr, targetLabel: code.Label, when: Boolean): Unit = { + // ... � compl�ter ... + tree match { + case Binop(op, left, right) => ()//op match { + // ... � compl�ter ... + + case Unop(op, expr) => () + // ... � compl�ter ... + + case _ => () + //TODO: caseDefault(tree) + + } + } // genCond + + +} diff --git a/sources/zweic/GeneratorTest.scala b/sources/zweic/GeneratorTest.scala new file mode 100644 index 0000000..6d4ff80 --- /dev/null +++ b/sources/zweic/GeneratorTest.scala @@ -0,0 +1,47 @@ +/* zweic -- a compiler for Zwei + * + * Stephane Micheloud & LAMP + * + * $Id$ + */ + +package zweic; + +/** + * usage: scala zweic.GeneratorTest [ ] + */ +object GeneratorTest { + import java.io._; + + def main(args: Array[String]) = { + if (args.length == 0) { + Console.println("usage: scala zweic.GeneratorTest [ ]"); + System.exit(1) + } + try { + val in = new FileInputStream(args(0)); + val tree = new Parser(in).parse; + in.close(); + if (Report.errors > 0) + System.err.println(Report.errors + " errors found."); + else { + val analyzer = new Analyzer(); + analyzer.analyzeProgram(tree); + if (Report.errors > 0) + System.err.println(Report.errors + " errors found."); + else { + val out = if (args.length < 2) new PrintWriter(System.out) + else new PrintWriter(new FileWriter(args(1))); + val generator = new Generator(analyzer); + generator.gen(tree); + generator.code.write(out) + } + } + System.exit(if (Report.errors > 0) 1 else 0) + } + catch { + case e: IOException => Report.fail(e.getMessage()); + } + } + +} diff --git a/sources/zweic/Parser-partial.scala b/sources/zweic/Parser-partial.scala new file mode 100644 index 0000000..f5ec5f4 --- /dev/null +++ b/sources/zweic/Parser-partial.scala @@ -0,0 +1,75 @@ +/* zweic -- a compiler for Zwei + * + * Stephane Micheloud & LAMP + * + * $Id$ + */ + +package zweic; + + +/** + * This class implements the parser of the zwei compiler. + */ +class Parser(in: java.io.InputStream) extends Scanner(in) { + import Tokens._; + + /** + * Reports an error that a specific token was expected but + * a different token found. + */ + private def error(expected: Token): Unit = + error("token of class " + expected); + + + /** + * Reports an error that a specific token was expected but + * a different token found. + */ + private def error(expected: String): Unit = { + val message = "syntax error\n" + + "expected: " + expected + "\n" + + "found : " + representation; + Report.fail(start, message); + } + + /** + * If the current token corresponds to the token class 'expected' + * then skip it, otherwise signal an error. + */ + private def accept(expected: Token): Unit = + if (token == expected) + nextToken; + else + error(expected); + + /** + * If the current token corresponds to the token class 'expected' + * then skip it and return success. + */ + private def check(expected: Token): Boolean = + if (token == expected) { + nextToken; + true + } else + false; + + + /** + * Parse the input and return an abstract syntax tree. + */ + def parse: Program = { + val result = program; + accept(EOF); + result + } + + /** + * Program = { ClassDecl } Expression + */ + private def program: Program = { + // ... � compl�ter ... + } + + // ... � compl�ter ... +} diff --git a/sources/zweic/Printer-partial.scala b/sources/zweic/Printer-partial.scala new file mode 100644 index 0000000..4fad2d0 --- /dev/null +++ b/sources/zweic/Printer-partial.scala @@ -0,0 +1,98 @@ +/* zweic -- a compiler for Zwei + * + * Stephane Micheloud & LAMP + * + * $Id$ + */ + +package zweic; + +import java.io.PrintWriter; + + +/** + * This class implements a pretty printer for abstract syntax + * trees in Zwei. + */ +class Printer(out: PrintWriter) { + import Operators._; + + /** + * Indentation string. + */ + private val step = " "; + + /** + * indentation level. + */ + private var level = 0; + + /** + * Prints a tree node. + */ + def print(tree: Tree): Printer = tree match { + case Program(decls, main) => + for (val d <- decls) + print(d).println; + print(main).println + // ... � compl�ter ... + case Select(prefix, selector) => + print(prefix).print(".").print(selector) + } + + /** + * Print abstract syntax trees separated by commas. + */ + private def print(trees: List[Tree]): Printer = trees match { + // ... � compl�ter ... + case _ => this + } + + /** + * Print a string. + */ + private def print(value: String): Printer = { + out.print(value); + this + } + + private def print(name: Name): Printer = print(name.name); + + private def print(formal: Pair[Name, TypeTree]): Printer = + print(formal._2).print(" ").print(formal._1); + + /** + * Print abstract syntax trees separated by commas. + */ + private def printFormals(formals: List[Pair[Name, TypeTree]]): Printer = + formals match { + // ... � compl�ter ... + case _ => this + } + + /** + * Print an end-of-line character and indent the following + * line appropriately. + */ + private def println = { + out.println(); + for (val i <- List.range(0, level)) out.print(step); + this + } + + /** + * Increment the indentation level. + */ + private def indent = { + level = level + 1; + this + } + + /** + * Decrement the indentation level. + */ + private def undent = { + level = level - 1; + this + } +} diff --git a/sources/zweic/Report.scala b/sources/zweic/Report.scala index ce4f05b..895769d 100755 --- a/sources/zweic/Report.scala +++ b/sources/zweic/Report.scala @@ -45,7 +45,7 @@ } /** Imprime la position et le message passés en argument. */ - def print(pos: Int, message: String): Unit = + private def print(pos: Int, message: String): Unit = System.err.println(Position.toString(pos) + ": " + message); } diff --git a/sources/zweic/Symbol.scala b/sources/zweic/Symbol.scala index 7798372..796dd95 100755 --- a/sources/zweic/Symbol.scala +++ b/sources/zweic/Symbol.scala @@ -77,7 +77,7 @@ def allMethods: List[MethodSymbol] = methods.values.toList; - + override def toString() = "class " + name; }