Implementation of Symbol table in C | Compiler Design

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;
   }

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; 
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

// 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++;
   }}}}

// 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

Implementation of Symbol table in C | Compiler Design
By: Prof. Dr. Fazal Rehman | Last updated: December 28, 2023

Symbol table in Compiler Design

Operations on Symbol table

Implementation of Symbol table

Symbol table implementation with hashing in C++

Basic Symbol table Program in C

Lab Exercises of Compiler Construction

Compiler Construction MCQs

Related Posts:

Leave a Comment