The class inheritance hierarchy I used is as follows: Exp: Implements all of the productions for Exp. The only method defined by Exp is the abstract method eval, which takes a rowIndex as a parameter and returns a double: abstract double eval(int rowIndex); The rowIndex is needed in case the expression has generic references. In this case the rowIndex is used to convert the generic reference to a concrete reference. For example, suppose the user has input the expression: a[id=1-3] = b[id] + c[id] and that the user wants to evaluate a[2]. a[1], a[2], and a[3] should all point to the same expression tree which means that 2 must be passed to eval so that when b[id] and c[id] get evaluated, they can use the 2 to retrieve b[2] and c[2] respectively. BinaryExp: Implements all of the productions that have a left and right operand for an Expression. DivideExp EqualsExp GreaterEqualExp GreaterThanExp LessEqualExp LessThanExp MinusExp MultiplyExp NotEqualsExp PlusExp ConditionalExp FctExp: The superclass for the min, max, and sum functions. FctExp maintains a parameter list of VarExp objects. Each VarExp object represents one of the cells referenced in the parameter list. For example, given the call "sum(a[i], b[1-3, 4, 8-9])", the parameter list would consist of VarExp objects for a[i], b[1], b[2], b[3], b[4], b[8], and b[9]. The appropriate function iterates through this list and calculates the appropriate result. The parameter list is constructed as follows: 1) if the parameter is a generic reference (e.g., b[id]), then a VarExp object is created and added to the parameter list. 2) if the parameter is a row list (e.g., b[1-3, 4, 8-9], then a list of RowRef object gets constructed by the RowList productions. The list of RowRef objects is then traversed to produce VarExp objects that get added to the parameter list. One VarExp object is produced for each referenced cell. In the above example VarExp objects would be created for b[1], b[2], b[3], b[4], b[8], and b[9]. MaxExp MinExp SumExp NumberExp UnaryMinusExp VarExp: A variable expression is a reference to either a specific cell (e.g., b[3]) or a generic cell (e.g., b[id]). A VarExp keeps track of the column's name (e.g., b) and its row index. If the reference is a generic reference then it sets the row index to -1. Here is the API: class VarExp extends Exp { // the number of rows for each column in the spreadsheet static final int NUMROWS = 100; // The hash table is keyed on the name of a column. Each column name has // a value which is an array of Cell objects, one for each row in the // column static Hashtable<String, Cell[]> varTable = new Hashtable<String, Cell[]>(); String colName; int row; static Cell getCell(String colName, int rowIndex) throws UndefinedCellException: returns a Cell object by using colName to retrieve the ccoumn's Cell array and then using the rowIndex to retrieve the specific Cell object. Throws an UndefinedCellException if the column's name is not included in the hash table or if the entry in the Cell array is null. static void setCell(String colName, int rowIndex, Exp formula): gets a Cell object by calling getCell and sets the Cell's formula variable to formula. public double eval(int rowNum) throws UndefinedCellException: Finds the appropriate Cell object using getCell and then calls the Cell's eval method. If the VarExp is a generic reference (i.e., its row index is -1) then eval uses the rowNum that is passed in to locate the cell. Otherwise eval uses rowIndex stored by VarExp. A Cell's eval method may throw an UndefinedCellException and VarExp's eval method does not handle it so the method header specifies that UndefinedCellException gets thrown. public VarExp(String id, int rowNum) { colName = id; row = rowNum; } Cell: used to record the value of a cell, the expression used to compute the cell's value, whether or not the cell has been evaluated, and whether or not the cell's value is undefined. Here is the API for a Cell: class Cell { Exp formula; boolean upToDate = false; boolean undef = false; double value = 0; public Cell(Exp expression) { formula = expression; } public void setCell(Exp expression) { formula = expression; upToDate = false; undef = false; } double eval(int rowNum) throws UndefinedCellException: If the cell's undef flag is true then the eval method throws an UndefinedCellException. Otherwise the eval method checks if the cell's value is up-to-dateby checking the upToDate flag. If the cell's value is not up-to-date, then the eval method marks it up-to-date, marks its value as undefined, and evaluates the formula. If the formula successfully evaluated, the cell is marked as defined. The reason for marking it undefined before the evaluation is that if the evaluation of the formula fails, then the cell's value should be undefined. Once the cell's value is up-to-date, its value is returned. GenericRef: used only for type checking generic references to make sure that a generic reference used on the right side of an expression (e.g., b[id]) matches the generic reference used on the left side of an expression (e.g., a[id=1-3]). Each time a generic reference is encountered, the cell name and the row name (e.g., id) is stored in a GenericRef object and the GenericRef object is added to a linked list. Once the parsing of the expression is complete, the parser iterates through the list and compares the row name with the row name used on the left side of the formula. If they do not match, the parser prints an error and throws away the formula. RowRef: Keeps track of the beginning and end of a range of rows (e.g., 3-6). UndefinedCellException: thrown when a formula is being evaluated and it references a cell that does not yet exist, or a cell whose value is marked undefined. An UndefinedCellException contains a cell name and a row number. An UndefinedCellException is caught by the parser when it tries to evaluate a formula. When caught, the parser prints out a message saying that the given cell is undefined and then a message indicating that the cell whose formula is being evaluated is undefined. reads lines of input, creates a parser object to parse each line of input, and parses the input. The parser parses the formula, and if it is correct, assigns it to a cell(s). The parser also evaluates the formula for each cell to which the formula is assigned. Here is the code for package formula; import*; import java.util.*; import formula.*; import java_cup.runtime.*; class interpreter { public static void main(String args[]) { interpreter singleton = new interpreter(); singleton.execute(); } interpreter() {} void execute() { java.util.Scanner input = new java.util.Scanner(; parser expParser; while (true) { try { System.out.print(">>> "); expParser = new parser(new Yylex(new StringReader(input.nextLine()))); expParser.parse(); } catch (java.util.NoSuchElementException e) { break; } catch (Exception e) {System.out.println(e);} } } }