You are to develop a symbol table for storing identifiers An

You are to develop a symbol table for storing identifiers. An identifier is a name created by a programmer for naming variables, methods, classes, etc. in a program. The symbol table for the following small Java program is given below. public class Assignment { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n; string name; n = input.nextInt(); name = input.next() etc. } SYMBOL TABLE Identifier Name Lines Appears On Assignment 1 args 3 input 5, 9, 10 n 6, 9 name 7, 10 Data Structures Needed An array of linked lists will be used for storing the information of the symbol table. There following classes are needed for the above data structure. public class LineNode { private int lineNum; private LineNode next; // constructor public LineNode(int lineNum, LineNode next) { this.lineNum = lineNum; this.next = next; } // getters public int getLineNum() { return lineNum; } public LineNode getNext() { return next; } } public class LineHeaderNode { private String identifier; private LineNode next; // constructor public LineHeaderNode(String identifier, LineNode next) { this.identifier = identifier; this.next = next; } // getters public int getIdentifier() { return identifier; } public LineNode getNext() { return next; } } Symbol Table Class The symbol class will contain an array of identifier nodes: LineHeaderNode[] symbol_table = new LineHeaderNode[50]; // for a table of 50 identifiers Provides a default constructor for creating an empty table. Provides methods for adding an identifier to the table (for a provided identifier and line number). Providesa print method for displaying its contents on the screen. If a specific identifier is already in the table, a new LineNode is created and linked in to the existing linked nodes for that identifier. If the identifier does not currently exist in the table, a new IdentifierHeadNode is created to point to a new LineNum node storing the line number that the identifier appeared on. UML Class Diagram Following is a UML class diagram for this project. This diagram indicates the classes that you are to use, and the relationships between them. Thus, a Symbol Table is a collection of Identifier Header Nodes, and an Identifier Header Node is a collection of Identifier Nodes. Approach Develop the Symbol Table class (and two other classes). Test it by developing a test driver program that simply creates a new (empty) Symbol Table, and allows the user to enter identifiers and the line num where each is (supposedly) found. (Everyday words can be entered for the sake of testing.) Once a number of entries into the table have been made, display the symbol table to check that all entries have been properly stored. 1 Add identifier 2 Display Table 3 Quit Expert Answer

Solution

import java.util.*;
class SymbolTable {
static class People {
String id; // Key: The symbol
Ast.Node def; // Value: The definition of this symbol
int hashVal; // What this id hashed to
int scope; // Scope level at which this symbol entered
People next; // Ptr to next People in this People list
People slink; // Ptr to next People in this scope list
}
static class Scope {
People slink;   
Scope next; // Ptr to next Scope record
}
static final int HASH_TABLE_SIZE = 211;
static People [] symbolTable = new People [HASH_TABLE_SIZE];
static int level = 0;
static Scope scopeList = new Scope ();
private SymbolTable () { }
static void enter (String str, Ast.Node def) {
People buck;
int i = hash (str);

// System.out.println (\"enter called with \'\" + str + \"\'\");

// Allocate a new People...
buck = new People ();
buck.id = str;
buck.scope = level;
buck.def = def;
buck.hashVal = i;

// Add the new People into the hash table People list...
buck.next = symbolTable [i];
symbolTable [i] = buck;

// Add this People into the slink list for the current scope level...
buck.slink = scopeList.slink;
scopeList.slink = buck;
}
// find (string)
// If found, it returns a ptr to its definition; otherwise it returns NULL.
static Ast.Node find (String str) {
int i = hash (str);
People buck = symbolTable [i];

// System.out.println (\"find called with \'\" + str + \"\'\");

while (buck != null) {
if (buck.id == str) {
return buck.def;
}
buck = buck.next;
}
return null;
}

static boolean alreadyDefined (String str) {

int i = hash (str);
People buck = symbolTable [i];

// System.out.println (\"alreadyDefined called with \'\" + str + \"\'\");

while (buck != null) {
if (buck.id == str) {
return (buck.scope == level);
}
buck = buck.next;
}
return false;
}
static void openScope () {
Scope sc = new Scope ();
sc.slink = null;
sc.next = scopeList;
scopeList = sc;
level++;

// System.out.println (\"openScope called: new level=\" + level);
}
static void closeScope ()
throws FatalError
{
People buck, temp;
Scope sc;
if (level <= 0) {
throw new LogicError (\"Compiler logic error in closeScope\");
}
buck = scopeList.slink;
while (buck != null) {
symbolTable [buck.hashVal] = buck.next;
temp = buck.slink;
buck.def = null;
buck.next = null;
buck.slink = null;
buck = temp;
}
sc = scopeList;
scopeList = scopeList.next;
sc.slink = null;
sc.next = null;
level--;

// System.out.println (\"closeScope called: new level=\" + level);
}
static int hash (String p) {
int i = p.hashCode (); // May return a negative number.
if (i == 0x80000000) {
i = 123;
} else if (i < 0) {
i = -i;
}
return i % HASH_TABLE_SIZE;
}

// Print the entire symbol table, starting with the current level
static void printTable () {
People buck;
System.out.println (\"========== The Symbol Table ==========\");
for (int lev = level; 0 <= lev; lev--) {
System.out.println (\" ========== Scope Level=\" + lev +\" ==========\");
for (int i = 0; i < HASH_TABLE_SIZE; i++) {
buck = symbolTable [i];
if (buck != null && buck.scope == lev) {
System.out.println (\" ========== People List # \" + i +
\" ==========\");
while (buck != null) {
if (buck.scope == lev) {
System.out.println (\" \" + buck.id +
\" [level=\" + buck.scope +
\", hashVal=\" + buck.hashVal + \"]\");
printDef (buck.def);
}
buck = buck.next;
}
}
}
// System.out.println (\" ===============================\");
}
System.out.println (\"===============================\");
}
static void printDef (Ast.Node p) {
if (p == null) {
System.out.println (\" NULL\");
} else if (p instanceof Ast.VarDecl) {
System.out.println (\" VarDecl...\");
} else if (p instanceof Ast.TypeDecl) {
System.out.println (\" TypeDecl...\");
} else if (p instanceof Ast.ProcDecl) {
System.out.println (\" ProcDecl... \");
} else if (p instanceof Ast.Formal) {
System.out.println (\" Formal... \");
} else {
System.out.println (\" ***** Not a VAR_DECL, PROC_DECL, TYPE_DECL, or FORMAL *****\");
}
}
}