import java.io.*; import java.lang.*; import java.util.*; class Lexical { private String next_token; /* Store next token in buffer */ int next_token_line = 1; int next_token_col = 0; private String found = ""; int found_line = 1; int found_col = 0; private FileReader rdfile; /* File to read from */ char curr_char = ' '; int curr_line = 1; int curr_col = 0; /* Constructor */ Lexical(String fd) { /* opens file called fd, begins reading */ try { rdfile = new FileReader(fd); } catch(FileNotFoundException e) { System.out.println("File Not Found!"); } } public String nextTk() { /* Access method for next_token */ return next_token; } public String getLoc() { return ("L" + next_token_line + "/C" + next_token_col); } public void skipWhite() { while(Character.isWhitespace(curr_char)) { curr_char = this.getChar(); if (curr_char == '@') break; } } public char getChar() { int check; char temp = ' '; try { check = rdfile.read(); if (check == -1) temp = '@'; else temp = (char) check; } catch(Exception e) {System.out.println("Read Error");} if (temp == '\n') { curr_col = 0; curr_line++; } else { curr_col++; } return temp; } /* reads next token from the file, stores it in next_token */ public void readNext() { /* We already have a token */ if (!found.equals("")) { /* Check for two-symbol operators */ if ((found.equals("<") || found.equals(">") || found.equals("=") || found.equals("!")) && curr_char == '=') { found = found + curr_char; curr_char = this.getChar(); } if (found.equals("&") && curr_char == '&') { found = found + curr_char; curr_char = this.getChar(); } if (found.equals("*") && curr_char == '*') { found = found + curr_char; curr_char = this.getChar(); } if (found.equals("/") && curr_char == '*') { String comment = found; /* Skip commments */ do { comment = comment + curr_char; curr_char = this.getChar(); } while(!comment.endsWith("*/")); } next_token = found; next_token_line = found_line; next_token_col = found_col; found = ""; } /* Don't have a token, find the next one */ else { next_token = ""; /* Find first occurence of not-white space */ if (Character.isWhitespace(curr_char)) { this.skipWhite(); } /* store start location of this token */ this.next_token_line = curr_line; this.next_token_col = curr_col; if (curr_char == '@') next_token = next_token + curr_char; /* Read in tokens */ while(!Character.isWhitespace(curr_char) && curr_char != '@') { /* #-Comment exclusion block */ while(curr_char == '#') { String comment = "" + curr_char; /* Skip commments */ do { curr_char = this.getChar(); comment = comment + curr_char; } while (!comment.endsWith("\n")); if (Character.isWhitespace(curr_char)) this.skipWhite(); this.next_token_line = curr_line; this.next_token_col = curr_col; } next_token = next_token + curr_char; curr_char = this.getChar(); /* Look for operators, end markers, etc. */ if (next_token.endsWith(";") || next_token.endsWith(",") || next_token.endsWith("=") || next_token.endsWith("{") || next_token.endsWith("}") || next_token.endsWith("(") || next_token.endsWith(")") || next_token.endsWith(":") || next_token.endsWith("?") || next_token.endsWith("&") || next_token.endsWith("||") || next_token.endsWith("~") || next_token.endsWith("<") || next_token.endsWith(">") || next_token.endsWith("!") || next_token.endsWith("+") || next_token.endsWith("-") || next_token.endsWith("*") || next_token.endsWith("/") || next_token.endsWith("%")) { /* Chop the appropiate number of characters from the end of the string provided chopping needs to be done */ if (next_token.length() > 1) { if (next_token.endsWith("||")) { if (next_token.length() > 2) { found = next_token.substring(next_token.length() - 2, next_token.length()); next_token = next_token.substring(0, next_token.length() - 2); found_line = curr_line; found_col = curr_col - 2; } } else { found = next_token.substring(next_token.length() - 1, next_token.length()); next_token = next_token.substring(0, next_token.length() - 1); if (curr_col == 0) { found_line = curr_line -1; found_col = next_token_col + next_token.length(); } else { found_line = curr_line; found_col = curr_col - 1; } } break; } if ((next_token.equals("<") || next_token.equals(">") || next_token.equals("=") || next_token.equals("!")) && curr_char == '=') { next_token = next_token + curr_char; curr_char = this.getChar(); } if (next_token.equals("&") && curr_char == '&') { next_token = next_token + curr_char; curr_char = this.getChar(); } if (next_token.equals("*") && curr_char == '*') { next_token = next_token + curr_char; curr_char = this.getChar(); } /* Special case for '/*'-comments */ if (next_token.equals("/")) { if (curr_char == '*') { String comment = ""; next_token = ""; /* Skip commments */ do { curr_char = this.getChar(); comment = comment + curr_char; } while(!comment.endsWith("*/")); curr_char = this.getChar(); if (Character.isWhitespace(curr_char)) { this.skipWhite(); } next_token_line = curr_line; next_token_col = curr_col; } else break; } else break; } } } } } class lex_test { public static void main(String args[]) { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); System.out.print("File name: "); String fd = ""; char x = ' '; do { try { x = (char) in.read(); } catch(Exception e) {} if (!Character.isWhitespace(x)) fd = fd + x; } while(!Character.isWhitespace(x)); FileOutputStream filewrite = null; try { filewrite = new FileOutputStream(fd + ".tree"); } catch(Exception e) {} Lexical la = new Lexical(fd); do { la.readNext(); System.out.print(la.nextTk()); System.out.print(la.getLoc()); } while(!la.nextTk().equals("\n")); /* TreeNode z = new TreeNode("tree", "here"); TreeNode zc = new TreeNode("tree child", "not here"); TreeNode za = new TreeNode("another tree", "here"); z.setLevel(3); z.addChild(zc); z.addChild(za); z.Print(filewrite); */ } } class TreeStackElement { private TreeNode element; private TreeStackElement below; TreeStackElement(TreeNode node, TreeStackElement next) { element = node; below = next; } public TreeNode getNode() { return element; } public TreeStackElement getBelow() { return below; } public void setBelow(TreeStackElement newbelow) { this.below = newbelow; } } class TreeStack { /* Naive stack. Doesn't check for empty pops */ TreeStackElement top; TreeStackElement temp; public void push(TreeStackElement newnode) { newnode.setBelow(top); this.top = newnode; } public TreeStackElement pop() { this.temp = top; this.top = top.getBelow(); return temp; } TreeStack(TreeStackElement base) { this.top = base; } } class TreeNode { private String label; // what kind of block is this? private String location; // where in the source was this construction found? private TreeNode[] children; // holds children of this tree private int numchildren; //keeps track of the number of children private int level; // used to print dots when printing tree /* Constructor */ TreeNode(String name, String loc) { label = name; location = loc; children = new TreeNode[10]; numchildren = 0; } TreeNode(String name, String loc, int kids) { label = name; location = loc; children = new TreeNode[kids]; numchildren = 0; } /* Sets the level of the tree, i.e. how many dots to print */ public void setLevel(int newlev) { this.level = newlev; for (int i = 0; i < numchildren; i++) { children[i].setLevel(newlev+1); } } /* Adds a child to this tree */ public void addChild(TreeNode newchild) { for (int i = numchildren-1; i > -1; i--) { children[i+1] = children[i]; } children[0] = newchild; numchildren++; newchild.setLevel(this.level+1); } /* Prints the tree to file specified by fout*/ public void Print(FileOutputStream fout) { // print .'s for each level PrintStream out = System.out; if(level == 0) { out.print("-----------------"); out.println(); } for (int i = 0; i < level; i++) { try { out.print(". "); } catch(Exception e) {} } try { out.print(this.label); // print label out.print("(" + this.numchildren + ")"); out.print(" @ " + this.location); out.println(); } catch(Exception e) {System.out.println("Write Error!");} for (int i = 0; i < numchildren; i++) { children[i].Print(fout); } if (level==0) { out.print("-----------------"); out.println(); } } /** Added for proj 2: Constrainer Access methods */ public String getLabel() { return label; } public int getNumKids() { return numchildren; } public TreeNode[] getKids() { return children; } } /* Class Parser: Implements the syntax analyzing part of the parser */ class Parser { /* utility variables and data structures */ TreeStack forest; /* stack of trees */ String justRead = ""; /* last read token from Lexical Analyzer */ String justReadLoc = ""; int justReadLine; int justReadCol; String fd = ""; /* name of file to be parsed */ Lexical lex; /* Lexical analyzer being used */ int readcount = 0; Parser(String file) { lex = new Lexical(file); lex.readNext(); justRead = lex.nextTk(); justReadLoc = lex.getLoc(); justReadLine = lex.curr_line; justReadCol = lex.curr_col; lex.readNext(); forest = new TreeStack(new TreeStackElement(new TreeNode("base", "L0/C0"), null)); fd = file; } public void finish(FileOutputStream fos) { TreeNode temp = forest.pop().getNode(); DecTable table = new DecTable(); table = Constrainer.Constrain(temp, table); Attributes a = new Attributes(); a = CodeGenerator.GenerateCode(temp, a); a.DumpCode(fos); } public static void main(String[] args) { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String fd = args[0]; char x = ' '; /* do { try { x = (char) in.read(); } catch(Exception e) {} if (!Character.isWhitespace(x)) fd = fd + x; } while(!Character.isWhitespace(x)); */ FileOutputStream filewrite = null; try { filewrite = new FileOutputStream("_CODE"); } catch(Exception e) {} Parser parse = new Parser(fd); try { parse.Tiny(); parse.finish(filewrite); } catch(RuntimeException r){ } } public void buildTree(String name, int n) { /* pops n TreeStackElements from the stack, builds a new TreeNode with name with the TreeNodef's contained in the stack elements as children, then pushes this new treenode onto the stack */ TreeNode newTree = new TreeNode(name, "L0/C0", n); // Create new tree for (int i = 0; i < n; i++) // add n children from stack { newTree.addChild(forest.pop().getNode()); } TreeStackElement newElement = new TreeStackElement(newTree, null); // push new tree on stack forest.push(newElement); } public void buildTree(String name, int n, String loc) { /* overloaded buildTree. does the same as above, but puts the location in the new tree */ TreeNode newTree = new TreeNode(name, loc, n); // Create new tree for (int i = 0; i < n; i++) // add n children from stack { newTree.addChild(forest.pop().getNode()); } TreeStackElement newElement = new TreeStackElement(newTree, null); // push new tree on stack forest.push(newElement); } public boolean checkToken(String token) { /* Checks to see if the last token read is the same as the expected token */ if (token.equals("")) { char[] temp = justRead.toCharArray(); for (int i = 0; i < temp.length; i++) { if (!(((temp[i] >= 'a') && (temp[i] <= 'z')) || ((temp[i] >= 'A') && (temp[i] <= 'Z')) || ((temp[i] >= '1') && (temp[i] <= '9') && i != 0) || temp[i] == '_')) { return false; } } return true; } if (token.equals("")) { char[] temp = justRead.toCharArray(); for (int i = 0; i < temp.length; i++) { if (!Character.isDigit(temp[i])) { return false; } } return true; } if (token.equals(justRead)) { return true; } else { return false; } } public void Read(String token) throws RuntimeException { /* Consumes the last read token, causes the lex to read the next token */ if (checkToken(token)) { justRead = lex.nextTk(); justReadLoc = lex.getLoc(); justReadLine = lex.next_token_line; justReadCol = lex.next_token_col; lex.readNext(); readcount++; } else { //System.out.println("Parse Error"); //System.out.println("Expected " + token + " Received " + justRead + " " + readcount); PrintStream error = System.out; error.println("****** syntax error @line " + justReadLine + ", column " + (justReadCol + justRead.length())); error.println("*** Parse Error"); throw new RuntimeException(); } } /************************************************************************************ * Here's the big stuff. The functions that simulate the productions of the grammar ** ************************************************************************************/ public void Name() { /* Name -> '' */ // System.out.print(" Name"); TreeNode iden = new TreeNode("", justReadLoc); iden.addChild(new TreeNode(justRead, justReadLoc)); TreeStackElement temp = new TreeStackElement(iden, null); forest.push(temp); Read(""); } public void Id() { /* Id -> '*' Name -> '&' Name -> Name */ // System.out.print(" Id"); if (checkToken("*")) { Read("*"); Name(); buildTree("*", 1); } else { if (checkToken("&")) { Read("&"); Name(); buildTree("&", 1); } else { Name(); } } } public void Initializer() { /* Initializer -> '' -> '&' Name */ // System.out.print(" Init"); if (checkToken("")) { TreeNode iden = new TreeNode("", justReadLoc); iden.addChild(new TreeNode(justRead, justReadLoc)); TreeStackElement temp = new TreeStackElement(iden, null); forest.push(temp); Read(""); } else { Read("&"); Name(); buildTree("&", 1); } } public void Atom() { /* Atom -> 'eof' -> '' -> '(' Expression ')' -> Id */ // System.out.print(" atom"); if (checkToken("eof")) { //System.out.println(justRead); TreeNode iden = new TreeNode("eof", justReadLoc); TreeStackElement temp = new TreeStackElement(iden, null); forest.push(temp); Read("eof"); } else { if (checkToken("")) { TreeNode iden = new TreeNode("", justReadLoc); iden.addChild(new TreeNode(justRead, justReadLoc)); TreeStackElement temp = new TreeStackElement(iden, null); forest.push(temp); Read(""); } else { if (checkToken("(")) { Read("("); Expression(); Read(")"); } else { Id(); } } } } public void Primary() { /* Primary -> '-' Primary -> '+' Primary -> '!' Primary -> Atom */ // System.out.print(" primary"); if (checkToken("-")) { Read("-"); Primary(); buildTree("-", 1); } else { if (checkToken("+")) { Read("+"); Primary(); } else { if (checkToken("!")) { Read("!"); Primary(); buildTree("!", 1); } else { Atom(); } } } } public void Exp() { /* Exp -> Primary '**' Exp -> Primary */ // System.out.print(" Exp"); Primary(); if (checkToken("**")) { String here = justReadLoc; Read("**"); Exp(); buildTree("**", 2, here); } } public void Factor() { /* Factor -> Exp '*' Factor -> Exp '/' Factor -> Exp '%' Factor -> Exp */ // System.out.print(" Factor"); Exp(); if (checkToken("*")) { Read("*"); Factor(); buildTree("*", 2); } else { if (checkToken("/")) { Read("/"); Factor(); buildTree("/", 2); } else { if (checkToken("%")) { Read("%"); Factor(); buildTree("%", 2); } } } } public void Term() { /* Term -> Term '+' Factor -> Term '-' Factor -> Factor */ Factor(); while(checkToken("+") || checkToken("-")) { if (checkToken("+")) { Read("+"); Factor(); buildTree("+", 2); } else { if (checkToken("-")) { Read("-"); Factor(); buildTree("-", 2); } } } } public void Comparison() { /* Comparison -> Term '<=' Term -> Term '==' Term -> Term '>=' Term -> Term '!=' Term -> Term '<' Term -> Term '>' Term -> Term */ // System.out.print(" Comparison"); Term(); if (checkToken("<=")) { String here = justReadLoc; Read("<="); Term(); buildTree("<=", 2, here); } else { if (checkToken("==")) { String here = justReadLoc; Read("=="); Term(); buildTree("==", 2, here); } else { if (checkToken(">=")) { String here = justReadLoc; Read(">="); Term(); buildTree(">=", 2, here); } else { if (checkToken("!=")) { String here = justReadLoc; Read("!="); Term(); buildTree("!=", 2, here); } else { if (checkToken("<")) { String here = justReadLoc; Read("<"); Term(); buildTree("<", 2, here); } else { if (checkToken(">")) { String here = justReadLoc; Read(">"); Term(); buildTree(">", 2, here); } } } } } } } public void LExpression() { /* LExpression -> LExpression '&&' Comparison -> LExpression '||' Comparison -> LExpression '~' Comparison -> Comparison */ //System.out.print(" lexpress"); Comparison(); while(checkToken("&&") || checkToken("||") || checkToken("~")) { if (checkToken("&&")) { String here = justReadLoc; Read("&&"); Comparison(); buildTree("and", 2, here); } else { if (checkToken("||")) { String here = justReadLoc; Read("||"); Comparison(); buildTree("or", 2, here); } else { if (checkToken("~")) { String here = justReadLoc; Read("~"); Comparison(); buildTree("xor~", 2, here); } } } } } public void Expression() { /* Expression -> LExpression '?' LExpression ':' LExpression -> LExpression */ //System.out.print(" express"); LExpression(); if (checkToken("?")) { Read("?"); LExpression(); Read(":"); LExpression(); buildTree("?", 3); } } public void Assignment() { //System.out.print(" assign"); Id(); Read("="); Expression(); buildTree("assign", 2); } public void Case() { /* Case -> 'case' '' ':' Block */ //System.out.print(" case"); String here = justReadLoc; Read("case"); TreeNode iden = new TreeNode("", justReadLoc); iden.addChild(new TreeNode(justRead, justReadLoc)); TreeStackElement temp = new TreeStackElement(iden, null); forest.push(temp); Read(""); Read(":"); Block(); buildTree("", 2, here); } public void Block() { /* Block -> '{' Statement* '}' */ // System.out.print(" block"); int N = 0; Read("{"); while(!checkToken("}")) { Statement(); N++; } Read("}"); buildTree("block", N); } public void Params() { /* Params -> '(' DclnList ? ')' */ //System.out.print(" params"); int N = 0; Read("("); if (checkToken("int")) { DclnList(); N = 1; } Read(")"); buildTree("params", N); } public void Function() { /* Function -> 'proc' Name Params '{' Dclns Statement* '}' */ //System.out.print(" function"); int N = 0; String here = justReadLoc; Read("proc"); Name(); Params(); Read("{"); Dclns(); while (!checkToken("}")) { Statement(); N++; } Read("}"); buildTree("function", N+3, here); } public void Dcln() { /* Dcln -> Id '=' Initializer -> Id */ // System.out.print(" dcln"); Id(); if (checkToken("=")) { Read("="); Initializer(); buildTree("=", 2); } } public void DclnList() { /* DclnList -> 'int Dcln list ',' */ //System.out.print(" dclnlist"); int N = 1; String here = justReadLoc; Read("int"); Dcln(); while(checkToken(",")) { Read(","); Dcln(); N++; } buildTree("dcln", N, here); } public void Dclns() { /* Dclns -> DclnList ';' -> */ //System.out.print(" dclns"); int N = 0; while(checkToken("int")) { DclnList(); Read(";"); N++; } buildTree("dclns", N); } public void Tiny() { /* Tiny -> Dclns Function+ */ /* Also, Tiny is the start symbol of the grammar */ Dclns(); int N = 1; do { Function(); N++; } while(checkToken("proc")); buildTree("program", N); if (!checkToken("@")) { Read("hi"); } } public void Statement() { int N = 0; if (checkToken("print")) { //System.out.print(" print"); String here = justReadLoc; Read("print"); Read("("); N = 1; Expression(); while(checkToken(",")) { Read(","); Expression(); N++; } Read(")"); Read(";"); buildTree("print", N, here); } else { if (checkToken("scan")) { //System.out.print(" scan"); String here = justReadLoc; Read("scan"); Read("("); N = 1; Id(); while(checkToken(",")) { Read(","); Id(); N++; } Read(")"); Read(";"); buildTree("scan", N, here); } else { if (checkToken("if")) { //System.out.println(" if"); String here = justReadLoc; Read("if"); Read("("); Expression(); Read(")"); Statement(); N=2; if (checkToken("else")) { Read("else"); Statement(); N++; } buildTree("if", N, here); } else { if (checkToken("while")) { String here = justReadLoc; Read("while"); Read("("); Expression(); Read(")"); Statement(); buildTree("while", 2, here); } else { if (checkToken("for")) { String here = justReadLoc; Read("for"); Read("("); Assignment(); Read(";"); Expression(); Read(";"); Assignment(); Read(")"); Statement(); buildTree("for", 4, here); } else { if (checkToken("do")) { String here = justReadLoc; Read("do"); Statement(); Read("while"); Expression(); Read(";"); buildTree("do", 2, here); } else { if (checkToken("switch")) { N = 0; String here = justReadLoc; Read("switch"); Read("("); Term(); Read(")"); Read("{"); do { Case(); N++; } while(checkToken("case")); Read("default"); Read(":"); Block(); Read("}"); buildTree("case", N+2, here); } else { if (checkToken("{")) Block(); else { if (checkToken(";")) { Read(";"); buildTree("", 0); } else { /* Peek at second token in buffer to see whether to produce call */ if (lex.nextTk().equals("(")) { Name(); Read("("); N=1; if (!checkToken(")")) { Expression(); N++; while (checkToken(",")) { Read(","); Expression(); N++; } } Read(")"); Read(";"); buildTree("call", N); } else { Assignment(); Read(";"); } } } } } } } } } } } } /* Begin Project 2 */ /* Constrainer Class: implements the constrainer */ class Constrainer { /* Static constrainer method. Takes a root tree node and a declaration table and checks to make sure that the tree meets the constrainer's criteria. The Declaration table is passed to allow recursion. */ static boolean foundmain = false; public static DecTable Constrain(TreeNode tree, DecTable table) { if (tree.getLabel().equals("program")) { table.OpenScope(); for (int i = 0; i < tree.getNumKids(); i++) { table = Constrain(tree.getKids()[i], table); } if (!foundmain) System.out.println("No function 'main' in program."); table.CloseScope(); return table; } else { if (tree.getLabel().equals("dcln")) { for (int i = 0; i < tree.getNumKids(); i++) { if (tree.getKids()[i].getLabel().equals("*")) { table.Enter(tree.getKids()[i].getKids()[0], "int"); } else { if (tree.getKids()[i].getLabel().equals("=")) { table.Enter(tree.getKids()[i].getKids()[0], "int"); } else { if (tree.getKids()[i].getLabel().equals("&")) { System.out.println("Cannot declare addresses"); } else { table.Enter(tree.getKids()[i], "int"); } } } } return table; } else { if (tree.getLabel().equals("function")) { if (foundmain) { System.out.println("main not the last function"); return table; } TreeNode param = tree.getKids()[1]; if (param.getNumKids() > 0) { TreeNode decn = param.getKids()[0]; int args = decn.getNumKids(); table.Enter(tree.getKids()[0], "proc" + args); } else { table.Enter(tree.getKids()[0], "proc0"); } if (tree.getKids()[0].getKids()[0].getLabel().equals("main")) { foundmain = true; } table.OpenScope(); for (int i = 1; i < tree.getNumKids(); i++) { table = Constrain(tree.getKids()[i], table); } table.CloseScope(); return table; } else { if (tree.getLabel().equals("call")) { int args = tree.getNumKids() - 1; String name = tree.getKids()[0].getKids()[0].getLabel(); if (table.Lookup(name) == null) { System.out.println("Function " + name + " is used before it is declared."); } if (!table.LookupType(name).equals("proc" + args)) { System.out.println("Incorrect number of arguments for function call or " + name + " not a function."); } for (int i = 1; i < tree.getNumKids(); i++) { table = Constrain(tree.getKids()[i], table); } return table; } else { if (tree.getLabel().equals("")) { String name = tree.getKids()[0].getLabel(); if (table.Lookup(name) == null) { System.out.println("Variable " + name + " is undeclared."); } if (!table.LookupType(name).equals("int")) { System.out.println("Variable " + name + " not of type int."); } return table; } } } } } if ((tree.getLabel().equals("assign") || tree.getLabel().equals("scan") || tree.getLabel().equals("=")) && tree.getKids()[0].getLabel().equals("&")) { System.out.println("Cannot assign values to addresses."); } for (int i = 0; i < tree.getNumKids(); i++) { table = Constrain(tree.getKids()[i], table); } return table; } } /* Table to hold Current Declarations */ class CurrDecTable { CurrDecTableItem[] table; int lastDec; int tableSize; CurrDecTable(int size) { table = new CurrDecTableItem[size]; for (int i = 0; i < size; i++) { table[i] = new CurrDecTableItem(null, 0, null); } lastDec = 0; tableSize = size; } /* Add: Adds a new declaration to the table current declaration table */ public void Add(String name, int value, String type) { if (lastDec+1 == tableSize) { CurrDecTableItem[] temp = new CurrDecTableItem[2*tableSize]; for (int i = 0; i < tableSize; i++) { temp[i] = table[i]; } tableSize = tableSize*2; table = temp; } table[lastDec+1] = new CurrDecTableItem(name, value, type); lastDec++; } /* Changes an existing declaration in the current declaration table */ public void Change(String name, int value, String type) { for (int i = 1; i <= lastDec; i++) { if (table[i].getName() != null && table[i].getName().equals(name)) { table[i].setValue(value); table[i].setType(type); } } } /* Removes a declaration from the current declaration table (its only valid scope was closed) */ public void Remove(String name) { for (int i = 1; i <= lastDec; i++) { if (table[i].getName() != null && table[i].getName().equals(name)) { table[i] = new CurrDecTableItem(null, 0, null); } } } /* Returns the location of the most recent declaration of this variable */ public int CheckVal(String name) { for (int i = 1; i <= lastDec; i++) { if (table[i].getName() != null && table[i].getName().equals(name)) { return table[i].getValue(); } } return 0; } /* Returns the type of the most recent declaration of this varaible (int or proc) */ public String CheckType(String name) { for (int i = 1; i <= lastDec; i++) { if (table[i].getName() != null && table[i].getName().equals(name)) { return table[i].getType(); } } return null; } } class CurrDecTableItem { private String name; private int value; private String type; /* Either int or proc. For proc, also includes a # indicating the number of arguments to take. e.g. proc2, proc0, proc57, etc. */ CurrDecTableItem(String n, int v, String t) { this.name = n; this.value = v; this.type = t; } public int getValue() { return value; } public void setValue(int v) { this.value = v; } public String getName() { return name; } public String getType() { return type; } public void setType(String t) { this.type = t; } } /* The declaration Table */ class DecTable { private int currScope; private int lastDec; private DecTableItem[] table; private CurrDecTable currDec; DecTable() { this.table = new DecTableItem[1000]; for (int i = 0; i < 1000; i++) { table[i] = new DecTableItem(null, 0, null, null); } currScope = 0; lastDec = -1; currDec = new CurrDecTable(100); } /* Adds a declaration to the table */ public void Enter(TreeNode where, String type) /* 'where' should be a identifier node */ { /* If array is full, double its size */ if (lastDec == table.length) { DecTableItem[] temp = new DecTableItem[2*table.length]; for (int i = 0; i < table.length; i++) { temp[i] = table[i]; } for (int i = table.length; i < temp.length; i++) { temp[i] = new DecTableItem(null, 0, null, null); } table = temp; } String name = where.getKids()[0].getLabel(); int prior = currDec.CheckVal(name); String ptype = currDec.CheckType(name); table[lastDec+1] = new DecTableItem(name, prior, where, ptype); lastDec++; if (prior > currScope) { System.out.println("Error: Variable " + name + " already declared in this scope."); } if (prior == 0) { currDec.Add(name, lastDec, type); } else { currDec.Change(name, lastDec, type); } } /* Opens a new scope */ public void OpenScope() { table[lastDec+1] = new DecTableItem("scope", currScope, null, null); lastDec++; currScope = lastDec; } /* Closes the current scope */ public void CloseScope() { for (int i = currScope+1; i <= lastDec; i++) { if (table[i].getPrior() == 0) { currDec.Remove(table[i].getName()); } else { currDec.Change(table[i].getName(), table[i].getPrior(), table[i].getType()); } } lastDec = currScope-1; currScope = table[currScope].getPrior(); } /* Looks up the last declaration of the variable specified by name */ public TreeNode Lookup(String name) { int here = currDec.CheckVal(name); return table[here].getDcln(); } public String LookupType(String name) { return currDec.CheckType(name); } } class DecTableItem { private String Name; /* Variable's name */ private int Prior; /* Location in declaration table of last declaration of this variable */ private TreeNode Dcln; /* Tree location of the declaration of this variable */ private String Type; /* type of the prior declaration of this variable (if any) */ DecTableItem(String name, int prior, TreeNode dcln, String type) { this.Name = name; this.Prior = prior; this.Dcln = dcln; this.Type = type; } public String getName() { return Name; } public int getPrior() { return Prior; } public TreeNode getDcln() { return Dcln; } public String getType() { return Type; } } class CodeGenerator { public static Attributes GenerateCode(TreeNode root, Attributes a) { if (root.getLabel().equals("program")) { a.table.OpenScope(); a = GenerateCode(root.getKids()[0], a); a.table.NotGlobal(); a.code[a.next] = new CodeLine("GOTO", "L0"); a.next++; for (int i = 1; i < root.getNumKids(); i++) { a = GenerateCode(root.getKids()[i], a); } a.table.CloseScope(); a.code[a.next] = new CodeLine("HALT"); a.next++; return a; } else { if (root.getLabel().equals("dcln")) { for (int i = 0; i < root.getNumKids(); i++) { if (root.getKids()[i].getLabel().equals("*")) { a.table.Enter(root.getKids()[i].getKids()[0].getKids()[0].getLabel(), Labeller.frameSize); } else { if (root.getKids()[i].getLabel().equals("=")) { a.table.Enter(root.getKids()[i].getKids()[0].getKids()[0].getLabel(), Labeller.frameSize); } else { a.table.Enter(root.getKids()[i].getKids()[0].getLabel(), Labeller.frameSize); } } a.code[a.next] = new CodeLine("LIT", "0"); a.next++; if (root.getKids()[i].getLabel().equals("=")) { a = GenerateCode(root.getKids()[i], a); } a.top++; Labeller.IncFrame(); } return a; } else { if (root.getLabel().equals("=")) { a = GenerateCode(root.getKids()[1], a); if (a.table.IsGlobal(root.getKids()[0].getKids()[0].getLabel())) { a.code[a.next] = new CodeLine("SGV", "" + a.table.Lookup(root.getKids()[0].getKids()[0].getLabel())); } else { a.code[a.next] = new CodeLine("SLV", "" + a.table.Lookup(root.getKids()[0].getKids()[0].getLabel())); } a.next++; a.top--; Labeller.DecFrame(); return a; } else { if (root.getLabel().equals("function")) { int label = 0; if (root.getKids()[0].getKids()[0].getLabel().equals("main")) { a.code[a.next] = new CodeLine("L0", "NOP", "", ""); a.next++; } else { label = Labeller.currLabel+1; a.table.Enter(root.getKids()[0].getKids()[0].getLabel(), label); a.code[a.next] = new CodeLine(Labeller.MakeLabel(), "NOP", "", ""); a.next++; } a.table.OpenScope(); if (!root.getKids()[0].getKids()[0].getLabel().equals("main")) Labeller.OpenFrame(); for (int i = 1; i < root.getNumKids(); i++) { a = GenerateCode(root.getKids()[i], a); } if (!root.getKids()[0].getKids()[0].getLabel().equals("main")) { a.code[a.next] = new CodeLine("RTN", "0"); a.next++; a.code[a.next] = new CodeLine("GOTO", "L" + label); a.next++; } a.table.CloseScope(); if (!root.getKids()[0].getKids()[0].getLabel().equals("main")) Labeller.CloseFrame(); return a; } else { if (root.getLabel().equals("print")) { for (int i = 0; i < root.getNumKids(); i++) { a = GenerateCode(root.getKids()[i], a); a.code[a.next] = new CodeLine("SOS", "OUTPUT"); a.next++; a.top--; Labeller.DecFrame(); } return a; } else { if (root.getLabel().equals("scan")) { for (int i = 0; i < root.getNumKids(); i++) { a.code[a.next] = new CodeLine("SOS", "INPUT"); a.next++; if (a.table.IsGlobal(root.getKids()[i].getKids()[0].getLabel())) { a.code[a.next] = new CodeLine("SGV", "" + a.table.Lookup(root.getKids()[i].getKids()[0].getLabel())); } else { a.code[a.next] = new CodeLine("SLV", "" + a.table.Lookup(root.getKids()[i].getKids()[0].getLabel())); } a.next++; } return a; } else { if (root.getLabel().equals("if") || root.getLabel().equals("?")) { a = GenerateCode(root.getKids()[0], a); String t = Labeller.MakeLabel(); String f = Labeller.MakeLabel(); String end = Labeller.MakeLabel(); a.code[a.next] = new CodeLine("COND", t, f); a.next++; a.top--; Labeller.DecFrame(); a.code[a.next] = new CodeLine(t, "NOP", "", ""); a.next++; a = GenerateCode(root.getKids()[1], a); a.code[a.next] = new CodeLine("GOTO", end); a.next++; a.code[a.next] = new CodeLine(f, "NOP", "", ""); a.next++; if (root.getNumKids() > 2) { a = GenerateCode(root.getKids()[2], a); } a.code[a.next] = new CodeLine(end, "NOP", "", ""); a.next++; return a; } else { if (root.getLabel().equals("while")) { String loop = Labeller.MakeLabel(); a.code[a.next] = new CodeLine(loop, "NOP", "", ""); a.next++; a = GenerateCode(root.getKids()[0], a); String t = Labeller.MakeLabel(); String f = Labeller.MakeLabel(); a.code[a.next] = new CodeLine("COND", t, f); a.top--; Labeller.DecFrame(); a.next++; a.code[a.next] = new CodeLine(t, "NOP", "", ""); a.next++; a = GenerateCode(root.getKids()[1], a); a.code[a.next] = new CodeLine("GOTO", loop); a.next++; a.code[a.next] = new CodeLine(f, "NOP", "", ""); a.next++; return a; } else { if (root.getLabel().equals("assign")) { a = GenerateCode(root.getKids()[1], a); if (root.getKids()[0].getLabel().equals("*")) { if (a.table.IsGlobal(root.getKids()[0].getKids()[0].getKids()[0].getLabel())) { a.code[a.next] = new CodeLine("SGIV", "" + a.table.Lookup(root.getKids()[0].getKids()[0].getKids()[0].getLabel())); } else { a.code[a.next] = new CodeLine("SLIV", "" + a.table.Lookup(root.getKids()[0].getKids()[0].getKids()[0].getLabel())); } } else { if (a.table.IsGlobal(root.getKids()[0].getKids()[0].getLabel())) { a.code[a.next] = new CodeLine("SGV", "" + a.table.Lookup(root.getKids()[0].getKids()[0].getLabel())); } else { a.code[a.next] = new CodeLine("SLV", "" + a.table.Lookup(root.getKids()[0].getKids()[0].getLabel())); } } a.next++; a.top--; Labeller.DecFrame(); return a; } else { if (root.getLabel().equals("for")) { a = GenerateCode(root.getKids()[0], a); String loop = Labeller.MakeLabel(); a.code[a.next] = new CodeLine(loop, "NOP", "", ""); a.next++; a = GenerateCode(root.getKids()[1], a); String t = Labeller.MakeLabel(); String f = Labeller.MakeLabel(); a.code[a.next] = new CodeLine("COND", t, f); a.next++; a.top--; Labeller.DecFrame(); a.code[a.next] = new CodeLine(t, "NOP", "", ""); a.next++; a = GenerateCode(root.getKids()[3], a); a = GenerateCode(root.getKids()[2], a); a.code[a.next] = new CodeLine("GOTO", loop); a.next++; a.code[a.next] = new CodeLine(f, "NOP", "", ""); a.next++; return a; } else { if (root.getLabel().equals("do")) { String loop = Labeller.MakeLabel(); a.code[a.next] = new CodeLine(loop, "NOP", "", ""); a.next++; a = GenerateCode(root.getKids()[0], a); a = GenerateCode(root.getKids()[1], a); String f = Labeller.MakeLabel(); a.code[a.next] = new CodeLine("COND", loop, f); a.top--; Labeller.DecFrame(); a.next++; a.code[a.next] = new CodeLine(f, "NOP", "", ""); a.next++; return a; } else { if (root.getLabel().equals("and") || root.getLabel().equals("or") || root.getLabel().equals("xor")) { a = GenerateCode(root.getKids()[0], a); a = GenerateCode(root.getKids()[1], a); if (root.getLabel().equals("and")) { a.code[a.next] = new CodeLine("BOP", "BAND"); a.next++; } if (root.getLabel().equals("or")) { a.code[a.next] = new CodeLine("BOP", "BOR"); a.next++; } if (root.getLabel().equals("xor")) { a.code[a.next] = new CodeLine("LLV", "" + (a.top-1)); a.next++; a.code[a.next] = new CodeLine("LLV", "" + (a.top-2)); a.next++; a.code[a.next] = new CodeLine("BOP", "BOR"); a.next++; a.code[a.next] = new CodeLine("LLV", "" + (a.top-1)); a.next++; a.code[a.next] = new CodeLine("LLV", "" + (a.top-2)); a.next++; a.code[a.next] = new CodeLine("BOP", "BAND"); a.next++; a.code[a.next] = new CodeLine("UOP", "UNOT"); a.next++; a.code[a.next] = new CodeLine("BOP", "BAND"); a.next++; a.code[a.next] = new CodeLine("SLV", "" + (a.top-2)); a.next++; a.code[a.next] = new CodeLine("POP", "1"); a.next++; } a.top--; Labeller.DecFrame(); return a; } else { if (root.getLabel().equals("<=") || root.getLabel().equals("==") || root.getLabel().equals(">=") || root.getLabel().equals("!=") || root.getLabel().equals("<") || root.getLabel().equals(">")) { a = GenerateCode(root.getKids()[0], a); a = GenerateCode(root.getKids()[1], a); if (root.getLabel().equals("<=")) a.code[a.next] = new CodeLine("BOP", "BLE"); if (root.getLabel().equals("==")) a.code[a.next] = new CodeLine("BOP", "BEQ"); if (root.getLabel().equals(">=")) a.code[a.next] = new CodeLine("BOP", "BGE"); if (root.getLabel().equals("!=")) a.code[a.next] = new CodeLine("BOP", "BNE"); if (root.getLabel().equals("<")) a.code[a.next] = new CodeLine("BOP", "BLT"); if (root.getLabel().equals(">")) a.code[a.next] = new CodeLine("BOP", "BGT"); a.next++; a.top--; Labeller.DecFrame(); return a; } else { if (root.getLabel().equals("+") || (root.getLabel().equals("-") && root.getNumKids() == 2) || (root.getLabel().equals("*") && root.getNumKids() == 2) || root.getLabel().equals("/") || root.getLabel().equals("%") || root.getLabel().equals("**")) { a = GenerateCode(root.getKids()[0], a); a = GenerateCode(root.getKids()[1], a); if (root.getLabel().equals("+")) a.code[a.next] = new CodeLine("BOP", "BPLUS"); if (root.getLabel().equals("-")) a.code[a.next] = new CodeLine("BOP", "BMINUS"); if (root.getLabel().equals("*")) a.code[a.next] = new CodeLine("BOP", "BMULT"); if (root.getLabel().equals("/")) a.code[a.next] = new CodeLine("BOP", "BDIV"); if (root.getLabel().equals("%")) a.code[a.next] = new CodeLine("BOP", "BMOD"); if (root.getLabel().equals("**")) a.code[a.next] = new CodeLine("BOP", "BEXP"); a.next++; a.top--; Labeller.DecFrame(); return a; } else { if ((root.getLabel().equals("-") && root.getNumKids() == 1) || root.getLabel().equals("!")) { a = GenerateCode(root.getKids()[0], a); if (root.getLabel().equals("-")) a.code[a.next] = new CodeLine("UOP", "UNEG"); if (root.getLabel().equals("!")) a.code[a.next] = new CodeLine("UOP", "UNOT"); a.next++; return a; } else { if (root.getLabel().equals("")) { a.code[a.next] = new CodeLine("LIT", root.getKids()[0].getLabel()); a.next++; a.top++; Labeller.IncFrame(); return a; } else { if (root.getLabel().equals("")) { if (a.table.IsGlobal(root.getKids()[0].getLabel())) { a.code[a.next] = new CodeLine("LGV", "" + a.table.Lookup(root.getKids()[0].getLabel())); } else { a.code[a.next] = new CodeLine("LLV", "" + a.table.Lookup(root.getKids()[0].getLabel())); } a.next++; a.top++; Labeller.IncFrame(); return a; } else { if (root.getLabel().equals("call")) { for (int i = 1; i < root.getNumKids(); i++) { a = GenerateCode(root.getKids()[i], a); Labeller.DecFrame(); /* because the previous line increments it, and we want those values to be passed */ } a.code[a.next] = new CodeLine("CODE", "L" + a.table.Lookup(root.getKids()[0].getKids()[0].getLabel())); a.next++; a.code[a.next] = new CodeLine("CALL", "" + Labeller.frameSize); a.next++; return a; } else { if (root.getLabel().equals("params")) { if (root.getNumKids() > 0) { for (int i = 0; i < root.getKids()[0].getNumKids(); i++) { if (root.getKids()[0].getKids()[i].getLabel().equals("*")) { a.table.Enter(root.getKids()[0].getKids()[i].getKids()[0].getKids()[0].getLabel(), i); } else { a.table.Enter(root.getKids()[0].getKids()[i].getKids()[0].getLabel(), i); } Labeller.IncFrame(); } } return a; } else { if ((root.getLabel().equals("*") && root.getNumKids() == 1) || root.getLabel().equals("&")) { if (root.getLabel().equals("*")) { if (a.table.IsGlobal(root.getKids()[0].getKids()[0].getLabel())) { a.code[a.next] = new CodeLine("LGIV", "" + a.table.Lookup(root.getKids()[0].getKids()[0].getLabel())); } else { a.code[a.next] = new CodeLine("LLIV", "" + a.table.Lookup(root.getKids()[0].getKids()[0].getLabel())); } } if (root.getLabel().equals("&")) { a.code[a.next] = new CodeLine("LIT", "" + a.table.Lookup(root.getKids()[0].getKids()[0].getLabel())); } a.next++; Labeller.IncFrame(); a.top++; return a; } else { if (root.getLabel().equals("case")) { a = GenerateCode(root.getKids()[0], a); String thisone = Labeller.MakeLabel(); String trynext = Labeller.MakeLabel(); String end = Labeller.MakeLabel(); a.code[a.next] = new CodeLine("GOTO", thisone); a.next++; for (int i = 1; i < root.getNumKids()-1; i++) { a.code[a.next] = new CodeLine(thisone, "DUP", "", ""); a.next++; a = GenerateCode(root.getKids()[i].getKids()[0], a); a.code[a.next] = new CodeLine("BOP", "BEQ"); a.next++; String match = Labeller.MakeLabel(); a.code[a.next] = new CodeLine("COND", match, trynext); a.next++; a.code[a.next] = new CodeLine(match, "NOP", "", ""); a.next++; a = GenerateCode(root.getKids()[i].getKids()[1], a); a.code[a.next] = new CodeLine("GOTO", end); a.next++; thisone = trynext; trynext = Labeller.MakeLabel(); } a.code[a.next] = new CodeLine(thisone, "NOP", "", ""); a.next++; a = GenerateCode(root.getKids()[root.getNumKids()-1], a); a.code[a.next] = new CodeLine(end, "POP", "1", ""); a.next++; return a; } else { if (root.getLabel().equals("eof")) { a.code[a.next] = new CodeLine("SOS", "EOF"); a.next++; a.top++; Labeller.IncFrame(); return a; } else { for (int i = 0; i < root.getNumKids(); i++) { a = GenerateCode(root.getKids()[i], a); } return a; } } } } } } } } } } } } } } } } } } } } } } } } class Attributes { int top; int next; CodeLine[] code; ModDecTable table; /* Keeps track of current location of variables in the stack */ Attributes() { top = 0; next = 0; table = new ModDecTable(); code = new CodeLine[10000]; } public void DumpCode(FileOutputStream fos) { PrintStream out = new PrintStream(fos); for (int i = 0; code[i] != null; i++) { out.println(code[i].Print()); } } } class Labeller { static int frameSize = 0; static Stack frameStack = new Stack(); static String noLabel = ""; static int currLabel = 0; public static void OpenFrame() { frameStack.push(new Integer(frameSize)); frameSize = 0; } public static void CloseFrame() { frameSize = ((Integer) frameStack.pop()).intValue(); } public static void IncFrame() { frameSize++; } public static void DecFrame() { frameSize--; } public static String MakeLabel() { currLabel++; return "L" + currLabel; } } class CodeLine { private String Label; private String Instr; private String Op1; private String Op2; CodeLine(String i) { this.Label = ""; this.Instr = i; this.Op1 = ""; this.Op2 = ""; } CodeLine(String i, String o1) { this.Label = ""; this.Instr = i; this.Op1 = o1; this.Op2 = ""; } CodeLine(String i, String o1, String o2) { this.Label = ""; this.Instr = i; this.Op1 = o1; this.Op2 = o2; } CodeLine(String l, String i, String o1, String o2) { this.Label = l; this.Instr = i; this.Op1 = o1; this.Op2 = o2; } public void SetLabel(String l) { this.Label = l; } public void SetInstr(String i) { this.Instr = i; } public void SetOp1(String o1) { this.Op1 = o1; } public void SetOp2(String o2) { this.Op2 = o2; } public String Print() { return Label + " " + Instr + " " + Op1 + " " + Op2; } } /*************************************************** Special declaration table for the code generator. Just like the one for the Constrainer, except it does not keep track of type ***************************************************/ class ModDecTable { private int currScope; private int lastDec; private boolean global; private ModDecTableItem[] table; private ModCurrDecTable currDec; ModDecTable() { this.table = new ModDecTableItem[1000]; for (int i = 0; i < 1000; i++) { table[i] = new ModDecTableItem(null, 0, 0, false); } currScope = 0; lastDec = -1; global = true; currDec = new ModCurrDecTable(100); } /* Adds a declaration to the table */ public void Enter(String name, int where) /* 'where' is stack location of identifier */ { /* If array is full, double its size */ if (lastDec == table.length) { ModDecTableItem[] temp = new ModDecTableItem[2*table.length]; for (int i = 0; i < table.length; i++) { temp[i] = table[i]; } for (int i = table.length; i < temp.length; i++) { temp[i] = new ModDecTableItem(null, 0, 0, false); } table = temp; } int prior = currDec.CheckVal(name); table[lastDec+1] = new ModDecTableItem(name, prior, where, global); lastDec++; if (prior == 0) { currDec.Add(name, lastDec); } else { currDec.Change(name, lastDec); } } /* Opens a new scope */ public void OpenScope() { table[lastDec+1] = new ModDecTableItem("scope", currScope, 0, false); lastDec++; currScope = lastDec; } /* Closes the current scope */ public void CloseScope() { for (int i = currScope+1; i <= lastDec; i++) { if (table[i].getPrior() == 0) { currDec.Remove(table[i].getName()); } else { currDec.Change(table[i].getName(), table[i].getPrior()); } } lastDec = currScope-1; currScope = table[currScope].getPrior(); } /* Looks up the last declaration of the variable specified by name */ public int Lookup(String name) { int here = currDec.CheckVal(name); return table[here].getDcln(); } public boolean IsGlobal(String name) { int here = currDec.CheckVal(name); return table[here].getGlbl(); } public void NotGlobal() { global = false; } } class ModDecTableItem { private String Name; /* Variable's name */ private int Prior; /* Location in declaration table of last declaration of this variable */ private int Dcln; /* Stack location of this variable */ private boolean Glbl; /* Whether variable is global */ ModDecTableItem(String name, int prior, int dcln, boolean glbl) { this.Name = name; this.Prior = prior; this.Dcln = dcln; this.Glbl = glbl; } public String getName() { return Name; } public int getPrior() { return Prior; } public int getDcln() { return Dcln; } public boolean getGlbl() { return Glbl; } } class ModCurrDecTable { ModCurrDecTableItem[] table; int lastDec; int tableSize; ModCurrDecTable(int size) { table = new ModCurrDecTableItem[size]; for (int i = 0; i < size; i++) { table[i] = new ModCurrDecTableItem(null, 0); } lastDec = 0; tableSize = size; } /* Add: Adds a new declaration to the table current declaration table */ public void Add(String name, int value) { if (lastDec+1 == tableSize) { ModCurrDecTableItem[] temp = new ModCurrDecTableItem[2*tableSize]; for (int i = 0; i < tableSize; i++) { temp[i] = table[i]; } tableSize = tableSize*2; table = temp; } table[lastDec+1] = new ModCurrDecTableItem(name, value); lastDec++; } /* Changes an existing declaration in the current declaration table */ public void Change(String name, int value) { for (int i = 1; i <= lastDec; i++) { if (table[i].getName() != null && table[i].getName().equals(name)) { table[i].setValue(value); } } } /* Removes a declaration from the current declaration table (its only valid scope was closed) */ public void Remove(String name) { for (int i = 1; i <= lastDec; i++) { if (table[i].getName() != null && table[i].getName().equals(name)) { table[i] = new ModCurrDecTableItem(null, 0); } } } /* Returns the location of the most recent declaration of this variable */ public int CheckVal(String name) { for (int i = 1; i <= lastDec; i++) { if (table[i].getName() != null && table[i].getName().equals(name)) { return table[i].getValue(); } } return 0; } } class ModCurrDecTableItem { private String name; private int value; ModCurrDecTableItem(String n, int v) { this.name = n; this.value = v; } public int getValue() { return value; } public void setValue(int v) { this.value = v; } public String getName() { return name; } } /**************************************** * End Code Generator's Declaration Table* *****************************************/