Computer Lab I index
1) Write a programm to recgnize static words from english
2 ) Lex programm to recgnize static words from english using structure
3) Lex program to recognize tokens from C program
4) 3) Write an ambiguous CFG to recognize an infix expression and implement a parser that recognizes the infix expression using YACC. Provide the details of all conflicting entries in the parser table generated by LEX and YACC and how they have been resolved. Input : Infix expressions with variables Output: a]Stepwise evaluation of expression, b] Symbol table c] explanation of conflicting entries in y.output file d] explanation for resolving the ambiguities
5) Write an ambiguous CFG to recognize an infix expression and implement a parser that recognizes the infix expression using YACC. Provide the details of all conflicting entries in the parser table generated by LEX and YACC and how they have been resolved. Input : Infix expressions with variables Output: a]Stepwise evaluation of expression, b] Symbol table c] explanation of conflicting entries in y.output file d] explanation for resolving the ambiguities
6) Write an attributed translation grammar to recognize declarations of variables, assignment statement with type checking as per syntax of C and generate equivalent three address code for the given input made up of constructs mentioned above using LEX and YACC. Write a code to store the identifiers from the input in a symbol table and also to record other relevant information about the identifiers. Display all records stored in the symbol table. Input: C code snippet Output: a] equivalent three address code b] Symbol table with type information c] Error handling for type checking
7) Write an attributed translation grammar to recognize declarations of variables, assignment statement & “while” statement as per syntax of C and generate equivalent three address code for the given input made up of constructs mentioned above using LEX and YACC. Write a code to store the identifiers from the input in a symbol table and also to record other relevant information about the identifiers. Display all records stored in the symbol table.
8) Write an attributed translation grammar to recognize declarations of variables, assignment statement & if- else statement as per syntax of C and generate equivalent three address code for the given input made up of constructs mentioned above using LEX and YACC. Write a code to store the identifiers from the input in a symbol table and also to record other relevant information about the identifiers. Display all records stored in the symbol table.
9) WAP to implement following code optimization techniques: a)common sub-expression elimination b)variable propagation
10 ) WAP to code optimization techniques: a)dead code elimination b) constant propagation
11) WAP to implement following code optimization techniques: a)strength reduction b) constant folding
12) WAP to label the tree for code generation. Input: Syntax Tree Output: Labelled syntax tree [use any tree traversal method]
13) WAP to generate the target code by using labelling algorithm. Input: Labelled tree Output: Target code
read more
2 ) Lex programm to recgnize static words from english using structure
3) Lex program to recognize tokens from C program
4) 3) Write an ambiguous CFG to recognize an infix expression and implement a parser that recognizes the infix expression using YACC. Provide the details of all conflicting entries in the parser table generated by LEX and YACC and how they have been resolved. Input : Infix expressions with variables Output: a]Stepwise evaluation of expression, b] Symbol table c] explanation of conflicting entries in y.output file d] explanation for resolving the ambiguities
5) Write an ambiguous CFG to recognize an infix expression and implement a parser that recognizes the infix expression using YACC. Provide the details of all conflicting entries in the parser table generated by LEX and YACC and how they have been resolved. Input : Infix expressions with variables Output: a]Stepwise evaluation of expression, b] Symbol table c] explanation of conflicting entries in y.output file d] explanation for resolving the ambiguities
6) Write an attributed translation grammar to recognize declarations of variables, assignment statement with type checking as per syntax of C and generate equivalent three address code for the given input made up of constructs mentioned above using LEX and YACC. Write a code to store the identifiers from the input in a symbol table and also to record other relevant information about the identifiers. Display all records stored in the symbol table. Input: C code snippet Output: a] equivalent three address code b] Symbol table with type information c] Error handling for type checking
7) Write an attributed translation grammar to recognize declarations of variables, assignment statement & “while” statement as per syntax of C and generate equivalent three address code for the given input made up of constructs mentioned above using LEX and YACC. Write a code to store the identifiers from the input in a symbol table and also to record other relevant information about the identifiers. Display all records stored in the symbol table.
8) Write an attributed translation grammar to recognize declarations of variables, assignment statement & if- else statement as per syntax of C and generate equivalent three address code for the given input made up of constructs mentioned above using LEX and YACC. Write a code to store the identifiers from the input in a symbol table and also to record other relevant information about the identifiers. Display all records stored in the symbol table.
9) WAP to implement following code optimization techniques: a)common sub-expression elimination b)variable propagation
10 ) WAP to code optimization techniques: a)dead code elimination b) constant propagation
11) WAP to implement following code optimization techniques: a)strength reduction b) constant folding
12) WAP to label the tree for code generation. Input: Syntax Tree Output: Labelled syntax tree [use any tree traversal method]
13) WAP to generate the target code by using labelling algorithm. Input: Labelled tree Output: Target code
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);
}
read more
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);
}
WAP to label the tree for code generation
/*
1) WAP to label the tree for code generation.
Input: Syntax Tree
Output: Labelled syntax tree [use any tree traversal method]
*/
#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)));
}
node * create()
{
node * temp;
char ch[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",ch);
if(strcmp(ch,"y")==0)
temp->left=create();
else
temp->left=NULL;
printf("\n\tIs there right node present for %s (y / n): ",temp->name);
scanf("%s",ch);
if(strcmp(ch,"y")==0)
temp->right=create();
else
temp->right=NULL;
return(temp);
}
void 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;
temp1=temp->right;
if(temp1->left==NULL && temp1->right==NULL) // rt leaf
temp1->label=0;
if(temp->left->label == temp->right->label)
temp->label=temp->left->label+1;
else
if(temp->left->label > temp->right->label)
temp->label=temp->left->label;
else
temp->label=temp->right->label;
}
}
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;
print(root);
}
read more
1) WAP to label the tree for code generation.
Input: Syntax Tree
Output: Labelled syntax tree [use any tree traversal method]
*/
#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)));
}
node * create()
{
node * temp;
char ch[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",ch);
if(strcmp(ch,"y")==0)
temp->left=create();
else
temp->left=NULL;
printf("\n\tIs there right node present for %s (y / n): ",temp->name);
scanf("%s",ch);
if(strcmp(ch,"y")==0)
temp->right=create();
else
temp->right=NULL;
return(temp);
}
void 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;
temp1=temp->right;
if(temp1->left==NULL && temp1->right==NULL) // rt leaf
temp1->label=0;
if(temp->left->label == temp->right->label)
temp->label=temp->left->label+1;
else
if(temp->left->label > temp->right->label)
temp->label=temp->left->label;
else
temp->label=temp->right->label;
}
}
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;
print(root);
}
code optimization techniques: a)strength reduction b) constant folding
### tac.txt #####
1 sq b - c
2 * 2 c c
3 := c - res
4 + a b no1
5 - res no1 res
6 + 3 5 pi
7 := pi - x
8 / x 2 res1
read more
1 sq b - c
2 * 2 c c
3 := c - res
4 + a b no1
5 - res no1 res
6 + 3 5 pi
7 := pi - x
8 / x 2 res1
##### pr_11a.c ######
/*
10) WAP to implement following code optimization techniques:
a)strength reduction b) constant folding
*/
#include<stdio.h>
struct holder
{
char seqno[3],op[3],arg1[8],arg2[8],result[8];
}tac[50];
int cnt=0,i,j,k;
char hunted[8];
int is_const(char arg[8])
{
for(j=0;j<strlen(arg);j++)
if(!isdigit(arg[j]))
return(0);
return(1);
}
void strength_red()
{
//check * sign and try to replace it by + and sq by *
for(i=0;i<cnt;i++)
{
if(strcmp(tac[i].op,"*")==0)
{
if(atoi(tac[i].arg1)==2 && !(is_const(tac[i].arg2)) )
{
strcpy(tac[i].op,"+");
strcpy(tac[i].arg1,tac[i].arg2);
}
else if(atoi(tac[i].arg2)==2 && !(is_const(tac[i].arg1)))
{
strcpy(tac[i].op,"+");
strcpy(tac[i].arg2,tac[i].arg1);
}
}
if(strcmp(tac[i].op,"/")==0 && atoi(tac[i].arg2)==2)
{
strcpy(tac[i].op,"*");
strcpy(tac[i].arg2,"0.5");
}
if(strcmp(tac[i].op,"sq")==0)
{
strcpy(tac[i].op,"*");
strcpy(tac[i].arg2,tac[i].arg1);
}
}
}
void const_folding()
{
//hunt var1 = const +/-/*// const and then insted of arg1 place result replece const
int val=0;
for(i=0;i<cnt;i++)
{
if(is_const(tac[i].arg1)&&is_const(tac[i].arg2))
{
if(strcmp("+",tac[i].op)==0)
sprintf(tac[i].arg1,"%d",atoi(tac[i].arg1)+atoi(tac[i].arg2));
if(strcmp("-",tac[i].op)==0)
sprintf(tac[i].arg1,"%d",atoi(tac[i].arg1)-atoi(tac[i].arg2));
if(strcmp("*",tac[i].op)==0)
sprintf(tac[i].arg1,"%d",atoi(tac[i].arg1)*atoi(tac[i].arg2));
if(strcmp("/",tac[i].op)==0)
sprintf(tac[i].arg1,"%d",atoi(tac[i].arg1)/atoi(tac[i].arg2));
sprintf(tac[i].arg2,"-");
sprintf(tac[i].op,":=");
}
}
}
int main()
{
FILE * fin =fopen("tac.txt","r");
int i;
while(!feof(fin))
{
fscanf(fin,"%s%s%s%s%s",tac[cnt].seqno,tac[cnt].op,tac[cnt].arg1,tac[cnt].arg2,tac[cnt].result);
cnt++;
}
cnt--;
printf("\n\t\t*** $$ PURE INPUT $$ ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}
strength_red();
const_folding();
printf("\n\t\t*** After Process ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}
fclose(fin);
}
#### output #####
pr@prashant-HP:~/LEX&YACC/11$ cc pr_11a.c
pr@prashant-HP:~/LEX&YACC/11$ ./a.out
*** $$ PURE INPUT $$ ****
Index OP Arg1 Arg2 Result
1 sq b - c
2 * 2 c c
3 := c - res
4 + a b no1
5 - res no1 res
6 + 3 5 pi
7 := pi - x
8 / x 2 res1
*** After Process ****
Index OP Arg1 Arg2 Result
1 * b b c
2 + c c c
3 := c - res
4 + a b no1
5 - res no1 res
6 := 8 - pi
7 := pi - x
8 * x 0.5 res1pr@prashant-HP:~/LEX&YACC/11$
code optimization techniques: a)dead code elimination b) constant propagation
### tac.txt ###
1 := b - c
2 * b c c
3 + b a res
4 - res no1 res
5 := 322 - no
6 := no - x
7 * x c res1
read more
1 := b - c
2 * b c c
3 + b a res
4 - res no1 res
5 := 322 - no
6 := no - x
7 * x c res1
###### pr_10.c ######
/*
9) WAP to implement following code optimization techniques:
a)dead code elimination b) constant propagation
*/
#include<stdio.h>
struct holder
{
char seqno[3],op[3],arg1[8],arg2[8],result[8];
}tac[50];
int cnt=0,i,j,k,used,isnum;
char hunted[8];
void removeline(int no)
{
for(k=no;k<=cnt;k++)
tac[k]=tac[k+1];
cnt--;
}
void eliminate_dead()
{
//if not used in future remove that line
for(i=0;i<cnt-1;i++)
{
used=0;
strcpy(hunted,tac[i].result);
for(j=i+1;j<cnt;j++)
{
if(strcmp(tac[j].arg1,hunted)==0 || strcmp(tac[j].arg2,hunted)==0)
{
used=1;
break;
}
}
if(!used)
{
printf("\n\t Removing .. %s",tac[i].seqno);
removeline(i);
i--;
}
}
}
void const_propo()
{
//hunt var1 = const and insted of var1 replece const
for(i=0;i<cnt;i++)
{
if(strcmp(tac[i].op,":=")==0 && strcmp(tac[i].arg2,"-")==0)
{
isnum=1;
for(j=0;j<strlen(tac[i].arg1);j++)
if(!isdigit(tac[i].arg1[j]))
isnum=0;
if(isnum)
{
strcpy(hunted,tac[i].result);
for(k=i+1;k<cnt;k++)
{
if(strcmp(tac[k].arg1,hunted)==0)
strcpy(tac[k].arg1,tac[i].arg1);
if(strcmp(tac[k].arg2,hunted)==0)
strcpy(tac[k].arg2,tac[i].arg1);
}
}
}
}
}
int main()
{
FILE * fin =fopen("tac.txt","r");
int i;
while(!feof(fin))
{
fscanf(fin,"%s%s%s%s%s",tac[cnt].seqno,tac[cnt].op,tac[cnt].arg1,tac[cnt].arg2,tac[cnt].result);
cnt++;
}
cnt--;
printf("\n\t\t*** PURE INPUT ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}
const_propo();
printf("\n\t\t*** After Process ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}
printf("\n\tEnter t0 cont..");
scanf("%d",&i);
eliminate_dead();
printf("\n\t\t*** After Process ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}
fclose(fin);
}
### output #####
./a.out
*** PURE INPUT ****
Index OP Arg1 Arg2 Result
1 := b - c
2 * b c c
3 + b a res
4 - res no1 res
5 := 3 - pi
6 := pi - x
7 * x c res1
*** After Process ****
Index OP Arg1 Arg2 Result
1 := b - c
2 * b c c
3 + b a res
5 := 3 - pi
7 * 3 c res1
optimization techniques: a)common sub-expression elimination b)variable propagation
###### tac.txt #######
1 + b a rep
2 * 2 c a
3 := c - res
4 + b a no1
5 - res no1 res
6 + 3 5 temp
7 := temp - x
8 * x c res1
###### pr_9.c ########
/*
8) WAP to implement following code optimization techniques:
a)common sub-expression elimination b)variable propagation
*/
#include<stdio.h>
struct holder
{
char seqno[3],op[3],arg1[8],arg2[8],result[8];
}tac[50];
int cnt=0,i,j,k,used=0;
char hunted[8];
void removeline()
{
for(k=j;k<=cnt;k++)
tac[k]=tac[k+1];
cnt--;
}
void eliminate()
{
//hunt value which having op arg1 arg2 same jst result different
for(i=0;i<cnt;i++)
{
used=0;
for(j=i+1;j<cnt;j++)
{
if(strcmp(tac[j].result,tac[i].result)==0||strcmp(tac[i].arg1,tac[j].result)==0 || strcmp(tac[i].arg2,tac[j].result)==0)
used=1;
if(strcmp(tac[j].op,tac[i].op)==0 && strcmp(tac[j].arg1,tac[i].arg1)==0 && strcmp(tac[j].arg2,tac[i].arg2)==0 && !used)
{
//remove this line and replace result field by original result ie of i th location
strcpy(hunted,tac[j].result);
for(k=j+1;k<cnt;k++)
{
if(strcmp(tac[k].arg1,hunted)==0)
strcpy(tac[k].arg1,tac[i].result);
if(strcmp(tac[k].arg2,hunted)==0)
strcpy(tac[k].arg2,tac[i].result);
}
removeline();
}
}
}
}
void var_propo()
{
//hunt var1 = var2 and insted of var2 replece var1
for(i=0;i<cnt;i++)
{
if(strcmp(tac[i].op,":=")==0 && strcmp(tac[i].arg2,"-")==0)
{
strcpy(hunted,tac[i].result);
for(k=i+1;k<cnt;k++)
{
if(strcmp(tac[k].arg1,hunted)==0)
strcpy(tac[k].arg1,tac[i].arg1);
if(strcmp(tac[k].arg2,hunted)==0)
strcpy(tac[k].arg2,tac[i].arg1);
}
}
}
}
int main()
{
FILE * fin =fopen("tac.txt","r");
int i;
while(!feof(fin))
{
fscanf(fin,"%s%s%s%s%s",tac[cnt].seqno,tac[cnt].op,tac[cnt].arg1,tac[cnt].arg2,tac[cnt].result);
cnt++;
}
cnt--;
printf("\n\t\t*** PURE INPUT ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}
eliminate();
var_propo();
printf("\n\t\t*** After Process ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}
fclose(fin);
}
read more
1 + b a rep
2 * 2 c a
3 := c - res
4 + b a no1
5 - res no1 res
6 + 3 5 temp
7 := temp - x
8 * x c res1
###### pr_9.c ########
/*
8) WAP to implement following code optimization techniques:
a)common sub-expression elimination b)variable propagation
*/
#include<stdio.h>
struct holder
{
char seqno[3],op[3],arg1[8],arg2[8],result[8];
}tac[50];
int cnt=0,i,j,k,used=0;
char hunted[8];
void removeline()
{
for(k=j;k<=cnt;k++)
tac[k]=tac[k+1];
cnt--;
}
void eliminate()
{
//hunt value which having op arg1 arg2 same jst result different
for(i=0;i<cnt;i++)
{
used=0;
for(j=i+1;j<cnt;j++)
{
if(strcmp(tac[j].result,tac[i].result)==0||strcmp(tac[i].arg1,tac[j].result)==0 || strcmp(tac[i].arg2,tac[j].result)==0)
used=1;
if(strcmp(tac[j].op,tac[i].op)==0 && strcmp(tac[j].arg1,tac[i].arg1)==0 && strcmp(tac[j].arg2,tac[i].arg2)==0 && !used)
{
//remove this line and replace result field by original result ie of i th location
strcpy(hunted,tac[j].result);
for(k=j+1;k<cnt;k++)
{
if(strcmp(tac[k].arg1,hunted)==0)
strcpy(tac[k].arg1,tac[i].result);
if(strcmp(tac[k].arg2,hunted)==0)
strcpy(tac[k].arg2,tac[i].result);
}
removeline();
}
}
}
}
void var_propo()
{
//hunt var1 = var2 and insted of var2 replece var1
for(i=0;i<cnt;i++)
{
if(strcmp(tac[i].op,":=")==0 && strcmp(tac[i].arg2,"-")==0)
{
strcpy(hunted,tac[i].result);
for(k=i+1;k<cnt;k++)
{
if(strcmp(tac[k].arg1,hunted)==0)
strcpy(tac[k].arg1,tac[i].arg1);
if(strcmp(tac[k].arg2,hunted)==0)
strcpy(tac[k].arg2,tac[i].arg1);
}
}
}
}
int main()
{
FILE * fin =fopen("tac.txt","r");
int i;
while(!feof(fin))
{
fscanf(fin,"%s%s%s%s%s",tac[cnt].seqno,tac[cnt].op,tac[cnt].arg1,tac[cnt].arg2,tac[cnt].result);
cnt++;
}
cnt--;
printf("\n\t\t*** PURE INPUT ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}
eliminate();
var_propo();
printf("\n\t\t*** After Process ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}
fclose(fin);
}
##### output #######
*** PURE INPUT ****
Index OP Arg1 Arg2 Result
1 + b a c
2 * 2 c c
3 := c - res
4 + b a no1
5 - res no1 res
6 + 3 5 temp
7 := temp - x
8 * x c res1
*** After Process ****
Index OP Arg1 Arg2 Result
1 + b a c
2 * 2 c c
3 := c - res
5 - c c res
6 + 3 5 temp
7 := temp - x
8 * temp c res1
pr@prashant-HP:~/LEX&YACC/9$
grammar to recognize declarations of variables, assignment statement & if- else statement as per syntax of C and generate equivalent three address code
##### pr.h ########
struct holder
{
char name[8];
char type[6];
}st[30];
read more
struct holder
{
char name[8];
char type[6];
}st[30];
##### pr_8.l ######
%{
#include<stdio.h>
#include "y.tab.h"
#include "pr.h"
char var_type[5];
int var_cnt=0,i;
extern yylval;
%}
type int|float|char
cond1 if
cond2 else
%%
main {return(mn);}
{type} {
strcpy(var_type,yytext);
return(Type);
}
{cond1} {return(IF);}
{cond2} {return(ELSE);}
[a-z]+[a-z0-9]* {
for(i=0;i<var_cnt;i++)
if(strcmp(st[i].name,yytext)==0)
break;
if(i==var_cnt)
{
strcpy(st[var_cnt].name,yytext);
strcpy(st[var_cnt++].type,var_type);
}
yylval=i;
return(var);
}
[0-9]+ {yylval=atoi(yytext);return(num);}
[ \t] {;}
. {return(yytext[0]);}
[\n] {;}
%%
##### pr_8.y #######
/*7) Write an attributed translation grammar to recognize declarations of variables, assignment statement & if- else statement as per syntax of C and generate equivalent three address code for the given input made up of constructs mentioned above using LEX and YACC. Write a code to store the identifiers from the input in a symbol table and also to record other relevant information about the identifiers. Display all records stored in the symbol table.
*/
%{
#include<stdio.h>
#include<stdlib.h>
#include "pr.h"
FILE * yyin;
int total_var=0,temp_cnt=0;
char e2_type[6],e1_type[6],e_type[6];
%}
%token mn var Type num IF ELSE WHILE
%%
edash : prog {printf("\n\t!!!End of programm!!!!\n");}
;
prog : mn '('')''{'mstmt'}' {;}
;
mstmt : stmt mstmt
|
stmt
;
stmt : dstmt';' {/*printf("\n\tValid Declration Statement");*/}
|
exstmt';' {//printf("\n\tValid Expression Statement");
}
|
dstmt {printf("\n\t**** Error--- Line Not Terminated by ';' ");}
|
exstmt {printf("\n\t**** Error--- Line Not Terminated by ';'");}
|
ifelse
|
next';'
;
dstmt : Type varlist
;
varlist : v','varlist
|
v
;
v : var {total_var++;}
|
var'='num { total_var++;
//Target code
printf("\n\t%s:=%d",st[$1].name,$3);
}
;
exstmt : var'='e {
if(strcmp(e1_type,"int")==0)
printf("\n\t%s := %d",st[$1].name,$3);
else
printf("\n\t%s:=T%d",st[$1].name,temp_cnt-1);
}
;
e : e '+' e1 {
//target Code
printf("\n\tT%d:=%s+%s",temp_cnt,st[$1].name,st[$3].name);
temp_cnt++;
}
|
e '-' e1 {
//target Code
printf("\n\tT%d:=%s-%s",temp_cnt,st[$1].name,st[$3].name);
temp_cnt++;
}
|
e1 { strcpy(e_type,e1_type);}
;
e1 : e1 '*' e2 {
//target Code
printf("\n\tT%d:=%s*%s",temp_cnt++,st[$1].name,st[$3].name);
}
|
e1 '/' e2 {
//target Code
printf("\n\tT%d:=%s/%s",temp_cnt++,st[$1].name,st[$3].name);
}
|
e2 {strcpy(e1_type,e2_type);}
;
e2 : var {strcpy(e2_type,st[$1].type);}
|
num { strcpy(e2_type,"int");}
;
next : var'+''+' {printf("\n\t%s=%s+1 ",st[$1].name,st[$1].name);}
|
var '-''-' {printf("\n\t%s=%s-1",st[$1].name,st[$1].name);}
;
ifelse : IF '(' cnd ')' '{' body1 '}' {printf("\nEnd:");}
|
IF '(' cnd ')' '{' body1 '}' ELSE '{' body2 '}' {;}
;
cnd : var '<' var {printf("\n\tIf %s < %s goto next else goto End_IF:\nNext:",st[$1].name,st[$3].name);}
|
var '<' num {printf(" \n\tIf %s < %d goto next else goto End_IF:\nNext:",st[$1].name,$3);}
|
var '>' var {printf(" \n\tIf %s > %s goto next else goto End_IF:\nNext:",st[$1].name,st[$3].name);}
|
var '>' num {printf(" \n\tIf %s > %d goto next else goto End_IF:\nNext:",st[$1].name,$3);}
|
var '<''=' var {printf(" \n\tIf %s <= %s goto next else goto End_IF:\nNext:",st[$1].name,st[$4].name);}
|
var '<''=' num {printf(" \n\tIf %s <= %d goto next else goto End_IF:\nNext:",st[$1].name,$4);}
|
var '>''=' var {printf(" \n\tIf %s >= %s goto next else goto End_IF:\nNext:",st[$1].name,st[$4].name);}
|
var '>''=' num {printf(" \n\tIf %s >= %d goto next else goto End_IF:\nNext:",st[$1].name,$4);}
|
var '!''=' var {printf(" \n\tIf %s != %s goto next else goto End_IF:\nNext:",st[$1].name,st[$4].name);}
|
var '!''=' num {printf(" \n\tIf %s != %d goto next else goto End_IF:\nNext:",st[$1].name,$4);}
|
var '=''=' var {printf(" \n\tIf %s <= %s goto next else goto End_IF:\nNext:",st[$1].name,st[$4].name);}
|
var '=''=' num {printf(" \n\tIf %s <= %d goto next else goto End_IF:\nNext:",st[$1].name,$4);}
;
body1 : mstmt {printf("\n\tGoto End \nEnd_IF:\n");}
;
body2 : mstmt {printf("\nEnd");}
;
%%
int main()
{
int i;
yyin=fopen("ip.c","r");
printf("\n\t***** SEE 3 ADDR code **** ");
yyparse();
printf("\n\t++++Now you want symbal table right??? Then SEE...++++");
for(i=0;i<total_var;i++)
{
printf("\n\t%s\t%s",st[i].name,st[i].type);
}
return(0);
}
void yyerror(char *c)
{
fprintf(stderr,"%s\n",c);
}
####### ip.c ######
main ( )
{
float a=0,b=4,c=5;
int no1 = 0,no2=0;
a=b+c;
no1=no2-a;
if(a<10)
{
c=b+c;
a++;
}
}
grammar to recognize declarations of variables, assignment statement & “while” statement as per syntax of C and generate equivalent three address code
##### pr.h ######
struct holder
{
char name[8];
char type[6];
}st[30];
####### pr_7.l #######
%{
#include<stdio.h>
#include "y.tab.h"
#include "pr.h"
char var_type[5];
int var_cnt=0,i;
extern yylval;
%}
type int|float|char
%%
main {return(mn);}
{type} {
strcpy(var_type,yytext);
return(Type);
}
while {return(WHILE);}
[a-z]+[a-z0-9]* {
for(i=0;i<var_cnt;i++)
if(strcmp(st[i].name,yytext)==0)
break;
if(i==var_cnt)
{
strcpy(st[var_cnt].name,yytext);
strcpy(st[var_cnt++].type,var_type);
}
yylval=i;
return(var);
}
[0-9]+ {yylval=atoi(yytext);return(num);}
[ \t] {;}
. {return(yytext[0]);}
[\n] {;}
%%
######## pr_7.y ##########
/*
6) Write an attributed translation grammar to recognize declarations of variables, assignment statement & “while” statement as per syntax of C and generate equivalent three address code for the given input made up of constructs mentioned above using LEX and YACC. Write a code to store the identifiers from the input in a symbol table and also to record other relevant information about the identifiers. Display all records stored in the symbol table.
*/
%{
#include<stdio.h>
#include<stdlib.h>
#include "pr.h"
FILE * yyin;
int total_var=0,temp_cnt=0;
char e2_type[6],e1_type[6],e_type[6];
%}
%token mn var Type num WHILE
%%
edash : prog {printf("\n\t!!!End of programm!!!!\n");}
;
prog : mn '('')''{'mstmt'}' {;}
;
mstmt : stmt mstmt
|
stmt
;
stmt : dstmt';' {/*printf("\n\tValid Declration Statement");*/}
|
exstmt';' {//printf("\n\tValid Expression Statement");
}
|
dstmt {printf("\n\t**** Error--- Line Not Terminated by ';' ");}
|
exstmt {printf("\n\t**** Error--- Line Not Terminated by ';'");}
|
whileloop
|
next';'
;
dstmt : Type varlist
;
varlist : v','varlist
|
v
;
v : var {total_var++;}
|
var'='num { total_var++;
//Target code
printf("\n\t%s:=%d",st[$1].name,$3);
}
;
exstmt : var'='e {
if(strcmp(e1_type,"int")==0)
printf("\n\t%s := %d",st[$1].name,$3);
else
printf("\n\t%s:=T%d",st[$1].name,temp_cnt-1);
}
;
e : e '+' e1 {
//target Code
printf("\n\tT%d:=%s+%s",temp_cnt,st[$1].name,st[$3].name);
temp_cnt++;
}
|
e '-' e1 {
//target Code
printf("\n\tT%d:=%s-%s",temp_cnt,st[$1].name,st[$3].name);
temp_cnt++;
}
|
e1 { strcpy(e_type,e1_type);}
;
e1 : e1 '*' e2 {
//target Code
printf("\n\tT%d:=%s*%s",temp_cnt++,st[$1].name,st[$3].name);
}
|
e1 '/' e2 {
//target Code
printf("\n\tT%d:=%s/%s",temp_cnt++,st[$1].name,st[$3].name);
}
|
e2 {strcpy(e1_type,e2_type);}
;
e2 : var {strcpy(e2_type,st[$1].type);}
|
num { strcpy(e2_type,"int");}
;
next : var'+''+' {printf("\n\t%s=%s+1 ",st[$1].name,st[$1].name);}
|
var '-''-' {printf("\n\t%s=%s-1",st[$1].name,st[$1].name);}
;
whileloop : WHILE '(' cnd ')' '{' body '}' {printf("\nEnd : ");}
;
cnd : var '<' var {printf("\nStart:\n\tIf %s < %s goto next else goto End\nNext:",st[$1].name,st[$3].name);}
|
var '<' num {printf("\nStart:\n\tIf %s < %d goto next else goto End\nNext:",st[$1].name,$3);}
|
var '>' var {printf("\nStart:\n\tIf %s > %s goto next else goto End\nNext:",st[$1].name,st[$3].name);}
|
var '>' num {printf("\nStart:\n\tIf %s > %d goto next else goto End\nNext:",st[$1].name,$3);}
|
var '<''=' var {printf("\nStart:\n\tIf %s <= %s goto next else goto End\nNext:",st[$1].name,st[$4].name);}
|
var '<''=' num {printf("\nStart:\n\tIf %s <= %d goto next else goto End\nNext:",st[$1].name,$4);}
|
var '>''=' var {printf("\nStart:\n\tIf %s >= %s goto next else goto End\nNext:",st[$1].name,st[$4].name);}
|
var '>''=' num {printf("\nStart:\n\tIf %s >= %d goto next else goto End\nNext:",st[$1].name,$4);}
;
body : mstmt {printf("\n\tgoto Start");}
;
%%
int main()
{
int i;
yyin=fopen("ip.c","r");
printf("\n\t***** SEE 3 ADDR code **** ");
yyparse();
printf("\n\t++++Now you want symbal table right??? Then SEE...++++");
for(i=0;i<total_var;i++)
{
printf("\n\t%s\t%s",st[i].name,st[i].type);
}
return(0);
}
void yyerror(char *c)
{
fprintf(stderr,"%s\n",c);
}
read more
struct holder
{
char name[8];
char type[6];
}st[30];
####### pr_7.l #######
%{
#include<stdio.h>
#include "y.tab.h"
#include "pr.h"
char var_type[5];
int var_cnt=0,i;
extern yylval;
%}
type int|float|char
%%
main {return(mn);}
{type} {
strcpy(var_type,yytext);
return(Type);
}
while {return(WHILE);}
[a-z]+[a-z0-9]* {
for(i=0;i<var_cnt;i++)
if(strcmp(st[i].name,yytext)==0)
break;
if(i==var_cnt)
{
strcpy(st[var_cnt].name,yytext);
strcpy(st[var_cnt++].type,var_type);
}
yylval=i;
return(var);
}
[0-9]+ {yylval=atoi(yytext);return(num);}
[ \t] {;}
. {return(yytext[0]);}
[\n] {;}
%%
######## pr_7.y ##########
/*
6) Write an attributed translation grammar to recognize declarations of variables, assignment statement & “while” statement as per syntax of C and generate equivalent three address code for the given input made up of constructs mentioned above using LEX and YACC. Write a code to store the identifiers from the input in a symbol table and also to record other relevant information about the identifiers. Display all records stored in the symbol table.
*/
%{
#include<stdio.h>
#include<stdlib.h>
#include "pr.h"
FILE * yyin;
int total_var=0,temp_cnt=0;
char e2_type[6],e1_type[6],e_type[6];
%}
%token mn var Type num WHILE
%%
edash : prog {printf("\n\t!!!End of programm!!!!\n");}
;
prog : mn '('')''{'mstmt'}' {;}
;
mstmt : stmt mstmt
|
stmt
;
stmt : dstmt';' {/*printf("\n\tValid Declration Statement");*/}
|
exstmt';' {//printf("\n\tValid Expression Statement");
}
|
dstmt {printf("\n\t**** Error--- Line Not Terminated by ';' ");}
|
exstmt {printf("\n\t**** Error--- Line Not Terminated by ';'");}
|
whileloop
|
next';'
;
dstmt : Type varlist
;
varlist : v','varlist
|
v
;
v : var {total_var++;}
|
var'='num { total_var++;
//Target code
printf("\n\t%s:=%d",st[$1].name,$3);
}
;
exstmt : var'='e {
if(strcmp(e1_type,"int")==0)
printf("\n\t%s := %d",st[$1].name,$3);
else
printf("\n\t%s:=T%d",st[$1].name,temp_cnt-1);
}
;
e : e '+' e1 {
//target Code
printf("\n\tT%d:=%s+%s",temp_cnt,st[$1].name,st[$3].name);
temp_cnt++;
}
|
e '-' e1 {
//target Code
printf("\n\tT%d:=%s-%s",temp_cnt,st[$1].name,st[$3].name);
temp_cnt++;
}
|
e1 { strcpy(e_type,e1_type);}
;
e1 : e1 '*' e2 {
//target Code
printf("\n\tT%d:=%s*%s",temp_cnt++,st[$1].name,st[$3].name);
}
|
e1 '/' e2 {
//target Code
printf("\n\tT%d:=%s/%s",temp_cnt++,st[$1].name,st[$3].name);
}
|
e2 {strcpy(e1_type,e2_type);}
;
e2 : var {strcpy(e2_type,st[$1].type);}
|
num { strcpy(e2_type,"int");}
;
next : var'+''+' {printf("\n\t%s=%s+1 ",st[$1].name,st[$1].name);}
|
var '-''-' {printf("\n\t%s=%s-1",st[$1].name,st[$1].name);}
;
whileloop : WHILE '(' cnd ')' '{' body '}' {printf("\nEnd : ");}
;
cnd : var '<' var {printf("\nStart:\n\tIf %s < %s goto next else goto End\nNext:",st[$1].name,st[$3].name);}
|
var '<' num {printf("\nStart:\n\tIf %s < %d goto next else goto End\nNext:",st[$1].name,$3);}
|
var '>' var {printf("\nStart:\n\tIf %s > %s goto next else goto End\nNext:",st[$1].name,st[$3].name);}
|
var '>' num {printf("\nStart:\n\tIf %s > %d goto next else goto End\nNext:",st[$1].name,$3);}
|
var '<''=' var {printf("\nStart:\n\tIf %s <= %s goto next else goto End\nNext:",st[$1].name,st[$4].name);}
|
var '<''=' num {printf("\nStart:\n\tIf %s <= %d goto next else goto End\nNext:",st[$1].name,$4);}
|
var '>''=' var {printf("\nStart:\n\tIf %s >= %s goto next else goto End\nNext:",st[$1].name,st[$4].name);}
|
var '>''=' num {printf("\nStart:\n\tIf %s >= %d goto next else goto End\nNext:",st[$1].name,$4);}
;
body : mstmt {printf("\n\tgoto Start");}
;
%%
int main()
{
int i;
yyin=fopen("ip.c","r");
printf("\n\t***** SEE 3 ADDR code **** ");
yyparse();
printf("\n\t++++Now you want symbal table right??? Then SEE...++++");
for(i=0;i<total_var;i++)
{
printf("\n\t%s\t%s",st[i].name,st[i].type);
}
return(0);
}
void yyerror(char *c)
{
fprintf(stderr,"%s\n",c);
}
####### ip.c ########
main ( )
{
float a=0,b=4,c=5;
int no1 = 0,no2=0;
a=b+c;
no1=no2-a;
while(a<10)
{
c=b+c;
a++;
}
}
Subscribe to:
Posts (Atom)
