Within this guide, you will gain an understanding of the symbol table in C++.
Compiler Design symbol table
To keep track of various entities like variable and function identifiers, objects, and classes, the compiler constructs and manages a data structure. Symbol tables represent a category of such data structures.
C++ code for symbol table entry:
Example:
#include <iostream>
#include <unordered_map>
#include <vector>
class SymbolTableEntry {
public:
std::string name;
std::string dataType;
std::string scope;
SymbolTableEntry(const std::string& n, const std::string& dt, const std::string&sc)
: name(n), dataType(dt), scope(sc) {}
};
class SymbolTable {
public:
void insert(constSymbolTableEntry& entry) {
entries.push_back(entry);
}
SymbolTableEntry* lookup(const std::string& name) {
for (auto&entry : entries) {
if (entry.name == name) {
return &entry;
}
}
return nullptr;
}
private:
std::vector<SymbolTableEntry> entries;
};
int main() {
SymbolTablesymbolTable;
symbolTable.insert(SymbolTableEntry("A", "int", "P1"));
symbolTable.insert(SymbolTableEntry("B", "int", "P1"));
symbolTable.insert(SymbolTableEntry("C", "int", "P1 inner block"));
symbolTable.insert(SymbolTableEntry("D", "int", "P1 inner block"));
symbolTable.insert(SymbolTableEntry("E", "int", "P1"));
symbolTable.insert(SymbolTableEntry("F", "int", "P1 inner block"));
symbolTable.insert(SymbolTableEntry("G", "int", "P1 inner block"));
symbolTable.insert(SymbolTableEntry("H", "int", "P2"));
symbolTable.insert(SymbolTableEntry("I", "int", "P2"));
symbolTable.insert(SymbolTableEntry("J", "int", "P2 inner block"));
symbolTable.insert(SymbolTableEntry("K", "int", "P2 inner block"));
symbolTable.insert(SymbolTableEntry("L", "int", "P2"));
SymbolTableEntry* entryA = symbolTable.lookup("A");
if (entryA) {
std::cout<< "Found symbol A in the symbol table." <<std::endl;
} else {
std::cout<< "Symbol A not found in the symbol table." <<std::endl;
}
SymbolTableEntry* entryX = symbolTable.lookup("X");
if (entryX) {
std::cout<< "Found symbol X in the symbol table." <<std::endl;
} else {
std::cout<< "Symbol X not found in the symbol table." <<std::endl;
}
return 0;
}
Output:
Found symbol A in the symbol table.
Symbol X not found in the symbol table.
Symbol table operations
There are various symbol table functions in C++. A few key symbol table operations in C++ include:
Operate on the Symbol table.
A symbol table can utilize the Allocate Operation to create a new, empty symbol table.
Operation Insert on the Symbol table
A symbol table's Insert Operation is employed for adding a name and providing a reference to the entry.
Operation Set_attribute on the Symbol table
Set_attribute represents a symbol table that can be manipulated to link an attribute with a particular entry.
Operation Get_attribute on the Symbol table
Retrieve_attribute is a symbol table that can be manipulated to access an attribute associated with a particular entry.
Operation of Lookup on the Symbol Table
Search A function in a symbol table can be employed to search for a specific name and retrieve a reference to its corresponding entry.
Free Operation on the Symbol table
A symbol table's memory can be reclaimed by executing a Free Operation to eliminate each entry. Further actions can be performed on the symbol table in a comparable fashion to execute removal operations.
Deployment of the Symbol table
It is possible to implement symbol tables using a variety of data structure methods. The following techniques are listed:
- LinkedList
- Hash Table
- Tree
Implementing symbol tables in C++ using hashing involves creating a data structure that stores key-value pairs with efficient lookup and insertion operations. Hashing allows for constant-time average case performance for these operations by using a hash function to map keys to indices in an array. Here's how you can implement symbol tables in C++ using hashing:
- Define a hash table data structure that consists of an array of linked lists. Each element in the array is a pointer to the head of a linked list.
- Create a hash function that takes a key and returns an index in the array where the key-value pair should be stored. This function should distribute keys evenly across the array to minimize collisions.
- Implement functions to insert a key-value pair into the hash table, retrieve the value associated with a key, and delete a key from the table. When inserting a new key-value pair, use the hash function to determine the index and add the pair to the corresponding linked list.
- Handle collisions by implementing a collision resolution strategy, such as chaining (using linked lists) or open addressing (probing the next available slot).
- To retrieve a value associated with a key, use the hash function to find the index and then search the linked list at that index for the key.
By following these steps, you can create an efficient symbol table implementation in C++ using hashing techniques.
// Symbol Table implementation in C++
#include <iostream>
using namespace std;
const int MAXIMUM = 200;
class Node {
string identifier, scope, type;
int Line_Number;
Node* next_Node;
public:
Node()
{
next_Node = NULL;
}
Node(string key, string value, string type, int Line_Number)
{
this->identifier = key;
this->scope = value;
this->type = type;
this->Line_Number = Line_Number;
next_Node = NULL;
}
void print()
{
cout<< "Identifier's Name:" << identifier
<< "\nType:" << type
<< "\nScope: " << scope
<< "\nLine Number: " <<Line_Number<<endl;
}
friend class SymbolTable;
};
class SymbolTable {
Node* header[MAXIMUM];
public:
SymbolTable()
{
for (int i = 0; i< MAXIMUM; i++)
header[i] = NULL;
}
int hashf(string id); // hash function
bool JavaCppTutorial_insertion(string id, string scope,
string Type, int Line_Number);
string JavaCppTutorial_search(string id);
bool deleteRecord(string id);
bool modify(string id, string scope,
string Type, int Line_Number);
};
// Identifyer modification function
bool SymbolTable::modify(string id, string s,
string t, int l)
{
int index = hashf(id);
Node* start = header[index];
if (start == NULL)
return "-1";
while (start != NULL) {
if (start->identifier == id) {
start->scope = s;
start->type = t;
start->Line_Number = l;
return true;
}
start = start->next_Node;
}
return false; // id not found
}
// Delete an identifier function
bool SymbolTable::deleteRecord(string id)
{
int index = hashf(id);
Node* JavaCppTutorial_Temporary_Variable = header[index];
Node* par = header[index];
// There is no identifier at that index.
if (JavaCppTutorial_Temporary_Variable == NULL) {
return false;
}
// There is only one identifier.
if (JavaCppTutorial_Temporary_Variable->identifier == id &&JavaCppTutorial_Temporary_Variable->next_Node == NULL) {
JavaCppTutorial_Temporary_Variable->next_Node = NULL;
delete JavaCppTutorial_Temporary_Variable;
return true;
}
while (JavaCppTutorial_Temporary_Variable->identifier != id &&JavaCppTutorial_Temporary_Variable->next_Node != NULL) {
par = JavaCppTutorial_Temporary_Variable;
JavaCppTutorial_Temporary_Variable = JavaCppTutorial_Temporary_Variable->next_Node;
}
if (JavaCppTutorial_Temporary_Variable->identifier == id &&JavaCppTutorial_Temporary_Variable->next_Node != NULL) {
par->next_Node = JavaCppTutorial_Temporary_Variable->next_Node;
JavaCppTutorial_Temporary_Variable->next_Node = NULL;
delete JavaCppTutorial_Temporary_Variable;
return true;
}
// remove the conclusion
else {
par->next_Node = NULL;
JavaCppTutorial_Temporary_Variable->next_Node = NULL;
delete JavaCppTutorial_Temporary_Variable;
return true;
}
return false;
}
// JavaCppTutorial_search identifier function
string SymbolTable::JavaCppTutorial_search(string id)
{
int index = hashf(id);
Node* start = header[index];
if (start == NULL)
return "-1";
while (start != NULL) {
if (start->identifier == id) {
start->print();
return start->scope;
}
start = start->next_Node;
}
return "-1"; // not found
}
// JavaCppTutorial_insertion function for an identifier
bool SymbolTable::JavaCppTutorial_insertion(string id, string scope,
string Type, int Line_Number)
{
int index = hashf(id);
Node* p = new Node(id, scope, Type, Line_Number);
if (header[index] == NULL) {
header[index] = p;
cout<< "\n"
<< id << " insertion";
return true;
}
else {
Node* start = header[index];
while (start->next_Node != NULL)
start = start->next_Node;
start->next_Node = p;
cout<< "\n"
<< id << " insertion";
return true;
}
return false;
}
int SymbolTable::hashf(string id)
{
int asciiSum = 0;
for (int i = 0; i<id.length(); i++) {
asciiSum = asciiSum + id[i];
}
return (asciiSum % 100);
}
int main()
{
SymbolTablest;
string check;
cout<< "**** SYMBOL_TABLE ****\n";
if (st.JavaCppTutorial_insertion("if", "local", "keyword", 4))
cout<< " -successfully";
else
cout<< "\nFailed to JavaCppTutorial_insertion.\n";
if (st.JavaCppTutorial_insertion("number", "global", "variable", 2))
cout<< " -successfully\n\n";
else
cout<< "\nFailed to JavaCppTutorial_insertion\n";
check = st.JavaCppTutorial_search("if");
if (check != "-1")
cout<< "Identifier Is present\n";
else
cout<< "\nIdentifier Not Present\n";
if (st.deleteRecord("if"))
cout<< "if Identifier is deleted\n";
else
cout<< "\nFailed to delete\n";
if (st.modify("number", "global", "variable", 3))
cout<< "\nNumber Identifier updated\n";
check = st.JavaCppTutorial_search("number");
if (check != "-1")
cout<< "Identifier Is present\n";
else
cout<< "\nIdentifier Not Present";
return 0;
}
Output:
**** SYMBOL_TABLE ****
if insertion -successfully
number insertion -successfully
Identifier's Name:if
Type:keyword
Scope: local
Line Number: 4
Identifier Is present
if Identifier is deleted
Number Identifier updated
Identifier's Name:number
Type:variable
Scope: global
Line Number: 3
Identifier Is present
Conclusion:
The symbol table plays a vital role in language processing systems by offering the necessary framework to handle the intricate meanings and actions of identifiers within C programs. Ensuring the accurate and effective execution of code relies heavily on this component.
