WAP to generate the target code by using labelling algorithm.

/*
2) WAP to generate the target code by using labelling algorithm.
Input: Labelled tree
Output: Target code
*/
#include<stdio.h>
#include<stdlib.h>

typedef struct holder
{
char name[5];
int label;
struct holder * left,*right;
}node;

node * root=NULL, *temp;

node * getnode()
{
return((node*)malloc(sizeof(node)));
}

int rstack[3]={0,1,2},tstack[3]={0,1,2},rtop=0,ttop=0;
char * mapop(char op[5])
{
if(strcmp("+",op)==0)
return("ADD");
if(strcmp("-",op)==0)
return("SUB");
if(strcmp("*",op)==0)
return("MUL");
if(strcmp("/",op)==0)
return("DIV");
if(strcmp("=",op)==0)
return("MOV");
return("Error");
}

node * create()
{
node * temp;
char name[5];
temp=getnode();
printf("\n\tEnter Node : ");
scanf("%s",temp->name);
printf("\n\tIs there left node present for %s (y / n): ",temp->name);
scanf("%s",name);
if(strcmp(name,"y")==0)
temp->left=create();
else
temp->left=NULL;

printf("\n\tIs there right node present for %s (y / n): ",temp->name);
scanf("%s",name);
if(strcmp(name,"y")==0)
temp->right=create();
else
temp->right=NULL;

return(temp);
}

int label(node * temp)
{
node * temp1;
if(temp->left!=NULL || temp->right!=NULL)
{
label(temp->left);
label(temp->right);

temp1=temp->left;
if(temp1->left==NULL && temp1->right==NULL) //left leaf node
temp1->label=1;
else if(temp1->left->label == temp1->right->label)
temp1->label=temp1->left->label+1;
else
if(temp1->left->label > temp1->right->label)
temp1->label=temp1->left->label;
else
temp1->label=temp1->right->label;

temp1=temp->right;
if(temp1->left==NULL && temp1->right==NULL) // rt leaf
temp1->label=0;
else if(temp1->left->label == temp1->right->label)
temp1->label=temp1->left->label+1;
else
if(temp1->left->label > temp1->right->label)
temp1->label=temp1->left->label;
else
temp1->label=temp1->right->label;

}
}

void swap()
{
int temp=rstack[rtop];
rstack[rtop]=rstack[rtop+1];
rstack[rtop+1]=temp;
}

void codegen(node * temp)
{
int i;
if(temp==NULL)
return;
if(temp->left==NULL && temp->right==NULL && temp->label==1) //ie left leaf node
printf("\n\tMOV %s , R%d\t#L",temp->name,rstack[rtop++]);
else if(temp->right->label==0) // rt leaf
{
codegen(temp->left);
printf("\n\t%s %s , R%d\t#R",mapop(temp->name),temp->right->name,rstack[rtop-1]);
}
else if(temp->left->label < temp->right->label && temp->left->label<3)
{
int R;
swap();
codegen(temp->right);
R=rstack[rtop-1];
//poping
for(i=rtop-1;i<3;i++)
rstack[i]=rstack[i+1];
rtop--;
codegen(temp->left);
printf("\n\t%s R%d , R%d\t#1",mapop(temp->name),R,rstack[rtop-1]);
//pushing
rstack[rtop++]=R;
swap();
}
else if(temp->left->label > temp->right->label && temp->right->label<3)
{
int R;
codegen(temp->left);
R=rstack[rtop-1];
//poping
for(i=rtop-1;i<3;i++)
rstack[i]=rstack[i+1];
rtop--;
codegen(temp->right);
printf("\n\t%s R%d , R%d\t#2",mapop(temp->name),R,rstack[rtop-1]);
//pushing
rstack[rtop++]=R;
}
else
{
int T;
codegen(temp->right);
T=tstack[ttop--];
printf("\n\tMOV R%d , T%d",rstack[rtop-1],T);
codegen(temp->left);
ttop++;
printf("\n\t%s T%d , R%d",mapop(temp->name),T,rstack[rtop-1]);
}
}
void print(node * temp)
{
if(temp!=NULL)
{
print(temp->left);
print(temp->right);
printf("\n\t %s \t %d",temp->name,temp->label);
}
}
int main()
{
int i,j,k,no;
printf("\n\tEnter syntax tree : ");
root=create();
label(root);
if(root->left->label == root->right->label)
root->label=root->left->label+1;
else if(root->left->label > root->right->label)
root->label=root->left->label;
else
root->label=root->right->label;
codegen(root);
print(root);
}