Wednesday, 3 June 2015
Saturday, 2 May 2015
STRUCTURE PROGRAMMING AND COMPILER CODE
STRUCTURE PROGRAMMING AND COMPILER CODE
1.FIRST AND FOLLOW
2.ELIMINATION OF LEFT RECURSION
3.SHIFT REDUCE PARSER
4.CODE OPTIMISATION
5.2 PASS ASSEMBLER
input.txt
6.LEXICAL ANALYSER
lexinput.txt
7.2 PASS MACRO
input.txt
1.FIRST AND FOLLOW
2.ELIMINATION OF LEFT RECURSION
3.SHIFT REDUCE PARSER
4.CODE OPTIMISATION
5.2 PASS ASSEMBLER
input.txt
6.LEXICAL ANALYSER
lexinput.txt
7.2 PASS MACRO
input.txt
2 PASS MACRO
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct mdt_table{
int index;
char card[30];
}MDT;
typedef struct mnt_table{
int index;
char name[15];
int mdtindex;
}MNT;
typedef struct ala_table{
char index[3];
char arg[15];
}ALA;
typedef struct ala_array{
ALA item[5];
}ALA_ITEM;
MNT mnt[5];
MDT mdt[40];
ALA ala[5];
int mdtc,mntc,mdtp,alac,alap;
char word3[10],ch3[2],word[10],line[20],ch,ch1[2],ch2[2],line1[20],line2[20],k;
FILE *input,*inter,*output;
fpos_t pos;
char* num[5]={"#1","#2","#3","#4","#5"};
void get_word(){
int i=0;
//char ch;
ch=getc(input);
while(ch!=EOF){
if((ch!=' ')&&(ch!=',')&&(ch!='\n'))
word[i++]=ch;
if((ch==' ')||(ch==',')||(ch=='\n')){
word[i]='\0';
break;
}
ch=getc(input);
}
}
void display_mnt(){
int i=0;
printf("\nMNT\n");
for(i=0;i<mntc;i++){
printf("%d\t%s\t%d",mnt[i].index,mnt[i].name,mnt[i].mdtindex);
printf("\n");
}
}
void display_mdt(){
int i=0;
printf("\nMDT\n");
for(i=0;i<mdtc;i++){
printf("%d\t%s",mdt[i].index,mdt[i].card);
printf("\n");
}
}
void display_ala(){
int i=0;
printf("\nALA\n");
for(i=0;i<alac;i++){
printf("%s\t%s",ala[i].index,ala[i].arg);
printf("\n");
}
}
void display_ala_item(ALA_ITEM obj){
int i;
printf("\nALA ITEM\n");
for(i=0;i<alap;i++){
printf("%s\t%s",obj.item[i].index,obj.item[i].arg);
printf("\n");
}
}
void search_ALA(){
int i;
for(i=0;i<alac;i++){
if(strcmp(word,ala[i].arg)==0){
strcpy(word,ala[i].index);
}
}
}
void PASS1(){
int i;
input=fopen("input.txt","r");
inter=fopen("inter.txt","w+");
mdtc=mntc=alac=0;
while(!feof(input)){
fgetpos(input,&pos);
get_word();
/*printf("%s\n",word);
fprintf(inter,"%s\n",word);*/
if(strcmp(word,"MACRO")!=0){
fsetpos(input,&pos);
fgets(line,20,input);
fprintf(inter,"%s",line);
}
if(strcmp(word,"MACRO")==0){
fgetpos(input,&pos);
get_word();
//mnt
//printf("%s",word);
strcpy(mnt[mntc].name,word);
mnt[mntc].index=mntc;
mnt[mntc].mdtindex=mdtc;
mntc++;
display_mnt();
//mdt
fsetpos(input,&pos);
i=0;
//enter arg line into mdt
while(!feof(input)){
ch=getc(input);
if(ch=='\n'){
line[i]='\0';
break;
}
line[i++]=ch;
}
//enter into mdt
//printf("%s",line);
mdt[mdtc].index=mdtc;
strcpy(mdt[mdtc].card,line);
mdtc++;
display_mdt();
//setup ala
fsetpos(input,&pos);
get_word();
do{
get_word();
strcpy(ala[alac].arg,word);
strcpy(ala[alac].index,num[alac]);
alac++;
}while(ch!='\n');//this is why ch is global
display_ala();
fgetpos(input,&pos);
get_word();
ch1[0]=ch;
ch1[1]='\0';
//printf("%s%s\n",word,ch1);
while(strcmp(word,"MEND")!=0){
//clear the array
memset(line1,0,strlen(line1));
do{
search_ALA();
strcat(line1,word);
strcat(line1,ch1);
//printf("\n%s",line1);
get_word();
ch1[0]=ch;
}while(ch1[0]!='\n');
search_ALA();
strcat(line1,word);
//strcat(line1,ch1);
mdt[mdtc].index=mdtc;
strcpy(mdt[mdtc].card,line1);
mdtc++;
get_word();
ch1[0]=ch;
}
//to enter mend to mdt
mdt[mdtc].index=mdtc;
strcpy(mdt[mdtc].card,word);
mdtc++;
display_mdt();
}
}
fclose(input);
fclose(inter);
}
int search_MNT(){
int i;
for(i=0;i<mntc;i++){
if(strcmp(word,mnt[i].name)==0){
mdtp=mnt[i].mdtindex;
return mnt[i].index;
}
}
return -1;
}
void get_word_line(){
int i=0;
ch3[1]='\0';
ch3[0]=line1[k];
memset(word3,0,strlen(word));
while(ch3[0]!='\0'){
if((ch3[0]!=' ')&&(ch3[0]!=',')&&(ch3[0]!='\0'))
word3[i++]=ch3[0];
if((ch3[0]==' ')||(ch3[0]==',')||(ch3[0]=='\0')){
word3[i]='\0';
break;
}
k++;
ch3[0]=line1[k];
}
}
void search_ALA_ITEM(ALA_ITEM obj){
int i;
for(i=0;i<alap;i++){
if(strcmp(word3,obj.item[i].index)==0){
memset(word3,0,strlen(word3));
strcpy(word3,obj.item[i].arg);
}
}
}
void PASS2(){
int f,i;
input=fopen("inter.txt","r");
output=fopen("output.txt","w+");
memset(word,0,strlen(word));
memset(line,0,strlen(line));
while(!feof(input)){
get_word();
ch2[0]=ch;
ch2[1]='\0';
//printf("%s%s",word,ch2);
//search in mnt
f=search_MNT();
//if not in mnt
if(f==-1){
fprintf(output,"%s%s",word,ch2);
if(strcmp(word,"END")==0)break;
}
else{
//setup ala
alap=0;
//for every call, new ALA_ITEM object
ALA_ITEM obj;
do{
get_word();
strcpy(obj.item[alap].index,num[alap]);
strcpy(obj.item[alap].arg,word);
alap++;
}while(ch!='\n');
//display the current ALA_ITEM object
display_ala_item(obj);
mdtp++;
while(strcmp(mdt[mdtp].card,"MEND")!=0){
memset(line1,0,strlen(line1));
strcpy(line1,mdt[mdtp].card);
//fprintf(output,"%s\n",line1);
k=0;
memset(line2,0,strlen(line2));
do{
get_word_line();
//printf("%s%s\n",word3,ch3);
k++;
//replace # with arg from corresponding ala
search_ALA_ITEM(obj);
//append to line
strcat(line2,word3);
strcat(line2,ch3);
}while(ch3[0]!='\0');
fprintf(output,"%s\n",line2);
mdtp++;
}
}
}
}
void main(){
PASS1();
PASS2();
}
#include<stdlib.h>
#include<string.h>
typedef struct mdt_table{
int index;
char card[30];
}MDT;
typedef struct mnt_table{
int index;
char name[15];
int mdtindex;
}MNT;
typedef struct ala_table{
char index[3];
char arg[15];
}ALA;
typedef struct ala_array{
ALA item[5];
}ALA_ITEM;
MNT mnt[5];
MDT mdt[40];
ALA ala[5];
int mdtc,mntc,mdtp,alac,alap;
char word3[10],ch3[2],word[10],line[20],ch,ch1[2],ch2[2],line1[20],line2[20],k;
FILE *input,*inter,*output;
fpos_t pos;
char* num[5]={"#1","#2","#3","#4","#5"};
void get_word(){
int i=0;
//char ch;
ch=getc(input);
while(ch!=EOF){
if((ch!=' ')&&(ch!=',')&&(ch!='\n'))
word[i++]=ch;
if((ch==' ')||(ch==',')||(ch=='\n')){
word[i]='\0';
break;
}
ch=getc(input);
}
}
void display_mnt(){
int i=0;
printf("\nMNT\n");
for(i=0;i<mntc;i++){
printf("%d\t%s\t%d",mnt[i].index,mnt[i].name,mnt[i].mdtindex);
printf("\n");
}
}
void display_mdt(){
int i=0;
printf("\nMDT\n");
for(i=0;i<mdtc;i++){
printf("%d\t%s",mdt[i].index,mdt[i].card);
printf("\n");
}
}
void display_ala(){
int i=0;
printf("\nALA\n");
for(i=0;i<alac;i++){
printf("%s\t%s",ala[i].index,ala[i].arg);
printf("\n");
}
}
void display_ala_item(ALA_ITEM obj){
int i;
printf("\nALA ITEM\n");
for(i=0;i<alap;i++){
printf("%s\t%s",obj.item[i].index,obj.item[i].arg);
printf("\n");
}
}
void search_ALA(){
int i;
for(i=0;i<alac;i++){
if(strcmp(word,ala[i].arg)==0){
strcpy(word,ala[i].index);
}
}
}
void PASS1(){
int i;
input=fopen("input.txt","r");
inter=fopen("inter.txt","w+");
mdtc=mntc=alac=0;
while(!feof(input)){
fgetpos(input,&pos);
get_word();
/*printf("%s\n",word);
fprintf(inter,"%s\n",word);*/
if(strcmp(word,"MACRO")!=0){
fsetpos(input,&pos);
fgets(line,20,input);
fprintf(inter,"%s",line);
}
if(strcmp(word,"MACRO")==0){
fgetpos(input,&pos);
get_word();
//mnt
//printf("%s",word);
strcpy(mnt[mntc].name,word);
mnt[mntc].index=mntc;
mnt[mntc].mdtindex=mdtc;
mntc++;
display_mnt();
//mdt
fsetpos(input,&pos);
i=0;
//enter arg line into mdt
while(!feof(input)){
ch=getc(input);
if(ch=='\n'){
line[i]='\0';
break;
}
line[i++]=ch;
}
//enter into mdt
//printf("%s",line);
mdt[mdtc].index=mdtc;
strcpy(mdt[mdtc].card,line);
mdtc++;
display_mdt();
//setup ala
fsetpos(input,&pos);
get_word();
do{
get_word();
strcpy(ala[alac].arg,word);
strcpy(ala[alac].index,num[alac]);
alac++;
}while(ch!='\n');//this is why ch is global
display_ala();
fgetpos(input,&pos);
get_word();
ch1[0]=ch;
ch1[1]='\0';
//printf("%s%s\n",word,ch1);
while(strcmp(word,"MEND")!=0){
//clear the array
memset(line1,0,strlen(line1));
do{
search_ALA();
strcat(line1,word);
strcat(line1,ch1);
//printf("\n%s",line1);
get_word();
ch1[0]=ch;
}while(ch1[0]!='\n');
search_ALA();
strcat(line1,word);
//strcat(line1,ch1);
mdt[mdtc].index=mdtc;
strcpy(mdt[mdtc].card,line1);
mdtc++;
get_word();
ch1[0]=ch;
}
//to enter mend to mdt
mdt[mdtc].index=mdtc;
strcpy(mdt[mdtc].card,word);
mdtc++;
display_mdt();
}
}
fclose(input);
fclose(inter);
}
int search_MNT(){
int i;
for(i=0;i<mntc;i++){
if(strcmp(word,mnt[i].name)==0){
mdtp=mnt[i].mdtindex;
return mnt[i].index;
}
}
return -1;
}
void get_word_line(){
int i=0;
ch3[1]='\0';
ch3[0]=line1[k];
memset(word3,0,strlen(word));
while(ch3[0]!='\0'){
if((ch3[0]!=' ')&&(ch3[0]!=',')&&(ch3[0]!='\0'))
word3[i++]=ch3[0];
if((ch3[0]==' ')||(ch3[0]==',')||(ch3[0]=='\0')){
word3[i]='\0';
break;
}
k++;
ch3[0]=line1[k];
}
}
void search_ALA_ITEM(ALA_ITEM obj){
int i;
for(i=0;i<alap;i++){
if(strcmp(word3,obj.item[i].index)==0){
memset(word3,0,strlen(word3));
strcpy(word3,obj.item[i].arg);
}
}
}
void PASS2(){
int f,i;
input=fopen("inter.txt","r");
output=fopen("output.txt","w+");
memset(word,0,strlen(word));
memset(line,0,strlen(line));
while(!feof(input)){
get_word();
ch2[0]=ch;
ch2[1]='\0';
//printf("%s%s",word,ch2);
//search in mnt
f=search_MNT();
//if not in mnt
if(f==-1){
fprintf(output,"%s%s",word,ch2);
if(strcmp(word,"END")==0)break;
}
else{
//setup ala
alap=0;
//for every call, new ALA_ITEM object
ALA_ITEM obj;
do{
get_word();
strcpy(obj.item[alap].index,num[alap]);
strcpy(obj.item[alap].arg,word);
alap++;
}while(ch!='\n');
//display the current ALA_ITEM object
display_ala_item(obj);
mdtp++;
while(strcmp(mdt[mdtp].card,"MEND")!=0){
memset(line1,0,strlen(line1));
strcpy(line1,mdt[mdtp].card);
//fprintf(output,"%s\n",line1);
k=0;
memset(line2,0,strlen(line2));
do{
get_word_line();
//printf("%s%s\n",word3,ch3);
k++;
//replace # with arg from corresponding ala
search_ALA_ITEM(obj);
//append to line
strcat(line2,word3);
strcat(line2,ch3);
}while(ch3[0]!='\0');
fprintf(output,"%s\n",line2);
mdtp++;
}
}
}
}
void main(){
PASS1();
PASS2();
}
LEXICAL ANALYSER
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void keyw(char *p);
int i=0,id=0,kw=0,num=0,op=0;
char keys[32][10]={"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
main()
{
char ch,str[25],seps[15]=" \t\n,;(){}[]#\"<>",oper[]="!%^&*-+=~|.<>/?";
int j;
char fname[50];
FILE *f1;
printf("enter file path (drive:\\fold\\filename)\n");
scanf("%s",fname);
f1 = fopen(fname,"r");
if(f1==NULL)
{
printf("file not found");
exit(0);
}
while((ch=fgetc(f1))!=EOF)
{
for(j=0;j<=14;j++)
{
if(ch==oper[j])
{
printf("%c is an operator\n",ch);
op++;
str[i]='\0';
keyw(str);
}
}
for(j=0;j<=14;j++)
{
if(i==-1)
break;
if(ch==seps[j])
{
if(ch=='#')
{
while(ch!='>')
{
printf("%c",ch);
ch=fgetc(f1);
}
printf("%c is a header file\n",ch);
i=-1;
break;
}
if(ch=='"')
{
do
{
ch=fgetc(f1);
printf("%c",ch);
}while(ch!='"');
printf("\b is an argument\n");
i=-1;
break;
}
str[i]='\0';
keyw(str);
}
}
if(i!=-1)
{
str[i]=ch;
i++;
}
else
i=0;
}
printf("Keywords: %d\nIdentifiers: %d\nOperators: %d\nNumbers: %d\n",kw,id,op,num);
}
void keyw(char *p)
{
int k,flag=0;
for(k=0;k<=31;k++)
{
if(strcmp(keys[k],p)==0)
{
printf("%s is a keyword\n",p);
kw++;
flag=1;
break;
}
}
if(flag==0)
{
if(isdigit(p[0]))
{
printf("%s is a number\n",p);
num++;
}
else
{
if(p[0]!='\0')
{
printf("%s is an identifier\n",p);
id++;
}
}
}
i=-1;
}
#include<ctype.h>
#include<string.h>
void keyw(char *p);
int i=0,id=0,kw=0,num=0,op=0;
char keys[32][10]={"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
main()
{
char ch,str[25],seps[15]=" \t\n,;(){}[]#\"<>",oper[]="!%^&*-+=~|.<>/?";
int j;
char fname[50];
FILE *f1;
printf("enter file path (drive:\\fold\\filename)\n");
scanf("%s",fname);
f1 = fopen(fname,"r");
if(f1==NULL)
{
printf("file not found");
exit(0);
}
while((ch=fgetc(f1))!=EOF)
{
for(j=0;j<=14;j++)
{
if(ch==oper[j])
{
printf("%c is an operator\n",ch);
op++;
str[i]='\0';
keyw(str);
}
}
for(j=0;j<=14;j++)
{
if(i==-1)
break;
if(ch==seps[j])
{
if(ch=='#')
{
while(ch!='>')
{
printf("%c",ch);
ch=fgetc(f1);
}
printf("%c is a header file\n",ch);
i=-1;
break;
}
if(ch=='"')
{
do
{
ch=fgetc(f1);
printf("%c",ch);
}while(ch!='"');
printf("\b is an argument\n");
i=-1;
break;
}
str[i]='\0';
keyw(str);
}
}
if(i!=-1)
{
str[i]=ch;
i++;
}
else
i=0;
}
printf("Keywords: %d\nIdentifiers: %d\nOperators: %d\nNumbers: %d\n",kw,id,op,num);
}
void keyw(char *p)
{
int k,flag=0;
for(k=0;k<=31;k++)
{
if(strcmp(keys[k],p)==0)
{
printf("%s is a keyword\n",p);
kw++;
flag=1;
break;
}
}
if(flag==0)
{
if(isdigit(p[0]))
{
printf("%s is a number\n",p);
num++;
}
else
{
if(p[0]!='\0')
{
printf("%s is an identifier\n",p);
id++;
}
}
}
i=-1;
}
2 PASS ASSEMBLER
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char POT[][7]={"START","USING","END"};
char MOT[][6]={"L","ST","A","S","M"};
char DEC[][4]={"DC","DS"};
typedef struct symbol{
char symbol[10];
int addr;
}SYMTAB;
SYMTAB sym[10];
int startaddr,lc,symcount=0,length;
char line[20],label[20],operand[20],opcode[20],prgname[20],op[4];
int search_POT(char opcode[]){
int i,j;
for(i=0;i<5;i++){
if(strcmp(opcode,POT[i])==0)
return i;
}
return -1;
}
int search_DEC(char opcode[]){
int i,j;
for(i=0;i<5;i++){
if(strcmp(opcode,DEC[i])==0)
return i;
}
return -1;
}
int calc_DEC(char opcode[],char operand[]){
int i=0,l,k=0;
char copy[10];
int j=0,m=0;
if(strcmp(opcode,"DC")==0){
switch(operand[0]){
case 'B':i=1;break;
case 'H':i=2;break;
case 'F':i=4;break;
case 'D':i=8;break;
}
for(j=2;operand[j]!='\'';j++){
op[m++]=operand[j];
}
op[m]='\0';
//printf(" %s ",op);
}
else{
l=strlen(operand);
switch(operand[l-1]){
case 'B':i=1;break;
case 'H':i=2;break;
case 'F':i=4;break;
case 'D':i=8;break;
}
for(j=0;j<=l-2;j++){
copy[k++]=operand[j];
}
copy[k]='\0';
//printf("%s",copy);
k=atoi(copy);
i=i*k;
}
return i;
}
void READ_LINE(){
char buff[20],word1[20],word2[20],word3[20];
int i,j=0,count=0;
label[0]=operand[0]=opcode[0]=word1[0]=word2[0]=word3[0]='\0';
for(i=0;line[i]!='\0';i++){
if(line[i]!=' '){
buff[j++]=line[i];
}
else{
buff[j]='\0';
strcpy(word3,word2);
strcpy(word2,word1);
strcpy(word1,buff);
j=0;
count++;
}
}
buff[j-1]='\0';
strcpy(word3,word2);
strcpy(word2,word1);
strcpy(word1,buff);
switch(count){
case 0: strcpy(opcode,word1);
break;
case 1: strcpy(opcode,word2);
strcpy(operand,word1);
break;
case 2: strcpy(label,word3);
strcpy(opcode,word2);
strcpy(operand,word1);
break;
}
}
void check_label(){
int k,dupsym=0;
for(k=0;k<symcount;k++){
if(strcmp(label,sym[k].symbol)==0){
sym[k].addr=-1;
dupsym=1;
break;
}
}
if(!dupsym){
strcpy(sym[symcount].symbol,label);
sym[symcount++].addr=lc;
}
//printf("%s %d",sym[symcount-1].symbol,sym[symcount-1].addr);
}
PASS1(){
FILE *input,*inter;
int p,m,d,l;
input=fopen("input.txt","r");
inter=fopen("inter.txt","w+");
if(input==NULL){
printf("Error");
exit(0);
}
if(inter==NULL){
printf("Error");
exit(0);
}
fgets(line,20,input);
READ_LINE();
printf("\nlabel:%s opcode:%s operand:%s",label,opcode,operand);
if(strcmp(opcode,"START")==0){
startaddr=atoi(operand);
lc=startaddr;
strcpy(prgname,label);
fprintf(inter,"%d",lc);
fgets(line,20,input);
}
else{
prgname[0]='\0';
startaddr=0;
lc=0;
fgets(line,20,input);
}
while(strcmp(line,"END\n")!=0){
READ_LINE();
printf("\nlabel:%s opcode:%s operand:%s",label,opcode,operand);
p=search_POT(opcode);
if(p!=-1){
l=0;
fprintf(inter,"\n%d",lc);
}
else{
d=search_DEC(opcode);
if(d!=-1){
l=calc_DEC(opcode,operand);
//if(label[0]!='\0')check_label();
if(strcmp(opcode,"DC")==0)fprintf(inter,"\n%d %s",lc,op);
else fprintf(inter,"\n%d --",lc);
//printf("%d",l);
}
else{
l=4;
fprintf(inter,"\n%d %s %s",lc,opcode,operand);
}
}
if(label[0]!='\0')check_label();
lc=lc+l;
fgets(line,20,input);
}
/*READ_LINE();
printf("\nopcode:%s",opcode);
*/
fprintf(inter,"\n%d",lc);
fclose(input);
fclose(inter);
}
char line1[20],lc1[5],op1[5],op2[5],opcode1[20];
void READ_LINE1(){
char buff[20],word1[20],word2[20],word3[20],word4[20];
int i,j=0,count=0;
lc1[0]=op1[0]=op2[0]=opcode1[0]=word1[0]=word2[0]=word3[0]=word4[0]='\0';
//printf("\n%s",line1);
for(i=0;line1[i]!='\0';i++){
if((line1[i]!=' ')&&(line1[i]!=',')){
buff[j++]=line1[i];
}
else{
buff[j]='\0';
strcpy(word4,word3);
strcpy(word3,word2);
strcpy(word2,word1);
strcpy(word1,buff);
j=0;
count++;
}
}
buff[j]='\0';
strcpy(word4,word3);
strcpy(word3,word2);
strcpy(word2,word1);
strcpy(word1,buff);
if(count==0){
strcpy(lc1,word1);
}
else if(count==1){
strcpy(lc1,word2);
strcpy(op1,word1);
}
else{
strcpy(lc1,word4);
strcpy(opcode1,word3);
strcpy(op1,word2);
strcpy(op2,word1);
}
//printf("lc=%s opcode=%s op1=%s op2=%s",lc1,opcode1,op1,op2);
}
int search_SYMTAB(){
int i,l,j,k=0;
char temp[5];
l=strlen(op2);
for(j=0;op2[j]!='\n';j++){
temp[k++]=op2[j];
}
//temp[k]='\0';
for(i=0;i<symcount;i++){
if(strcmp(temp,sym[i].symbol)==0){
return i;
}
}
return -1;
}
void PASS2(){
FILE *inter,*output;
int c;
inter=fopen("inter.txt","r");
output=fopen("output.txt","w+");
while(fgets(line1,20,inter)!=NULL){
//printf("%s",line1);
READ_LINE1();
if(op2[0]=='\0')
fprintf(output,"%s",line1);
else{
c=search_SYMTAB();
if(c==-1)printf("Undefined symbol");
else{
fprintf(output,"%s %s %s,%d\n",lc1,opcode1,op1,sym[c].addr);
}
}
}
}
void main(){
PASS1();
PASS2();
printf("\n");
}
#include<string.h>
#include<stdlib.h>
char POT[][7]={"START","USING","END"};
char MOT[][6]={"L","ST","A","S","M"};
char DEC[][4]={"DC","DS"};
typedef struct symbol{
char symbol[10];
int addr;
}SYMTAB;
SYMTAB sym[10];
int startaddr,lc,symcount=0,length;
char line[20],label[20],operand[20],opcode[20],prgname[20],op[4];
int search_POT(char opcode[]){
int i,j;
for(i=0;i<5;i++){
if(strcmp(opcode,POT[i])==0)
return i;
}
return -1;
}
int search_DEC(char opcode[]){
int i,j;
for(i=0;i<5;i++){
if(strcmp(opcode,DEC[i])==0)
return i;
}
return -1;
}
int calc_DEC(char opcode[],char operand[]){
int i=0,l,k=0;
char copy[10];
int j=0,m=0;
if(strcmp(opcode,"DC")==0){
switch(operand[0]){
case 'B':i=1;break;
case 'H':i=2;break;
case 'F':i=4;break;
case 'D':i=8;break;
}
for(j=2;operand[j]!='\'';j++){
op[m++]=operand[j];
}
op[m]='\0';
//printf(" %s ",op);
}
else{
l=strlen(operand);
switch(operand[l-1]){
case 'B':i=1;break;
case 'H':i=2;break;
case 'F':i=4;break;
case 'D':i=8;break;
}
for(j=0;j<=l-2;j++){
copy[k++]=operand[j];
}
copy[k]='\0';
//printf("%s",copy);
k=atoi(copy);
i=i*k;
}
return i;
}
void READ_LINE(){
char buff[20],word1[20],word2[20],word3[20];
int i,j=0,count=0;
label[0]=operand[0]=opcode[0]=word1[0]=word2[0]=word3[0]='\0';
for(i=0;line[i]!='\0';i++){
if(line[i]!=' '){
buff[j++]=line[i];
}
else{
buff[j]='\0';
strcpy(word3,word2);
strcpy(word2,word1);
strcpy(word1,buff);
j=0;
count++;
}
}
buff[j-1]='\0';
strcpy(word3,word2);
strcpy(word2,word1);
strcpy(word1,buff);
switch(count){
case 0: strcpy(opcode,word1);
break;
case 1: strcpy(opcode,word2);
strcpy(operand,word1);
break;
case 2: strcpy(label,word3);
strcpy(opcode,word2);
strcpy(operand,word1);
break;
}
}
void check_label(){
int k,dupsym=0;
for(k=0;k<symcount;k++){
if(strcmp(label,sym[k].symbol)==0){
sym[k].addr=-1;
dupsym=1;
break;
}
}
if(!dupsym){
strcpy(sym[symcount].symbol,label);
sym[symcount++].addr=lc;
}
//printf("%s %d",sym[symcount-1].symbol,sym[symcount-1].addr);
}
PASS1(){
FILE *input,*inter;
int p,m,d,l;
input=fopen("input.txt","r");
inter=fopen("inter.txt","w+");
if(input==NULL){
printf("Error");
exit(0);
}
if(inter==NULL){
printf("Error");
exit(0);
}
fgets(line,20,input);
READ_LINE();
printf("\nlabel:%s opcode:%s operand:%s",label,opcode,operand);
if(strcmp(opcode,"START")==0){
startaddr=atoi(operand);
lc=startaddr;
strcpy(prgname,label);
fprintf(inter,"%d",lc);
fgets(line,20,input);
}
else{
prgname[0]='\0';
startaddr=0;
lc=0;
fgets(line,20,input);
}
while(strcmp(line,"END\n")!=0){
READ_LINE();
printf("\nlabel:%s opcode:%s operand:%s",label,opcode,operand);
p=search_POT(opcode);
if(p!=-1){
l=0;
fprintf(inter,"\n%d",lc);
}
else{
d=search_DEC(opcode);
if(d!=-1){
l=calc_DEC(opcode,operand);
//if(label[0]!='\0')check_label();
if(strcmp(opcode,"DC")==0)fprintf(inter,"\n%d %s",lc,op);
else fprintf(inter,"\n%d --",lc);
//printf("%d",l);
}
else{
l=4;
fprintf(inter,"\n%d %s %s",lc,opcode,operand);
}
}
if(label[0]!='\0')check_label();
lc=lc+l;
fgets(line,20,input);
}
/*READ_LINE();
printf("\nopcode:%s",opcode);
*/
fprintf(inter,"\n%d",lc);
fclose(input);
fclose(inter);
}
char line1[20],lc1[5],op1[5],op2[5],opcode1[20];
void READ_LINE1(){
char buff[20],word1[20],word2[20],word3[20],word4[20];
int i,j=0,count=0;
lc1[0]=op1[0]=op2[0]=opcode1[0]=word1[0]=word2[0]=word3[0]=word4[0]='\0';
//printf("\n%s",line1);
for(i=0;line1[i]!='\0';i++){
if((line1[i]!=' ')&&(line1[i]!=',')){
buff[j++]=line1[i];
}
else{
buff[j]='\0';
strcpy(word4,word3);
strcpy(word3,word2);
strcpy(word2,word1);
strcpy(word1,buff);
j=0;
count++;
}
}
buff[j]='\0';
strcpy(word4,word3);
strcpy(word3,word2);
strcpy(word2,word1);
strcpy(word1,buff);
if(count==0){
strcpy(lc1,word1);
}
else if(count==1){
strcpy(lc1,word2);
strcpy(op1,word1);
}
else{
strcpy(lc1,word4);
strcpy(opcode1,word3);
strcpy(op1,word2);
strcpy(op2,word1);
}
//printf("lc=%s opcode=%s op1=%s op2=%s",lc1,opcode1,op1,op2);
}
int search_SYMTAB(){
int i,l,j,k=0;
char temp[5];
l=strlen(op2);
for(j=0;op2[j]!='\n';j++){
temp[k++]=op2[j];
}
//temp[k]='\0';
for(i=0;i<symcount;i++){
if(strcmp(temp,sym[i].symbol)==0){
return i;
}
}
return -1;
}
void PASS2(){
FILE *inter,*output;
int c;
inter=fopen("inter.txt","r");
output=fopen("output.txt","w+");
while(fgets(line1,20,inter)!=NULL){
//printf("%s",line1);
READ_LINE1();
if(op2[0]=='\0')
fprintf(output,"%s",line1);
else{
c=search_SYMTAB();
if(c==-1)printf("Undefined symbol");
else{
fprintf(output,"%s %s %s,%d\n",lc1,opcode1,op1,sym[c].addr);
}
}
}
}
void main(){
PASS1();
PASS2();
printf("\n");
}
CODE OPTIMISATION
#include<stdio.h>
#include<string.h>
#include<ctype.h>
typedef struct{
char arg1,arg2,op,result;
char LHS,RHS[20];
}three_add;
three_add q[10];
int x=0,asc=65;
char OP[20],OD[20],t1,t2;//OP and OD represent operator and data stack
char substring[20];
char* substr(char* string,int start,int end){
int k,l;
memset(substring,0,sizeof(substring));
substring[0]='\0';
for(l=start,k=0;l<=end;l++,k++){
substring[k]=string[l];
substring[k+1]='\0';
}
return substring;
}
int priority(char ele){
int pr;
if(ele=='^')pr=3;
else if(ele=='*'||ele=='/'||ele=='%')pr=2;
else if(ele=='+'||ele=='-')pr=1;
else pr=0;
return pr;
}
void pop(char* op,char* od){
char op1,od1,od2;
op1=op[strlen(op)-1];//pop the operator at stack top from operator stack
od2=od[strlen(od)-1];//topmost is stored in od2 not od1
od1=od[strlen(od)-2];
//Form the three address
q[x].result=(char)asc;
q[x].arg1=od1;
q[x].op=op1;
q[x].arg2=od2;
//push the result into the data stack
od[strlen(od)-2]=(char)asc;
od[strlen(od)-1]='\0';
op[strlen(op)-1]='\0';
asc++;
x++;
}
int main(){
char string[20],str[20];
int i=0,j,len1,len2;
memset(str,0,sizeof(str));
memset(string,0,sizeof(string));
string[0]='\0';
printf("Enter the infix expression:");
scanf("%c=%s",&q[0].LHS,q[0].RHS);
strcpy(string,q[0].RHS);
len1=strlen(string);
for(i=0;i<strlen(string);i++){
str[0]='\0';
if(string[0]=='-'){
q[x].arg1=string[1];/*if infix=-b+a+7+(b+c)-9-s*w then after this step, it is A+a+7+(b+c)-9-s*w where A=-b*/
q[x].op='\0';
q[x].arg2=string[0];//string[0] is arg2 and not arg1 because we are printing arg2 first
q[x].result=(char)asc;
str[0]=q[x].result;//write A to str
str[1]='\0';
strcat(str,substr(string,2,len1));//copy from + to -9
asc++;
x++;
strcpy(string,str);
}
else if(string[i]=='('){
memset(str,0,sizeof(str));
q[x].arg1=string[i+1];//to replace (b+c) with B
q[x].op=string[i+2];
q[x].arg2=string[i+3];
q[x].result=(char)asc;
strcpy(str,substr(string,0,i-1));//copy from A+ to 7+ in str
len2=strlen(str);
str[len2]=q[x].result;//write B to str
str[len2+1]='\0';
strcat(str,substr(string,i+5,len1));
asc++;
x++;
strcpy(string,str);//hence the string in string is A+a+7+B-9-s*w
}
}
for(i=0;i<strlen(string);i++){
t1=string[i];//t1 is the current string
if(priority(t1)==0){//it is data ie number and not operator
OD[strlen(OD)]=t1;
}
else{
for(j=(strlen(OP)-1);j>=0;j--){//traverse the stack
t2=OP[j];//t2 is the stack top
if(priority(t1)>priority(t2))
break;
else
pop(OP,OD);//pop until the priority of the symbol at stack top is less than the priority of the given symbol
}
OP[strlen(OP)]=t1;//push the current operator into the stack
}
}
//the three addresses are formed in sequence
for(i=strlen(OP)-1;i>=0;i--)//pop the remaining operators from the stack
pop(OP,OD);
if(q[0].LHS!=' '){//The last line of three address For eg:S=c+a*b, A=a*b,B=c+A,S=B. It is for S=B line
q[x].arg1=q[x-1].result;
q[x].result=q[0].LHS;
}
//print the three address
for(i=0;i<=x;i++){
if(q[i].result!='\0'){
if(i==x)//last one
printf("\n\n%c:=%c",q[i].result,q[i].arg1);//done above
else
printf("\n\n%c:=%c %c %c",q[i].result,q[i].arg2,q[i].op,q[i].arg1);//arg2 printed first
}
}
return 0;
}
#include<string.h>
#include<ctype.h>
typedef struct{
char arg1,arg2,op,result;
char LHS,RHS[20];
}three_add;
three_add q[10];
int x=0,asc=65;
char OP[20],OD[20],t1,t2;//OP and OD represent operator and data stack
char substring[20];
char* substr(char* string,int start,int end){
int k,l;
memset(substring,0,sizeof(substring));
substring[0]='\0';
for(l=start,k=0;l<=end;l++,k++){
substring[k]=string[l];
substring[k+1]='\0';
}
return substring;
}
int priority(char ele){
int pr;
if(ele=='^')pr=3;
else if(ele=='*'||ele=='/'||ele=='%')pr=2;
else if(ele=='+'||ele=='-')pr=1;
else pr=0;
return pr;
}
void pop(char* op,char* od){
char op1,od1,od2;
op1=op[strlen(op)-1];//pop the operator at stack top from operator stack
od2=od[strlen(od)-1];//topmost is stored in od2 not od1
od1=od[strlen(od)-2];
//Form the three address
q[x].result=(char)asc;
q[x].arg1=od1;
q[x].op=op1;
q[x].arg2=od2;
//push the result into the data stack
od[strlen(od)-2]=(char)asc;
od[strlen(od)-1]='\0';
op[strlen(op)-1]='\0';
asc++;
x++;
}
int main(){
char string[20],str[20];
int i=0,j,len1,len2;
memset(str,0,sizeof(str));
memset(string,0,sizeof(string));
string[0]='\0';
printf("Enter the infix expression:");
scanf("%c=%s",&q[0].LHS,q[0].RHS);
strcpy(string,q[0].RHS);
len1=strlen(string);
for(i=0;i<strlen(string);i++){
str[0]='\0';
if(string[0]=='-'){
q[x].arg1=string[1];/*if infix=-b+a+7+(b+c)-9-s*w then after this step, it is A+a+7+(b+c)-9-s*w where A=-b*/
q[x].op='\0';
q[x].arg2=string[0];//string[0] is arg2 and not arg1 because we are printing arg2 first
q[x].result=(char)asc;
str[0]=q[x].result;//write A to str
str[1]='\0';
strcat(str,substr(string,2,len1));//copy from + to -9
asc++;
x++;
strcpy(string,str);
}
else if(string[i]=='('){
memset(str,0,sizeof(str));
q[x].arg1=string[i+1];//to replace (b+c) with B
q[x].op=string[i+2];
q[x].arg2=string[i+3];
q[x].result=(char)asc;
strcpy(str,substr(string,0,i-1));//copy from A+ to 7+ in str
len2=strlen(str);
str[len2]=q[x].result;//write B to str
str[len2+1]='\0';
strcat(str,substr(string,i+5,len1));
asc++;
x++;
strcpy(string,str);//hence the string in string is A+a+7+B-9-s*w
}
}
for(i=0;i<strlen(string);i++){
t1=string[i];//t1 is the current string
if(priority(t1)==0){//it is data ie number and not operator
OD[strlen(OD)]=t1;
}
else{
for(j=(strlen(OP)-1);j>=0;j--){//traverse the stack
t2=OP[j];//t2 is the stack top
if(priority(t1)>priority(t2))
break;
else
pop(OP,OD);//pop until the priority of the symbol at stack top is less than the priority of the given symbol
}
OP[strlen(OP)]=t1;//push the current operator into the stack
}
}
//the three addresses are formed in sequence
for(i=strlen(OP)-1;i>=0;i--)//pop the remaining operators from the stack
pop(OP,OD);
if(q[0].LHS!=' '){//The last line of three address For eg:S=c+a*b, A=a*b,B=c+A,S=B. It is for S=B line
q[x].arg1=q[x-1].result;
q[x].result=q[0].LHS;
}
//print the three address
for(i=0;i<=x;i++){
if(q[i].result!='\0'){
if(i==x)//last one
printf("\n\n%c:=%c",q[i].result,q[i].arg1);//done above
else
printf("\n\n%c:=%c %c %c",q[i].result,q[i].arg2,q[i].op,q[i].arg1);//arg2 printed first
}
}
return 0;
}
SHIFT REDUCE PARSER
#include<stdio.h>
#include<stdlib.h>
//#include<conio.h>
#include<string.h>
char ip_sym[15],stack[15];
int ip_ptr=0,st_ptr=0,len,i;
char temp[2],temp2[2];
char act[15];
void check();
void main()
{
//clrscr();
printf("\n\t\t SHIFT REDUCE PARSER\n");
printf("\n GRAMMER\n");
printf("\n E->E+E\n E->E");
printf("\n E->E*E\n E->i");
printf("\n enter the input symbol:\t");
gets(ip_sym);
printf("\n\t stack implementation table");
printf("\n stack\t\t input symbol\t\t action");
printf("\n______\t\t ____________\t\t ______\n");
printf("\n $\t\t%s$\t\t\t--",ip_sym);
strcpy(act,"shift ");
temp[0]=ip_sym[ip_ptr];
temp[1]='\0';
strcat(act,temp);
len=strlen(ip_sym);
for(i=0;i<=len-1;i++)
{
stack[st_ptr]=ip_sym[ip_ptr];
stack[st_ptr+1]='\0';
ip_sym[ip_ptr]=' ';
ip_ptr++;
printf("\n $%s\t\t%s$\t\t\t%s",stack,ip_sym,act);
strcpy(act,"shift ");
temp[0]=ip_sym[ip_ptr];
temp[1]='\0';
strcat(act,temp);
check();
st_ptr++;
}
st_ptr++;
check();
}
void check()
{
int flag=0;
temp2[0]=stack[st_ptr];
temp2[1]='\0';
if((!strcmp(temp2,"i")))
{
stack[st_ptr]='E';
printf("\n $%s\t\t%s$\t\t\tE->i",stack, ip_sym);
flag=1; }
if((!strcmp(temp2,"+"))||(!strcmp(temp2,"*"))||(!strcmp(temp2,"/")))
{
flag=1;
}
if((!strcmp(stack,"E+E"))||(!strcmp(stack,"E"))||(!strcmp(stack,"E*E")))
{
strcpy(stack,"E");
st_ptr=0;
if(!strcmp(stack,"E+E"))
printf("\n $%s\t\t%s$\t\t\tE->E+E",stack,ip_sym);
else
if(!strcmp(stack,"E"))
printf("\n $%s\t\t%s$\t\t\tE->E",stack,ip_sym);
else
printf("\n $%s\t\t%s$\t\t\tE->E*E",stack,ip_sym);
flag=1;
}
if(!strcmp(stack,"E")&&ip_ptr==len)
{
printf("\n $%s\t\t%s$\t\t\tACCEPT",stack,ip_sym);
//getch();
exit(0);
}
if(flag==0)
{
printf("\n %s\t\t%s \t\t\tREJECT",stack,ip_sym);
//getch();
exit(0);
}
return;
}
ELIMINATION OF LEFT RECURSION
#define SIZE 10
#include<stdio.h>
main () {
char non_terminal;
char beta,alpha;
char production[SIZE];
int index=3; /* starting of the string following "->" */
printf("Enter the grammar:\n");
scanf("%s",production);
non_terminal=production[0];
if(non_terminal==production[index]) {
alpha=production[index+1];
printf("Grammar is left recursive.\n");
while(production[index]!=0 && production[index]!='|')
index++;
if(production[index]!=0) {
beta=production[index+1];
printf("Grammar without left recursion:\n");
printf("%c->%c%c\'",non_terminal,beta,non_terminal);
printf("\n%c\'->%c%c\'|e\n",non_terminal,alpha,non_terminal);
}
else
printf("Grammar can't be reduced\n");
}
else
printf("Grammar is not left recursive.\n");
}
#include<stdio.h>
main () {
char non_terminal;
char beta,alpha;
char production[SIZE];
int index=3; /* starting of the string following "->" */
printf("Enter the grammar:\n");
scanf("%s",production);
non_terminal=production[0];
if(non_terminal==production[index]) {
alpha=production[index+1];
printf("Grammar is left recursive.\n");
while(production[index]!=0 && production[index]!='|')
index++;
if(production[index]!=0) {
beta=production[index+1];
printf("Grammar without left recursion:\n");
printf("%c->%c%c\'",non_terminal,beta,non_terminal);
printf("\n%c\'->%c%c\'|e\n",non_terminal,alpha,non_terminal);
}
else
printf("Grammar can't be reduced\n");
}
else
printf("Grammar is not left recursive.\n");
}
FIRST AND FOLLOW
#include<stdio.h>
#include<ctype.h>
char a[100][8];
struct firTab
{
int n;
char firT[5];
};
struct folTab
{
int n;
char folT[5];
};
int n;
struct folTab follow[5];
struct firTab first[5];
int col;
void findFirst(char,char);
void findFollow(char,char);
void folTabOperation(char,char);
void firTabOperation(char,char);
void main()
{
int i,j,c=0,cnt=0;
char ip;
char b[8];
printf("Enter the number of productions(atmost 8):");
scanf("%d",&n);
printf("\nFIRST AND FOLLOW SET \n\nenter %d productions in format A->B+T\n",n);
for(i=0;i<n;i++)
{
scanf("%s",&a[i]);
}
for(i=0;i<n;i++)
{ c=0;
for(j=0;j<i+1;j++)
{
if(a[i][0] == b[j])
{
c=1;
break;
}
}
if(c !=1)
{
b[cnt] = a[i][0];
cnt++;
}
}
printf("\n");
for(i=0;i<cnt;i++)
{ col=1;
first[i].firT[0] = b[i];
first[i].n=0;
findFirst(b[i],i);
}
for(i=0;i<cnt;i++)
{
col=1;
follow[i].folT[0] = b[i];
follow[i].n=0;
findFollow(b[i],i);
}
printf("\n");
for(i=0;i<cnt;i++)
{
for(j=0;j<=first[i].n;j++)
{
if(j==0)
{
printf("First(%c) : {",first[i].firT[j]);
}
else
{
printf(" %c",first[i].firT[j]);
}
}
printf(" } ");
printf("\n");
}
printf("\n");
for(i=0;i<cnt;i++)
{
for(j=0;j<=follow[i].n;j++)
{
if(j==0)
{
printf("Follow(%c) : {",follow[i].folT[j]);
}
else
{
printf(" %c",follow[i].folT[j]);
}
}
printf(" } ");
printf("\n");
}
}
void findFirst(char ip,char pos)
{
int i;
for(i=0;i<n;i++)
{
if(ip == a[i][0])
{
if(isupper(a[i][3]))
{
findFirst(a[i][3],pos);
}
else
{
first[pos].firT[col]=a[i][3];
first[pos].n++;
col++;
}
}
}
}
void findFollow(char ip,char row)
{ int i,j;
if(row==0 && col==1)
{
follow[row].folT[col]= '$';
col++;
follow[row].n++;
}
for(i=0;i<n;i++)
{
for(j=3;j<7;j++)
{
if(a[i][j] == ip)
{
if(a[i][j+1] == '\0')
{
if(a[i][j] != a[i][0])
{
folTabOperation(a[i][0],row);
}
}
else if(isupper(a[i][j+1]))
{ if(a[i][j+1] != a[i][0])
{
firTabOperation(a[i][j+1],row);
}
}
else
{
follow[row].folT[col] = a[i][j+1];
col++;
follow[row].n++;
}
}
}
}
}
void folTabOperation(char ip,char row)
{ int i,j;
for(i=0;i<5;i++)
{
if(ip == follow[i].folT[0])
{
for(j=1;j<=follow[i].n;j++)
{
follow[row].folT[col] = follow[i].folT[j];
col++;
follow[row].n++;
}
}
}
}
void firTabOperation(char ip,char row)
{
int i,j;
for(i=0;i<5;i++)
{
if(ip == first[i].firT[0])
{
for(j=1;j<=first[i].n;j++)
{
if(first[i].firT[j] != '0')
{
follow[row].folT[col] = first[i].firT[j];
follow[row].n++;
col++;
}
else
{
folTabOperation(ip,row);
}
}
}
}
}
#include<ctype.h>
char a[100][8];
struct firTab
{
int n;
char firT[5];
};
struct folTab
{
int n;
char folT[5];
};
int n;
struct folTab follow[5];
struct firTab first[5];
int col;
void findFirst(char,char);
void findFollow(char,char);
void folTabOperation(char,char);
void firTabOperation(char,char);
void main()
{
int i,j,c=0,cnt=0;
char ip;
char b[8];
printf("Enter the number of productions(atmost 8):");
scanf("%d",&n);
printf("\nFIRST AND FOLLOW SET \n\nenter %d productions in format A->B+T\n",n);
for(i=0;i<n;i++)
{
scanf("%s",&a[i]);
}
for(i=0;i<n;i++)
{ c=0;
for(j=0;j<i+1;j++)
{
if(a[i][0] == b[j])
{
c=1;
break;
}
}
if(c !=1)
{
b[cnt] = a[i][0];
cnt++;
}
}
printf("\n");
for(i=0;i<cnt;i++)
{ col=1;
first[i].firT[0] = b[i];
first[i].n=0;
findFirst(b[i],i);
}
for(i=0;i<cnt;i++)
{
col=1;
follow[i].folT[0] = b[i];
follow[i].n=0;
findFollow(b[i],i);
}
printf("\n");
for(i=0;i<cnt;i++)
{
for(j=0;j<=first[i].n;j++)
{
if(j==0)
{
printf("First(%c) : {",first[i].firT[j]);
}
else
{
printf(" %c",first[i].firT[j]);
}
}
printf(" } ");
printf("\n");
}
printf("\n");
for(i=0;i<cnt;i++)
{
for(j=0;j<=follow[i].n;j++)
{
if(j==0)
{
printf("Follow(%c) : {",follow[i].folT[j]);
}
else
{
printf(" %c",follow[i].folT[j]);
}
}
printf(" } ");
printf("\n");
}
}
void findFirst(char ip,char pos)
{
int i;
for(i=0;i<n;i++)
{
if(ip == a[i][0])
{
if(isupper(a[i][3]))
{
findFirst(a[i][3],pos);
}
else
{
first[pos].firT[col]=a[i][3];
first[pos].n++;
col++;
}
}
}
}
void findFollow(char ip,char row)
{ int i,j;
if(row==0 && col==1)
{
follow[row].folT[col]= '$';
col++;
follow[row].n++;
}
for(i=0;i<n;i++)
{
for(j=3;j<7;j++)
{
if(a[i][j] == ip)
{
if(a[i][j+1] == '\0')
{
if(a[i][j] != a[i][0])
{
folTabOperation(a[i][0],row);
}
}
else if(isupper(a[i][j+1]))
{ if(a[i][j+1] != a[i][0])
{
firTabOperation(a[i][j+1],row);
}
}
else
{
follow[row].folT[col] = a[i][j+1];
col++;
follow[row].n++;
}
}
}
}
}
void folTabOperation(char ip,char row)
{ int i,j;
for(i=0;i<5;i++)
{
if(ip == follow[i].folT[0])
{
for(j=1;j<=follow[i].n;j++)
{
follow[row].folT[col] = follow[i].folT[j];
col++;
follow[row].n++;
}
}
}
}
void firTabOperation(char ip,char row)
{
int i,j;
for(i=0;i<5;i++)
{
if(ip == first[i].firT[0])
{
for(j=1;j<=first[i].n;j++)
{
if(first[i].firT[j] != '0')
{
follow[row].folT[col] = first[i].firT[j];
follow[row].n++;
col++;
}
else
{
folTabOperation(ip,row);
}
}
}
}
}
Monday, 12 January 2015
BOOTH PROGRAM
BOOTH PROGRAM
import java.util.*;
class BOOTH
{
public static int[] add(int a[],int m1[])
{
int carry=0;
int sum[]=new int [4];
for(int i=3;i>=0;i--)
{
sum[i]=(a[i]+m1[i]+carry)%2;
carry=(a[i]+m1[i]+carry)/2;
}
return sum;
}
public static void shift(int a[],int q[])
{
int b=a[3];
for(int i=2;i>=0;i--)
{
a[i+1]=a[i];
q[i+1]=q[i];
}
q[0]=b;
}
public static int[] comp(int m1[])
{
int z[]={0,0,0,1};
for(int i=0;i<4;i++)
{
if(m1[i]==0)
m1[1]=1;
else
m1[i]=0;
}
int c[]=add(m1,z);
return c;
}
public static void display(int a[],int q[],int Q1,int m[])
{
for(int i=0;i<4;i++)
{
System.out.print(a[i]);
}
System.out.print("\t");
for(int i=0;i<4;i++)
{
System.out.print(q[i]);
}
System.out.print("\t");
System.out.print(Q1);
System.out.print("\t");
for(int i=0;i<4;i++)
{
System.out.print(m[i]);
}
System.out.print("\t");
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int m[]=new int[4];
int q[]=new int[4];
int a[]={0,0,0,0};
int Q1=0;
int count=4;
int m1[]=new int[4];
System.out.println("ENTER MULTIPLICAND:");
for(int i=0;i<4;i++)
{
m[i]=sc.nextInt();
}
System.out.println("ENTER MULTIPLIER:");
for(int i=0;i<4;i++)
{
q[i]=sc.nextInt();
}
System.out.println("A \t Q \tQ-1\t M \toperation");
display(a,q,Q1,m);
System.out.print("Initial\n");
for(int i=count;i>0;i--)
{
for(int j=0;j<4;j++)
{
m1[j]=m[j];
}
if(q[3]==0&&Q1==1)
{
a=add(a,m1);
display(a,q,Q1,m);
System.out.print("A<~A+M\n");
}
if((q[3]==1&&Q1==1)||(q[3]==3&&Q1==0))
{ }
if(q[3]==1&&Q1==0)
{
int c[]=comp(m1);
a=add(a,c);
display(a,q,Q1,m);
System.out.print("A<~A-M\n");
}
Q1=q[3];
shift(a,q);
display(a,q,Q1,m);
System.out.print("shift\n");
}
}
}
OUTPUT:
