18CSC304J - COMPILER DESIGN

LAB RECORD

SEMESTER – VI

2023 - 2024

DEPARTMENT OF COMPUTER SCIENCE ENGINEERING

SRM INSTITUTE OF SCIENCE AND TECHNOLOGY
(UNDER SECTION 3 OF THE UGC ACT, 1956) VADAPALANI CAMPUS

CHENNAI - 600 026

1
 SRM INSTITUTE OF SCIENCE AND TECHNOLOGY
VADAPALANI CAMPUS
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

BONAFIDECERTIFICATE

Certified to be the bonafide record of the work done by ------------------------------------------------------------

Register Number --------------------------------------------------- ofB.Tech – CSE Specialization in AIML, Third

Year, VI Semester as a Partial Fulfillment of Degree of Bachelor of Technology in Computer Science and Engineering

with specialization in Artificial Intelligence and Machine Learning for the Laboratory of the course18CSC304J–

CompilerDesignduringthe academic year 2023-2024.

DATE FACULTY IN CHARGE HEAD OF THE DEPARTMENT

Submitted for even semester examination held on - atSRMIST,Vadapalani.

DATE Examiner-1 Examiner-II

2
 INDEX
Ex..NO Date Name of experiment Page
Sign
number
1. 18/1/2024 Implementation of Lexical Analyzer

2. 30/1/2024 Conversion from Regular Expression to NFA

3. 6/2/2024 Conversion from NFA to DFA

Elimination of Ambiguity, Left Factoring and

4. 13/2/2024
Left Recursion

5. 13/2/2024 FIRST and FOLLOW computation

6. 20/2/2024 Predictive Parsing Table

7. 27/2/2024 Shift Reduce Parsing

8. 5/3/2024 Computation of LEADING and TRAILING

9. 12/3/2024 Computation of LR(0) items

Intermediate Code Generation

10. 12/3/2024
Quadruple, Triple and Indirect Triple

Intermediate Code Generation

11. 19/3/2024
Postfix and Prefix

12. 19/3/2024 A Simple Code generator

13. 26/3/2024 Implementation of DAG

14. 3/4/2024 Implementation of Global Data Flow Analysis

15. 12/4/2024 Implementation of storage allocation strategies

3
Date :
Ex.No. : 1
Implementation of Lexical Analyzer

Aim:

To writea C program to implement Lexical Analyzer.

Algorithm:
1. Start
2. Get C program inputfile.
3. Read the contents of file character by character intoch.
4. If op contains ch, print operator.
5. If pun contains ch, print punctuation.
6. If ch is alphanumeric, store in buffer buf and read nextcharacter.
7. Store ch until whitespace or new line isencountered.
8. If keyword contains buf, printkeyword.
9. If isdigit(buf) true, printdigit.
10. Else, print identifier.

Program: #include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
int iskeyword(char buf[])
{
char keyword[11][10]={"int","float","for","while","if","else","do","double","return","void","main"};
int i, flag=0;
for(i=0;i<11;i++)
{
if(strcmp(keyword[i],buf)==0)
{
flag=1;
break;
}}
4
 return flag;
}
void main()
{
char op[7]={'+','-','=','*','/','%','&'};
char pun[3]={',',';','!'};
char ch,buf[15],name[10];
FILE *fp;
int i,j=0;
clrscr();
printf("enter file name: ");
scanf("%s",name);
fp=fopen(name,"r");
while((ch=fgetc(fp))!=EOF)
{
for(i=0;i<7;i++)
if(ch==op[i])
printf("\n%c: operator",ch);
for(i=0;i<3;i++) if(ch==pun[i])
printf("\n%c: punctuation",ch);
if(isalnum(ch))
buf[j++]=ch;
else
if((ch==' '||ch=='\n')&&(j!=0))
{
buf[j]='\0';
j=0;
if(iskeyword(buf)==1)
printf("\n%s: keyword",buf);
else if((int)buf[0]>=48&&(int)buf[0]<=57)
printf("\n%s: digit",buf);
5
 else
printf("\n%s: identifier",buf);
}}
fclose(fp);g
etch();
}

Output:

Result:
Thus, the C program to implement lexical analyzer has been executed and the output has been verified
successfully

6
 Date : Regular Expression to NFA
Ex.No. : 2

Aim:
To write a program to convert Regular Expression to NFA.
Algorithm:
1. Start
2. Get input of the regularexpression.
3. Read input character by character intos.
4. If s is alphabet, store inret[].
5. If s is ‘.’, ‘+’, ‘*’, determine transition inputs according to Thompson’sConstruction.
6. Store the transition inputs inret.
7. Display the output.

Program: #include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
int ret[100];
static int pos=0;
static int sc=0;
void nfa(int st, int p, char* s)
{
inti,sp,fs[15],fsc=0;
sp=st;
pos=p;s
c=st;
while(*s!=NULL)
{
if(isalpha(*s))
{
ret[pos++]=sp;
ret[pos++]=*s;
ret[pos++]=++sc;
7
}
if(*s=='.')
{
sp=sc; ret[pos++]=sc;
ret[pos++]=238;
ret[pos++]=++sc;
sp=sc;
}
if(*s=='+')
{
sp=st;
fs[fsc++]=sc;
}
if(*s=='*')
{
ret[pos++]=sc;
ret[pos++]=238;
ret[pos++]=sp;
ret[pos++]=sp;
ret[pos++]=238;r
et[pos++]=sc;
}
if(*s=='(')
{
char ps[50]

8
int i=0, flag=1; s++;
while(flag!=0)
{
ps[i++]=*s;
if(*s=='(')
flag++;
if(*s==')')
flag--;
s++;
}
ps[--i]='\0';
nfa(sc,pos,ps);
s--;
}
s++;
}
sc++;
}
void main()
{
int i;
char *inp;
printf("\nenter the regular expression: ");
gets(inp);
nfa(1,0,in
p);
printf("\nstate input state\n");

for(i=0;i<pos;i+=3)

9
 printf("%d -->%c--> %d\n",ret[i],ret[i+1],ret[i+2]);
printf("\n");
getch();
}

Output:

Result:

Thus, the C program to construct NFA for the given regular expression has been executed and the output has
been verified successfully

10
Date : Conversion of NFA to DFA
Ex.No. :3

Aim:
To write a program to convert NFA to DFA.
Algorithm:
1. Start
2. Get the input for NFAtransitions.
3. Determine the closure of input state.
4. Find the states that can be traversed from present for each inputsymbol.
5. If any new state is found, take it as current state and repeat step4.
6. Repeat steps 4 and 5 until no new state isfound.
7. Display the DFAtable.
Program:
#include<stdio.h>
#include<conio.h>
#include<string.h>
char nfa[50][50],s[20],st[10][20],eclos[20],input[20];
int x,e,top=0,topd=0,n=0,ns,nos,in;
int checke(char a)
{
int i;
for(i=0;i<e;i++)
{
if(eclos[i]==a)r
eturn i;
}
return-1;
}
int check(chara)
{
11
 int i;
for(i=0;i<in;i++)
{
if(input[i]==a)
return i;
}
return -1;
}
void push(char a)
{
s[top]=a;
top++;
}
char pop()
{
top--;
return s[top];
}
void pushd(char *a)
{
strcpy(st[topd],a);
topd++;
}
char *popd()
{
topd--;
return st[topd];
}
int ctoi(char a)
{
int i=a-48;
12
 return i;
}
char itoc(int a)
{
char i=a+48;
return i;
}
char *eclosure(char *a)
{
int i,j; char c;
for(i=0;i<strlen(a);i++)
push(a[i]); e=strlen(a);
strcpy(eclos,a);
while(top!=0)
{
c=pop(); for(j=0;j<ns;j++)
{
if(nfa[ctoi(c)][j]=='e')
{
if(check(itoc(j))==-1)
{
eclos[e]=itoc(j); push(eclos[e]);
e++;
}
}
}
}
eclos[e]='\0'; return
eclos;
}
void main()
13
 {
int i,j,k,count;
char ec[20],a[20],b[20],c[20],dstates[10][10]; clrscr();
printf("Enter the number of states\n");
scanf("%d",&ns);
for(i=0;i<ns;i++)
{
for(j=0;j<ns;j++)
{
printf("Move [%d][%d]:",i,j);
scanf("%s",&nfa[i][j]); if(nfa[i][j]!='-' && nfa[i][j]!='e')
{
if((check(nfa[i][j]))==-1) input[in++]=nfa[i][j];
}
}
}d=0; nos=0; c[0]=itoc(0);
c[1]='\0';
pushd(eclosure(c));
strcpy(dstates[nos],eclosure(c));
for(x=0;x<in;x++)
printf("\t%c",input[x]); printf("\n");
while(topd>0)
{
strcpy(a,popd());
printf(" %s",a); for(i=0;i<in;i++)
{
int len=0; for(j=0;j<strlen(a);j++)
{
int x=ctoi(a[j]); for(k=0;k<ns;k++)
{
if(nfa[x][k]==input[i]) ec[len++]=itoc(k);
14
 }
}
ec[len]='\0'; strcpy(b,eclosure(ec)); count=0;
for(j=0;j<=nos;j++)
{
if(strcmp(dstates[j],b)==0) count++;
}
if(count==0)
{
if(b[0]!='\0')
{
nos++; pushd(b);
strcpy(dstates[nos],b);
}
}
printf("\t%s",b);
}
printf("\n");
}
getch();
}

15
Output:

Result:
Thus, the C program to convert NFA to DFA has been executed and the output has been verified successfully

16
 Date :
Ex.No. : 5.a
Left Recursion

Aim:
To write program to perform Left recursion.

Algorithm:
1. For each nonterminal :
a. Repeat until an iteration leaves the grammar unchanged:
b. For each rule , being a sequence of terminals and non terminals.
2. If begins with a nonterminal and :
a. Let be without its leading.
b. Remove the rule .
c. For each rule :
d. Add the rule .
3. Remove direct left recursion for as described above.

Program:
#include<stdio.h>
#include<string.h>
int main()
{ int i,j,n,k;
int lrec = 0;
char prod[100];
char newprod1[100]= "";
char newprod2[100]= "";
char alpha[100] = "";
char beta[100]= "";
char sts[20]="";
scanf("%s",prod);
sts[0] = prod[0]; // sts is Start Symbol
int size = (int)(strlen(prod));
for(i=0;i<size;i++) {
if(prod[i] == '|')
{ k = i; } }
if(prod[3] == prod[0]) //E->E+T
{ lrec = 1;
17
 }
if(lrec == 1)
{
int c =0;
k = k-1;
for(i=4;i<=k;i++)
{
alpha[c] = prod[i];
c++;
}
c = 0;
for(i=k+2;i<size;i++)
{
beta[c] = prod[i];
c++;
}
strcat(newprod1,sts);//-,E
//printf(strcat(newprod1,sts));
strcat(newprod1,"->");//->
strcat(newprod1,beta);//T
strcat(newprod1,sts);//E
strcat(newprod1,"'");//E'
strcat(newprod2,sts);//E
strcat(newprod2,"'");//E'
strcat(newprod2,"->");//->
strcat(newprod2,alpha);//+T
strcat(newprod2,sts);//E
strcat(newprod2,"'");//'
strcat(newprod2,"|e");//|e
printf("\n%s\n%s",newprod1,newprod2);//E->TE' }
}

18
Output:

Result:
Thus, the C program to remove Left recursion in the given grammar has been executed and the output has been
verified successfully

19
 Date :
Ex.No. : 5.b
Left Factoring

Aim:
To write program to perform Left recursion.

Algorithm:

1. For each non terminal A find the longest prefix α common to two or more of its alternatives.
2. If α!= E,i. e., there is a non trivial common prefix, replace all the A productions.
3. A-> αβ1| αβ2|…………..| αβn| ɣ where ɣ represents all alternatives that do not begin with α by
4. A==> α A’| ɣ
5. A’==>β1|β2|………….|βn
6. Here A’ is new non terminal. Repeatedly apply this transformation until no two alternatives for a non-
terminal have a common prefix.

Program:
#include<stdio.h>
#include<string.h>
int main()
{
char a[10],a1[10],a2[10],a3[10],a4[10],a5[10];
int i,j=0,k,l;
printf("Enter any productions A->");
gets(a);
for(i=0;a[i]!='|';i++,j++)
a1[j]=a[i];
a1[j]='\0';
for(j=++i,i=0;a[j]!='\0';j++,i++)
a2[i]=a[j];
a2[i]='\0';
k=0; l=0;
for(i=0;i<strlen(a1)||i<strlen(a2);i++)
{
if(a1[i]==a2[i])
20
 {
a3[k]=a1[i];
k++;
}
else
{
a4[l]=a1[i];
a5[l]=a2[i];
l++;
}
}
a3[k]='A';
a3[++k]='\0';
a4[l]='|';
a5[l]='\0';
a4[++l]='\0';
//printf("%s",a1);
//printf("\n99.%s",strcat(a4,a3));
printf("\n A->%s'",a3);
printf("\n A'->%s|\356",a5);
return 0;
}
Output:

Result:
Thus, the C program to generate left factored grammar has been executed and the output has been verified

21
 Date :
Ex.No. :5
Computation of First and Follow Sets

Aim:

To write a program to compute first and follow sets of grammar productions.

Algorithm:
1. Start
2. Check whether the first element of a non-terminal production is aterminal.
3. If true, add it to First(NT).
4. For Follow, check if the NT exists on RHS of anyproduction.
If next symbol is
i. NT, then add First(NT) to Follow.
ii. T, add T toFollow.
iii. Nothing, then add Follow(source) toFollow.
Program:
#include<stdio.h>
#include<conio.h>
#include<String.h> int
n,m=0,p,i=0,j=0; char
a[10][10],f[10]; void
follow(char c); void
first(char c); void
main()
{
int i,z; char
c,ch;
clrscr();
printf("Enter the no of productions:\n");
scanf("%d",&n);
printf("Enter the productions:\n");
for(i=0;i<n;i++)
scanf("%s%c",a[i],&ch);
do{
m=0; 22
 printf("Enter the elemets whose fisrt & follow is to be found:");
scanf("%c",&c);
first(c);
printf("First(%c)={",c);
for(i=0;i<m;i++)
printf("%c",f[i]);
printf("}\n");
strcpy(f,"");
flushall();
m=0;
follow(c);
printf("Follow(%c)={",c);
for(i=0;i<m;i++)
printf("%c",f[i]);
printf("}\n");
printf("Continue(0/1)?");
scanf("%d%c",&z,&ch);
}while(z==1);
getch();
}

void first(char c)
{
int k; if(!isupper(c))
f[m++]=c;
for(k=0;k<n;k++)if
(a[k][0]==c)

{
if(a[k][2]=='$')
follow(a[k][0]);
else if(islower(a[k][2]))
23
f[m++]=a[k][2];
else first(a[k][2]);
}
}
}
void follow(char c)
{
if(a[0][0]==c)
f[m++]='$';
for(i=0;i<n;i++)
{
for(j=2;j<strlen(a[i]);j++)
{
if(a[i][j]==c)
{
if(a[i][j+1]!='\0')
first(a[i][j+1]); if(a[i][j+1]=='\0' &&
c!=a[i][0])
follow(a[i][0]);
}}
}}

24
 Output:

Result:
Thus, the C program to compute First( ) and Follow( ) for the non-terminals of given CFG has been executed and
the output has been verified successfully

25
 Date :
Ex.No. : 6
Construction of Predictive Parsing Table

Aim:
To write a program to construct predictive parsing table.

Algorithm:
1. Start
2. Find the first and follow of eachNT.
3. For each production A->α inG
4. For each terminal a inFirst(α).
5. Add A-> α toM[A,a].
6. If € is in First(α)
7. For each symbol b inFollow(A).
8. Add A-> α toM[A,b].
Program:
#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char fin[10][20],st[10][20],ft[20][20],fol[20][20];
int a=0,e,i,t,b,c,n,k,l=0,j,s,m,p;
clrscr();
printf("enter the no. of coordinates\n");
scanf("%d",&n);
printf("enter the productions in a grammar(@ for epsilon)\n");
for(i=0;i<n;i++)
scanf("%s",st[i]);
for(i=0;i<n;i++)
fol[i][0]='\0';
for(s=0;s<n;s++)
{

26
 for(i=0;i<n;i++)
{
j=3;
l=0;
a=0;
l1:if(!((st[i][j]>64)&&(st[i][j]<91)))
{
for(m=0;m<l;m++)
{
if(ft[i][m]==st[i][j]) goto s1;
}
t[i][l]=st[i][j];
s1:j=j+1;
}
else
{
if(s>0)
{

while(st[i][t]!=st[a][0]) a++;
b=0;
while(ft[a][b]!='\0')
{
for(m=0;m<l;m++)
{

27
if(ft[i][m]==ft[a][b]) goto s2;
}}}}
while(st[i][j]!='\0')
{
if(st[i][j]=='|')
{
j=j+1;
goto l1;
}
j=j+1;
}
ft[i][l]='\0';
}}
printf("first pos\n");
for(i=0;i<n;i++)
printf("FIRS[%c]=%s\n",st[i][0],ft[i]);
fol[0][0]='$';
for(i=0;i<n;i++)
{
k=0;
j=3;
if(i==0)

l=1;
else
l=0;
k1:while((st[i][0]!=st[k][j])&&(k<n))
{
if(st[k][j]=='\0')
{ 28
 k++;
j=2;
}
j++;
}
j=j+1;
if(st[i][0]==st[k][j-1])
{
if((st[k][j]!='|')&&(st[k][j]!='\0'))
{
a=0;
if(!((st[k][j]>64)&&(st[k][j]<91)))
{
for(m=0;m<l;m++)
{
if(fol[i][m]==st[k][j]) goto q3;
}
fol[i][l]=st[k][j]; l++;

q3:

else
{
While

(st[k][j]!=st[a][0]) a++;

29
{
if(ft[a][p]!='@')
{
for(m=0;m<l;m++)
{
if(fol[i][m]==ft[a][p]) goto q2;
}
l=l+1;
fol[i][l]=ft[a][p];
e=1; q2:p++;
}
if(e==1)
{
e=0;
goto a1;
else
{
a1:c=0; a=0;
while(st[k][0]!=st[a][0])
{

30
 while((fol[a][c]!='\0')&&(st[a][0]!=st[i][0]))
{
for(m=0;m<l;m++)
{
if(fol[i][m]==fol[a][c])
goto q1;
}
fol[i][l]=fol[a][c];
l++;
q1:c++;
}
}
goto k1;
}
fol[i][l]='\0';
}
printf("follow pos\n");
for(i=0;i<n;i++)

31
 printf("FOLLOW[%c]=%s\n",st[i][0],fol[i]);
printf("\n");
s=0;
for(i=0;i<n;i++)
{
j=3;
while(st[i][j]!='\0')
{
if((st[i][j-1]=='|')||(j==3))
{
for(p=0;p<=2;p++)
{
fin[s][p]=st[i][p];
}
t=j;
for(p=3;((st[i][j]!='|')&&(st[i][j]!='\0'));p++)
{
fin[s][p]=st[i][j];
j++;
}
fin[s][p]='\0';
if(st[i][k]=='@')
{
b=0;
a=0;
while(st[a][0]!=st[i][0])
a++;

32
 while(fol[a][b]!='\0')
{
printf("M[%c,%c]=%s\n",st[i][0],fol[a][b],fin[s]);
b++;
}}
else if(!((st[i][t]>64)&&(st[i][t]<91)))
printf("M[%c,%c]=%s\n",st[i][0],st[i][t],fin[s]);
else
{
b=0;
a=0;
while(st[a][0]!=st[i][3])
a++;
while(ft[a][b]!='\0')
{
printf("M[%c,%c]=%s\n",st[i][0],ft[a][b],fin[s]);
b++;
}}
s++;
}
if(st[i][j]=='|')
j++;
}}
getch();
}

33
 Output:

Result:

Thus, the C program to predictive parsing table for the given LL(1) grammar has been executed and the output
has been verified successfully

34
Date :
Ex.No. : 7
Implementation of Shift Reduce Parsing

Aim:

To write a program to implement shift reduce parsing.

Algorithm:
1. Start
2. Get the inputstring.
3. Read the data from input buffer one at atime.
4. Using stack and push & pop operations, shift and reduce symbols with respect to productionrules.
5. Continue the process till symbol shift and production rules reduce reaches the startsymbol.
6. Display stack implementationtable.
Program:
#include<stdio.h>
#include<conio.h>
#include<string.h>
int k=0,z=0,i=0,j=0,c=0;
char a[16],ac[20],stk[15],act[10];
void check();
voidmain()
{
clrscr();
puts("GRAMMAR is E->E+E \n E->E*E \n E->(E) \n E->id");
puts("enter input string ");
gets(a);
c=strlen(a);
strcpy(act,"SHIFT->");
puts("stack \t input \t action");
for(k=0,i=0; j<c; k++,i++,j++)
{
if(a[j]=='i' && a[j+1]=='d')
35
{
stk[i]=a[j];
stk[i+1]=a[j+1];
stk[i+2]='\0';
a[j]=' ';
a[j+1]=' ';
printf("\n$%s\t%s$\t%sid",stk,a,act);
check();
}
else
{
stk[i]=a[j];
stk[i+1]='\0';
a[j]=' ';
printf("\n$%s\t%s$\t%ssymbols",stk,a,act);
check();
}
}
getch();
}
void check()
{
strcpy(ac,"REDUCE TO E");
for(z=0; z<c; z++)
if(stk[z]=='i' && stk[z+1]=='d')
{
stk[z]='E';

36
 stk[z+1]='\0';
printf("\n$%s\t%s$\t%s",stk,a,ac);
j++;
}
for(z=0; z<c; z++)
if(stk[z]=='E' && stk[z+1]=='+' && stk[z+2]=='E')
{
stk[z]='E';
stk[z+1]='\0';
stk[z+2]='\0';
printf("\n$%s\t%s$\t%s",stk,a,ac);
i=i-2;
}
for(z=0; z<c; z++)
if(stk[z]=='E' && stk[z+1]=='*' && stk[z+2]=='E')
{
stk[z]='E';
stk[z+1]='\0';
stk[z+1]='\0';
printf("\n$%s\t%s$\t%s",stk,a,ac);
i=i-2;
}
for(z=0; z<c; z++)
if(stk[z]=='(' && stk[z+1]=='E' && stk[z+2]==')')
{
stk[z]='E';
stk[z+1]='\0';

37
 stk[z+1]='\0';
printf("\n$%s\t%s$\t%s",stk,a,ac);
i=i-2;
}
}

Output:

Result:

Thus, the C program to perform shift/reduce parsing has been executed and the output has been verified
successfully

38
 Date :
Ex.No. :
Computation of Leading and Trailing Sets

Aim:
To write a program to compute Leading and Trailing sets.

Algorithm:
1. Start
2. Get the input ofproductions.
3. WithavariablevalforcheckingthevalidNT,iftheyareduplicated, getallnonterminalsinanarray.
4. In each production, check the first occurrence of terminal and add it toLeading(NT).
5. Scan the productions and find the last terminal. Add it toTrailing(NT).
6. ConsiderproductionswithNTonRHSandcheckleadingandtrailingofthatNTandaddittoleading and
trailing of left sideNT.
Program:
#include<iostream>
using namespace std;
#include<string.h>
#include<conio.h>
int nt,t,top=0;
char s[50],NT[10],T[10],st[50],l[10][10],tr[50][50];
int searchnt(char a)
{
int count=-1,i;
for(i=0;i<nt;i++)
{
if(NT[i]==a)
return i;
} return count;
}
int searchter(char a)
39
{
int count=-1,i;
for(i=0;i<t;i++)
{
if(T[i]==a)
return i;
}
return count;
}
void push(char a)
{
s[top]=a;
top++;
}
char pop()
{
top--;
return s[top];
}
void installl(int a,int b)
{
if(l[a][b]=='f')
{
l[a][b]='t';
push(T[b]);
push(NT[a]);
}
}
void installt(int a,int b)
{
if(tr[a][b]=='f')
{
40
tr[a][b]='t';
push(T[b]);
push(NT[a]);
}}
int main()
{
int i,s,k,j,n;
char pr[30][30],b,c;
//clrscr(); cout<<"Enter the no of productions:";
cin>>n;
cout<<"Enter the productions one by one\n";
for(i=0;i<n;i++)
cin>>pr[i];
nt=0;
t=0;
for(i=0;i<n;i++)
{
if((searchnt(pr[i][0]))==-1)
NT[nt++]=pr[i][0];
}
for(i=0;i<n;i++)
{
for(j=3;j<strlen(pr[i]);j++)
{
if(searchnt(pr[i][j])==-1)
{
if(searchter(pr[i][j])==-1)
T[t++]=pr[i][j];
}
}
}
for(i=0;i<nt;i++)
41
{
for(j=0;j<t;j++)
l[i][j]='f';
}
for(i=0;i<nt;i++)
{
for(j=0;j<t;j++)
tr[i][j]='f';
}
for(i=0;i<nt;i++)
{
for(j=0;j<n;j++)
{
if(NT[(searchnt(pr[j][0]))]==NT[i])
{
if(searchter(pr[j][3])!=-1)
installl(searchnt(pr[j][0]),searchter(pr[j][3]));
else
{
for(k=3;k<strlen(pr[j]);k++)
{ if(searchnt(pr[j][k])==-1)
{
installl(searchnt(pr[j][0]),searchter(pr[j][k]));
break;
}
}
}
}
}
}
while(top!=0)
{
42
b=pop();
c=pop();
for(s=0;s<n;s++)
{
if(pr[s][3]==b)
installl(searchnt(pr[s][0]),searchter(c));
}
}
for(i=0;i<nt;i++)
{
cout<<"Leading["<<NT[i]<<"]"<<"\t{";
for(j=0;j<t;j++)
{
if(l[i][j]=='t')
cout<<T[j]<<",";
}
cout<<"}\n";
}
top=0;
for(i=0;i<nt;i++)
{
for(j=0;j<n;j++)
{
if(NT[searchnt(pr[j][0])]==NT[i])
{
if(searchter(pr[j][strlen(pr[j])-1])!=-1)
installt(searchnt(pr[j][0]),searchter(pr[j][strlen(pr[j])-1]));
else
{
for(k=(strlen(pr[j])-1);k>=3;k--)
{
if(searchnt(pr[j][k])==-1)
43
{
installt(searchnt(pr[j][0]),searchter(pr[j][k]));
break;
}
}
}
}
}
}
while(top!=0)
{
b=pop();
c=pop();
for(s=0;s<n;s++)
{
if(pr[s][3]==b)
installt(searchnt(pr[s][0]),searchter(c));
}
}
for(i=0;i<nt;i++)
{
cout<<"Trailing["<<NT[i]<<"]"<<"\t{";
for(j=0;j<t;j++)
{
if(tr[i][j]=='t')
cout<<T[j]<<",";
}
cout<<"}\n";
}
return 0;

44
 Output:

Results:

Thus, the C program to compute leading and trailing sets have been executed and the output has been verified
successfully

45
 Date :
Ex.No. :9
Computation of LR(0)

Aim:

To write a program to compute LR(0) items.

Algorithm
1. Start
2. Generate augmentedgrammar.
3. Start with C0 by including all marked productions[S->.α]
4. Compute the closure of item setC0
5. Perform a read operation on items in an itemset.
6. Compute the closure of new itemset.
7. Continue reading until all .S have travelled through all itemsets
Program:
#include<iostream.h>#i
nclude<conio.h>
#include<string.h>
char prod[20][20],listofvar[26]="ABCDEFGHIJKLMNOPQR";
int novar=1,i=0,j=0,k=0,n=0,m=0,arr[30];
int noitem=0;
struct Grammar
{ char lhs;
char rhs[8];
}g[20],item[20],clos[20][10];
int isvariable(char variable)
{ for(int i=0;i<novar;i++)
if(g[i].lhs==variable)
return i+1;
return 0;
} void findclosure(int z, char a)

46
 { int n=0,i=0,j=0,k=0,l=0;
for(i=0;i<arr[z];i++)
{
for(j=0;j<strlen(clos[z][i].rhs);j++)
{
if(clos[z][i].rhs[j]=='.' && clos[z][i].rhs[j+1]==a)
{
clos[noitem][n].lhs=clos[z][i].lhs;
strcpy(clos[noitem][n].rhs,clos[z][i].rhs);
chartemp=clos[noitem][n].rhs[j];
clos[noitem][n].rhs[j]=clos[noitem][n].rhs[j+1];
clos[noitem][n].rhs[j+1]=temp;
n=n+1;
}}}

for(i=0;i<n;i++)
{
for(j=0;j<strlen(clos[noitem][i].rhs);j++)
{
if(clos[noitem][i].rhs[j]=='.' && isvariable(clos[noitem][i].rhs[j+1])>0)
{
for(k=0;k<novar;k++)
{
if(clos[noitem][i].rhs[j+1]==clos[0][k].lhs)
{
for(l=0;l<n;l++)
if(clos[noitem][l].lhs==clos[0][k].lhs &&strcmp(clos[noitem][l].rhs,clos[0][k].rhs)==0) break;

47
if(l==n) { clos[noitem][n].lhs=clos[0][k].lhs;
strcpy(clos[noitem][n].rhs,clos[0][k].rhs); n=n+1;
}}}}}}
arr[noitem]=n; int
flag=0;
for(i=0;i<noitem;i++)
{
if(arr[i]==n)
{
for(j=0;j<arr[i];j++)
{ int c=0; for(k=0;k<arr[i];k++)
if(clos[noitem][k].lhs==clos[i][k].lhs && strcmp(clos[noitem][k].rhs,clos[i][k].rhs)==0) c=c+1;
if(c==arr[i])
{ flag=1;
goto exit;
}}}}
exit:; if(flag==0)
arr[noitem++]=n;
}
void main()

{clrscr();
cout<<"ENTER THE PRODUCTIONS OF THE GRAMMAR(0 TO END) :\n";
do

48
 cin>>prod[i++];
}while(strcmp(prod[i-1],"0")!=0);
for(n=0;n<i-1;n++)
{
m=0;
j=novar;
g[novar++].lhs=prod[n][0];
for(k=3;k<strlen(prod[n]);k++)
{ if(prod[n][k] != '|')
g[j].rhs[m++]=prod[n][k];
if(prod[n][k]=='|')
{ g[j].rhs[m]='\0';
m=0;
j=novar;
g[novar++].lhs=prod[n][0];
}
}}
for(i=0;i<26;i++)
if(!isvariable(listofvar[i]))
break;
g[0].lhs=listofvar[i];
char temp[2]={g[1].lhs,'\0'};
strcat(g[0].rhs,temp);

49
cout<<"\n\n augumented grammar \n";
for(i=0;i<novar;i++)
cout<<endl<<g[i].lhs<<"->"<<g[i].rhs<<""; getch();
for(i=0;i<novar;i++)
{
clos[noitem][i].lhs=g[i].lhs;
strcpy(clos[noitem][i].rhs,g[i].rhs);
if(strcmp(clos[noitem][i].rhs,"ε")==0)
strcpy(clos[noitem][i].rhs,".");
else
{ for(int j=strlen(clos[noitem][i].rhs)+1;j>=0;j-
clos[noitem][i].rhs[j]=clos[noitem][i].rhs[j-1];
clos[noitem][i].rhs[0]='.';
}
}
arr[noitem++]=novar; for(int
z=0;z<noitem;z++)
{ char list[10];
int l=0; for(j=0;j<arr[z];j++)
{
for(k=0;k<strlen(clos[z][j].rhs)-1;k++)
{
if(clos[z][j].rhs[k]=='.')
{
for(m=0;m<l;m++)

50
if(list[m]==clos[z][j].rhs[k+1]) break;
if(m==l) list[l++]=clos[z][j].rhs[k+1];
}} }
for(int x=0;x<l;x++)
findclosure(z,list[x]);
}
cout<<"\n THE SET OF ITEMS ARE \n\n";
for(z=0;z<noitem;z++)
{ cout<<"\n I"<<z<<"\n\n";
for(j=0;j<arr[z];j++)
cout<<clos[z][j].lhs<<"->"<<clos[z][j].rhs<<"\n";
getch();
}
getch();
}

51
Output:

52
Result:
Thus, the C program to generate LR(0) items has been executed and the output has been verified successfully

53
 Date :
Ex.No. :10
Intermediate Code Generation- Three Address Codes
Aim:
To write a C Program to generate a three address code.

Algorithm:
1. Initially check the choice of the user
2. Assignment shows how it is assigned in three address code
3. Arithmetic shows how it solves in three address code
4. Relational shows how it proves the relations in three address code
5. Stop the program by exit

Code:
#include"stdio.h"
#include"conio.h"
#include"string.h"
#include"process.h"
int i=1,j=0,no=0,tmpch=90;
char str[100],left[15],right[15];
void findopr();
void explore();
void fleft(int);
void fright(int);
struct exp
{
int pos;
char op;
}k[15];
void main()
{
printf("Enter the Expression :- ");
scanf("%s",str);
printf("The Intermediate code:-\t\tExpression\n");
findopr();
explore();
getch();
54
}
void findopr()
{ for(i=0;str[i]!='\0';i++)
if(str[i]==':')
{
k[j].pos=i;
k[j++].op=':';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='/')
{
k[j].pos=i;
k[j++].op='/';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='*')
{
k[j].pos=i;
k[j++].op='*';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='+')
{
k[j].pos=i;
k[j++].op='+';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='-')
{
k[j].pos=i;
k[j++].op='-';
}
55
}
void explore()
{
i=1;
while(k[i].op!='\0')
{
fleft(k[i].pos);
fright(k[i].pos);
str[k[i].pos]=tmpch--;
printf("\t%c := %s%c%s\t\t",str[k[i].pos],left,k[i].op,right);
for(j=0;j <strlen(str);j++)
if(str[j]!='$')
printf("%c",str[j]);
printf("\n");
i++;
}
fright(-1);
if(no==0)
{
fleft(strlen(str));
printf("\t%s := %s",right,left);
getch();
exit(0);
}
printf("\t%s := %c",right,str[k[--i].pos]);
getch();
}
void fleft(int x)
{
int w=0,flag=0;
x--;

56
while(x!= -1 &&str[x]!= '+' &&str[x]!='*'&&str[x]!='='&&str[x]!='\0'&&str[x]!='
'&&str[x]!='/'&&str[x]!=':')
{
if(str[x]!='$'&& flag==0)
{
left[w++]=str[x];
left[w]='\0';
str[x]='$';
flag=1;
}
x--;
}
}
void fright(int x)
{
int w=0,flag=0;
x++;
while(x!= -1 && str[x]!= '+'&&str[x]!='*'&&str[x]!='\0'&&str[x]!='='&&str[x]!=':'&&str[x]!='-
'&&str[x]!='/')
{
if(str[x]!='$'&& flag==0)
{
right[w++]=str[x];
right[w]='\0';
str[x]='$';
flag=1;
}
x++;
}
}

57
OUTPUT:

RESULT:
Thus, the C program to generate 3-address code for the give expression has been executed and the output has
been verified successfully

58
 Date :
Ex.No. : 11
Intermediate Code Generation- Prefix, Postfix

Aim:

To write a program to convert infix expression to postfix and prefix expression.

Algorithm:
1. Scan the infix expression from left toright.
2. If the scanned character is an operand, outputit.
3. Else,
i. If the precedence of the scanned operator is greater than the precedence of the operator in the
stack(or the stack is empty), pushit.
ii. Else,Poptheoperatorfromthestackuntiltheprecedenceofthescannedoperatorisless-equal
totheprecedenceoftheoperatorresidingonthetopofthestack.Pushthescannedoperatorto thestack.
4. If the scanned character is an ‘(‘, push it to thestack.
5. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ isencountered.
6. Repeat steps 2-6 until infix expression is scanned.
7. Pop and output from the stack until it is not empty. Output is postfixexpression.
8. Reverse the infixstring.
9. Apply infix to postfixoperations.
10. Reversed output string is prefix expression.
Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int pop();
int precedence(char symbol);
int isEmpty();
void infix_to_prefix();
void infix_to_postfix(); int
checker(char symbol);
void push(long int symbol);

59
char prefix_string[20], infix_string[20], postfix_string[20];
int top;
long int stack[20];

int main()
{
int i, length;
char temp;
top = -1;
clrscr();
printf("\nEnter an Expression in Infix format:\t");
scanf("%[^\n]s", infix_string); infix_to_postfix();
printf("\nExpression in Postfix Format: \t%s\n", postfix_string);
strrev(infix_string);
infix_to_prefix();
strrev(postfix_string);
strcpy(prefix_string,postfix_string);
length=strlen(prefix_string);
printf("\nExpression in Prefix Format: \t");
for(i=0;i<length;i++)
if(prefix_string[i]!='(' && prefix_string[i]!=')')
printf("%c",prefix_string[i]);
getch();
return 0;
}

60
 void infix_to_postfix()
{
unsigned int count, temp = 0; char
next;
char symbol;
for(count = 0; count < strlen(infix_string); count++)
{

symbol = infix_string[count];
if(!checker(symbol))
switch(symbol)
{
case '(': push(symbol); break;
case ')':
while((next = pop()) != '(') postfix_string[temp++] = next;
break; case '+':
case '-':
case '*':
case '/':
case '%':
case '^':
while(!isEmpty() && precedence(stack[top]) >= precedence(symbol)) postfix_string[temp++] = pop();
push(symbol); break; default:

61
postfix_string[temp++] = symbol;
}}
while(!isEmpty())
postfix_string[temp++] = pop();
postfix_string[temp] = '\0';
}
void infix_to_prefix()
{ unsigned int count, temp = 0;
charnext;
char symbol;
for(count = 0; count < strlen(infix_string); count++)
{

symbol = infix_string[count];
if(!checker(symbol))
switch(symbol)
{
case ')': push(symbol); break;
case '()':
while((next = pop()) != ')') postfix_string[temp++] = next;
break; case '+':
case '-':
case '*':
case '/':
case '%':
case '^':

62
while(!isEmpty() && precedence(stack[top]) >= precedence(symbol)) postfix_string[temp++] = pop();
push(symbol); break; default:
postfix_string[temp++] = symbol;
}}
while(!isEmpty()) postfix_string[temp++]=
pop();
postfix_string[temp] = '\0';
}
int precedence(char symbol)
{ switch(symbol)
{
case '(': return 0; case '+':
case '-':
return 1; case '*':
case '/':
case '%':
return 2; case '^':
return 3; default:
return 0;
}}

63
int checker(char symbol)
{ if(symbol == '\t' || symbol == '')
return1;
return 0;
}
void push(long int symbol)
{ if(top >20)
{
printf("Stack Overflow\n");
exit(1);
}
top = top + 1;
stack[top] = symbol;
}
int isEmpty()
{ if(top ==-1)
return 1;
return 0;
}
int pop()
{ if(isEmpty())
{
printf("Stack is Empty\n");
exit(1);
}
return(stack[top--]);
}

64
 Output:

Result:

Thus, the C program to convert the given infix to prefix and postfix expression has been executed and the output
has been verified successfully

65
 Date : SIMPLECODEGENERATOR
Ex.No. :12

Aim:
Towriteaprogramtogenerateasimplecode.

Algorithm:

1. StartGetaddresscodesequence.
2. Determinecurrentlocationof3using address(for1stoperand).
3. Ifcurrentlocationnotalreadyexistgeneratemove(B,O).
4. UpdateaddressofA(for2ndoperand).
5. IfcurrentvalueofBand () isnull,exist.
6. Iftheygenerateoperator()A,3ADPR.
7. Storethemoveinstructioninmemory
8. Stop
Program:

#include<iostream>usingnamespa
cestd;#include<string.h>#include
<conio.h>
charreg[10][3]={"R0","R1","R2","R3","R4","R5"};
char
stmt[10][10],code[15];intnostmt=0,i=0,o
utput[15];
void icode(charsource[10],chardest[10],intout)
{
strcat(code,source);strcat(code
,"");strcat(code,dest);output[i]
=out;cout<<code<<endl;getch
();
}
intmain()
{
//clrscr();intj,i;
cout<<"Enterthestatements(ENDto end):\n";do

{
cin>>stmt[nostmt++];
}while(strcmp(stmt[nostmt-
1],"END")!=0);nostmt=nostmt-1;
cout<<"\nTHEINTERMEDIATECODEIS\n\n";
for(i=0;i<nostmt;i++)
{
strcpy(code,"");int rd=- 66
1,k;for(j=0;j<i;j++)
{
if(stmt[j][0]==stmt[i][2])rs=output[j];if(st
mt[j][0]==stmt[1][4])rd=output[j];
}
if(rs==-1)
{
strcpy(code,"MOV");
chartemp[2]={stmt[i][2],'\0'};icode(temp,reg
[i],i);
}
if(stmt[i][3]=='+')
strcpy(code,"ADD
");if(stmt[i][3]=='-
')strcpy(code,"SUB");
if(stmt[i][3]=='*')
strcpy(code,"MUL");
if(stmt[i][3]=='/')
strcpy(code,"DIV ");if(rd==-1){
chartemp[2]={stmt[i][4],'\0'};if(rs!=-1)
k=output[rs];else
k=i;icode(temp,reg[k],k);}
if(rs!=-1 && rd!=-
1){intflag=0;for(j=i;j<nostmt;j++)
if(stmt[j][2]==stmt[i][2]||stmt[j][2]==stmt[i][4])flag=1;
if(flag!=1)icode(reg[output[rs]],reg[output[rd]],output[rd]);if(fla
g==1)icode(reg[output[rd]],reg[output[rs]],output[rs]);
}
}
strcpy(code,"MOV");
chartemp[2]={stmt[i-1][0],'\0'};
icode(reg[output[i-1]],temp,0);
}

67
OUTPUT:

Result:

Thus, the C program to generate assembly code for the given three address code has been executed and
the output has been verified successfully

68
 Date :
Ex.No. : 13 IMPLEMENTATIONOFDAG

Aim:
TowriteaCProgramtogenerateaDirectedAcyclicGraph

Algorithm:

1. Readtheinput String.

2. Createaleafnodewiththelabelforeachoperand- identifier.

3. Createinteriornodeswithanoperator symbolandpointerstoleftandrightoperands.

2. Createalistofattachedidentifiers foreachnodetoholdthecomputedvalues.

Case (i) x : = y OP zCase

(ii) x : = OP yCase (iii)x:=y

1: Ifyisundefined thencreatenode(y).

2. Ifzisundefined,createnode(z) forcase(i).

3. Forthecase(i),createanode(OP)whoseleftchildisnode(y)andrightchildisnode(z).

Letnbethisnode.

Forcase(ii),determinewhetherthereisnode(OP)withonechildnode(y).Ifnotcreatesu

chanode.

For case(iii), nodenwillbenode(y).

3. Deletexfromthelistofidentifiers fornode(x).Appendxtothelistofattachedidentifiersforthe
node nfoundinstep3 andsetnode(x)ton.

Program:
#include<stdio.h> 69
#include<string.h>
#include<ctype.h>#include<co
nio.h>voidmain()
{
structda
{
intptr,left,right;charlabel;
}dag[25];
intptr,l,j,change,n=0,i=0,state=1,x,y,k;charstore,*in
put1,input[25],var;clrscr();
for(i=0;i<25;i++)
{
dag[i].ptr=NULL;dag[i].left=NU
LL;dag[i].right=NULL;dag[i].la
bel=NULL;
}
printf("\n\nENTER THE
EXPRESSION\n\n");scanf("%s",input1);
/*EX:((a*b-c))+(b-
c))*/for(i=0;i<25;i++)input[i]=NUL
L;l=strlen(input1);
a:for(i=0;input1[i]!=')';i++);
for(j=i;input1[j]!='(';j--
);for(x=j+1;x<i;x++)if(isalpha(input1
[x]))input[n++]=input1[x];else
if(input1[x]!='0')store=input1[x];inp
ut[n++]=store;for(x=j;x<=i;x++)inp
ut1[x]='0';if(input1[0]!='0')goto
a;for(i=0;i<n;i++)
{

dag[i].label=input[i];dag[i].ptr=i;
if(!isalpha(input[i])&&!isdigit(input[i]))
70
{
dag[i].right=i-
1;ptr=i;var=input[i-
1];if(isalpha(var))ptr=ptr-2;
else
{
ptr=i-1; b:
if(!isalpha(var)&&!isdigit(var))
{
ptr=dag[ptr].left;var=input[pt
r];gotob;
}
elseptr=ptr-1;
}
dag[i].left=ptr;
}
}
printf("\nSYNTAXTREEFORGIVENEXPRESSION\n\n");
printf("\n\n PTR \t\t LEFT PTR \t\t RIGHT PTR \t\t
LABEL\n\n");for(i=0;i<n;i++)/* draw the syntaxtree forthefollowing
outputwithpointervalue*/printf("\n%d\t%d\t%d\t%c\n",dag[i].ptr,dag[i].left,dag[i].right,dag[i].l
abel); getch();
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if((dag[i].label==dag[j].label&&dag[i].left==dag[j].left)&&dag[i].right==dag[j].right)
{
for(k=0;k<n;k++)
{
if(dag[k].left==dag[j].ptr)dag[k].left=dag[i].ptr;if(dag[k].right==dag[j].ptr)dag[k].rig
ht=dag[i].ptr;
}
71
dag[j].ptr=dag[i].ptr;}}}
printf("\nDAGFORGIVENEXPRESSION\n\n");
printf("\n\n PTR \t LEFT PTR \t RIGHT PTR \t LABEL
\n\n");for(i=0;i<n;i++)/*drawDAGfor thefollowing outputwith pointervalue*/
printf("\n%dt\t%d\t\t%d\t\t%c\n",dag[i].ptr,dag[i].left,dag[i].right,dag[i].label);getch();
Output

Result:
Thus, the C program to construct DAG has been executed and the output has been verified successfully

72
 Date : IMPLEMENTATIONOFGLOBALDATAFLOWANALYSIS
Ex.No. :14

Aim:
To writeaCprogramtoImplementDataFlowAnalysis
Algorithm:

1. Starttheprogramexecution
2. Read the totalnumberofexpressions
3. Readtheleftandrightsideofeachexpressions
4. Displaytheexpressionswithlineno
5. DisplaytheDataflowmovementwithparticularexpressions
6. Stoptheprogramexecution

Program:
# include <stdio.h>
#include<conio.h>
# include<string.h>
structop{
charleft[10];charright[10];
}op2[15],prt[15];

intmain(){
inta,j,i,k,n,m,q,l=1;char*p,*li;chartemp,t;
char*tem,*mat;printf("enter
no.of.values");scanf("%d",&n);for(i=0;i
<n;i++){printf("left");scanf("%s",op2[i].
left);printf("right");scanf("%s",op2[i].rig
ht);}printf("intermediate
code");for(i=0;i<n;i++)
{printf("Lineno=%d\n",l);printf("%s=",op2[i].left);
printf("%s\n",op2[i].right);l++;}
printf("dataflowanalysis");for(i=0;i<n;i
++)
{for(j=0;j<n;j++)
{mat=strstr(op2[j].right,op2[i].left);if(mat)
{printf("\n%sisliveat%s\n",op2[i].left,op2[j].right);}}}return0;}
73
Output:

Result:
Thus, the C program to perform global data flow analysis has been executed and the output has been verified
successfully

74
 Date : IMPLEMENTATIONOFSTORAGEALLOCATION - STACK
Ex.No. :15.a

Aim:

To implementStackStorageAllocationStrategiesusingCprogram.
Algorithm:
1. Initiallycheck whetherthestack isempty
2. Insertanelementintothestackusingpushoperation
3. Insertmoreelementsontothestackuntilstackbecomesfull
4. Deleteanelementfromthestackusing popoperation
5. Displaythe elementsinthe stack
6. Stoptheprogrambyexit

Program:
#include<stdio.h>#include<con
io.h>
inti,stk[100],top=-1,n;
voidshow()
{
for(i=0;i<=top;i++)printf("%d\t",stk[i]);
}
voidpush()
{
intitem;if(top==n-1)
printf("\nStackisfull.");else {
printf("\nEntertheitem:");scanf("%d",&item);st
k[++top]=item; }}
voidpop(){
if(top==-1)
printf("Stackisempty.");else{
printf("%dispopped.",stk[top]);top--; }}
intmain(){
int i,op;
printf("Enterthesizeofthestack: ");scanf("%d",&n);
do 75
{
printf("\n1:Push");
printf("\n2
:Pop");printf("\n3:Display");printf("\n4 :
Exit");
printf("\nEnteryourchoice:");scanf("%d",&op);
switch(op)
{
case1:
push();break;
case2:
pop();break;
case3:
show();break;
}
}while(op!=4);getch();
}
Output:

76
Result:

Thus, the C program to implement storage allocate using stack has been executed and the output has
been verified successfully

77
 Date : IMPLEMENTATIONOFSTORAGEALLOCATION - HEAP
Ex.No. :15.b

Aim:

To implementStackStorageAllocationStrategiesusingCprogram.
Algorithm:
1. Initiallycheck whetherthestack isempty
2. Insertanelementintothestackusingpushoperation
3. Insertmoreelementsontothestackuntilstackbecomesfull
4. Deleteanelementfromthestackusing popoperation
5. Displaythe elementsinthe stack
6. Stoptheprogrambyexit

Program :
#include<stdio.h>

#include<conio.h>#include<std
lib.h>#defineTRUE1
#define FALSE
0typedefstructHeap
{intdata;
structHeap*next;
}node;
node *create();voidmain()
{/*localdeclarations*/intchoice,val;
charans;node*head;
void display(node *);node
*search(node *,int);node
*insert(node*);voiddele(node
**);head=NULL;
do
{
printf("\nVariousoperationsonHeap");printf("\n1.Cre
ate");printf("\n2.Display");
printf("\n3.Insert an element in a
list");printf("\n4.Deleteanelementfromlist");printf("\n 78
5.Quit");
printf("\n Enter Your Choice(1-5):
");scanf("%d",&choice);
switch(choice)
{ case 1:head=create();break;
case 2:display(head);break;
case 3:head=insert(head);break;
case4:dele(&head);break;
case 5:exit(0);default:
printf("InvalidChoice,Tryagain");getch();
}}
while(choice!=5);}

node *create(){
node *temp,*new1,*head;intval,flag;
charans='y';
node
*get_node();temp=NULL;flag
=TRUE;
do{
printf("\nEntertheElement:");scanf("%d",&v
al);new1=get_node();if(new1==NULL)
printf("\nMemoryisnotallocated");new1->
data=val;
if(flag==TRUE)/* Executedonlyforthefirst time*/{head=new1;
temp=head;/*headisthefirstnodeintheheap*/flag=FALSE;
}else
{ temp-
>next=new1;temp=new1;}
printf("\nDoyouwanttoentermoreelements?(y/n)");ans=getch();
}while(ans=='y');printf("\nThelistiscreated
");getch();
returnhead;}
79
node *get_node(){node *temp;
temp=(node*)malloc(sizeof(node));temp-
>next=NULL;
returntemp;}
voiddisplay(node*head){node *temp;
temp=head;if(temp==NULL){
printf("\n The list is empty\n");getch();
return;}
while(temp!= NULL){printf("%d-
>",temp-> data);temp=temp-
>next;}printf("NULL");
getch();}
node*search(node*head,int key){node *temp;

intfound;temp=head;
if(temp==NULL){
printf("The linked list is empty\n");getch();
return
NULL;}found=FALSE;
while((temp!=NULL)&&(found==FALSE))
{if(temp->data!=key)temp = temp-
>next;else
found =TRUE;
}if(found==TRUE){
printf("\n The Elements is present in the list\n");getch();
returntemp;
}else
printf("\n The Element is not present in the list\n");getch();
returnNULL;}
node*insert(node*head)
{intchoice;
node
*insert_head(node*);voidinsert_after(n
ode*);voidinsert_last(node*);
80
printf("\n1. Insertanodeasaheadnode");printf("\n2.
Insertanodeasalastnode");
printf("\nEnter your choice for insertion of node (1-2):
");scanf("%d",&choice);
switch(choice)
{ case 1:head
=insert_head(head);break;
case 2:insert_last(head);break;}
returnhead;
}/*Insertionofnodeatfirst
position*/node*insert_head(node*head){
node*New,*temp;
New=get_node();
printf ("\n Enter the element which you want to insert:
");scanf("%d",&New->data);
if(head==NULL)head=New;
else
{temp=head;

New->next=temp;head= New;
}
returnhead;
}/*Insertionofnodeat
lastposition*/voidinsert_last(node *head){
node*New,*temp;
New=get_node();
printf ("\n Enter the element which you want to insert:
");scanf("%d",&New->data);
if(head==NULL){head=New;
}else
{temp=head;
while(temp->next!=NULL)temp=temp-
>next;
temp->next=New;
81
New->next=NULL;}}
node*get_prev(node*head,intval){node*temp,*p
rev;
intflag;temp=head;
if(temp==NULL)returnNULL;
flag = FALSE;prev=
NULL;
while(temp!=NULL&&!flag)
{if(temp->data!=val){prev=temp;
temp=temp->next;
}else
flag =TRUE;
} if(flag) /*if Flag is true*/returnprev;
else
returnNULL;}
voiddele(node**head)
{intkey;
node*New,*temp,*prev;temp=*head;
if(temp== NULL){
printf ("\n The list is empty\n ");getch();
return;}
printf("\nENTERtheElementyouwanttodelete:");scanf("%d",&ke
y);

temp=search(*head,key);if(temp
!=NULL){
prev=get_prev(*head,key);if(prev!=
NULL){
prev ->next = temp-> next;free(temp);
}else{
*head =temp->next;
free(temp);//usingthe mem.Dellocationfunction
}
82
printf("\nThe Element is deleted\n");getch();
}}

Output:

83
Result:
Thus, the C program to implement storage allocate using heap has been executed and the output has been
verified successfully

84