diff options
Diffstat (limited to 'Homework/cs5300/compiler/p5-compiler/submit')
34 files changed, 1895 insertions, 0 deletions
diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ASTVisitor.java b/Homework/cs5300/compiler/p5-compiler/submit/ASTVisitor.java new file mode 100644 index 0000000..5cafbb1 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ASTVisitor.java @@ -0,0 +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.*; + +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 { + 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/Homework/cs5300/compiler/p5-compiler/submit/MIPSResult.java b/Homework/cs5300/compiler/p5-compiler/submit/MIPSResult.java new file mode 100644 index 0000000..bccfe76 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/MIPSResult.java @@ -0,0 +1,60 @@ +/* + */ +package submit; + +import submit.ast.VarType; + +/** + * This class represents the result of generating MIPS code. There are various + * forms this result can take: 1) void, for cases where the calling node doesn't + * need any information returned, such as a return statement. 2) register, for + * cases where the called node needs to inform the calling node what register a + * result is placed in, such as BinaryOperator. 3) address, for cases where the + * returning result is in memory, such as StringConstant. + * + * To instantiate a MIPSResult object use the factory methods create...(). + * + */ +public class MIPSResult { + + private final String register; + private final String address; + private final VarType type; + + public static MIPSResult createVoidResult() { + return new MIPSResult(null, null, null); + } + + public static MIPSResult createRegisterResult(String register, VarType type) { + return new MIPSResult(register, null, type); + } + + public static MIPSResult createAddressResult(String address, VarType type) { + return new MIPSResult(null, address, type); + } + + private MIPSResult(String register, String address, VarType type) { + this.register = register; + this.address = address; + this.type = type; + } + + /** + * Anytime you get a register from a result you should seriously consider + * calling regAllocator.clear(reg) after using the register to minimize + * register usage. + * + * @return + */ + public String getRegister() { + return register; + } + + public String getAddress() { + return address; + } + + public VarType getType() { + return type; + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/RegisterAllocator.java b/Homework/cs5300/compiler/p5-compiler/submit/RegisterAllocator.java new file mode 100644 index 0000000..b0c9d03 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/RegisterAllocator.java @@ -0,0 +1,151 @@ +/* + */ +package submit; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashSet; +import java.util.List; +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<>(); + + public RegisterAllocator() { clearAll(); } + + 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 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())); + + return register; + } + + 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 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 int saveS(StringBuilder code, int baseOffset) { + // return saveRestore(code, baseOffset, true, true); + // } + + 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 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 void clearAll() { + Arrays.fill(t, false); + Arrays.fill(s, false); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/SymbolInfo.java b/Homework/cs5300/compiler/p5-compiler/submit/SymbolInfo.java new file mode 100644 index 0000000..c640718 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/SymbolInfo.java @@ -0,0 +1,43 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit; + +import submit.ast.VarType; + +/** + * + * @author edwajohn + */ +public class SymbolInfo { + + private final String id; + // 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; + this.type = type; + 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/Homework/cs5300/compiler/p5-compiler/submit/SymbolTable.java b/Homework/cs5300/compiler/p5-compiler/submit/SymbolTable.java new file mode 100644 index 0000000..09251bc --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/SymbolTable.java @@ -0,0 +1,118 @@ +package submit; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import submit.ast.VarType; + +/* + * Code formatter project + * CS 4481 + */ +/** + * + */ +public class SymbolTable { + + private final HashMap<String, SymbolInfo> table; + 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 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 + } + + /** + * Returns null if no symbol with that id is in this symbol table or an + * ancestor table. + * + * @param id + * @return + */ + public SymbolInfo find(String id) { + if (table.containsKey(id)) { + return table.get(id); + } + if (parent != null) { + return parent.find(id); + } + return null; + } + + /** + * Returns the new child. + * + * @return + */ + public SymbolTable createChild() { + SymbolTable child = new SymbolTable(); + children.add(child); + child.parent = this; + return child; + } + + public SymbolTable getParent() { return parent; } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/AbstractNode.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/AbstractNode.java new file mode 100644 index 0000000..0a53882 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/AbstractNode.java @@ -0,0 +1,15 @@ +package submit.ast; + +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +public class AbstractNode implements Node { + public void toCminus(StringBuilder sb, String prefix) { + } + + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, SymbolTable symbolTable, + RegisterAllocator regAllocator) { + return MIPSResult.createVoidResult(); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/Assignment.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Assignment.java new file mode 100644 index 0000000..9c06cbe --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Assignment.java @@ -0,0 +1,58 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class Assignment extends AbstractNode implements Expression { + + private final Mutable mutable; + private final AssignmentType type; + private final Expression rhs; + + public Assignment(Mutable mutable, String assign, Expression rhs) { + this.mutable = mutable; + this.type = AssignmentType.fromString(assign); + this.rhs = rhs; + } + + public void toCminus(StringBuilder builder, final String prefix) { + mutable.toCminus(builder, prefix); + if (rhs != null) { + builder.append(" ").append(type.toString()).append(" "); + rhs.toCminus(builder, prefix); + } else { + builder.append(type.toString()); + } + } + + 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/Homework/cs5300/compiler/p5-compiler/submit/ast/AssignmentType.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/AssignmentType.java new file mode 100644 index 0000000..9dd2bdf --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/AssignmentType.java @@ -0,0 +1,35 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public enum AssignmentType { + + EQUALS("="), PLUS("+="), MINUS("-="), TIMES("*="), DIVIDE("/="), INC("++"), DEC("--"); + + private final String value; + + private AssignmentType(String value) { + this.value = value; + } + + public static AssignmentType fromString(String s) { + for (AssignmentType at : AssignmentType.values()) { + if (at.value.equals(s)) { + return at; + } + } + throw new RuntimeException("Illegal string in AssignType.fromString()"); + } + + @Override + public String toString() { + return value; + } + +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/BinaryOperator.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/BinaryOperator.java new file mode 100644 index 0000000..3afce78 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/BinaryOperator.java @@ -0,0 +1,89 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class BinaryOperator extends AbstractNode implements Expression { + + private final Expression lhs, rhs; + private final BinaryOperatorType type; + + public BinaryOperator(Expression lhs, BinaryOperatorType type, + Expression rhs) { + this.lhs = lhs; + this.type = type; + this.rhs = rhs; + } + + public BinaryOperator(Expression lhs, String type, Expression rhs) { + this.lhs = lhs; + this.type = BinaryOperatorType.fromString(type); + this.rhs = rhs; + } + + @Override + public void toCminus(StringBuilder builder, String prefix) { + lhs.toCminus(builder, prefix); + builder.append(" ").append(type).append(" "); + rhs.toCminus(builder, prefix); + } + + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator registerAllocator) { + + switch (type) { + case PLUS: + case MINUS: + case TIMES: + case DIVIDE: + MIPSResult left = lhs.toMIPS(code, data, symbolTable, registerAllocator); + String leftRegister = + registerAllocator.getRegisterOrLoadIntoRegister(left, code); + + MIPSResult right = rhs.toMIPS(code, data, symbolTable, registerAllocator); + String rightRegister = + registerAllocator.getRegisterOrLoadIntoRegister(right, code); + String resultRegister = registerAllocator.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)); + code.append(String.format("mflo %s\n", resultRegister)); + break; + case DIVIDE: + code.append(String.format("div %s %s\n", leftRegister, rightRegister)); + code.append(String.format("mflo %s\n", resultRegister)); + break; + default: + break; + } + + registerAllocator.clear(leftRegister); + registerAllocator.clear(rightRegister); + + return MIPSResult.createRegisterResult(resultRegister, VarType.INT); + default: + break; + } + + return MIPSResult.createVoidResult(); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/BinaryOperatorType.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/BinaryOperatorType.java new file mode 100644 index 0000000..fea3d6e --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/BinaryOperatorType.java @@ -0,0 +1,45 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public enum BinaryOperatorType { + + OR("||"), + AND("&&"), + LE("<="), + LT("<"), + GT(">"), + GE(">="), + EQ("=="), + NE("!="), + PLUS("+"), + MINUS("-"), + TIMES("*"), + DIVIDE("/"), + MOD("%"); + + private final String value; + + private BinaryOperatorType(String value) { this.value = value; } + + public static BinaryOperatorType fromString(String s) { + for (BinaryOperatorType at : BinaryOperatorType.values()) { + if (at.value.equals(s)) { + return at; + } + } + throw new RuntimeException("Illegal string in OperatorType.fromString(): " + + s); + } + + @Override + public String toString() { + return value; + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/BoolConstant.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/BoolConstant.java new file mode 100644 index 0000000..2a7a281 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/BoolConstant.java @@ -0,0 +1,23 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public class BoolConstant extends AbstractNode implements Expression { + private final boolean value; + + public BoolConstant(boolean value) { this.value = value; } + + public void toCminus(StringBuilder builder, final String prefix) { + if (value) { + builder.append("true"); + } else { + builder.append("false"); + } + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/Break.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Break.java new file mode 100644 index 0000000..0582c91 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Break.java @@ -0,0 +1,16 @@ +/* + * Code formatter project + * CS 4481 + */ +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/Homework/cs5300/compiler/p5-compiler/submit/ast/Call.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Call.java new file mode 100644 index 0000000..7da86cd --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Call.java @@ -0,0 +1,139 @@ +/* + * Code formatter project + * CS 4481 + */ +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 implements Expression { + + private final String id; + private final List<Expression> args; + + public Call(String id, List<Expression> args) { + this.id = id; + this.args = new ArrayList<>(args); + } + + private void println(List<MIPSResult> mipsResults, StringBuilder code, + StringBuilder data, SymbolTable symbolTable, + RegisterAllocator registerAllocator) { + code.append("# println\n"); + + for (MIPSResult result : mipsResults) { + if (result.getRegister() == null && result.getAddress() != null) { + if (result.getAddress().startsWith("$")) { + // Hack - might be a register + registerAllocator.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("("); + for (Expression arg : args) { + arg.toCminus(builder, prefix); + builder.append(", "); + } + if (!args.isEmpty()) { + builder.setLength(builder.length() - 2); + } + builder.append(")"); + } + + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator registerAllocator) { + List<MIPSResult> argMips; + String resultRegister = null; + + if (this.id.equals("println")) { + argMips = + args.stream() + .map(e -> e.toMIPS(code, data, symbolTable, registerAllocator)) + .collect(Collectors.toList()); + this.println(argMips, code, data, symbolTable, registerAllocator); + } else { + argMips = new ArrayList<MIPSResult>(); + String returnAddr = registerAllocator.getAny(); + code.append(String.format("move %s $ra\n", returnAddr)); + int savedRegistersOffset = registerAllocator.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, registerAllocator); + argMips.add(mipsResult); + i -= 4; + + String reg = + registerAllocator.getRegisterOrLoadIntoRegister(mipsResult, code); + code.append(String.format("sw %s %d($sp)\n", reg, i)); + + registerAllocator.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)); + + registerAllocator.saveRestore(code, -symbolTable.getOffset(), false, + false); + code.append(String.format("# symbol table size - %d\n", i)); + + resultRegister = registerAllocator.getAny(); + registerAllocator.loadIntoRegisterWithOffset( + MIPSResult.createAddressResult("$sp", VarType.INT), code, + resultRegister, i - 4); + + code.append(String.format("move $ra %s\n", returnAddr)); + registerAllocator.clear(returnAddr); + } + + for (MIPSResult arg : argMips) + if (arg.getRegister() != null) + registerAllocator.clear(arg.getRegister()); + + if (resultRegister != null) { + VarType returnType = symbolTable.find(id).getType(); + return MIPSResult.createRegisterResult(resultRegister, returnType); + } + + return MIPSResult.createVoidResult(); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/CharConstant.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/CharConstant.java new file mode 100644 index 0000000..5334be2 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/CharConstant.java @@ -0,0 +1,19 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public class CharConstant extends AbstractNode implements Expression { + private final char value; + + public CharConstant(char value) { this.value = value; } + + public void toCminus(StringBuilder builder, final String prefix) { + builder.append("'").append(value).append("'"); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/CompoundStatement.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/CompoundStatement.java new file mode 100644 index 0000000..4d1c666 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/CompoundStatement.java @@ -0,0 +1,59 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import java.util.List; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class CompoundStatement extends AbstractNode implements Statement { + + private final List<Statement> statements; + private SymbolTable symbolTable; + + 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"); + for (Statement s : statements) { + s.toCminus(builder, prefix + " "); + } + builder.append(prefix).append("}\n"); + } + + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator registerAllocator) { + 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, registerAllocator); + + code.append("# Exit scope.\n"); + code.append(String.format("addi $sp $sp %s\n", -symbolTable.getOffset())); + + return MIPSResult.createVoidResult(); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/Declaration.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Declaration.java new file mode 100644 index 0000000..99c1c1a --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Declaration.java @@ -0,0 +1,11 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public interface Declaration extends Statement {} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/Expression.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Expression.java new file mode 100644 index 0000000..d31753a --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Expression.java @@ -0,0 +1,11 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public interface Expression extends Node {} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/ExpressionStatement.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/ExpressionStatement.java new file mode 100644 index 0000000..7870a2e --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/ExpressionStatement.java @@ -0,0 +1,37 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class ExpressionStatement extends AbstractNode implements Statement { + + private final Expression expression; + + public ExpressionStatement(Expression expression) { + this.expression = expression; + } + + @Override + public void toCminus(StringBuilder builder, String prefix) { + builder.append(prefix); + expression.toCminus(builder, prefix); + builder.append(";\n"); + } + + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator registerAllocator) { + expression.toMIPS(code, data, symbolTable, registerAllocator); + return MIPSResult.createVoidResult(); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/FunDeclaration.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/FunDeclaration.java new file mode 100644 index 0000000..f60840b --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/FunDeclaration.java @@ -0,0 +1,65 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import java.util.ArrayList; +import java.util.List; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class FunDeclaration extends AbstractNode implements Declaration { + + private final VarType returnType; + private final String id; + private final ArrayList<Param> params; + private final Statement statement; + + public FunDeclaration(VarType returnType, String id, List<Param> params, + Statement statement) { + this.returnType = returnType; + this.id = id; + this.params = new ArrayList<>(params); + this.statement = statement; + } + + public void toCminus(StringBuilder builder, final String prefix) { + String rt = (returnType != null) ? returnType.toString() : "void"; + builder.append("\n").append(rt).append(" "); + builder.append(id); + builder.append("("); + + for (Param param : params) { + param.toCminus(builder, prefix); + builder.append(", "); + } + if (!params.isEmpty()) { + builder.delete(builder.length() - 2, builder.length()); + } + builder.append(")\n"); + statement.toCminus(builder, prefix); + } + + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator registerAllocator) { + code.append(id).append(":\n"); + + statement.toMIPS(code, data, symbolTable, registerAllocator); + + if (id.equals("main")) + code.append("li $v0 10\nsyscall\n"); + else + code.append("jr $ra\n"); + registerAllocator.clearAll(); + + return MIPSResult.createVoidResult(); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/If.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/If.java new file mode 100644 index 0000000..1a481ed --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/If.java @@ -0,0 +1,45 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public class If extends AbstractNode implements Statement { + + private final Expression expression; + private final Statement trueStatement; + private final Statement falseStatement; + + public If(Expression expression, Statement trueStatement, + Statement falseStatement) { + this.expression = expression; + this.trueStatement = trueStatement; + this.falseStatement = falseStatement; + } + + @Override + public void toCminus(StringBuilder builder, String prefix) { + builder.append(prefix).append("if ("); + expression.toCminus(builder, prefix); + builder.append(")\n"); + if (trueStatement instanceof CompoundStatement) { + trueStatement.toCminus(builder, prefix); + } else { + trueStatement.toCminus(builder, prefix + " "); + } + if (falseStatement != null) { + builder.append(prefix).append("else\n"); + // falseStatement.toCminus(builder, prefix); + if (falseStatement instanceof CompoundStatement) { + falseStatement.toCminus(builder, prefix); + } else { + falseStatement.toCminus(builder, prefix + " "); + } + } + // builder.append(prefix).append("}"); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/Mutable.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Mutable.java new file mode 100644 index 0000000..ac9b7ff --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Mutable.java @@ -0,0 +1,45 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class Mutable implements Expression { + + private final String id; + private final Expression index; + + public Mutable(String id, Expression index) { + this.id = id; + this.index = index; + } + + @Override + public void toCminus(StringBuilder builder, String prefix) { + builder.append(id); + if (index != null) { + builder.append("["); + index.toCminus(builder, prefix); + builder.append("]"); + } + } + + 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/Homework/cs5300/compiler/p5-compiler/submit/ast/Node.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Node.java new file mode 100644 index 0000000..cc6c2d5 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Node.java @@ -0,0 +1,12 @@ +package submit.ast; + +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +public interface Node { + void toCminus(StringBuilder builder, final String prefix); + + MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, RegisterAllocator regAllocator); +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/NumConstant.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/NumConstant.java new file mode 100644 index 0000000..3389238 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/NumConstant.java @@ -0,0 +1,34 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class NumConstant extends AbstractNode implements Expression { + + private final int 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 registerAllocator) { + String register = registerAllocator.getAny(); + code.append(String.format("li %s %d\n", register, value)); + + return MIPSResult.createRegisterResult(register, VarType.INT); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/Param.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Param.java new file mode 100644 index 0000000..921b179 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Param.java @@ -0,0 +1,36 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public class Param extends AbstractNode implements Node { + + private final VarType type; + private final String id; + private final boolean array; + + public Param(VarType type, String id, boolean array) { + this.type = type; + this.id = id; + this.array = array; + } + + public VarType getType() { return type; } + + public String getId() { return id; } + + public boolean isArray() { return array; } + + public void toCminus(StringBuilder builder, final String prefix) { + if (isArray()) { + builder.append(type).append(" ").append(id).append("[]"); + } else { + builder.append(type).append(" ").append(id); + } + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/ParenExpression.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/ParenExpression.java new file mode 100644 index 0000000..e61dfe3 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/ParenExpression.java @@ -0,0 +1,36 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class ParenExpression extends AbstractNode implements Expression { + + private final Expression expression; + + public ParenExpression(Expression expression) { + this.expression = expression; + } + + @Override + public void toCminus(StringBuilder builder, String prefix) { + builder.append("("); + expression.toCminus(builder, prefix); + builder.append(")"); + } + + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator registerAllocator) { + return expression.toMIPS(code, data, symbolTable, registerAllocator); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/Program.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Program.java new file mode 100644 index 0000000..e32a7d2 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Program.java @@ -0,0 +1,50 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import java.util.ArrayList; +import java.util.List; +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class Program extends AbstractNode implements Node { + + private ArrayList<Declaration> declarations; + + public Program(List<Declaration> declarations) { + this.declarations = new ArrayList<>(declarations); + } + + @Override + public String toString() { + StringBuilder builder = new StringBuilder(); + toCminus(builder, ""); + return builder.toString(); + } + + @Override + public void toCminus(StringBuilder builder, String prefix) { + for (Declaration declaration : declarations) { + declaration.toCminus(builder, ""); + } + } + + @Override + public MIPSResult toMIPS(StringBuilder code, StringBuilder data, + SymbolTable symbolTable, + RegisterAllocator registerAllocator) { + // Store newline in .data + data.append("newline: .asciiz \"\\n\"\n"); + + for (Declaration declaration : declarations) + declaration.toMIPS(code, data, symbolTable, registerAllocator); + return MIPSResult.createVoidResult(); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/Return.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Return.java new file mode 100644 index 0000000..b5dd761 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Return.java @@ -0,0 +1,46 @@ +/* + * Code formatter project + * CS 4481 + */ +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; } + + @Override + public void toCminus(StringBuilder builder, String prefix) { + builder.append(prefix); + if (expr == null) { + builder.append("return;\n"); + } else { + builder.append("return "); + expr.toCminus(builder, prefix); + builder.append(";\n"); + } + } + + @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())); + } + return MIPSResult.createVoidResult(); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/Statement.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/Statement.java new file mode 100644 index 0000000..2daeb9d --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/Statement.java @@ -0,0 +1,18 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import java.util.ArrayList; + +/** + * + * @author edwajohn + */ +public interface Statement extends Node { + public static CompoundStatement empty() { + submit.SymbolTable newTable = new submit.SymbolTable(); + return new CompoundStatement(new ArrayList<>(), newTable); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/StringConstant.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/StringConstant.java new file mode 100644 index 0000000..bd4c37d --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/StringConstant.java @@ -0,0 +1,34 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class StringConstant extends AbstractNode implements Expression { + + private final String 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 registerAllocator) { + 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/Homework/cs5300/compiler/p5-compiler/submit/ast/UnaryOperator.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/UnaryOperator.java new file mode 100644 index 0000000..799a0be --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/UnaryOperator.java @@ -0,0 +1,54 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import submit.MIPSResult; +import submit.RegisterAllocator; +import submit.SymbolTable; + +/** + * + * @author edwajohn + */ +public class UnaryOperator extends AbstractNode implements Expression { + + private final UnaryOperatorType type; + private final Expression expression; + + public UnaryOperator(String type, Expression expression) { + this.type = UnaryOperatorType.fromString(type); + this.expression = expression; + } + + @Override + public void toCminus(StringBuilder builder, String prefix) { + 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); + + if (type == UnaryOperatorType.NEG) { + code.append("# Negation\n"); + if (result.getAddress() != null) { + String reg = regAllocator.getRegisterOrLoadIntoRegister(result, code); + + code.append(String.format("sub %s, $zero, %s\n", reg, reg)) + .append(String.format("sw %s 0(%s)\n", reg, result.getAddress())); + + regAllocator.clear(reg); + } else { + code.append(String.format("sub %s, $zero, %s\n", result.getRegister(), + result.getRegister())); + } + } + + return result; + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/UnaryOperatorType.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/UnaryOperatorType.java new file mode 100644 index 0000000..828ee5a --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/UnaryOperatorType.java @@ -0,0 +1,35 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public enum UnaryOperatorType { + + NOT("!"), NEG("-"), DEREF("*"), QUESTION("?"); + + private final String value; + + private UnaryOperatorType(String value) { + this.value = value; + } + + public static UnaryOperatorType fromString(String s) { + for (UnaryOperatorType at : UnaryOperatorType.values()) { + if (at.value.equals(s)) { + return at; + } + } + throw new RuntimeException("Illegal string in UnaryOperatorType.fromString()"); + } + + @Override + public String toString() { + return value; + } + +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/VarDeclaration.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/VarDeclaration.java new file mode 100644 index 0000000..809518f --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/VarDeclaration.java @@ -0,0 +1,48 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +import java.util.ArrayList; +import java.util.List; + +/** + * + * @author edwajohn + */ +public class VarDeclaration extends AbstractNode implements Declaration { + + private final VarType type; + private final List<String> ids; + private final List<Integer> arraySizes; + private final 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; + this.isStatic = isStatic; + } + + public void toCminus(StringBuilder builder, final String prefix) { + builder.append(prefix); + if (isStatic) { + builder.append("static "); + } + builder.append(type).append(" "); + for (int i = 0; i < ids.size(); ++i) { + final String id = ids.get(i); + final int arraySize = arraySizes.get(i); + if (arraySize >= 0) { + builder.append(id).append("[").append(arraySize).append("]").append( + ", "); + } else { + builder.append(id).append(", "); + } + } + builder.delete(builder.length() - 2, builder.length()); + builder.append(";\n"); + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/VarType.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/VarType.java new file mode 100644 index 0000000..e797d50 --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/VarType.java @@ -0,0 +1,34 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public enum VarType { + + INT("int"), + BOOL("bool"), + CHAR("char"); + + private final String value; + + private VarType(String value) { this.value = value; } + + public static VarType fromString(String s) { + for (VarType vt : VarType.values()) { + if (vt.value.equals(s)) { + return vt; + } + } + throw new RuntimeException("Illegal string in VarType.fromString()"); + } + + @Override + public String toString() { + return value; + } +} diff --git a/Homework/cs5300/compiler/p5-compiler/submit/ast/While.java b/Homework/cs5300/compiler/p5-compiler/submit/ast/While.java new file mode 100644 index 0000000..70b8e9f --- /dev/null +++ b/Homework/cs5300/compiler/p5-compiler/submit/ast/While.java @@ -0,0 +1,32 @@ +/* + * Code formatter project + * CS 4481 + */ +package submit.ast; + +/** + * + * @author edwajohn + */ +public class While extends AbstractNode implements Statement { + + private final Expression expression; + private final Statement statement; + + public While(Expression expression, Statement statement) { + this.expression = expression; + this.statement = statement; + } + + @Override + public void toCminus(StringBuilder builder, String prefix) { + builder.append(prefix).append("while ("); + expression.toCminus(builder, prefix); + builder.append(")\n"); + if (statement instanceof CompoundStatement) { + statement.toCminus(builder, prefix); + } else { + statement.toCminus(builder, prefix + " "); + } + } +} |