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

Read More

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

Read More

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

Read More

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

Read More

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

}

Read More

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:

Read More

INSERT AN ELEMENT IN SORTED ARRAY

                            INSERT AN ELEMENT IN SORTED ARRAY

#include <stdio.h>

void insert_sorted();

int a[50], n, item;

main()

{

int i;

printf("\nEnter size of an array: ");

scanf("%d", &n);

printf("\nEnter sorted elements of an array:\n");

for(i=0; i<n; i++)

scanf("%d", &a[i]);

printf("\nEnter ITEM to insert: ");

scanf("%d", &item);

insert_sorted();

printf("\n\nAfter insertion:\n");

for(i=0; i<n; i++)

printf("\n%d", a[i]);

getch();

}

void insert_sorted()

{

int i = n-1;

while(item<a[i] && i>=0)

{

a[i+1] = a[i];

i--;

}

a[i+1] = item;

n++;

}

OUTPUT

Read More