SYMBOL TABLE ROUTINES Choose an organization for your symbol table data structur

Question

SYMBOL TABLE ROUTINES Choose an organization for your symbol table data structures for the identifier names and records and write the FIND and INSERT routines. Put these routines into a dummy main program to prove that th work Submit Symbol table routines Grading: s the program comect? Is the program elegant? Well written? s the program well tested? Important routines: FIND in CURRENT SCOPE-1, FIND IN ALL SCOPES-2, INSERT, DISPLAY Driver program to test FIND (both versions), INSERT, DISPLAY, you need a driver (main) program that can: (1) open and close scopes, (2) check if a name is already in the symbol table (ST), and (3) add it into the ST if not already there. Requirements: identifiers must be stored without truncation, but also without wasting space. This probably means tring allocation routines (although in some languages, a string table must be used) an important question is whether the high level language is case sensitive (is "a" the same as "A" For now, assume the language compiled IS case sensitive you may use any library or utility functions available Java has a HashTable with findKey and put which are almost find and insert) symbol table entries must be expandable. For this program, there is no information to store about each identifier name (unless you choose to store a "block number to distinguish between two different occurrences of the same name separate symbol tables for each scope (OPEN CLOSE) or (2) storing some means of differentiating between multiple copies of the same identifier, such as the "block number" ofthe declaration FIND should be an efficient routine; it will be called often. INSERT should be at least relativel efficient. Hash tables and balanced binary trees are the usual choices for a symbol table organization. FIND must return more than a simple Boolean; if found, it must return some means of retrieving the information in the symbol table (pointer to or copy of the record) FIND and INSERT must be separate routines; neither may be nested inside the other. Probably neither should call the other Test your program by creating a dummy file of identifier names with some method of indicating that a block starts or stops. Onc dummy file is below, but it isn't sufficient to test your program.

Explanation / Answer

A symbol table is a data structure for managing scope. Conceptually, a symbol table is just another lookup table. The key is the symbol (the name) and the result is whatever information has been associated with that symbol (e.g., the symbol's type). in this program i have implemented symbol tables using Java hashtables. Each hashtable represents a scope and associates a symbol with some data. The ``data'' is whatever data the programmer wishes to associate with each identifier. The following class SymbolTable defines the routines, which can be called from the driver class: import java.util.Stack; import java.util.Hashtable; class SymbolTable { private Stack tbl; /** Creates an empty symbol table. */ public SymbolTable() { tbl = new Stack(); } /** Enters a new scope. A scope must be entered before anything * can be added to the table. * */ public void enterScope() { tbl.push(new Hashtable()); } /** Exits the most recently entered scope. */ public void exitScope() { if (tbl.empty()) { System.out.println("existScope: can't remove scope from an empty symbol table."); return null; } tbl.pop(); } /** Adds a new entry to the symbol table. * * @param id the symbol * @param info the data asosciated with id * */ public void addId(AbstractSymbol id, Object info) { if (tbl.empty()) { System.out.println("addId: can't add a symbol without a scope."); return null; } ((Hashtable)tbl.peek()).put(id, info); /*The peek() method is used to look at the object at the top of this stack without removing it from the stack.*/ } /** * Looks up an item through all scopes of the symbol table. If * found it returns the associated information field, if not it * returns null. * * @param sym the symbol * @return the info associated with sym, or null if not found * */ public Object findInAllScopes(AbstractSymbol sym) { if (tbl.empty()) { System.out.println("lookup: no scope in symbol table."); RETURN NULL; } // considering stack behaves like a vector for (int i = tbl.size() - 1; i >= 0; i--) { Object info = ((Hashtable)tbl.elementAt(i)).get(sym); if (info != null) return info; } return null; } /** * Probes the symbol table. Check the top scope (only) for the * symbol sym. If found, return the information field. * If not return null. * * @param sym the symbol * @return the info associated with sym, or null if not found * */ public Object findInCurrentScope(AbstractSymbol sym) { if (tbl.empty()) { System.out.println("lookup: no scope in symbol table."); return null; } return ((Hashtable)tbl.peek()).get(sym); } /** Gets the string representation of the symbol table. It can be used to display the symbol table * * @return the string rep * */ public String toString() { String res = ""; for (int i = tbl.size() - 1, j = 0; i >= 0; i--, j++) { res += "Scope " + j + ": " + tbl.elementAt(i) + " "; } return res; } } The main driver class SymtabExample is as follows: class SymtabExample { public static void main(String args[]) { // crate a new symbol table; entries will be name/age pairs SymbolTable map = new SymbolTable(); // create some names AbstractSymbol fred = AbstractTable.stringtable.addString("Fred"); AbstractSymbol mary = AbstractTable.stringtable.addString("Mary"); AbstractSymbol miguel = AbstractTable.stringtable.addString("Miguel"); map.enterScope(); // add a couple of entries mapping name to age. // note the second argument must be a pointer to an integer map.addId(fred, new Integer(22)); map.addId(mary, new Integer(25)); // add a scope, add more names: map.enterScope(); map.addId(miguel, new Integer(35)); //insert record map.addId(mary, new Integer(23)); // check whether Fred is in the current scope; predicate is false System.out.println((map.findInCurrentScope(fred) != null) ? "Yes" : "No"); // check whether Mary is in any scope; predicate is true System.out.println((map.findInAllScopes(mary) != null) ? "Yes" : "No"); // print age of most-closely-nested Mary System.out.println(map.findInAllScopes(mary)); // check whether Miguel is in the current scope; predicate is true System.out.println((map.findInCurrentScope(miguel) != null) ? "Yes" : "No"); // leave a scope map.exitScope(); // print age of most-closely-nested Mary System.out.println(map.findInAllScopes(mary)); // check whether Fred is in the current scope; predicate is now true System.out.println((map.findInCurrentScope(fred) != null) ? "Yes" : "No"); // check whether Miguel is in any scope; predicate is now false System.out.println((map.findInAllScopes(miguel) != null) ? "Yes" : "No"); } }

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.