diff options
42 files changed, 1057 insertions, 532 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..3df94c1 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +**/*.asm +classes diff --git a/.vscode/launch.json b/.vscode/launch.json deleted file mode 100644 index 8fbb478..0000000 --- a/.vscode/launch.json +++ /dev/null @@ -1,28 +0,0 @@ -{ - // Use IntelliSense to learn about possible attributes. - // Hover to view descriptions of existing attributes. - // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387 - "version": "0.2.0", - "configurations": [ - { - "type": "java", - "name": "Main", - "request": "launch", - "mainClass": "main.Main", - "projectName": "p5-compiler_25e45799" - }, - { - "type": "java", - "name": "Main", - "request": "launch", - "mainClass": "Main", - "projectName": "p5-compiler_25e45799" - }, - { - "type": "java", - "name": "Current File", - "request": "launch", - "mainClass": "${file}" - } - ] -} diff --git a/.vscode/settings.json b/.vscode/settings.json deleted file mode 100644 index 0687886..0000000 --- a/.vscode/settings.json +++ /dev/null @@ -1,8 +0,0 @@ -{ - "java.project.referencedLibraries": [ - "lib/**/*.jar", - "antlr-4.9.1-complete.jar" - ], - "rpc.enabled": false, - "java.debug.settings.onBuildFailureProceed": true -} diff --git a/data/test1.asm b/data/test1.asm deleted file mode 100644 index 6c203dc..0000000 --- a/data/test1.asm +++ /dev/null @@ -1,13 +0,0 @@ -# All program code is placed after the -# .text assembler directive -.text - -# Declare main as a global function -.globl main - -j main - -# All memory structures are placed after the -# .data assembler directive -.data - diff --git a/data/test1.c b/data/test1.c index e336f81..68ff11e 100644 --- a/data/test1.c +++ b/data/test1.c @@ -1,3 +1,5 @@ -void main() { +void main() +{ println("Hello world"); + println(7 % 3, "hi"); } diff --git a/data/test10.c b/data/test10.c index a90a21f..af8599d 100644 --- a/data/test10.c +++ b/data/test10.c @@ -1,20 +1,22 @@ int fib(int i) { - if (i == 0) return 1; - if (i == 1) return 1; - return fib(i-1) + fib(i-2); + if (i == 0) + return 1; + if (i == 1) + return 1; + return fib(i - 1) + fib(i - 2); } void main() { println("This program prints the first 11 numbers of the Fibonacci sequence"); - println(fib(0)); // 1 - println(fib(1)); // 1 - println(fib(2)); // 2 - println(fib(3)); // 3 - println(fib(4)); // 5 - println(fib(5)); // 8 - println(fib(6)); // 13 - println(fib(7)); // 21 - println(fib(8)); // 34 - println(fib(9)); // 55 + println(fib(0)); // 1 + println(fib(1)); // 1 + println(fib(2)); // 2 + println(fib(3)); // 3 + println(fib(4)); // 5 + println(fib(5)); // 8 + println(fib(6)); // 13 + println(fib(7)); // 21 + println(fib(8)); // 34 + println(fib(9)); // 55 println(fib(10)); // 89 } diff --git a/data/test2.c b/data/test2.c index 136ba74..ec9b22a 100644 --- a/data/test2.c +++ b/data/test2.c @@ -1,8 +1,9 @@ -void main() { +void main() +{ println("This program prints 7 7 7 7 7 (separated by newlines)"); println(7); - println(3+4); - println(14/2); - println(7*1); - println((7*2)/2); + println(3 + 4); + println(14 / 2); + println(7 * 1); + println((7 * 2) / 2); } diff --git a/data/test4.c b/data/test4.c index c4c31c2..04c877a 100644 --- a/data/test4.c +++ b/data/test4.c @@ -8,14 +8,14 @@ void main() { { int a; a = 5; - println(a+b); + println(a + b); { - int b; - b = 9; - a = -2; - println(a+b); + int b; + b = 9; + a = -2; + println(a + b); } b = 4; } - println(a+b); + println(a + b); } diff --git a/data/test9.c b/data/test9.c index 1aacb59..c0e348c 100644 --- a/data/test9.c +++ b/data/test9.c @@ -19,7 +19,7 @@ void main() { if (a == 3) { println("4 correct"); } - if (a >= 4) { + if (a != 4) { println("5 not correct"); } else { println("5 correct"); diff --git a/submit/ASTVisitor.java b/submit/ASTVisitor.java index b8762b5..5cafbb1 100644 --- a/submit/ASTVisitor.java +++ b/submit/ASTVisitor.java @@ -1,304 +1,342 @@ package submit; +import java.util.ArrayList; +import java.util.List; +import java.util.logging.Logger; import org.antlr.v4.runtime.tree.ParseTree; import org.antlr.v4.runtime.tree.TerminalNode; import parser.CminusBaseVisitor; import parser.CminusParser; import submit.ast.*; -import java.util.ArrayList; -import java.util.List; -import java.util.logging.Logger; - public class ASTVisitor extends CminusBaseVisitor<Node> { - private final Logger LOGGER; - private SymbolTable symbolTable; - - public ASTVisitor(Logger LOGGER) { - this.LOGGER = LOGGER; - } - - public SymbolTable getSymbolTable() { - return symbolTable; - } - - private VarType getVarType(CminusParser.TypeSpecifierContext ctx) { - final String t = ctx.getText(); - return (t.equals("int")) ? VarType.INT : (t.equals("bool")) ? VarType.BOOL : VarType.CHAR; - } - - @Override - public Node visitProgram(CminusParser.ProgramContext ctx) { - symbolTable = new SymbolTable(); - List<Declaration> decls = new ArrayList<>(); - for (CminusParser.DeclarationContext d : ctx.declaration()) { - decls.add((Declaration) visitDeclaration(d)); - } - return new Program(decls); - } - - @Override - public Node visitVarDeclaration(CminusParser.VarDeclarationContext ctx) { - VarType type = getVarType(ctx.typeSpecifier()); - List<String> ids = new ArrayList<>(); - List<Integer> arraySizes = new ArrayList<>(); - for (CminusParser.VarDeclIdContext v : ctx.varDeclId()) { - String id = v.ID().getText(); - ids.add(id); - symbolTable.addSymbol(id, new SymbolInfo(id, type, false)); - if (v.NUMCONST() != null) { - arraySizes.add(Integer.parseInt(v.NUMCONST().getText())); - } else { - arraySizes.add(-1); - } - } - final boolean isStatic = false; - return new VarDeclaration(type, ids, arraySizes, isStatic); - } - - @Override - public Node visitFunDeclaration(CminusParser.FunDeclarationContext ctx) { - VarType returnType = null; - if (ctx.typeSpecifier() != null) { - returnType = getVarType(ctx.typeSpecifier()); - } - String id = ctx.ID().getText(); - List<Param> params = new ArrayList<>(); - for (CminusParser.ParamContext p : ctx.param()) { - params.add((Param) visitParam(p)); - } - Statement statement = (Statement) visitStatement(ctx.statement()); - symbolTable.addSymbol(id, new SymbolInfo(id, returnType, true)); - return new FunDeclaration(returnType, id, params, statement); - } - - @Override - public Node visitParam(CminusParser.ParamContext ctx) { - VarType type = getVarType(ctx.typeSpecifier()); - String id = ctx.paramId().ID().getText(); - symbolTable.addSymbol(id, new SymbolInfo(id, type, false)); - return new Param(type, id, ctx.paramId().children.size() > 1); - } - - @Override - public Node visitCompoundStmt(CminusParser.CompoundStmtContext ctx) { - symbolTable = symbolTable.createChild(); - List<Statement> statements = new ArrayList<>(); - for (CminusParser.VarDeclarationContext d : ctx.varDeclaration()) { - statements.add((VarDeclaration) visitVarDeclaration(d)); - } - for (CminusParser.StatementContext d : ctx.statement()) { - statements.add((Statement) visitStatement(d)); - } - symbolTable = symbolTable.getParent(); - return new CompoundStatement(statements); - } - - @Override - public Node visitExpressionStmt(CminusParser.ExpressionStmtContext ctx) { - if (ctx.expression() == null) { - return Statement.empty(); - } - return new ExpressionStatement((Expression) visitExpression(ctx.expression())); - } - - @Override - public Node visitIfStmt(CminusParser.IfStmtContext ctx) { - Expression expression = (Expression) visitSimpleExpression(ctx.simpleExpression()); - Statement trueStatement = (Statement) visitStatement(ctx.statement(0)); - Statement falseStatement = null; - if (ctx.statement().size() > 1) { - falseStatement = (Statement) visitStatement(ctx.statement(1)); - } - return new If(expression, trueStatement, falseStatement); - } - - @Override - public Node visitWhileStmt(CminusParser.WhileStmtContext ctx) { - Expression expression = (Expression) visitSimpleExpression(ctx.simpleExpression()); - Statement statement = (Statement) visitStatement(ctx.statement()); - return new While(expression, statement); - } - - @Override - public Node visitReturnStmt(CminusParser.ReturnStmtContext ctx) { - if (ctx.expression() != null) { - return new Return((Expression) visitExpression(ctx.expression())); - } - return new Return(null); - } - - @Override - public Node visitBreakStmt(CminusParser.BreakStmtContext ctx) { - return new Break(); - } - - @Override - public Node visitExpression(CminusParser.ExpressionContext ctx) { - final Node ret; - CminusParser.MutableContext mutable = ctx.mutable(); - CminusParser.ExpressionContext expression = ctx.expression(); - if (mutable != null) { - // Assignment - ParseTree operator = ctx.getChild(1); - Mutable lhs = (Mutable) visitMutable(mutable);// new Mutable(mutable.ID().getText(), (Expression) - // visitExpression(mutable.expression())); - Expression rhs = null; - if (expression != null) { - rhs = (Expression) visitExpression(expression); - } - ret = new Assignment(lhs, operator.getText(), rhs); - } else { - ret = visitSimpleExpression(ctx.simpleExpression()); - } - return ret; - } - - @Override - public Node visitOrExpression(CminusParser.OrExpressionContext ctx) { - List<Node> ands = new ArrayList<>(); - for (CminusParser.AndExpressionContext and : ctx.andExpression()) { - ands.add(visitAndExpression(and)); - } - if (ands.size() == 1) { - return ands.get(0); - } - BinaryOperator op = new BinaryOperator((Expression) ands.get(0), "||", (Expression) ands.get(1)); - for (int i = 2; i < ands.size(); ++i) { - op = new BinaryOperator(op, "||", (Expression) ands.get(i)); - } - return op; - } - - @Override - public Node visitAndExpression(CminusParser.AndExpressionContext ctx) { - List<Node> uns = new ArrayList<>(); - for (CminusParser.UnaryRelExpressionContext un : ctx.unaryRelExpression()) { - uns.add(visitUnaryRelExpression(un)); - } - if (uns.size() == 1) { - return uns.get(0); - } - BinaryOperator op = new BinaryOperator((Expression) uns.get(0), "&&", (Expression) uns.get(1)); - for (int i = 2; i < uns.size(); ++i) { - op = new BinaryOperator(op, "&&", (Expression) uns.get(i)); - } - return op; - } - - @Override - public Node visitUnaryRelExpression(CminusParser.UnaryRelExpressionContext ctx) { - Expression e = (Expression) visitRelExpression(ctx.relExpression()); - for (TerminalNode n : ctx.BANG()) { - e = new UnaryOperator("!", e); - } - return e; - } - - @Override - public Node visitRelExpression(CminusParser.RelExpressionContext ctx) { - List<Node> uns = new ArrayList<>(); - for (CminusParser.SumExpressionContext un : ctx.sumExpression()) { - uns.add(visitSumExpression(un)); - } - if (uns.size() == 1) { - return uns.get(0); - } - BinaryOperator op = new BinaryOperator((Expression) uns.get(0), ctx.relop(0).getText(), - (Expression) uns.get(1)); - for (int i = 2; i < uns.size(); ++i) { - op = new BinaryOperator(op, ctx.relop(i - 1).getText(), (Expression) uns.get(i)); - } - return op; - } - - @Override - public Node visitSumExpression(CminusParser.SumExpressionContext ctx) { - List<Node> es = new ArrayList<>(); - for (CminusParser.TermExpressionContext e : ctx.termExpression()) { - es.add(visitTermExpression(e)); - } - if (es.size() == 1) { - return es.get(0); - } - BinaryOperator op = new BinaryOperator((Expression) es.get(0), ctx.sumop(0).getText(), (Expression) es.get(1)); - for (int i = 2; i < es.size(); ++i) { - op = new BinaryOperator(op, ctx.sumop(i - 1).getText(), (Expression) es.get(i)); - } - return op; - } - - @Override - public Node visitTermExpression(CminusParser.TermExpressionContext ctx) { - List<Node> es = new ArrayList<>(); - for (CminusParser.UnaryExpressionContext e : ctx.unaryExpression()) { - es.add(visitUnaryExpression(e)); - } - if (es.size() == 1) { - return es.get(0); - } - BinaryOperator op = new BinaryOperator((Expression) es.get(0), ctx.mulop(0).getText(), (Expression) es.get(1)); - for (int i = 2; i < es.size(); ++i) { - op = new BinaryOperator(op, ctx.mulop(i - 1).getText(), (Expression) es.get(i)); - } - return op; - } - - @Override - public Node visitUnaryExpression(CminusParser.UnaryExpressionContext ctx) { - Node ret = visitFactor(ctx.factor()); - for (int i = ctx.unaryop().size() - 1; i >= 0; i--) { - ret = new UnaryOperator(ctx.unaryop(i).getText(), (Expression) ret); - } - return ret; - } - - @Override - public Node visitMutable(CminusParser.MutableContext ctx) { - Expression e = null; - if (ctx.expression() != null) { - e = (Expression) visitExpression(ctx.expression()); - } - String id = ctx.ID().getText(); - if (symbolTable.find(id) == null) { - LOGGER.warning("Undefined symbol on line " + ctx.getStart().getLine() + ": " + id); - } - return new Mutable(id, e); - } - - @Override - public Node visitImmutable(CminusParser.ImmutableContext ctx) { - if (ctx.expression() != null) { - return new ParenExpression((Expression) visitExpression(ctx.expression())); - } - return visitChildren(ctx); - } - - @Override - public Node visitCall(CminusParser.CallContext ctx) { - final String id = ctx.ID().getText(); - final List<Expression> args = new ArrayList<>(); - for (CminusParser.ExpressionContext e : ctx.expression()) { - args.add((Expression) visitExpression(e)); - } - if (symbolTable.find(id) == null) { - LOGGER.warning("Undefined symbol on line " + ctx.getStart().getLine() + ": " + id); - } - return new Call(id, args); - } - - @Override - public Node visitConstant(CminusParser.ConstantContext ctx) { - final Node node; - if (ctx.NUMCONST() != null) { - node = new NumConstant(Integer.parseInt(ctx.NUMCONST().getText())); - } else if (ctx.CHARCONST() != null) { - node = new CharConstant(ctx.CHARCONST().getText().charAt(0)); - } else if (ctx.STRINGCONST() != null) { - node = new StringConstant(ctx.STRINGCONST().getText()); - } else { - node = new BoolConstant(ctx.getText().equals("true")); - } - return node; + private final Logger LOGGER; + private SymbolTable symbolTable; + + public ASTVisitor(Logger LOGGER) { this.LOGGER = LOGGER; } + + public SymbolTable getSymbolTable() { return symbolTable; } + + private VarType getVarType(CminusParser.TypeSpecifierContext ctx) { + final String t = ctx.getText(); + return (t.equals("int")) ? VarType.INT + : (t.equals("bool")) ? VarType.BOOL + : VarType.CHAR; + } + + @Override + public Node visitProgram(CminusParser.ProgramContext ctx) { + symbolTable = new SymbolTable(); + List<Declaration> decls = new ArrayList<>(); + for (CminusParser.DeclarationContext d : ctx.declaration()) { + decls.add((Declaration)visitDeclaration(d)); + } + return new Program(decls); + } + + @Override + public Node visitVarDeclaration(CminusParser.VarDeclarationContext ctx) { + VarType type = getVarType(ctx.typeSpecifier()); + List<String> ids = new ArrayList<>(); + List<Integer> arraySizes = new ArrayList<>(); + for (CminusParser.VarDeclIdContext v : ctx.varDeclId()) { + String id = v.ID().getText(); + ids.add(id); + // symbolTable.addSymbol(id, new SymbolInfo(id, type, false)); + if (v.NUMCONST() != null) { + arraySizes.add(Integer.parseInt(v.NUMCONST().getText())); + } else { + int offset = symbolTable.addOffset(1); + + SymbolInfo symbol = new SymbolInfo(id, type, false, offset); + symbolTable.addSymbol(id, symbol); + + arraySizes.add(-1); + } + } + final boolean isStatic = false; + return new VarDeclaration(type, ids, arraySizes, isStatic); + } + + @Override + public Node visitFunDeclaration(CminusParser.FunDeclarationContext ctx) { + VarType returnType = null; + if (ctx.typeSpecifier() != null) { + returnType = getVarType(ctx.typeSpecifier()); + } + String id = ctx.ID().getText(); + symbolTable.addSymbol(id, new SymbolInfo(id, returnType, true)); + + List<Param> params = new ArrayList<>(); + + SymbolTable newTable = symbolTable.createChild(); + symbolTable = newTable; + + if (returnType != null) { + symbolTable.addSymbol("return", + new SymbolInfo("return", returnType, false, + symbolTable.addOffset(1))); + } + + for (CminusParser.ParamContext p : ctx.param()) { + params.add((Param)visitParam(p)); + } + + CompoundStatement statement = + (CompoundStatement)visitStatement(ctx.statement()); + + statement.getSymbolTable().addOtherTableBefore(newTable); + symbolTable = newTable.getParent(); + + return new FunDeclaration(returnType, id, params, statement); + } + + @Override + public Node visitParam(CminusParser.ParamContext ctx) { + VarType type = getVarType(ctx.typeSpecifier()); + String id = ctx.paramId().ID().getText(); + symbolTable.addSymbol( + id, new SymbolInfo(id, type, false, symbolTable.addOffset(1))); + + return new Param(type, id, ctx.paramId().children.size() > 1); + } + + @Override + public Node visitCompoundStmt(CminusParser.CompoundStmtContext ctx) { + SymbolTable child = symbolTable.createChild(); + symbolTable = child; + + List<Statement> statements = new ArrayList<>(); + for (CminusParser.VarDeclarationContext d : ctx.varDeclaration()) { + statements.add((VarDeclaration)visitVarDeclaration(d)); + } + for (CminusParser.StatementContext d : ctx.statement()) { + statements.add((Statement)visitStatement(d)); + } + symbolTable = child.getParent(); + + return new CompoundStatement(statements, child); + } + + @Override + public Node visitExpressionStmt(CminusParser.ExpressionStmtContext ctx) { + if (ctx.expression() == null) { + return Statement.empty(); + } + return new ExpressionStatement( + (Expression)visitExpression(ctx.expression())); + } + + @Override + public Node visitIfStmt(CminusParser.IfStmtContext ctx) { + Expression expression = + (Expression)visitSimpleExpression(ctx.simpleExpression()); + Statement trueStatement = (Statement)visitStatement(ctx.statement(0)); + Statement falseStatement = null; + if (ctx.statement().size() > 1) { + falseStatement = (Statement)visitStatement(ctx.statement(1)); + } + return new If(expression, trueStatement, falseStatement); + } + + @Override + public Node visitWhileStmt(CminusParser.WhileStmtContext ctx) { + Expression expression = + (Expression)visitSimpleExpression(ctx.simpleExpression()); + Statement statement = (Statement)visitStatement(ctx.statement()); + return new While(expression, statement); + } + + @Override + public Node visitReturnStmt(CminusParser.ReturnStmtContext ctx) { + if (ctx.expression() != null) { + return new Return((Expression)visitExpression(ctx.expression())); + } + return new Return(null); + } + + @Override + public Node visitBreakStmt(CminusParser.BreakStmtContext ctx) { + return new Break(); + } + + @Override + public Node visitExpression(CminusParser.ExpressionContext ctx) { + final Node ret; + CminusParser.MutableContext mutable = ctx.mutable(); + CminusParser.ExpressionContext expression = ctx.expression(); + if (mutable != null) { + // Assignment + ParseTree operator = ctx.getChild(1); + Mutable lhs = (Mutable)visitMutable( + mutable); // new Mutable(mutable.ID().getText(), (Expression) + // visitExpression(mutable.expression())); + Expression rhs = null; + if (expression != null) { + rhs = (Expression)visitExpression(expression); + } + ret = new Assignment(lhs, operator.getText(), rhs); + } else { + ret = visitSimpleExpression(ctx.simpleExpression()); + } + return ret; + } + + @Override + public Node visitOrExpression(CminusParser.OrExpressionContext ctx) { + List<Node> ands = new ArrayList<>(); + for (CminusParser.AndExpressionContext and : ctx.andExpression()) { + ands.add(visitAndExpression(and)); + } + if (ands.size() == 1) { + return ands.get(0); + } + BinaryOperator op = new BinaryOperator((Expression)ands.get(0), "||", + (Expression)ands.get(1)); + for (int i = 2; i < ands.size(); ++i) { + op = new BinaryOperator(op, "||", (Expression)ands.get(i)); + } + return op; + } + + @Override + public Node visitAndExpression(CminusParser.AndExpressionContext ctx) { + List<Node> uns = new ArrayList<>(); + for (CminusParser.UnaryRelExpressionContext un : ctx.unaryRelExpression()) { + uns.add(visitUnaryRelExpression(un)); + } + if (uns.size() == 1) { + return uns.get(0); + } + BinaryOperator op = new BinaryOperator((Expression)uns.get(0), "&&", + (Expression)uns.get(1)); + for (int i = 2; i < uns.size(); ++i) { + op = new BinaryOperator(op, "&&", (Expression)uns.get(i)); + } + return op; + } + + @Override + public Node + visitUnaryRelExpression(CminusParser.UnaryRelExpressionContext ctx) { + Expression e = (Expression)visitRelExpression(ctx.relExpression()); + for (TerminalNode n : ctx.BANG()) { + e = new UnaryOperator("!", e); + } + return e; + } + + @Override + public Node visitRelExpression(CminusParser.RelExpressionContext ctx) { + List<Node> uns = new ArrayList<>(); + for (CminusParser.SumExpressionContext un : ctx.sumExpression()) { + uns.add(visitSumExpression(un)); + } + if (uns.size() == 1) { + return uns.get(0); + } + BinaryOperator op = new BinaryOperator( + (Expression)uns.get(0), ctx.relop(0).getText(), (Expression)uns.get(1)); + for (int i = 2; i < uns.size(); ++i) { + op = new BinaryOperator(op, ctx.relop(i - 1).getText(), + (Expression)uns.get(i)); + } + return op; + } + + @Override + public Node visitSumExpression(CminusParser.SumExpressionContext ctx) { + List<Node> es = new ArrayList<>(); + for (CminusParser.TermExpressionContext e : ctx.termExpression()) { + es.add(visitTermExpression(e)); + } + if (es.size() == 1) { + return es.get(0); + } + BinaryOperator op = new BinaryOperator( + (Expression)es.get(0), ctx.sumop(0).getText(), (Expression)es.get(1)); + for (int i = 2; i < es.size(); ++i) { + op = new BinaryOperator(op, ctx.sumop(i - 1).getText(), + (Expression)es.get(i)); + } + return op; + } + + @Override + public Node visitTermExpression(CminusParser.TermExpressionContext ctx) { + List<Node> es = new ArrayList<>(); + for (CminusParser.UnaryExpressionContext e : ctx.unaryExpression()) { + es.add(visitUnaryExpression(e)); + } + if (es.size() == 1) { + return es.get(0); + } + BinaryOperator op = new BinaryOperator( + (Expression)es.get(0), ctx.mulop(0).getText(), (Expression)es.get(1)); + for (int i = 2; i < es.size(); ++i) { + op = new BinaryOperator(op, ctx.mulop(i - 1).getText(), + (Expression)es.get(i)); + } + return op; + } + + @Override + public Node visitUnaryExpression(CminusParser.UnaryExpressionContext ctx) { + Node ret = visitFactor(ctx.factor()); + for (int i = ctx.unaryop().size() - 1; i >= 0; i--) { + ret = new UnaryOperator(ctx.unaryop(i).getText(), (Expression)ret); + } + return ret; + } + + @Override + public Node visitMutable(CminusParser.MutableContext ctx) { + Expression e = null; + if (ctx.expression() != null) { + e = (Expression)visitExpression(ctx.expression()); + } + String id = ctx.ID().getText(); + if (symbolTable.find(id) == null) { + LOGGER.warning("Undefined symbol on line " + ctx.getStart().getLine() + + ": " + id); + } + return new Mutable(id, e); + } + + @Override + public Node visitImmutable(CminusParser.ImmutableContext ctx) { + if (ctx.expression() != null) { + return new ParenExpression((Expression)visitExpression(ctx.expression())); + } + return visitChildren(ctx); + } + + @Override + public Node visitCall(CminusParser.CallContext ctx) { + final String id = ctx.ID().getText(); + final List<Expression> args = new ArrayList<>(); + for (CminusParser.ExpressionContext e : ctx.expression()) { + args.add((Expression)visitExpression(e)); + } + if (symbolTable.find(id) == null) { + LOGGER.warning("Undefined symbol on line " + ctx.getStart().getLine() + + ": " + id); + } + return new Call(id, args); + } + + @Override + public Node visitConstant(CminusParser.ConstantContext ctx) { + final Node node; + if (ctx.NUMCONST() != null) { + node = new NumConstant(Integer.parseInt(ctx.NUMCONST().getText())); + } else if (ctx.CHARCONST() != null) { + node = new CharConstant(ctx.CHARCONST().getText().charAt(0)); + } else if (ctx.STRINGCONST() != null) { + node = new StringConstant(ctx.STRINGCONST().getText()); + } else { + node = new BoolConstant(ctx.getText().equals("true")); } + return node; + } } diff --git a/submit/MIPSResult.java b/submit/MIPSResult.java index 212719e..bccfe76 100644 --- a/submit/MIPSResult.java +++ b/submit/MIPSResult.java @@ -57,5 +57,4 @@ public class MIPSResult { public VarType getType() { return type; } - } diff --git a/submit/RegisterAllocator.java b/submit/RegisterAllocator.java index ce18b2b..161435d 100644 --- a/submit/RegisterAllocator.java +++ b/submit/RegisterAllocator.java @@ -15,112 +15,139 @@ import java.util.Set; */ public final class RegisterAllocator { - // True if t is used - private final boolean[] t = new boolean[10]; - private final boolean[] s = new boolean[8]; - private final Set<String> used = new HashSet<>(); + // True if t is used + private final boolean[] t = new boolean[10]; + private final boolean[] s = new boolean[8]; + private final Set<String> used = new HashSet<>(); - public RegisterAllocator() { - clearAll(); - } + public RegisterAllocator() { clearAll(); } - public String getT() { - for (int i = 0; i < t.length; ++i) { - if (!t[i]) { - t[i] = true; - String str = "$t" + i; - used.add(str); - return str; - } - } - return null; + public String getRegisterOrLoadIntoRegister(MIPSResult result, + StringBuilder code) { + if (result.getRegister() != null) { + return result.getRegister(); } + String reg = result.getAddress(); + return this.loadIntoRegister(result, code, reg); + } -// public String getS() { -// for (int i = 0; i < s.length; ++i) { -// if (!s[i]) { -// s[i] = true; -// String str = "$s" + i; -// used.add(str); -// return str; -// } -// } -// return null; -// } - - // Returns the number of bytes used to save the registers - public int saveRestore(StringBuilder code, int baseOffset, boolean s_or_t, boolean save) { - boolean[] r = s; - String prefix = "$s"; - if (!s_or_t) { - r = t; - prefix = "$t"; - } - String instruction = "sw"; - if (!save) { - instruction = "lw"; - } - int offset = 0; - for (int i = 0; i < r.length; ++i) { - if (r[i]) { - offset -= 4; - String str = prefix + i; - code.append(instruction).append(" ").append(str).append(" ").append(offset-baseOffset).append("($sp)\n"); - } - } - return -offset; - } + public String loadIntoRegister(MIPSResult result, StringBuilder code, + String register) { + return loadIntoRegisterWithOffset(result, code, register, 0); + } + + public String loadIntoRegisterWithOffset(MIPSResult result, + StringBuilder code, String register, + int offset) { + code.append( + String.format("lw %s %d(%s)\n", register, offset, result.getAddress())); -// public int saveS(StringBuilder code, int baseOffset) { -// return saveRestore(code, baseOffset, true, true); -// } + return register; + } - public int saveT(StringBuilder code, int baseOffset) { - return saveRestore(code, baseOffset, false, true); + public String getT() { + for (int i = 0; i < t.length; ++i) { + if (!t[i]) { + t[i] = true; + String str = "$t" + i; + used.add(str); + return str; + } } + return null; + } -// public int restoreS(StringBuilder code, int baseOffset) { -// return saveRestore(code, baseOffset, true, false); -// } + // public String getS() { + // for (int i = 0; i < s.length; ++i) { + // if (!s[i]) { + // s[i] = true; + // String str = "$s" + i; + // used.add(str); + // return str; + // } + // } + // return null; + // } - public int restoreT(StringBuilder code, int baseOffset) { - return saveRestore(code, baseOffset, false, false); + // Returns the number of bytes used to save the registers + public int saveRestore(StringBuilder code, int baseOffset, boolean s_or_t, + boolean save) { + boolean[] r = s; + String prefix = "$s"; + if (!s_or_t) { + r = t; + prefix = "$t"; } - - public List<String> getUsed() { - return new ArrayList<>(used); + String instruction = "sw"; + if (!save) { + instruction = "lw"; } - - /** - * Any time you call this method you should seriously consider adding a - * corresponding clear() call. - * - * @return - */ - public String getAny() { -// String availS = getS(); -// if (availS != null) { -// return availS; -// } - String t = getT(); - if (t == null) { - throw new RuntimeException("Out of registers"); - } - return t; + int offset = 0; + for (int i = 0; i < r.length; ++i) { + if (r[i]) { + offset -= 4; + String str = prefix + i; + code.append(instruction) + .append(" ") + .append(str) + .append(" ") + .append(offset - baseOffset) + .append("($sp)\n"); + } } + return -offset; + } + + // public int saveS(StringBuilder code, int baseOffset) { + // return saveRestore(code, baseOffset, true, true); + // } - public void clear(String reg) { - if (reg.charAt(1) == 's') { - s[Integer.parseInt(reg.substring(2))] = false; - } else if (reg.charAt(1) == 't') { - t[Integer.parseInt(reg.substring(2))] = false; - } else { - throw new RuntimeException("Unexpected register in clear"); - } + public int saveT(StringBuilder code, int baseOffset) { + return saveRestore(code, baseOffset, false, true); + } + + // public int restoreS(StringBuilder code, int baseOffset) { + // return saveRestore(code, baseOffset, true, false); + // } + + public int restoreT(StringBuilder code, int baseOffset) { + return saveRestore(code, baseOffset, false, false); + } + + public List<String> getUsed() { return new ArrayList<>(used); } + + /** + * Any time you call this method you should seriously consider adding a + * corresponding clear() call. + * + * @return + */ + public String getAny() { + // String availS = getS(); + // if (availS != null) { + // return availS; + // } + String t = getT(); + if (t == null) { + throw new RuntimeException("Out of registers"); } + return t; + } - public void clearAll() { - Arrays.fill(t, false); - Arrays.fill(s, false); + public void clear(String reg) { + if (reg == null) + return; + if (reg.charAt(1) == 's') { + s[Integer.parseInt(reg.substring(2))] = false; + } else if (reg.charAt(1) == 't') { + t[Integer.parseInt(reg.substring(2))] = false; + } else { + throw new RuntimeException("Unexpected register in clear"); } + } + + public void clearAll() { + Arrays.fill(t, false); + Arrays.fill(s, false); + } } diff --git a/submit/SymbolInfo.java b/submit/SymbolInfo.java index 19c3f9b..c640718 100644 --- a/submit/SymbolInfo.java +++ b/submit/SymbolInfo.java @@ -16,6 +16,7 @@ public class SymbolInfo { // In the case of a function, type is the return type private final VarType type; private final boolean function; + private int offset; public SymbolInfo(String id, VarType type, boolean function) { this.id = id; @@ -23,9 +24,20 @@ public class SymbolInfo { this.function = function; } + public SymbolInfo(String id, VarType type, boolean function, int offset) { + this(id, type, function); + this.offset = offset; + } + @Override public String toString() { return "<" + id + ", " + type + '>'; } + public VarType getType() { return type; } + + public boolean isFunction() { return function; } + + public int getOffset() { return offset; } + public void setOffset(int offset) { this.offset = offset; } } diff --git a/submit/SymbolTable.java b/submit/SymbolTable.java index 7ca6b27..09251bc 100644 --- a/submit/SymbolTable.java +++ b/submit/SymbolTable.java @@ -3,6 +3,7 @@ package submit; import java.util.ArrayList; import java.util.HashMap; import java.util.List; +import submit.ast.VarType; /* * Code formatter project @@ -17,14 +18,71 @@ public class SymbolTable { private SymbolTable parent; private final List<SymbolTable> children; + private int offset; + + public static int LABEL_IDENTIFIER = 0; + + public static String nextId() { + return Integer.toString(SymbolTable.LABEL_IDENTIFIER++); + } + public SymbolTable() { + offset = 0; table = new HashMap<>(); parent = null; children = new ArrayList<>(); + + this.addGlobalSymbols(); + } + + public List<String> symbolNames() { return new ArrayList<>(table.keySet()); } + + public void addGlobalSymbols() { + SymbolInfo println = new SymbolInfo("println", null, true); + this.addSymbol("println", println); + } + + public void addSymbol(String id, SymbolInfo symbol) { table.put(id, symbol); } + + public int addOffset(int n) { + offset -= 4 * n; + return offset; + } + + public int getOffset() { return this.offset; } + + // Add symbols in before and reorder offsets such that symbols in before have + // a "higher" offset + public void addOtherTableBefore(SymbolTable before) { + offset = 0; + List<String> thisSymbols = symbolNames(); + + for (String id : before.symbolNames()) { + SymbolInfo symbol = before.find(id); + if (!symbol.isFunction()) { + addOffset(1); + symbol.setOffset(offset); + } + addSymbol(id, symbol); + } + + for (String id : thisSymbols) { + SymbolInfo symbol = table.get(id); + if (!symbol.isFunction()) { + addOffset(1); + table.get(id).setOffset(offset); + } + } } - public void addSymbol(String id, SymbolInfo symbol) { - table.put(id, symbol); + public int offsetOf(String id) { + if (table.containsKey(id)) { + return table.get(id).getOffset(); + } + if (parent != null) { + return -parent.getOffset() + parent.offsetOf(id); + } + return 0; // This shouldn't happen :D } /** @@ -56,8 +114,5 @@ public class SymbolTable { return child; } - public SymbolTable getParent() { - return parent; - } - + public SymbolTable getParent() { return parent; } } diff --git a/submit/ast/AbstractNode.java b/submit/ast/AbstractNode.java index 01719aa..0a53882 100644 --- a/submit/ast/AbstractNode.java +++ b/submit/ast/AbstractNode.java @@ -10,6 +10,6 @@ public class AbstractNode implements Node { public MIPSResult toMIPS(StringBuilder code, StringBuilder data, SymbolTable symbolTable, RegisterAllocator regAllocator) { - return null; + return MIPSResult.createVoidResult(); } } diff --git a/submit/ast/Assignment.java b/submit/ast/Assignment.java index 1a5d172..9c06cbe 100644 --- a/submit/ast/Assignment.java +++ b/submit/ast/Assignment.java @@ -4,6 +4,10 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn @@ -30,4 +34,25 @@ public class Assignment extends AbstractNode implements Expression { } } + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + MIPSResult mut = mutable.toMIPS(code, data, symbolTable, regAllocator); + MIPSResult result = rhs.toMIPS(code, data, symbolTable, regAllocator); + + String registerWithAddressOfMutable = mut.getAddress(); + + if (result.getRegister() != null) { + code.append(String.format("sw %s 0(%s)\n", result.getRegister(), + registerWithAddressOfMutable)); + regAllocator.clear(result.getRegister()); + } else if (result.getAddress() != null) { + regAllocator.loadIntoRegister(result, code, result.getAddress()); + regAllocator.clear(result.getAddress()); + } + + regAllocator.clear(registerWithAddressOfMutable); + + return MIPSResult.createVoidResult(); + } } diff --git a/submit/ast/BinaryOperator.java b/submit/ast/BinaryOperator.java index d18766b..2545dd0 100644 --- a/submit/ast/BinaryOperator.java +++ b/submit/ast/BinaryOperator.java @@ -4,6 +4,10 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn @@ -13,7 +17,8 @@ public class BinaryOperator extends AbstractNode implements Expression { private final Expression lhs, rhs; private final BinaryOperatorType type; - public BinaryOperator(Expression lhs, BinaryOperatorType type, Expression rhs) { + public BinaryOperator(Expression lhs, BinaryOperatorType type, + Expression rhs) { this.lhs = lhs; this.type = type; this.rhs = rhs; @@ -32,4 +37,86 @@ public class BinaryOperator extends AbstractNode implements Expression { rhs.toCminus(builder, prefix); } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + MIPSResult left = lhs.toMIPS(code, data, symbolTable, regAllocator); + String leftRegister = + regAllocator.getRegisterOrLoadIntoRegister(left, code); + + MIPSResult right = rhs.toMIPS(code, data, symbolTable, regAllocator); + String rightRegister = + regAllocator.getRegisterOrLoadIntoRegister(right, code); + String resultRegister = regAllocator.getAny(); + + switch (type) { + case PLUS: + code.append(String.format("add %s %s %s\n", resultRegister, leftRegister, + rightRegister)); + break; + case MINUS: + code.append(String.format("sub %s %s %s\n", resultRegister, leftRegister, + rightRegister)); + break; + case TIMES: + code.append(String.format("mult %s %s\n", leftRegister, rightRegister)) + .append(String.format("mflo %s\n", resultRegister)); + break; + case DIVIDE: + code.append(String.format("div %s %s\n", leftRegister, rightRegister)) + .append(String.format("mflo %s\n", resultRegister)); + break; + case MOD: + code.append(String.format("div %s %s\n", leftRegister, rightRegister)) + .append(String.format("mfhi %s\n", resultRegister)); + break; + case LT: + code.append(String.format("slt %s %s %s\n", resultRegister, leftRegister, + rightRegister)) + .append( + String.format("subi %s %s 1\n", resultRegister, resultRegister)); + break; + case GT: + code.append(String.format("slt %s %s %s\n", resultRegister, rightRegister, + leftRegister)) + .append( + String.format("subi %s %s 1\n", resultRegister, resultRegister)); + break; + case LE: + code.append(String.format("slt %s %s %s\n", resultRegister, rightRegister, + leftRegister)); + break; + case GE: + code.append(String.format("slt %s %s %s\n", resultRegister, leftRegister, + rightRegister)); + break; + case EQ: + code.append(String.format("sub %s %s %s\n", resultRegister, leftRegister, + rightRegister)); + break; + case OR: + code.append(String.format("or %s %s %s\n", resultRegister, leftRegister, + rightRegister)); + break; + case AND: + code.append(String.format("abs %s %s\n", leftRegister, leftRegister)) + .append(String.format("abs %s %s\n", rightRegister, rightRegister)) + .append(String.format("add %s %s %s\n", resultRegister, leftRegister, + rightRegister)); + break; + case NE: + code.append(String.format("xor %s %s %s\n", resultRegister, leftRegister, + rightRegister)) + .append( + String.format("sltiu %s %s 1\n", resultRegister, resultRegister)); + default: + break; + } + + regAllocator.clear(leftRegister); + regAllocator.clear(rightRegister); + + return MIPSResult.createRegisterResult(resultRegister, VarType.INT); + } } diff --git a/submit/ast/BinaryOperatorType.java b/submit/ast/BinaryOperatorType.java index 37235c8..fea3d6e 100644 --- a/submit/ast/BinaryOperatorType.java +++ b/submit/ast/BinaryOperatorType.java @@ -10,15 +10,23 @@ package submit.ast; */ public enum BinaryOperatorType { - OR("||"), AND("&&"), - LE("<="), LT("<"), GT(">"), GE(">="), EQ("=="), NE("!="), - PLUS("+"), MINUS("-"), TIMES("*"), DIVIDE("/"), MOD("%"); + OR("||"), + AND("&&"), + LE("<="), + LT("<"), + GT(">"), + GE(">="), + EQ("=="), + NE("!="), + PLUS("+"), + MINUS("-"), + TIMES("*"), + DIVIDE("/"), + MOD("%"); private final String value; - private BinaryOperatorType(String value) { - this.value = value; - } + private BinaryOperatorType(String value) { this.value = value; } public static BinaryOperatorType fromString(String s) { for (BinaryOperatorType at : BinaryOperatorType.values()) { @@ -26,12 +34,12 @@ public enum BinaryOperatorType { return at; } } - throw new RuntimeException("Illegal string in OperatorType.fromString(): " + s); + throw new RuntimeException("Illegal string in OperatorType.fromString(): " + + s); } @Override public String toString() { return value; } - } diff --git a/submit/ast/BoolConstant.java b/submit/ast/BoolConstant.java index 4b0ad2c..2a7a281 100644 --- a/submit/ast/BoolConstant.java +++ b/submit/ast/BoolConstant.java @@ -9,12 +9,9 @@ package submit.ast; * @author edwajohn */ public class BoolConstant extends AbstractNode implements Expression { - private final boolean value; - public BoolConstant(boolean value) { - this.value = value; - } + public BoolConstant(boolean value) { this.value = value; } public void toCminus(StringBuilder builder, final String prefix) { if (value) { @@ -23,5 +20,4 @@ public class BoolConstant extends AbstractNode implements Expression { builder.append("false"); } } - } diff --git a/submit/ast/Break.java b/submit/ast/Break.java index e3f28bc..0582c91 100644 --- a/submit/ast/Break.java +++ b/submit/ast/Break.java @@ -9,10 +9,8 @@ package submit.ast; * @author edwajohn */ public class Break extends AbstractNode implements Statement { - @Override public void toCminus(StringBuilder builder, String prefix) { builder.append(prefix).append("break;\n"); } - } diff --git a/submit/ast/Call.java b/submit/ast/Call.java index b6e61ba..25ab2ea 100644 --- a/submit/ast/Call.java +++ b/submit/ast/Call.java @@ -6,12 +6,16 @@ package submit.ast; import java.util.ArrayList; import java.util.List; +import java.util.stream.Collectors; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; /** * * @author edwajohn */ -public class Call extends AbstractNode implements Expression { +public class Call implements Expression { private final String id; private final List<Expression> args; @@ -21,6 +25,39 @@ public class Call extends AbstractNode implements Expression { this.args = new ArrayList<>(args); } + private void println(List<MIPSResult> mipsResults, StringBuilder code, + StringBuilder data, SymbolTable symbolTable, + RegisterAllocator regAllocator) { + code.append("# println\n"); + + for (MIPSResult result : mipsResults) { + if (result.getRegister() == null && result.getAddress() != null) { + if (result.getAddress().startsWith("$")) { + // Hack - might be a register + regAllocator.loadIntoRegister(result, code, "$a0"); + } else { + code.append(String.format("la $a0 %s\n", result.getAddress())); + } + } else if (result.getRegister() != null) { + code.append(String.format("move $a0 %s\n", result.getRegister())); + } + + if (result.getType() == VarType.INT) { + code.append("li $v0 1\n"); + } else if (result.getType() == VarType.CHAR) { + code.append("li $v0 11\n"); + } else { + code.append("li $v0 4\n"); + } + code.append("syscall\n"); + } + + // End line with newline + code.append(String.format("la $a0 %s\n", "newline")); + code.append("li $v0 4\n"); + code.append("syscall\n"); + } + @Override public void toCminus(StringBuilder builder, String prefix) { builder.append(id).append("("); @@ -34,4 +71,69 @@ public class Call extends AbstractNode implements Expression { builder.append(")"); } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + List<MIPSResult> argMips; + String resultRegister = null; + + if (this.id.equals("println")) { + argMips = + args.stream() + .map(e -> e.toMIPS(code, data, symbolTable, regAllocator)) + .collect(Collectors.toList()); + this.println(argMips, code, data, symbolTable, regAllocator); + } else { + argMips = new ArrayList<MIPSResult>(); + String returnAddr = regAllocator.getAny(); + code.append(String.format("move %s $ra\n", returnAddr)); + int savedRegistersOffset = regAllocator.saveRestore( + code, -symbolTable.getOffset(), false, true); + + int argsOffset = symbolTable.getOffset() - savedRegistersOffset; + int i = argsOffset; + for (Expression expression : args) { + MIPSResult mipsResult = + expression.toMIPS(code, data, symbolTable, regAllocator); + argMips.add(mipsResult); + i -= 4; + + String reg = + regAllocator.getRegisterOrLoadIntoRegister(mipsResult, code); + code.append(String.format("sw %s %d($sp)\n", reg, i)); + + regAllocator.clear(reg); + } + + code.append(String.format("add $sp $sp %d\n", argsOffset)); + + code.append(String.format("jal %s\n", id)); + + code.append(String.format("add $sp $sp %d\n", -argsOffset)); + + regAllocator.saveRestore(code, -symbolTable.getOffset(), false, + false); + code.append(String.format("# symbol table size - %d\n", i)); + + resultRegister = regAllocator.getAny(); + regAllocator.loadIntoRegisterWithOffset( + MIPSResult.createAddressResult("$sp", VarType.INT), code, + resultRegister, i - 4); + + code.append(String.format("move $ra %s\n", returnAddr)); + regAllocator.clear(returnAddr); + } + + for (MIPSResult arg : argMips) + if (arg.getRegister() != null) + regAllocator.clear(arg.getRegister()); + + if (resultRegister != null) { + VarType returnType = symbolTable.find(id).getType(); + return MIPSResult.createRegisterResult(resultRegister, returnType); + } + + return MIPSResult.createVoidResult(); + } } diff --git a/submit/ast/CharConstant.java b/submit/ast/CharConstant.java index 8ca801d..5334be2 100644 --- a/submit/ast/CharConstant.java +++ b/submit/ast/CharConstant.java @@ -9,15 +9,11 @@ package submit.ast; * @author edwajohn */ public class CharConstant extends AbstractNode implements Expression { - private final char value; - public CharConstant(char value) { - this.value = value; - } + public CharConstant(char value) { this.value = value; } public void toCminus(StringBuilder builder, final String prefix) { builder.append("'").append(value).append("'"); } - } diff --git a/submit/ast/CompoundStatement.java b/submit/ast/CompoundStatement.java index bd5628a..e8d9256 100644 --- a/submit/ast/CompoundStatement.java +++ b/submit/ast/CompoundStatement.java @@ -5,6 +5,9 @@ package submit.ast; import java.util.List; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; /** * @@ -13,11 +16,16 @@ import java.util.List; public class CompoundStatement extends AbstractNode implements Statement { private final List<Statement> statements; + private SymbolTable symbolTable; - public CompoundStatement(List<Statement> statements) { + public CompoundStatement(List<Statement> statements, + SymbolTable symbolTable) { this.statements = statements; + this.symbolTable = symbolTable; } + public SymbolTable getSymbolTable() { return symbolTable; } + @Override public void toCminus(StringBuilder builder, String prefix) { builder.append(prefix).append("{\n"); @@ -27,4 +35,25 @@ public class CompoundStatement extends AbstractNode implements Statement { builder.append(prefix).append("}\n"); } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + code.append("# Entering a new scope.\n"); + code.append("# Symbols in symbol table:\n"); + for (String name : this.symbolTable.symbolNames()) + code.append( + String.format("# %s : %d\n", name, this.symbolTable.offsetOf(name))); + + code.append("# Update the stack pointer.\n"); + code.append(String.format("addi $sp $sp %d\n", symbolTable.getOffset())); + + for (Statement statement : statements) + statement.toMIPS(code, data, this.symbolTable, regAllocator); + + code.append("# Exit scope.\n"); + code.append(String.format("addi $sp $sp %s\n", -symbolTable.getOffset())); + + return MIPSResult.createVoidResult(); + } } diff --git a/submit/ast/Declaration.java b/submit/ast/Declaration.java index 32947e6..99c1c1a 100644 --- a/submit/ast/Declaration.java +++ b/submit/ast/Declaration.java @@ -8,6 +8,4 @@ package submit.ast; * * @author edwajohn */ -public interface Declaration extends Statement { - -} +public interface Declaration extends Statement {} diff --git a/submit/ast/Expression.java b/submit/ast/Expression.java index 910f6f0..d31753a 100644 --- a/submit/ast/Expression.java +++ b/submit/ast/Expression.java @@ -8,6 +8,4 @@ package submit.ast; * * @author edwajohn */ -public interface Expression extends Node { - -} +public interface Expression extends Node {} diff --git a/submit/ast/ExpressionStatement.java b/submit/ast/ExpressionStatement.java index 69071d8..a7ed5d2 100644 --- a/submit/ast/ExpressionStatement.java +++ b/submit/ast/ExpressionStatement.java @@ -4,6 +4,10 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn @@ -23,4 +27,11 @@ public class ExpressionStatement extends AbstractNode implements Statement { builder.append(";\n"); } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + expression.toMIPS(code, data, symbolTable, regAllocator); + return MIPSResult.createVoidResult(); + } } diff --git a/submit/ast/FunDeclaration.java b/submit/ast/FunDeclaration.java index 1ec2ca6..3980119 100644 --- a/submit/ast/FunDeclaration.java +++ b/submit/ast/FunDeclaration.java @@ -6,6 +6,9 @@ package submit.ast; import java.util.ArrayList; import java.util.List; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; /** * @@ -19,7 +22,7 @@ public class FunDeclaration extends AbstractNode implements Declaration { private final Statement statement; public FunDeclaration(VarType returnType, String id, List<Param> params, - Statement statement) { + Statement statement) { this.returnType = returnType; this.id = id; this.params = new ArrayList<>(params); @@ -43,4 +46,20 @@ public class FunDeclaration extends AbstractNode implements Declaration { statement.toCminus(builder, prefix); } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + code.append(id).append(":\n"); + + statement.toMIPS(code, data, symbolTable, regAllocator); + + if (id.equals("main")) + code.append("li $v0 10\nsyscall\n"); + else + code.append("jr $ra\n"); + regAllocator.clearAll(); + + return MIPSResult.createVoidResult(); + } } diff --git a/submit/ast/If.java b/submit/ast/If.java index a516c94..0c47ce9 100644 --- a/submit/ast/If.java +++ b/submit/ast/If.java @@ -4,6 +4,10 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn @@ -14,7 +18,8 @@ public class If extends AbstractNode implements Statement { private final Statement trueStatement; private final Statement falseStatement; - public If(Expression expression, Statement trueStatement, Statement falseStatement) { + public If(Expression expression, Statement trueStatement, + Statement falseStatement) { this.expression = expression; this.trueStatement = trueStatement; this.falseStatement = falseStatement; @@ -41,4 +46,37 @@ public class If extends AbstractNode implements Statement { } // builder.append(prefix).append("}"); } + + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + String continueLabel = "if_" + SymbolTable.nextId(); + String elseLabel = "else_" + SymbolTable.nextId(); + + MIPSResult expressionTruthiness = + expression.toMIPS(code, data, symbolTable, regAllocator); + + code.append(String.format("bne %s $zero %s\n", + expressionTruthiness.getRegister(), elseLabel)); + regAllocator.clear(expressionTruthiness.getRegister()); + + MIPSResult trueRes = + trueStatement.toMIPS(code, data, symbolTable, regAllocator); + regAllocator.clear(trueRes.getRegister()); + + code.append(String.format("j %s\n", continueLabel)) + .append(String.format("%s:\n", elseLabel)); + + regAllocator.clear(expressionTruthiness.getRegister()); + + if (falseStatement != null) { + MIPSResult falseRes = + falseStatement.toMIPS(code, data, symbolTable, regAllocator); + regAllocator.clear(falseRes.getRegister()); + } + code.append(String.format("%s:\n", continueLabel)); + + return MIPSResult.createVoidResult(); + } } diff --git a/submit/ast/Mutable.java b/submit/ast/Mutable.java index d549371..ac9b7ff 100644 --- a/submit/ast/Mutable.java +++ b/submit/ast/Mutable.java @@ -4,11 +4,15 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn */ -public class Mutable extends AbstractNode implements Expression { +public class Mutable implements Expression { private final String id; private final Expression index; @@ -28,4 +32,14 @@ public class Mutable extends AbstractNode implements Expression { } } + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + String stackReg = regAllocator.getAny(); + + code.append(String.format("li %s %d\n", stackReg, symbolTable.offsetOf(id))) + .append(String.format("add %s %s $sp\n", stackReg, stackReg)); + + return MIPSResult.createAddressResult(stackReg, VarType.INT); + } } diff --git a/submit/ast/Node.java b/submit/ast/Node.java index 2eed788..cc6c2d5 100644 --- a/submit/ast/Node.java +++ b/submit/ast/Node.java @@ -5,7 +5,8 @@ import submit.RegisterAllocator; import submit.SymbolTable; public interface Node { - void toCminus(StringBuilder builder, final String prefix); + void toCminus(StringBuilder builder, final String prefix); - MIPSResult toMIPS(StringBuilder code, StringBuilder data, SymbolTable symbolTable, RegisterAllocator regAllocator); + MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, RegisterAllocator regAllocator); } diff --git a/submit/ast/NumConstant.java b/submit/ast/NumConstant.java index 4e343fd..3287bd5 100644 --- a/submit/ast/NumConstant.java +++ b/submit/ast/NumConstant.java @@ -4,6 +4,10 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn @@ -12,12 +16,19 @@ public class NumConstant extends AbstractNode implements Expression { private final int value; - public NumConstant(int value) { - this.value = value; - } + public NumConstant(int value) { this.value = value; } public void toCminus(StringBuilder builder, final String prefix) { builder.append(Integer.toString(value)); } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + String register = regAllocator.getAny(); + code.append(String.format("li %s %d\n", register, value)); + + return MIPSResult.createRegisterResult(register, VarType.INT); + } } diff --git a/submit/ast/Param.java b/submit/ast/Param.java index 478c6e2..921b179 100644 --- a/submit/ast/Param.java +++ b/submit/ast/Param.java @@ -20,17 +20,11 @@ public class Param extends AbstractNode implements Node { this.array = array; } - public VarType getType() { - return type; - } + public VarType getType() { return type; } - public String getId() { - return id; - } + public String getId() { return id; } - public boolean isArray() { - return array; - } + public boolean isArray() { return array; } public void toCminus(StringBuilder builder, final String prefix) { if (isArray()) { @@ -39,5 +33,4 @@ public class Param extends AbstractNode implements Node { builder.append(type).append(" ").append(id); } } - } diff --git a/submit/ast/ParenExpression.java b/submit/ast/ParenExpression.java index 2eb0b8f..8d5b65f 100644 --- a/submit/ast/ParenExpression.java +++ b/submit/ast/ParenExpression.java @@ -4,6 +4,10 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn @@ -23,4 +27,10 @@ public class ParenExpression extends AbstractNode implements Expression { builder.append(")"); } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + return expression.toMIPS(code, data, symbolTable, regAllocator); + } } diff --git a/submit/ast/Program.java b/submit/ast/Program.java index 1478961..74b9ea8 100644 --- a/submit/ast/Program.java +++ b/submit/ast/Program.java @@ -6,6 +6,9 @@ package submit.ast; import java.util.ArrayList; import java.util.List; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; /** * @@ -33,4 +36,14 @@ public class Program extends AbstractNode implements Node { } } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + data.append("newline: .asciiz \"\\n\"\n"); + + for (Declaration declaration : declarations) + declaration.toMIPS(code, data, symbolTable, regAllocator); + return MIPSResult.createVoidResult(); + } } diff --git a/submit/ast/Return.java b/submit/ast/Return.java index 47a8c16..ebae15f 100644 --- a/submit/ast/Return.java +++ b/submit/ast/Return.java @@ -4,17 +4,18 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn */ public class Return extends AbstractNode implements Statement { - private final Expression expr; - public Return(Expression expr) { - this.expr = expr; - } + public Return(Expression expr) { this.expr = expr; } @Override public void toCminus(StringBuilder builder, String prefix) { @@ -28,4 +29,19 @@ public class Return extends AbstractNode implements Statement { } } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + if (expr != null) { + String reg = regAllocator.getRegisterOrLoadIntoRegister( + expr.toMIPS(code, data, symbolTable, regAllocator), code); + code.append( + String.format("# symbol table size - %d\n", symbolTable.getOffset())); + code.append( + String.format("sw %s %d($sp)\n", reg, symbolTable.getOffset())); + code.append("jr $ra\n"); + } + return MIPSResult.createVoidResult(); + } } diff --git a/submit/ast/Statement.java b/submit/ast/Statement.java index 2e0581e..2daeb9d 100644 --- a/submit/ast/Statement.java +++ b/submit/ast/Statement.java @@ -11,6 +11,8 @@ import java.util.ArrayList; * @author edwajohn */ public interface Statement extends Node { - public static CompoundStatement empty() { return new CompoundStatement(new ArrayList<>()); } - + public static CompoundStatement empty() { + submit.SymbolTable newTable = new submit.SymbolTable(); + return new CompoundStatement(new ArrayList<>(), newTable); + } } diff --git a/submit/ast/StringConstant.java b/submit/ast/StringConstant.java index c3b966e..5aaa5c3 100644 --- a/submit/ast/StringConstant.java +++ b/submit/ast/StringConstant.java @@ -4,6 +4,10 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn @@ -12,12 +16,19 @@ public class StringConstant extends AbstractNode implements Expression { private final String value; - public StringConstant(String value) { - this.value = value; - } + public StringConstant(String value) { this.value = value; } public void toCminus(StringBuilder builder, final String prefix) { builder.append("\"").append(value).append("\""); } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + String label = String.format("string_%s", SymbolTable.nextId()); + data.append(String.format("%s: .asciiz %s\n", label, value)); + + return MIPSResult.createAddressResult(label, null); + } } diff --git a/submit/ast/UnaryOperator.java b/submit/ast/UnaryOperator.java index 1b5082a..5195ef0 100644 --- a/submit/ast/UnaryOperator.java +++ b/submit/ast/UnaryOperator.java @@ -4,6 +4,10 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn @@ -23,5 +27,27 @@ public class UnaryOperator extends AbstractNode implements Expression { builder.append(type); expression.toCminus(builder, prefix); } + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + MIPSResult result = + expression.toMIPS(code, data, symbolTable, regAllocator); + + String reg = regAllocator.getRegisterOrLoadIntoRegister(result, code); + switch (type) { + case NEG: + code.append(String.format("sub %s $zero %s\n", reg, reg)); + break; + case NOT: + code.append(String.format("sltu %s $zero %s\n", reg, reg)) + .append(String.format("xori %s %s 1\n", reg, reg)); + break; + default: + break; + } + + return MIPSResult.createRegisterResult(reg, VarType.INT); + } } diff --git a/submit/ast/VarDeclaration.java b/submit/ast/VarDeclaration.java index d2a5264..809518f 100644 --- a/submit/ast/VarDeclaration.java +++ b/submit/ast/VarDeclaration.java @@ -18,7 +18,8 @@ public class VarDeclaration extends AbstractNode implements Declaration { private final List<Integer> arraySizes; private final boolean isStatic; - public VarDeclaration(VarType type, List<String> ids, List<Integer> arraySizes, boolean isStatic) { + public VarDeclaration(VarType type, List<String> ids, + List<Integer> arraySizes, boolean isStatic) { this.type = type; this.ids = new ArrayList<>(ids); this.arraySizes = arraySizes; @@ -35,7 +36,8 @@ public class VarDeclaration extends AbstractNode implements Declaration { final String id = ids.get(i); final int arraySize = arraySizes.get(i); if (arraySize >= 0) { - builder.append(id).append("[").append(arraySize).append("]").append(", "); + builder.append(id).append("[").append(arraySize).append("]").append( + ", "); } else { builder.append(id).append(", "); } @@ -43,5 +45,4 @@ public class VarDeclaration extends AbstractNode implements Declaration { builder.delete(builder.length() - 2, builder.length()); builder.append(";\n"); } - } diff --git a/submit/ast/VarType.java b/submit/ast/VarType.java index ba28946..e797d50 100644 --- a/submit/ast/VarType.java +++ b/submit/ast/VarType.java @@ -10,13 +10,13 @@ package submit.ast; */ public enum VarType { - INT("int"), BOOL("bool"), CHAR("char"); + INT("int"), + BOOL("bool"), + CHAR("char"); private final String value; - private VarType(String value) { - this.value = value; - } + private VarType(String value) { this.value = value; } public static VarType fromString(String s) { for (VarType vt : VarType.values()) { @@ -31,5 +31,4 @@ public enum VarType { public String toString() { return value; } - } diff --git a/submit/ast/While.java b/submit/ast/While.java index a37195e..41c3963 100644 --- a/submit/ast/While.java +++ b/submit/ast/While.java @@ -4,6 +4,10 @@ */ package submit.ast; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + /** * * @author edwajohn @@ -28,6 +32,29 @@ public class While extends AbstractNode implements Statement { } else { statement.toCminus(builder, prefix + " "); } + } + + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator regAllocator) { + String loopLabel = "while_truthy_" + SymbolTable.nextId(); + String finishedLabel = "finished_while_" + SymbolTable.nextId(); + + code.append(String.format("%s:\n", loopLabel)); + + MIPSResult expressionTruthiness = + expression.toMIPS(code, data, symbolTable, regAllocator); + + code.append(String.format("bne %s $zero %s\n", + expressionTruthiness.getRegister(), + finishedLabel)); + + MIPSResult inside = statement.toMIPS(code, data, symbolTable, regAllocator); + regAllocator.clear(inside.getRegister()); + code.append(String.format("j %s\n", loopLabel)) + .append(String.format("%s:\n", finishedLabel)); + return MIPSResult.createVoidResult(); } } @@ -0,0 +1,7 @@ +#!/bin/zsh + +# usage: ./test.sh <test-number> + +javac -d classes -cp classes -cp *.jar **/*.java && java -cp "classes:antlr-4.9.1-complete.jar" main.Main data/test$1.c + +java -jar data/examples/Mars4_5.jar data/test$1.asm |