Generic Programming Notes

Download notes for the fourth chapter of Programming Paradigms.

(Prepared by Santhosh Kumar S)

Generic Programming.docx

Single Pass Assembler in C

Question

To implement a single Pass assembler in C language.

Program

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int count[20];
void wordcount()
{
FILE *f3;
f3=fopen("input.c","r");
int word=0,i=1;
char c;
while((c=getc(f3))!=EOF)
{
if(c==' ')
word+=1;
if(c=='\n')
{
word+=1;
count[i] = word;
printf("\n No.of words in line %d is %d",i,word);
i++;
word=0;
}
}
fclose(f3);
}
void main()
{
char lbl[10],mne[10],opd[10],mne1[10],opd1[10],opd2[10],val[10],adr1[10];
int locctr,linenumber,f;
FILE *f1,*f2,*f3,*f4;
f1=fopen("input.c","r");
f2=fopen("symtab.c","w+");
f4=fopen("inter.c","w");
printf("\n WORD COUNT OF THE PROGRAM IS :");
wordcount();
printf("\n Source \t Code \t Opcode \t Object code\n");
fscanf(f1,"%s %s %x",lbl,mne,&locctr);
linenumber=2;
while(!feof(f1))
{
if(count[linenumber]==3)
{
fscanf(f1,"%s %s %s",lbl,mne,opd);
fprintf(f4,"%x \t %s \t %s \t %s\n",locctr,lbl,mne,opd);
fprintf(f2,"%x \t %s \t %s\n",locctr,lbl,opd);
if(strcmp(mne,"RESB")==0 || strcmp(mne,"RESW")==0)
{
printf("%s \t %s \t 00 \t 0000\n",lbl,mne);
}
else
printf("%s \t %s \t 00 \t 000%s\n",lbl,mne,opd);
}
if(count[linenumber]==2)
{
fscanf(f1,"%s %s",mne,opd);
fprintf(f4,"%x \t %s \t %s\n",locctr,mne,opd);
printf("%s \t %s \t",mne,opd);
f3=fopen("opcode.c","r");
while(!feof(f3))
{
fscanf(f3,"%s%s\n",mne1,opd1);
if(strcmp(mne,mne1)==0)
printf("%s \t",opd1);
}
fclose(f3);
f=0;
rewind(f2);
//f2=fopen("symtab.c","r");
while(!feof(f2))
{
fscanf(f2,"%s %s %s",adr1,opd2,val);
if(strcmp(opd,opd2)==0)
{
printf("%s\n",adr1);
f=1;
}
}
if(f=0)
printf("0000\n");
}
if(count[linenumber]==1)
{
fscanf(f1,"%s\n",mne);
fprintf(f4,"%x %s\n",locctr,mne);
}
linenumber+=1;
if(strcmp(mne,"WORD")==0)
locctr+=3;
else if(strcmp(mne,"BYTE")==0)
locctr+=strlen(opd);
else if(strcmp(mne,"RESW")==0)
locctr+=3*(atoi(opd));
else if(strcmp(mne,"RESB")==0)
locctr+=atoi(opd);
else
locctr+=3;
}
fclose(f1);
fclose(f2);
fclose(f4);
}

Download Source Code

Macro Processor in C

Question

To Implement a Macro Processor in C language.

Program

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
void main()
{
FILE *fp1,*fp2,*fp3,*fp4;
char opcode[50],name[50],def[50];
fp1=fopen("source.dat","r");
fp2=fopen("define.dat","w");
fp3=fopen("name.dat","w");
fp4=fopen("out.dat","w");
while(!feof(fp1))
{
fscanf(fp1,"%s",opcode);
strcpy(name,opcode);
fscanf(fp1,"%s",opcode);
if(strcmp(opcode,"MACRO")==0)
{
fprintf(fp3,"%s\n",name);
fprintf(fp2,"%s\n",name);
while(strcmp(opcode,"MEND")!=0)
{
fprintf(fp2,"%s\n",opcode);
fscanf(fp1,"%s",opcode);
}
fprintf(fp2,"MEND\n");
}
}
fclose(fp1);
fclose(fp2);
fclose(fp3);
fp1=fopen("source.dat","r");
fp3=fopen("name.dat","r");
fp2=fopen("define.dat","r");
fscanf(fp2,"%s",def);
while(!feof(fp1))
{
fscanf(fp1,"%s",opcode);
fscanf(fp3,"%s",name);
if(strcmp(opcode,name)==0)
{
fscanf(fp1,"%s",opcode);
if(strcmp(opcode,"MACRO")==0)
{
while(strcmp(opcode,"MEND")!=0)
{
fscanf(fp1,"%s",opcode);
}
}
}
else
{
strcpy(name," ");
if(strcmp(opcode,def)==0)
{
fscanf(fp2,"%s",def);
if(strcmp(def,"MACRO")==0)
fscanf(fp2,"%s",def);
while(strcmp(def,"MEND")!=0)
{
fprintf(fp4,"%s\n",def);
fscanf(fp2,"%s",def);
}
fscanf(fp2,"%s",def);
}
else if(strcmp(opcode,"END")==0)
{
fprintf(fp4,"END\n");
break;
}
else
{
fprintf(fp4,"%s\n",opcode);
}

}
}
}

Download Source Code

source.dat

ADDA MACRO
CLEAR A
ADD 05
MEND
SUBA MACRO
CLEAR A
SUB 05
MEND
COPY START 0
CLEAR X
ADDA
SUBA
END

define.dat

ADDA
MACRO
CLEAR
A
ADD
05
MEND
SUBA
MACRO
CLEAR
A
SUB
05
MEND

name.dat

ADDA
SUBA

out.dat

COPY
START
0
CLEAR
X
CLEAR
A
ADD
05
CLEAR
A
SUB
05
END

Symbol Table with Hashing

Question

Implementation of Symbol Table with Suitable Hashing.

Program

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
struct symtable
{
int address;
char label[10];
int flag;
}a[11];
int hashvalue,addr,i,ch;
char lbl[10];
void display()
{
printf("\n The Symbol Table is \n");
printf("\n Hash Values Address Label\n");
for(i=0;i<11;i++)
{
printf("\n\n %d %d %s",i,a[i].address,a[i].label);
}
}
void create()
{
char opt[10];
do
{
printf("\n Enter the address:");
scanf("%d",&addr);
hashvalue=addr%11;
printf("\n Enter the Label:");
scanf("%s",lbl);
if(a[hashvalue].flag==0)
{
a[hashvalue].address=addr;
strcpy(a[hashvalue].label,lbl);
a[hashvalue].flag=1;
}
else
{
int allocated=0;
for(hashvalue++;hashvalue<11;hashvalue++)
{
if(a[hashvalue].flag==0)
{
a[hashvalue].address=addr;
strcpy(a[hashvalue].label,lbl);
a[hashvalue].flag=1;
allocated=1;
break;
}
}
if(allocated==0)
{
hashvalue=0;

for(;hashvalue<11;hashvalue++)
{
if(a[hashvalue].flag==0)
{
a[hashvalue].address=addr;
strcpy(a[hashvalue].label,lbl);
a[hashvalue].flag=1;
break;
}
}
}
}
printf("\n Continue(y/n)? ");
scanf("%s",opt);
}while(strcmp(opt,"n")!=0);
display();
}

void search()
{
printf("\n Enter the label:");
scanf("%s",lbl);
for(i=0;i<11;i++)
{
if(a[i].flag==1)
{
if(strcmp(a[i].label,lbl)==0)
{
printf("\n The label %s found at address %d",lbl,a[i].address);
}
}
}
}
void main()
{
for(i=0;i<10;i++)
{
a[i].flag = 0;
a[i].address=0;
strcpy(a[i].label," ");
}
while(1)
{
ph:
printf("\n\n 1.Create a Symbol Table \n 2.Search in Symbol Table \n 3.Exit");
printf("\n\n Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
create();
break;
case 2:
search();
break;
case 3:
exit(0);
break;
default:
printf("\n Enter a valid option:");
goto ph;
}
}
}

Download Source Code

Designing a Two Pass Assembler

In this post I will explain the basic logic involved in designing a two pass assembler and write the 'C' program code to simulate the Pass1 and Pass2 of the Assembler.

A Simple Assembler consists of Two data structures namely,

1. OPTAB(Operation Table)
2. SYMTAB(Symbol Table)

Note - LOCCTR is a variable that is used in assigning the addresses. Initially it is assigned to the address specified after 'START' , then after reading each instruction it is incremented to the length of the Instruction so as to keep track of the location.

OPTAB

1. In a simple Assembler it looks for menomic operation code and translate the into machine language equivalents.

2. In a complex Assemblers, it also contains information about instruction format and length.

3. OPTAB in first pass is used to find the instruction length for incrementing LOCCTR, and in second pass tells which information format to use in assembling the instruction.

4. Organised as a Hash Table with mnemonic opcode as Key.

SYMTAB

1. Includes name and address for each Label in the program.

2. During Pass1 of the assembler,labels and the address specified by LOCCTR are entered into SYMTAB as we encounter the labels in the program.

3. During Pass2 we lookup the Symbols used as operands and obtain the address to be inserted in the assembled instructions.

4. Implemented as a hash table for efficiency. However the hash function must be properly selected.

Programming the Pass1 and Pass2

Now let us focus on programming the pass1 in 'C' language.

Pass1

• Here we use three files namely - Input.c, Intermediate.c, SymbolTable.c (you can name it as you wish, but use this for clarity).
• Pass1 usually wrires Intermediate file that contains source statement together with its assigned address.
• Here we use a function named "wordcount" to compute the number of words in each line of the program.

Let us begin with the "wordcount() function." It reads the "Input.c" file which contains the Input or source program.

variables used - "word" to keep track of the number of words, "i" to keep track of the line number, character "c" to fetch each character from the input file.

Logic

1. If "c" encounters a blank space increment the word and if it encounters a "\n i.e. new line", increment the word and then display the number of words in the line which is ofcourse the value in "word". For later usage let us store the no.of words in each line in a global array count.

2. Increment the i value, and set word to 0 and repeat step 1.

3. Repeat the above steps until EOF(End of File) is encountered.

Code

int count[20];
void wordcount()
{
FILE *f3;
int word=0,i=1;
char c;

f3=fopen("INPUT.C","r");
c=fgetc(f3);
while(c!=EOF)
{
if(c==' ') // blank space
word+=1;
if(c=='\n')
{
word+=1;
count[i] = word;
printf("\n No.of Words in line number %d is %d",i,word);
i++;
word=0; // Important
}
c=fgetc(f3);
}
fclose(f3);
}

After wordcount we changer our focus to construct the INTERMEDIATE.C and SYMBOLTABLE.c,

Logic

1. Use the LOCCTR to keep track of addresses.
2. We read each line from INPUT.C,

• If the line has 1 word, then it means it has only a "Mnemonic" code, so add the mnemonic to INTERMEDIATE.c along with LOCCTR value.
  
• If the line has 2 words, then it means it has "Mnemonic" as well as an "operand". Add both of this and LOCCTR value in INTERMEDIATE.c.
• If the line has 3 words, then it has "Mnemonic", "Operand" as well as label before the mnemonic. So add Label, Mnemonic, operand and LOCCTR address to the Intermediate.c.

3. Repeat the step 2 until the end of file INPUT.c
4. Thus all the tables get constructed.

Code

FILE *f1,*f2,*f3;

int linenumber, locctr;
char lbl[20], mne[10], opd[10], ch;

printf("\n Word count for Input program");
wordcount();

f1=fopen("INPUT.c","r");
f2=fopen("INTERMEDIATE.c","w");
f3=fopen("SYMTAB.c","w");

fscanf(f1,"%s %s %x", lbl, mne, &locctr);
linenumber=2;
while(!feof(f1))
{

if(count[linenumber]==1)
{
fscanf(f1,"%s\n",mne);
fprintf(f3,"%x \t %s\n",locctr,mne);
}

if(count[linenumber]==2)
{
fscanf(f1,"%s %s\n",mne,opd);
fprintf(f3,"%x \t %s \t %s\n",locctr,mne,opd);
}
if(count[linenumber]==3)
{
fscanf(f1,"%s %s %s\n",lbl,mne,opd);
fprintf(f3,"%x \t %s \t %s \t %s\n",locctr,lbl,mne,opd);
fprintf(f2,"%s \t %x",lbl,locctr);
}

linenumber+=1;

if(strcmp(mne,"WORD")==0)
locctr+=3;
else if(strcmp(mne,"BYTE")==0)
locctr+=strlen(opd);
else if(strcmp(mne,"RESW")==0)
locctr+=3*atoi(opd);
else if(strcmp(mne,"RESB")==0)
locctr+=atoi(opd);

//atoi converts string to integer

else
locctr+=3;
}
fclose(f1);
fclose(f2);
fclose(f2);
}


(Programming Pass2 will be explained soon)

Until then,

G.Vivek Venkatesh

Problem with my Internet Connection

Hi friends, there is some problem with my BSNL Internet Connection for the past three days. Downloads are happening at 1 Kbps . I have written a complaint to BSNL and the problem is yet to be rectified. Thats why could not post any programs.

Hope the problem is rectified soon.

Until then
Vivek Venkatesh G