SYMBOL TABLE ROUTINES Choose an organization for your symbol table -data structu
ID: 3876990 • Letter: S
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 they work. Submit: (1) Symbol table routines (2) Test runs (input and output) Grading: Is the program correct? Is the program elegant? Well written? Is 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 string 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). - the table must be able to handle multiple entrics of the same name. This can be done by (1) having 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" of the declaration. - FIND should be an efficient routine; it will be called often. INSERT should be at least relatively 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. One dummy file is below, but it isn't sufficient to test your program.Explanation / Answer
//Program for SymbolTable. Place in file called SymbolTable.java
import java.security.Principal;
import java.util.ArrayList;
import java.util.Hashtable;
public class SymbolTable {
private Hashtable<String, ArrayList<Integer>> symbolTable;
private int numberOfScopes;
public SymbolTable() {
// TODO Auto-generated constructor stub
symbolTable = new Hashtable<String, ArrayList<Integer>>();
numberOfScopes = 0;
}
public void insert(String symbol, int blockNumber) {
ArrayList<Integer> blockNumbers = symbolTable.get(symbol);
if(blockNumbers==null)
blockNumbers = new ArrayList<Integer>();
blockNumbers.add(blockNumber);
symbolTable.put(symbol, blockNumbers);
}
public boolean find(String symbol, int blockNumber) {
ArrayList<Integer> blockNumbers = symbolTable.get(symbol);
if (blockNumbers!=null&&blockNumbers.contains(blockNumber))
return true;
else
return false;
}
public boolean findInAll(String symbol) {
ArrayList<Integer> blockNumbers = symbolTable.get(symbol);
if (blockNumbers != null)
return true;
else
return false;
}
public void display() {
String[] output = new String[numberOfScopes+1];
for(int i=0;i<=numberOfScopes;i++)
output[i] = new String("");
for(String symbol: symbolTable.keySet()) {
ArrayList<Integer> blockNumbers = symbolTable.get(symbol);
for(int blockNumber: blockNumbers) {
output[blockNumber]=(output[blockNumber]+symbol+" ");
}
}
for(int i=1;i<=numberOfScopes;i++) {
System.out.println("Scope "+(i));
if(!output[i].equals(""))
System.out.println(output[i]);
else
System.out.println("No Symbols available.");
}
}
public void addScope() {
numberOfScopes++;
}
}
//Program for SymbolTableDriver(With Main Method) Place in a separate java file called SymbolTableDriver.java
package symboltable;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class SymbolTableDriver {
public static void main(String[] args) {
// TODO Auto-generated method stub
SymbolTable symbolTable = new SymbolTable();
int currentBlock = 0;
int closed = 0;
Stack<Integer> stack = new Stack<Integer>();
try {
BufferedReader br = new BufferedReader(new InputStreamReader(
new FileInputStream(new File("sample.txt"))));
String line = br.readLine();
while (line != null) {
String[] words = line.split(" ");
for (String word : words) {
if (word.startsWith("{")) {
if (currentBlock != 0)
stack.push(currentBlock);
currentBlock += closed + 1;
symbolTable.addScope();
if (word.length() > 1) {
String symbol = word.substring(1);
if (!symbolTable.find(symbol, currentBlock)) {
symbolTable.insert(symbol, currentBlock);
}
}
} else if (word.endsWith("}")) {
closed++;
if (word.length() > 1) {
String symbol = word
.substring(0, word.length() - 1);
if (!symbolTable.find(symbol, currentBlock)) {
symbolTable.insert(symbol, currentBlock);
}
}
if (!stack.isEmpty())
currentBlock = stack.pop();
} else {
if (!symbolTable.find(word, currentBlock)) {
symbolTable.insert(word, currentBlock);
}
}
}
line = br.readLine();
}
symbolTable.display();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
//Sample input. Place in a file called sample.txt and compile and run the SymbolTableDriver class
{ a A b B
{ }
{a A}
{b B c}
{ }
a A c C}
//Sample output
Scope 1
b A a C c B
Scope 2
No Symbols available.
Scope 3
A a
Scope 4
b c B
Scope 5
No Symbols available.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.