import java.lang.*; import java.io.*; import java.util.Random; /* * HJ version ported from Java version at http://www.csse.monash.edu.au/~lloyd/tildeProgLang/Java2/Exp/. * * @author Vincent Cave * @author Sanjay Chatterjee * @author Max Grossman * @author Vivek Sarkar (vsarkar@rice.edu) * * See below for acknowledgments for original code * * L. Allison, September 2001, * School of Computer Science and Software Engineering, * Monash University, Australia 3800. * * Released under the GNU General Public License Version 2, June 1991. */ public class MatrixEval // The main program { public static class Matrix { public final int cols; public final int rows; public final int[][] data; public Matrix(int rows, int cols) { this.rows = rows; this.cols = cols; this.data = new int[rows][cols]; } } public static Matrix matrixAdd(Matrix a, Matrix b) { int rows = a.rows; int cols = a.cols; assert (b.rows == rows && b.cols == cols) : "a and b are not conformable for operation +"; Matrix result = new Matrix(rows,cols); for (point[i,j] : [0:rows-1,0:cols-1]) result.data[i][j] = a.data[i][j] + b.data[i][j]; return result; } public static Matrix matrixMinus(Matrix a, Matrix b) { int rows = a.rows; int cols = a.cols; assert(b.rows == rows && b.cols == cols) : "a and b are not conformable for operation -"; Matrix result = new Matrix(rows,cols); for (point[i,j] : [0:rows-1,0:cols-1]) result.data[i][j] = a.data[i][j] - b.data[i][j]; return result; } public static Matrix matrixMultiply(Matrix a, Matrix b) { int arows = a.rows; int acols = a.cols; int brows = b.rows; int bcols = b.cols; if (acols != brows) { Expression.error("Invalid dimensions for matrix multiply"); } // a and b are not conformable Matrix result = new Matrix(arows,bcols); for (point[i,j] : [0:arows-1,0:bcols-1]) { result.data[i][j] = 0; for (point[k] : [0:acols-1]) { result.data[i][j] += a.data[i][k] * b.data[k][j]; } } return result; } public static Matrix matrixId(Matrix a) { int rows = a.rows; int cols = a.cols; Matrix result = new Matrix(rows,cols); for (point[i,j] : [0:rows-1,0:cols-1]) result.data[i][j] = a.data[i][j]; return result; } public static Matrix matrixNeg(Matrix a) { int rows = a.rows; int cols = a.cols; Matrix result = new Matrix(rows,cols); for (point[i,j] : [0:rows-1,0:cols-1]) result.data[i][j] = -a.data[i][j]; return result; } public static void printMatrix(Matrix a) { int rows = a.rows; int cols = a.cols; System.out.println("["); for (point[i] : [0:rows-1]) { System.out.print(" [ "); for (point[j] : [0:cols-1]) System.out.print(a.data[i][j] + " "); System.out.println("]"); } System.out.println("]"); } public static void main(String[] argv) { if (argv.length != 1) { System.out.println("usage: hj MatrixEval input_file_name"); return; } FileInputStream in = null; Expression e = null; try { in = new FileInputStream(argv[0]); Syntax syn = new Syntax(new Lexical(in)); e = syn.exp(); // parse input expression } catch (IOException io) { io.printStackTrace(); return; } System.out.print("Input expression:"); System.out.println(e.toString()); // print input expression long start = System.nanoTime(); Matrix result = e.eval(); // evaluate input expression long end = System.nanoTime(); System.out.println("result[0][0] = " + result.data[0][0]); System.out.println("Time taken for expression evaluation = " + (end-start)/1000000 + " milliseconds"); // printMatrix(result); }// main } abstract class Expression // Defines expression parse-trees { public abstract void appendSB(StringBuffer sb); // printing public abstract MatrixEval.Matrix eval(); // evaluate expression public static class Ident extends Expression // Ident { public final String id; // e.g. x public int rows, cols, seed; public Ident(String id) { this.id = id; extractDims(id); } public void appendSB(StringBuffer sb) { sb.append(id); } public void extractDims(String id) { int indexOfM = id.indexOf('m'); if(indexOfM != 0) {error("indexOfM != 0");} // ident must start with 'm' int indexOfX = id.indexOf('x'); if (indexOfX == -1) { // identity matrix case rows = Integer.parseInt(id.substring(indexOfM + 1)); if(rows <= 0) {error("rows <= 0");} cols = -1; seed = -1; } else { // random matrix case int indexOfS = id.indexOf('s'); if (indexOfX >= indexOfS) { error("indexOfX >= indexOfS"); } rows = Integer.parseInt(id.substring((indexOfM + 1), indexOfX)); if(rows <= 0) {error("rows <= 0");}; cols = Integer.parseInt(id.substring((indexOfX + 1), indexOfS)); if(cols <= 0) {error("cols <= 0");}; seed = Integer.parseInt(id.substring(indexOfS + 1)); } } public MatrixEval.Matrix eval() { MatrixEval.Matrix result; if (cols == -1) { // identity matrix case cols = rows; result = new MatrixEval.Matrix(rows,cols); for (point[i] : [0:rows-1]) result.data[i][i] = 1; } else { // random matrix case Random r = new Random(seed); result = new MatrixEval.Matrix(rows,cols); for (point[i,j] : [0:rows-1,0:cols-1]) result.data[i][j] = r.nextInt(); } return result; } } public static class IntCon extends Expression // IntCon { public final int n; // e.g. 3 public IntCon(int n) { this.n = n; } public void appendSB(StringBuffer sb) { sb.append(String.valueOf(n)); } public MatrixEval.Matrix eval() { error("Unhandled Integer scalar"); return null; } } public static class Unary extends Expression // Unary { public final int opr; public final Expression e; // e.g. -7 public Unary(int opr, Expression e) { this.e = e; this.opr = opr; } public void appendSB(StringBuffer sb) { sb.append("(" + Lexical.Symbol[opr] + " "); e.appendSB(sb); sb.append(")"); } public MatrixEval.Matrix eval() { switch (opr) { case Lexical.plus: return MatrixEval.matrixId(e.eval()); case Lexical.minus: return MatrixEval.matrixNeg(e.eval()); default: error("Unhandled Unary operator"); } return null; } }// Unary public static class Binary extends Expression // Binary { public final int opr; public final Expression lft, rgt; // e.g. x+3 public Binary(int opr, Expression lft, Expression rgt) { this.opr = opr; this.lft = lft; this.rgt = rgt; } public void appendSB(StringBuffer sb) { sb.append("("); lft.appendSB(sb); sb.append(" " + Lexical.Symbol[opr] + " "); rgt.appendSB(sb); sb.append(")"); } public MatrixEval.Matrix eval() { switch (opr) { case Lexical.plus: return MatrixEval.matrixAdd(lft.eval(), rgt.eval()); case Lexical.minus: return MatrixEval.matrixMinus(lft.eval(), rgt.eval()); case Lexical.times: return MatrixEval.matrixMultiply(lft.eval(), rgt.eval()); default: error("Unhandled binary operator"); } return null; } }// Binary /* Using a StringBuffer gives linear rather than quadratic complexity. */ public String toString() { StringBuffer sb = new StringBuffer(); // efficiency! appendSB(sb); return sb.toString(); }// toString public static void error(String msg) { System.out.println("\nError: " + msg); System.exit(1); }// error }// Expression class class Lexical // Lexical processor of symbols { InputStream inp; int sy = -1; // lexical state variables char ch = ' '; byte[] buffer = new byte[1]; boolean eof = false; String theWord = ""; int theInt = 666; public static final int // symbol codes... word = 0, numeral = 1, open = 2, // ( close = 3, // ) plus = 4, // + minus = 5, // - times = 6, // * over = 7, // / eofSy = 8; public static final String[] Symbol = new String[] { "", "", "(", ")", "+", "-", "*", "/", "" };// Symbol public Lexical(InputStream inp) // constructor { this.inp = inp; insymbol(); }// constructor public int sy() { return sy; } // Define public boolean eoi() { return sy == eofSy; } // what a public String theWord() { return theWord; } // Lexical public int theInt() { return theInt; } // object is public void insymbol() // insymbol // get the next symbol from the input stream { if (sy == eofSy) return; while (ch == ' ') getch(); // skip white space if (eof) sy = eofSy; else if (Character.isLetter(ch)) // words { StringBuffer w = new StringBuffer(); while (Character.isLetterOrDigit(ch)) { try { //Workaround compiler bug if (false) { throw new java.io.IOException(); } w.append(ch); } catch (java.io.IOException e) { } getch(); } theWord = w.toString(); sy = word; } else if (Character.isDigit(ch)) // numbers { theInt = 0; while (Character.isDigit(ch)) { theInt = theInt * 10 + ((int) ch) - ((int) '0'); getch(); } sy = numeral; } else // special symbols { int ch2 = ch; getch(); switch (ch2) { case '+': sy = plus; break; case '-': sy = minus; break; case '*': sy = times; break; // case '/': sy = over; break; case '(': sy = open; break; case ')': sy = close; break; default: error("bad symbol"); } } }// insymbol void getch() // getch // NB. changes variable ch as a side-effect. { ch = '.'; if (sy == eofSy) return; try { int n = 0; if (inp.available() > 0) n = inp.read(buffer); if (n <= 0) eof = true; else ch = (char) buffer[0]; } catch (Exception e) { } if (ch == '\n' || ch == '\t') ch = ' '; }// getch void skipRest() { if (!eof) System.out.print("skipping to end of input..."); int n = 0; while (!eof) { if (n % 80 == 0) System.out.println(); // break line System.out.print(ch); n++; getch(); } System.out.println(); }// skipRest public void error(String msg) // error { System.out.println("\nError: " + msg + " sy=" + sy + " ch=" + ch + " theWord=" + theWord + " theInt=" + theInt); skipRest(); System.exit(1); }// error }// Lexical class class Syntax { private final Lexical lex; private final long // useful Symbol Sets unOprs = (1L << Lexical.minus), binOprs = (1L << Lexical.plus) | (1L << Lexical.minus) | (1L << Lexical.times) | (1L << Lexical.over), startsExp = unOprs | (1L << Lexical.word) | (1L << Lexical.numeral) | (1L << Lexical.open); int[] oprPriority = new int[Lexical.eofSy]; void init() { for (int i = 0; i < oprPriority.length; i++) oprPriority[i] = 0; oprPriority[Lexical.plus] = 1; oprPriority[Lexical.minus] = 1; oprPriority[Lexical.times] = 2; oprPriority[Lexical.over] = 2; }// init public Syntax(Lexical lex) // constructor { this.lex = lex; init(); } private boolean syIs(int sym) // test and skip symbol { if (lex.sy() == sym) { lex.insymbol(); return true; } return false; }// syIs private void check(int sym) // check and skip a particular symbol { if (lex.sy() == sym) lex.insymbol(); else error(Lexical.Symbol[sym] + " Expected"); }// check public Expression exp() // exp() { Expression e = exp(1); check(Lexical.eofSy); return e; } private Expression exp(int priority) // exp(...) { Expression e = null; if (priority < 3) { e = exp(priority + 1); int sym = lex.sy(); while (member(sym, binOprs) && oprPriority[sym] == priority) { lex.insymbol(); // e.g. 1+2+3 e = new Expression.Binary(sym, e, exp(priority + 1)); sym = lex.sy(); } } else if (member(lex.sy(), unOprs)) // unary op, e.g. -3 { int sym = lex.sy(); lex.insymbol(); e = new Expression.Unary(sym, exp(priority)); } else // operand { switch (lex.sy()) { case Lexical.word: e = new Expression.Ident(lex.theWord); lex.insymbol(); break; case Lexical.numeral: e = new Expression.IntCon(lex.theInt); lex.insymbol(); break; case Lexical.open: // e.g. (e) lex.insymbol(); e = exp(1); check(Lexical.close); break; default: error("bad operand"); }// switch }// if return e; }// exp(...) boolean member(int n, long s) // ? is n a member of the "set" s ? { return ((1L << n) & s) != 0; } void error(String msg) { lex.error("Syntax: " + msg); } // error }// Syntax class