CREATION OF SYMBOL TABLE
USING HASHING AND VALIDATION
PROGRAM CODE:-
HEADER FILE:- <hash.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#define SETADDRESS 0x0F
#define SETVALUE 0xF0
struct hashtable
{
struct linkedlist **lists;
int sizeofhashtable;
};
struct linkedlist
{
struct node *headernode;
int numberofelements;
};
struct node
{
double initialvalue;
char symbolname[50];
int address;
int size;
char datatype[10];
struct node *next;
};
struct linkedlist* createlinkedlist();
int hash(struct hashtable *h,char *string);
struct hashtable* createhashtable();
int insertintohashtable(struct hashtable *h,char symbolname[],int address,double initialvalue,char datatype[],int size);
int insertintolinkedlist(struct linkedlist *l,struct node *n);
void displaylist(struct linkedlist *list);
void displayhashtable(struct hashtable *h);
int deletefromhashtable(struct hashtable *h,char symbolname[]);
int deletefromlist(struct linkedlist *l,char symbolname[]);
int updatehashtable(struct hashtable *h,char symbolname[],double newvalue,int mask);
int updatelinkedlist(struct linkedlist *list,char symbolname[],double newvalue,int mask);
char* searchlist(struct linkedlist *list,char symbolname[]);
char* searchtable(struct hashtable *h,char symbolname[]);
int hash(struct hashtable *h,char *string)
{
if(string[0] >= 'A' && string[0] <= 'Z')
return (string[0]-65)%h->sizeofhashtable;
if(string[0] >= 'a' && string[0] <= 'z')
return (string[0]-97)%h->sizeofhashtable;
return (string[0] - 48)%h->sizeofhashtable;
}
struct hashtable* createhashtable()
{
struct hashtable *h = (struct hashtable *)malloc(sizeof(struct hashtable));
int i;
h->sizeofhashtable = 26;
h->lists = (struct linkedlist **)malloc(sizeof(struct linkedlist*)*h->sizeofhashtable);
for(i=0;i<h->sizeofhashtable;i++)
h->lists[i] = createlinkedlist();
return h;
}
struct linkedlist* createlinkedlist()
{
struct linkedlist *temp = (struct linkedlist *)malloc(sizeof(struct linkedlist));
temp->numberofelements = 0;
temp->headernode = (struct node *)malloc(sizeof(struct node));
temp->headernode->next = NULL;
return temp;
}
int insertintohashtable(struct hashtable *h,char symbolname[],int address,double initialvalue,char datatype[],int size)
{
struct node *temp = (struct node*)malloc(sizeof(struct node));
strcpy(temp->symbolname,symbolname);
strcpy(temp->datatype,datatype);
temp->initialvalue = initialvalue;
temp->address = address;
temp->size = size;
return insertintolinkedlist(h->lists[hash(h,symbolname)],temp);
}
int insertintolinkedlist(struct linkedlist *l,struct node *n)
{
struct node *list = l->headernode;
while(list->next != NULL)
{
if(strcmp(list->next->symbolname,n->symbolname) == 0)
return -1;
list = list->next;
}
list->next = n;
l->numberofelements++;
return 1;
}
void displaylist(struct linkedlist *list)
{
struct node *l = list->headernode;
if(l->next == NULL)
return;
l=l->next;
while(l->next != NULL)
{
printf("[%s,%s,%g,%d,%d] --> ",l->symbolname,l->datatype,l->initialvalue,l->address,l->size);
l=l->next;
}
printf("[%s,%s,%g,%d,%d]",l->symbolname,l->datatype,l->initialvalue,l->address,l->size);
}
void displayhashtable(struct hashtable *h)
{
int i;
printf("\nHashTable:\n");
printf("Hash Value\t\tHashed Elements\n");
for(i=0;i<h->sizeofhashtable;i++)
{
printf("\n%c|%c\t\t",i+65,i+97);
displaylist(h->lists[i]);
}
printf("\n\n");
}
int deletefromhashtable(struct hashtable *h,char symbolname[])
{
return deletefromlist(h->lists[hash(h,symbolname)],symbolname);
}
int deletefromlist(struct linkedlist *list,char symbolname[])
{
struct node *l =list->headernode;
while(l->next != NULL)
{
if(strcmp(l->next->symbolname,symbolname)==0)
{
l->next = l->next->next;
list->numberofelements--;
return 1;
}
l = l->next;
}
return -1;
}
int updatehashtable(struct hashtable *h,char symbolname[],double newvalue,int mask)
{
return updatelinkedlist(h->lists[hash(h,symbolname)],symbolname,newvalue,mask);
}
int updatelinkedlist(struct linkedlist *l,char symbolname[],double newvalue,int mask)
{
struct node *list = l->headernode;
while(list->next != NULL)
{
if(strcmp(list->next->symbolname,symbolname) == 0)
{
if((mask & 0xFF) == SETADDRESS )
list->next->address = (int)newvalue;
if((mask & 0xFF) == SETVALUE)
list->next->initialvalue = newvalue;
return 1;
}
list=list->next;
}
return -1;
}
char* searchtable(struct hashtable *h,char symbolname[])
{
return searchlist(h->lists[hash(h,symbolname)],symbolname);
}
char* searchlist(struct linkedlist *list,char symbolname[])
{
struct node *l = list->headernode;
char *buff = (char *)malloc(sizeof(char)*100);
while(l->next!=NULL)
{
if(strcmp(l->next->symbolname,symbolname) == 0)
{
sprintf(buff,"[%s,%s,%g,%d,%d]",l->next->symbolname,l->next->datatype,l->next->initialvalue,l->next->address,l->next->size);
return buff;
}
l = l->next;
}
return NULL;
}
USING HASHING AND VALIDATION
PROGRAM CODE:-
HEADER FILE:- <hash.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#define SETADDRESS 0x0F
#define SETVALUE 0xF0
struct hashtable
{
struct linkedlist **lists;
int sizeofhashtable;
};
struct linkedlist
{
struct node *headernode;
int numberofelements;
};
struct node
{
double initialvalue;
char symbolname[50];
int address;
int size;
char datatype[10];
struct node *next;
};
struct linkedlist* createlinkedlist();
int hash(struct hashtable *h,char *string);
struct hashtable* createhashtable();
int insertintohashtable(struct hashtable *h,char symbolname[],int address,double initialvalue,char datatype[],int size);
int insertintolinkedlist(struct linkedlist *l,struct node *n);
void displaylist(struct linkedlist *list);
void displayhashtable(struct hashtable *h);
int deletefromhashtable(struct hashtable *h,char symbolname[]);
int deletefromlist(struct linkedlist *l,char symbolname[]);
int updatehashtable(struct hashtable *h,char symbolname[],double newvalue,int mask);
int updatelinkedlist(struct linkedlist *list,char symbolname[],double newvalue,int mask);
char* searchlist(struct linkedlist *list,char symbolname[]);
char* searchtable(struct hashtable *h,char symbolname[]);
int hash(struct hashtable *h,char *string)
{
if(string[0] >= 'A' && string[0] <= 'Z')
return (string[0]-65)%h->sizeofhashtable;
if(string[0] >= 'a' && string[0] <= 'z')
return (string[0]-97)%h->sizeofhashtable;
return (string[0] - 48)%h->sizeofhashtable;
}
struct hashtable* createhashtable()
{
struct hashtable *h = (struct hashtable *)malloc(sizeof(struct hashtable));
int i;
h->sizeofhashtable = 26;
h->lists = (struct linkedlist **)malloc(sizeof(struct linkedlist*)*h->sizeofhashtable);
for(i=0;i<h->sizeofhashtable;i++)
h->lists[i] = createlinkedlist();
return h;
}
struct linkedlist* createlinkedlist()
{
struct linkedlist *temp = (struct linkedlist *)malloc(sizeof(struct linkedlist));
temp->numberofelements = 0;
temp->headernode = (struct node *)malloc(sizeof(struct node));
temp->headernode->next = NULL;
return temp;
}
int insertintohashtable(struct hashtable *h,char symbolname[],int address,double initialvalue,char datatype[],int size)
{
struct node *temp = (struct node*)malloc(sizeof(struct node));
strcpy(temp->symbolname,symbolname);
strcpy(temp->datatype,datatype);
temp->initialvalue = initialvalue;
temp->address = address;
temp->size = size;
return insertintolinkedlist(h->lists[hash(h,symbolname)],temp);
}
int insertintolinkedlist(struct linkedlist *l,struct node *n)
{
struct node *list = l->headernode;
while(list->next != NULL)
{
if(strcmp(list->next->symbolname,n->symbolname) == 0)
return -1;
list = list->next;
}
list->next = n;
l->numberofelements++;
return 1;
}
void displaylist(struct linkedlist *list)
{
struct node *l = list->headernode;
if(l->next == NULL)
return;
l=l->next;
while(l->next != NULL)
{
printf("[%s,%s,%g,%d,%d] --> ",l->symbolname,l->datatype,l->initialvalue,l->address,l->size);
l=l->next;
}
printf("[%s,%s,%g,%d,%d]",l->symbolname,l->datatype,l->initialvalue,l->address,l->size);
}
void displayhashtable(struct hashtable *h)
{
int i;
printf("\nHashTable:\n");
printf("Hash Value\t\tHashed Elements\n");
for(i=0;i<h->sizeofhashtable;i++)
{
printf("\n%c|%c\t\t",i+65,i+97);
displaylist(h->lists[i]);
}
printf("\n\n");
}
int deletefromhashtable(struct hashtable *h,char symbolname[])
{
return deletefromlist(h->lists[hash(h,symbolname)],symbolname);
}
int deletefromlist(struct linkedlist *list,char symbolname[])
{
struct node *l =list->headernode;
while(l->next != NULL)
{
if(strcmp(l->next->symbolname,symbolname)==0)
{
l->next = l->next->next;
list->numberofelements--;
return 1;
}
l = l->next;
}
return -1;
}
int updatehashtable(struct hashtable *h,char symbolname[],double newvalue,int mask)
{
return updatelinkedlist(h->lists[hash(h,symbolname)],symbolname,newvalue,mask);
}
int updatelinkedlist(struct linkedlist *l,char symbolname[],double newvalue,int mask)
{
struct node *list = l->headernode;
while(list->next != NULL)
{
if(strcmp(list->next->symbolname,symbolname) == 0)
{
if((mask & 0xFF) == SETADDRESS )
list->next->address = (int)newvalue;
if((mask & 0xFF) == SETVALUE)
list->next->initialvalue = newvalue;
return 1;
}
list=list->next;
}
return -1;
}
char* searchtable(struct hashtable *h,char symbolname[])
{
return searchlist(h->lists[hash(h,symbolname)],symbolname);
}
char* searchlist(struct linkedlist *list,char symbolname[])
{
struct node *l = list->headernode;
char *buff = (char *)malloc(sizeof(char)*100);
while(l->next!=NULL)
{
if(strcmp(l->next->symbolname,symbolname) == 0)
{
sprintf(buff,"[%s,%s,%g,%d,%d]",l->next->symbolname,l->next->datatype,l->next->initialvalue,l->next->address,l->next->size);
return buff;
}
l = l->next;
}
return NULL;
}
MAIN CODE:- SYMTAB.C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hash.h"
struct keywordlist
{
char **keywords;
int *size;
int numberofkeywords;
};
struct keywordlist* getkeywordlist()
{
int i;
struct keywordlist *temp = (struct keywordlist *)malloc(sizeof(struct keywordlist));
temp->numberofkeywords = 4;
temp->keywords = (char **)malloc(sizeof(char *) * temp->numberofkeywords);
temp->size = (int *)malloc(sizeof(int) * temp->numberofkeywords);
for(i=0;i<temp->numberofkeywords;i++)
temp->keywords[i] = (char *)malloc(sizeof(char) * 10);
strcpy(temp->keywords[0],"int");
temp->size[0] = sizeof(int);
strcpy(temp->keywords[1],"float");
temp->size[1] = sizeof(float);
strcpy(temp->keywords[2],"char");
temp->size[2] = sizeof(char);
strcpy(temp->keywords[3],"double");
temp->size[3] = sizeof(double);
return temp;
}
int checklist(struct keywordlist *l,char word[])
{
int i;
for(i=0;i<l->numberofkeywords;i++)
if(strcmp(l->keywords[i],word) == 0)
return 1;
return -1;
}
int getsize(struct keywordlist *l,char word[])
{
int i;
for(i=0;i<l->numberofkeywords;i++)
if(strcmp(l->keywords[i],word) == 0)
return l->size[i];
return -1;
}
struct hashtable* parseline(struct hashtable *h ,struct keywordlist *list ,char line[],int *address)
{
int commapresent=0;
int equaltopresent=0;
int numberofwords=1;
int size;
double initialvalue;
char word1[100],word2[100],initval[100],variablename[100];
char *datatype,*buffer,*temp;
int length = strlen(line);
int i,j,k;
for(i=0;i<strlen(line);i++)
{
if(line[i] == ' ')
numberofwords++;
else if(line[i]==',')
commapresent = 1;
else if(line[i] == '=')
equaltopresent = 1;
}
if(numberofwords == 1)
return NULL;
sscanf(line,"%s %s",word1,word2);
if(checklist(list,word1) < 0)
return NULL;
if(line[length-1]=='{' && line[length-2]=='(')
return NULL;
if(line[length-1]=='(' && commapresent ==0 && equaltopresent ==0)
return NULL;
if(line[length-1] == ')')
{
buffer = strsep(&line,")");
while(buffer!=NULL)
{
line = strsep(&buffer,",");
parseline(h,list,line,address);
}
}
else
{
datatype = strsep(&line," ");
while(line != NULL)
{
size = getsize(list,datatype);
strcpy(word1,datatype);
initialvalue = 0;
temp = strsep(&line,",");
for(i=0,j=0;i<strlen(temp);i++)
{
if(!((temp[i]>='a' && temp[i]<='z') || (temp[i]>='A' && temp[i]<='Z') || temp[i]=='_' || (j>0 && temp[i]>='0' && temp[i]<='9') || (j==0 && temp[i] == '*')))
{
if(!(temp[i] == ' ' && j==0))
break;
}
else
variablename[j++] = temp[i];
}
while(temp[i] ==' ')
i++;
variablename[j] = '\0';
if(temp[i] == '=')
{
i++;
while(temp[i]==' ')
i++;
for(k=0;;i++)
{
if(temp[i] == '\0' || temp[i] == ';' || temp[i] ==',')
{
if(k>0)
{
initval[k] ='\0';
initialvalue = strtod(initval,NULL);
}
break;
}
else if((temp[i]>='0' && temp[i] <= '9') || (temp[i]=='-' && k==0) ||(temp[i] == '.'))
initval[k++] = temp[i];
else
break;
}
}
if(variablename[0] == '*')
{
strcat(word1,"*");
for(i=1;i<=strlen(variablename);i++)
variablename[i-1] = variablename[i];
variablename[i] = '\0';
size = sizeof(int *);
}
// printf("\n\t\t\"%s\" datatype: %s size: %d address: %d initval:%d\n",variablename,word1,size,*address,initialvalue);
if(insertintohashtable(h,variablename,*address,initialvalue,word1,size) < 0)
return NULL;
*address = *address +size;
}
}
return h;
}
char * getlinefromfile(FILE *fp)
{
char *buffer = (char *)malloc(sizeof(char)*1000);
char ch='\0';
char ch2='\0';
int position = 0;
int pausereading = 0;
int multilinecomment = 0;
int singlelinecomment = 0;
int stopreading = 0;
while(ch2!=EOF)
{
ch = fgetc(fp);
ch2 = fgetc(fp);
fseek(fp,-1,SEEK_CUR);
if(ch == '/' && ch2=='/')
pausereading = singlelinecomment = 1;
else
if(ch == '/' && ch2 == '*')
pausereading = multilinecomment = 1;
if(ch == '\t')
ch = ' ';
if(ch2 == '\t')
ch2 = ' ';
if(pausereading == 0 && stopreading == 0)
{
if(ch == '\n')
{
if(position > 0 && buffer[0] == '#')
stopreading = 1;
}
else
{
if(ch == ';')
stopreading =1;
else if(ch == '{')
stopreading = 1;
else if(ch == '(')
stopreading = 1;
else if(ch == '}')
stopreading = 1;
else if(ch == ')')
stopreading = 1;
if(!(ch == ' ' && ch2 == ' ') && !(ch == ' ' && position == 0) && !(ch == ' ' && !((ch2>='a' && ch2<='z') || (ch2>='A' && ch2<='Z') || (ch2>='0' && ch2<='9') || ch2 =='_' || ch2 == '*')))
buffer[position++] = ch;
}
}
else
{
if(singlelinecomment == 1)
{
if(ch == '\n')
singlelinecomment = pausereading = 0;
}
else if(multilinecomment == 1)
{
if(ch == '*' && ch == '/')
multilinecomment = pausereading = 0;
}
}
if(stopreading == 1)
break;
}
if(position == 0)
return NULL;
buffer[position] ='\0';
return buffer;
}
struct hashtable* generatesymboltable(struct keywordlist *list,char *filename,int *address)
{
struct hashtable *h = createhashtable();
FILE *fp = fopen(filename,"r");
char *line = getlinefromfile(fp);
while(line != NULL)
{
parseline(h,list,line,address);
line = getlinefromfile(fp);
}
return h;
}
int main (int argc, char *argv[])
{
struct hashtable *h;
int i;
int address = strtol(argv[2],NULL,10);
int choice;
double input;
char ch,buffer[100],buffer2[100];
char *ret;
struct keywordlist *list = getkeywordlist();
h = generatesymboltable(list,argv[1],&address);
if(h!=NULL)
{
displayhashtable(h);
while(1)
{
printf("\nChoose operation: \n\t1. Display\n\t2. Insert\n\t3. Delete\n\t4. Search\n\t5. Update\n\t6. Exit\n\t:");
scanf("%d",&choice);
if(choice == 6)
break;
switch(choice)
{
case 1:
displayhashtable(h);
break;
case 2:
i=0;
printf("\nEnter Declaration Statmement(terminate with ;): ");
getchar();
while((ch=getchar()) != '\n')
buffer[i++] = ch;
buffer[i] = '\0';
strcpy(buffer2,buffer);
if(parseline(h,list,buffer2,&address) == NULL)
printf("\n\t%s contains symbols already present in symbol table\n",buffer);
else
printf("\n\t%s inserted into the symbol table\n",buffer);
break;
case 3:
printf("\nEnter symbol name: ");
scanf("%s",buffer);
if(deletefromhashtable(h,buffer) < 0 )
printf("\n\t%s not found in symbol table\n",buffer);
else
printf("\n\t%s deleted from symbol table\n",buffer);
break;
case 4:
printf("\nEnter symbol name: ");
scanf("%s",buffer);
ret = NULL;
ret = searchtable(h,buffer);
if(ret == NULL)
printf("\n\t%s not found in symbol table\n",buffer);
else
printf("\n\tSearch Result: %s\n",ret);
break;
case 5:
printf("\nEnter symbol name : ");
scanf("%s",buffer);
printf("\nEnter new value: ");
scanf("%lg",&input);
if(updatehashtable(h,buffer,input,SETVALUE) < 0)
printf("\n\t%s is not present in symbol table\n",buffer);
else
printf("\n\tInitial value of %s updated\n",buffer);
break;
default:
printf("\n\t Invalid choice\n");
}
}
}
return 0;
}
SAMPLE INPUT-FILE:-
int main()
{
int a=-35,b=22;
char *variable,variable2;
int* _a,_b;
void *x,*y;
short int variw;
double var=9.3287,var3;
return 0;
}
No comments:
Post a Comment