If you are here to read about the symbol table, then it means that you already know about the basic flow of all the phases of the compiler as demonstrated in the diagram. If you want to read about phases of the compiler and their relation with symbol table then must read the article “phases of compiler“.
Symbol table in Compiler Design
The compiler creates and maintains a data structure to store information about the occurrence of various entities such as variable and function names, objects and classes, etc. This kind of data structure is known as a symbol table.
C++ Code
void P1()
{
int A;
int B;
{
int C;
int D;
}
int E;
{
int F;
int G;
}
}
void P2()
{
int H;
int I;
{
int J;
int K;
}
int L;
}
The symbol table for C++ Code
Operations on Symbol table
Allocate Operation on Symbol table
Allocate Operation can be performed on a symbol table to allocate a new empty symbol table.
Insert Operation on Symbol table
Insert Operation can be performed on a symbol table to insert a name in a symbol table and return a pointer to its entry.
Set_attribute Operation on Symbol table
Set_attribute Operation can be performed on a symbol table to associate an attribute with a given entry.
Get_attribute Operation on Symbol table
Get_attribute Operation can be performed on a symbol table to get an attribute associated with a given entry.
Lookup Operation on Symbol table
Lookup Operation can be performed on a symbol table to search for a name and return a pointer to its entry.
Free Operation on Symbol table
Free Operation can be performed on a symbol table to remove all entries and free the storage of a symbol table.
Some other operations just like delete operations can also be performed on the symbol table.
Implementation of Symbol table
Symbol tables can be implemented with different kinds of data structure techniques. Some of the techniques are mentioned below;
- LinkedList
- Hash Table
- Tree
A basic example of creating the symbol table of C++ Code
int t4tutorials(int x, int y)
{
int addition = 0;
addition = x + y;
return sum;
}
Symbol Table for the code shown above.
| NAME | TYPE | SCOPE |
| t4tutorials | function | global |
| x | int | function parameter |
| y | int | function parameter |
| addition | int | local |
Symbol table implementation with hashing in C++
// C++ program to implement Symbol Table
#include <iostream>
using namespace std;
const int MAXIMUM = 100;
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 T4Tutorials_insertion(string id, string scope,
string Type, int Line_Number);
string T4Tutorials_search(string id);
bool deleteRecord(string id);
bool modify(string id, string scope,
string Type, int Line_Number);
};
// Function to modify an identifier
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
}
// Function to delete an identifier
bool SymbolTable::deleteRecord(string id)
{
int index = hashf(id);
Node* T4Tutorials_Temporary_Variable = header[index];
Node* par = header[index];
// no identifier is present at that index
if (T4Tutorials_Temporary_Variable == NULL) {
return false;
}
// only one identifier is present
if (T4Tutorials_Temporary_Variable->identifier == id && T4Tutorials_Temporary_Variable->next_Node == NULL) {
T4Tutorials_Temporary_Variable->next_Node = NULL;
delete T4Tutorials_Temporary_Variable;
return true;
}
while (T4Tutorials_Temporary_Variable->identifier != id && T4Tutorials_Temporary_Variable->next_Node != NULL) {
par = T4Tutorials_Temporary_Variable;
T4Tutorials_Temporary_Variable = T4Tutorials_Temporary_Variable->next_Node;
}
if (T4Tutorials_Temporary_Variable->identifier == id && T4Tutorials_Temporary_Variable->next_Node != NULL) {
par->next_Node = T4Tutorials_Temporary_Variable->next_Node;
T4Tutorials_Temporary_Variable->next_Node = NULL;
delete T4Tutorials_Temporary_Variable;
return true;
}
// delete at the end
else {
par->next_Node = NULL;
T4Tutorials_Temporary_Variable->next_Node = NULL;
delete T4Tutorials_Temporary_Variable;
return true;
}
return false;
}
// Function to T4Tutorials_search an identifier
string SymbolTable::T4Tutorials_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
}
// Function to T4Tutorials_insertion an identifier
bool SymbolTable::T4Tutorials_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()
{
SymbolTable st;
string check;
cout << "**** SYMBOL_TABLE ****\n";
// T4Tutorials_insertion 'if'
if (st.T4Tutorials_insertion("if", "local", "keyword", 4))
cout << " -successfully";
else
cout << "\nFailed to T4Tutorials_insertion.\n";
// T4Tutorials_insertion 'number'
if (st.T4Tutorials_insertion("number", "global", "variable", 2))
cout << " -successfully\n\n";
else
cout << "\nFailed to T4Tutorials_insertion\n";
// T4Tutorials_search 'if'
check = st.T4Tutorials_search("if");
if (check != "-1")
cout << "Identifier Is present\n";
else
cout << "\nIdentifier Not Present\n";
// delete 'if'
if (st.deleteRecord("if"))
cout << "if Identifier is deleted\n";
else
cout << "\nFailed to delete\n";
// modify 'number'
if (st.modify("number", "global", "variable", 3))
cout << "\nNumber Identifier updated\n";
// T4Tutorials_search and print 'number'
check = st.T4Tutorials_search("number");
if (check != "-1")
cout << "Identifier Is present\n";
else
cout << "\nIdentifier Not Present";
return 0;
}
Basic Symbol table Program in C
Write a program for implementing a Symbol Table using C.
// symbol table Implementation
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
void main()
{
int x=0, n, i=0,j=0;
void *mypointer,*T4Tutorials_address[5];
char ch,T4Tutorials_Search,T4Tutorials_Array2[15],T4Tutorials_Array3[15],c;
printf("Input the expression ending with $ sign:");
while((c=getchar())!='$')
{
T4Tutorials_Array2[i]=c;
i++;
}
n=i-1;
printf("Given Expression:");
i=0;
while(i<=n)
{
printf("%c",T4Tutorials_Array2[i]);
i++;
}
printf("\n Symbol Table display\n");
printf("Symbol \t addr \t type");
while(j<=n)
{
c=T4Tutorials_Array2[j];
if(isalpha(toascii(c)))
{
mypointer=malloc(c);
T4Tutorials_address[x]=mypointer;
T4Tutorials_Array3[x]=c;
printf("\n%c \t %d \t identifier\n",c,mypointer);
x++;
j++;
}
else
{
ch=c;
if(ch=='+'||ch=='-'||ch=='*'||ch=='=')
{
mypointer=malloc(ch);
T4Tutorials_address[x]=mypointer;
T4Tutorials_Array3[x]=ch;
printf("\n %c \t %d \t operator\n",ch,mypointer);
x++;
j++;
}}}}
Output
