Compiler Design

The purpose of this assignment is to give the student a practical introduction to the structure and usage of the foundational elements of the compiler project. The code developed here will be used throughout the rest of the semester. Creating the ADTs given below, exactly as described, is crucial to the success of the project! While there is room for individuality in the actual implementation, it is necessary that each structure utilize exactly the interfaces and storage capabilities described, in order for them to be used effectively and efficiently in the development of the rest of the project. The language required to operate with the automated testing system for all submissions is Java. Read all requirements below carefully!

Program Objectives- 1: Implement a class for wach of the following: Symbol Table, Quad Table, and Reserve Table according to the interface requirements provided below.

Main Program: The student must create their own main program for this part of the project in order to test their developed classes. A test program will be created by the instructor for the submitted Java classes to thoroughly test the ADT methods and verify that they work according to specifications. The exact mechanism to submit the code for testing via Canvas will be specified prior to the due date.

ADTs To Implement: The following ADTs must be established as separate Java classes, each according to the exacting requirements below:

1) Class SymbolTable The symbol table conceptually is a fixed index list (i.e., once a row of data has been added, its index must not change during the run of the program) consisting of an indexed list of entries, with each entry (a single row of data) containing: a name field (String type); a kind field (to hold a label, variable, or constant indicator, represented by a char, l, v, or c); a data_type field specifying the data as an integer, float, or string (represented by a char, i, f, or s); and a set of 3 value fields (integerValue, floatValue, stringValue) to hold one of these: an integer, double, or String, as specified by the data_type field. (Later, it will be clear why labels will always store their data in the integerValue field, while variables and constants may use any one of the integerValue, floatValue, stringValue storage areas based on their data_type field). The interface to the SymbolTable must implement the following methods (in addition to a constructor, as shown):

SymbolTable(int maxSize) Initializes the SymbolTable to hold maxSize rows of data.

int AddSymbol(String symbol, char kind, int value) int AddSymbol(String symbol, char kind, double value) int AddSymbol(String symbol, char kind, String value)

Three overloaded methods to add symbol with given kind and value to the end of the symbol table, automatically setting the correct data_type, and returns the index where the symbol was located. If the symbol is already in the table according to a non-case-sensitive comparison [Total matches total as well as ToTaL]with all the existing strings in the table, no change or verification is made, and this just returns the row index where the symbol was found.These methods only FAIL, and return -1, when the table already contains maxSize rows, and adding a new row would exceed this size limit.

int LookupSymbol(String symbol) Returns the index where symbol is found, or -1s if not in the table. Uses a noncase-sensitive comparison.

String GetSymbol(int index) char GetKind(int index) char GetDataType(int index) String GetString(int index) int GetInteger(int index) double GetFloat(int index) Return the various values currently stored at index.

UpdateSymbol(int index, char kind, int value) UpdateSymbol(int index, char kind, double value) UpdateSymbol(int index, char kind, String value) Overloaded methods, these set appropriate fields at the slot indicated by index.

PrintSymbolTable(String filename) Prints to a plain text file all the data in only the occupied rows of the symbol table. Must be in neat tabular format, 1 text line per row, selectively showing only the the value field (stringValue, integerValue, or floatValue) which is active for that row based on the dataType for that row.

2) Class QuadTable The QuadTable is different from the SymbolTable in its access and contents. Each fixed indexed entry row consits of four int values representing an opcode and three operands. The methods needed are:

QuadTable(maxSize) Constructor creates a new, empty QuadTable ready for data to be added, with the specified maxumum number of rows (maxSize). An array is suggested as the cleanest implementation of this, along with an int nextAvailable counter to keep track of which rows have been used.

int NextQuad() Returns the int index of the next open slot in the QuadTable. Very important during code generation, this must be implemented exactly as described, and must be the index where the next AddQuad call will put its data.

void AddQuad(int opcode, op1, op2, op3) Expands the active length of the quad table by adding a new row at the NextQuad slot, with the parameters sent as the new contents, and increments the NextQuad counter to the next available (empty) index when done.

int GetQuad(int index, int column) Returns the int data for the row and column specified at index, column.

void UpdateQuad(int index, opcode, op1, op2, op3) Changes the contents of the existing quad at index. Used only when backfilling jump addresses later, during code generation, and very important.

PrintQuadTable(String filename) Prints to the named file only the currently used contents of the Quad table in neat tabular format, one row per output text line.

3) Class ReserveTable This is a lookup table/association list ADT that will be used later for the opcode lookups, and even later in the compiler, a separate instance will hold the reserved word list for the language. Make sure it is built so that it can be used for both applications. Each indexed entry is a pair consisting of a name string and an integer code. The table as we use it is static, and intialized once at the start of the program, and then used only for lookups later on. There are no updates. The needed methods are:

ReserveTable(int maxSize) Constructor, as needed.

int Add(string name, int code) Returns the index of the row where the data was placed; just adds to end of list, and does not check for duplicates..

int LookupName(String name) Returns the code associated with name if name is in the table, else returns -1.

String LookupCode(int code) Returns the associated name if code is there, else an empty string

PrintReserveTable(String filename) Prints to the named file the currently used contents of the Reserve table in neat tabular format, one row per text line.

Main.java

public class main {

public static void main(String[] args) { String filePath = "d:\\"; int indexA, indexB, idx, nameindex, tooMany, testInt; int opcode, op1, op2, op3, rcode; double testFloat; String testString, testSymbol; char testKind, testType; SymbolTable st = new SymbolTable(6); QuadTable qt = new QuadTable(10); ReserveTable rt = new ReserveTable(5); // Symbol table tests will try adding the same thing twice, compare placement indexes idx = st.AddSymbol("count",'v',2345); //0 idx = st.AddSymbol("sum",'v',88.6); //1 // this is the one which will attempt a duplicate // the following should match the first MyInt added, and not add again or change indexA = st.AddSymbol("MyInt", 'v',25); //2 idx = st.AddSymbol("ToTal",'v',"my string"); //3 // here try different capitalization, should come back with same as indexA indexB = st.AddSymbol("myint", 'c',25.0); if (indexA != indexB) System.out.println("Symbol Table duplicate add check failed"); nameindex = st.AddSymbol("Name",'v',"Paul Williams"); //4 idx = st.AddSymbol("realCount",'v',922.65); //5 last one there is room for tooMany = st.AddSymbol("noRoom",'v',16); //6 should fail, return -1 if (tooMany != -1) System.out.println("Symbol Table size exceeded check failed");

// Look for 'name' case insensitive idx = st.LookupSymbol("NaMe"); if (idx != nameindex) System.out.println("Symbol Table lookup of NaMe failed"); testSymbol = st.GetSymbol(idx); testKind = st.GetKind(idx); testType = st.GetDataType(idx); testString = st.GetString(idx); testFloat = st.GetFloat(idx); testInt = st.GetInteger(idx); System.out.println(testSymbol+"|"+testKind+"|"+testType+"|"+testString+"|"+testFloat+"|"+testInt+"|");

st.UpdateSymbol(idx, 'c', "James Roberts" ); testSymbol = st.GetSymbol(idx); testKind = st.GetKind(idx); testType = st.GetDataType(idx); testString = st.GetString(idx); testFloat = st.GetFloat(idx); testInt = st.GetInteger(idx); System.out.println(testSymbol+"|"+testKind+"|"+testType+"|"+testString+"|"+testFloat+"|"+testInt+"|"); // Print the symbol table contents, only the valid data should print, lines 0 through 5 st.PrintSymbolTable(filePath+"symbolTable.txt");

// Quad table testing fill it to capacity for (idx = 0; idx < 5; idx++ ) { qt.AddQuad(idx*2, idx+2, idx*3, idx+12); } if (qt.NextQuad() != 5) System.out.println("NextQuad was not the expected value 5");

for (idx = 5; idx < 10; idx++ ) { qt.AddQuad(idx*2, idx+2, idx*3, idx+12); }

qt.UpdateQuad(9, 1, 2, 3, 4);

opcode = qt.GetQuad(9, 0); op1 = qt.GetQuad(9, 1); op2 = qt.GetQuad(9, 2); op3 = qt.GetQuad(9, 3); if ((opcode !=1)||(op1 !=2)||(op2 !=3)||(op3 != 4)) System.out.println("Update Quad Failed on slot 9"); qt.PrintQuadTable(filePath+"quadTable.txt"); //Reserve Table tests 5 elements rt.Add("for", 20); rt.Add("NEXT", 21); rt.Add("Begin", 22); rt.Add("END", 23); rt.Add("program", 24); rcode = rt.LookupName("FOR"); if (rcode != 20) System.out.println("Lookup FOR failed"); rcode = rt.LookupName("ProGram"); if (rcode != 24) System.out.println("Lookup ProGram failed"); rcode = rt.LookupName("NotThere"); if (rcode != -1) System.out.println("Lookup NotThere failed"); testString = rt.LookupCode(20); if (testString.compareToIgnoreCase("FOR") != 0) System.out.println("Lookup 20 failed"); testString = rt.LookupCode(24); if (testString.compareToIgnoreCase("program") != 0) System.out.println("Lookup 24 failed"); testString = rt.LookupCode(44); if (testString.compareToIgnoreCase("") != 0) System.out.println("Lookup 44 failed");

rt.PrintReserveTable(filePath+"reserveTable.txt"); } }