2127210501090

IMPLEMENTATION OF CONTROL FLOW ANAL

YSIS Type your te
EX.NO:
DATE:

Aim:

To implement control flow analysis using LEX.

Algorithm:
1. Start.
2. Make the first line instruction, instruction with labels, branch instructions as individ nodes.
3. Print the individual blocks along with the line numbers.
4. Construct the control flow graph.
5. Print the blocks, graph and the exit block for the given . ode.
6. Stop.

Source Code:

cfa.l:
%option noyywrap
%{
#include<stdio.h>
#include<string.h>

void addblock(char *);

void append_code(char *);
int lnc=1,bno=1,prev=0;
char str[500]="",lineno[500]="",t[5];

struct graph{
char code[500];
}blarr[1000];
%}
space [ \t]
rop ">"|"<"|"=="|"<="|">="|"<>"
aop "+"|"-"|"*"|"/"|"%"
asignop "="
digit [0-9]
num {digit}+
letter [a-zA-Z]
iden {letter}({letter}|{digit})*

53
 2127210501090

exp ({iden}|{num}){space}*({aop}{space}*({iden}|{num}))?
aexp {iden}{space}*{asignop}{space}*{exp}
rexp {iden}{space}*{rop}{space}*({iden}|{num})
%%
{aexp} {append_code(yytext);prev=0;}
"if "{rexp}(" goto L"{digit}+) {addblock(yytext);}
L{digit}+:.+ {
if(strcmp(str,"")!=0)
{
printf("Block No:%d\tLine no's:%s\n",bno,lineno);
strcpy(blarr[bno].code,str);
}
if(prev==0)
bno++;
strcpy(str,yytext);
sprintf(t,"%d,",lnc);
strcpy(lineno,t);
}
("goto L"{digit}+) {addblock(yytext);}
\n {lnc++;;}
{space}* ;
. ;
%%
void main()
{
int i,j,count;
int blgraph[200][200]={0};
char *substr,*s;
yyin=fopen("cfain.txt","r");
yylex();
for(i=1;i<bno;i++)
{
if((substr=strstr(blarr[i].code,"goto"))==NULL)
blgraph[i][i+1]=1;
else if(((substr=strstr(blarr[i].code,"goto"))!=NULL) && ((s=strstr(blarr[i].code,"if"))!=NULL))
blgraph[i][i+1]=1;
if((substr=strstr(blarr[i].code,"goto"))!=NULL)
{
s=strdup(substr+5);
strcat(s,":");
for(j=1;j<bno;j++)
if(strstr(blarr[j].code,s)!=NULL)
blgraph[i][j]=1;
}

54
 2127210501090

}
printf("\nThe Control Flow Graph for the given code is:\n");
printf("Block");
for(i=1;i<bno;i++)
printf("\t%d",i);
for(i=1;i<bno;i++)
{
printf("\n%d",i);
for(j=1;j<bno;j++)
printf("\t%d",blgraph[i][j]);
}
printf("\nThe Exit block(s):");
for(i=2;i<bno;i++)
{
count=0;
for(j=1;j<bno;j++)
count=count+blgraph[i][j];
if(count==0)
printf("B%d",i);
}
printf("\n");
}
void addblock(char *s)
{
append_code(s);
printf("Block No:%d\tLine no's:%s\n",bno,lineno);
strcpy(blarr[bno].code,str);
strcpy(str,"");
strcpy(lineno,"");
bno++;
prev=1;
}
void append_code(char *s)
{
strcat(str,s);
sprintf(t,"%d,",lnc);
strcat(lineno,t);
}

Input:
cfain.txt:
a=1
b=2
L0: c = a + b

55
 2127210501090

d=c-a
if c < d goto L2
L1: d = b + d
if d < 1 goto L3
L2: b = a + b
e=c a
if e == 0 goto L0
a=b+d
b=a d
goto L4
L3: d = a + b
e=e+1
goto L1
L4: return

Sample Output:
Block No:1 Line no's:1,2,
Block No:2 Line no's:3,4,5,
Block No:3 Line no's:6,7,
Block No:4 Line no's:8,9,10,
Block No:5 Line no's:11,12,13,
Block No:6 Line no's:14,15,16,

The Control Flow Graph for the given code is:

Block 1 2 3 4 5 6
1 0 1 0 0 0 0
2 0 0 1 1 0 0
3 0 0 0 1 0 1
4 0 1 0 0 1 0
5 0 0 0 0 0 0
6 0 0 1 0 0 0

The Exit block(s):B5

Result:
Thus the program for control flow analysis has been compiled and executed successfully.

56
 2127210501090

EX NO: 10 IMPLEMENTATION OF DATA FLOW ANALYSIS

DATE:

AIM:
To write a C program to implement data flow analysis.

ALGORITHM:

1. START.
2. Get the number of statements and the statements.
3. For the first read statement tokenize definition and expression, store the expression value in

av[0] and initialize kill [0] to null.

4. for the next statements, tokenize definition and expression. (i) Check if the definition is a part of av[i-1] or a part of
expression,if so add av[i-1] to kill.
0 (ii) Check if expression is not a part of definition, check if it has been killed already then make
1 (iii) If expression is part of definition, check if it has been killed already then make kill null
2

kill null else add to kill[i].

else add to kill[i].
5. Repeat 5 till all statements are processed.
6. Display statements, available statement and kill.
7. STOP

SOURCE CODE:

#include<stdio.h>
#include<string.h>
struct block
{
char l[5];
char r[20];
}b[10];

struct result
{
char res[10];
}r[10];

int check(int val, int ind)

{
int i, len;
len = strlen(r[ind].res);
for(i=0;i<len;i+=2)
{
if(r[ind].res[i] == val)
return 0;
}

49
 2127210501090

return 1;
}
void main()
{
int n, i, j, k, len;
printf("Enter no of values :: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nLeft :: ");
scanf("%s",b[i].l);
printf("Right :: ");
scanf("%s",b[i].r);
}

printf("\nCode :: \n");
for(i=0;i<n-1;i++)
{
printf("\t%s = ",b[i].l);
printf("%s\n",b[i].r);
}
printf("\treturn %s",b[i].r);

//split
r[n-1].res[0] = b[i].r[0];
for(i=n-2;i>=0;i--)
{
k=0;
len = strlen(b[i].r);
for(j=0;j<len;j+=2)
{
if(check(b[i].r[j], i))
{
r[i].res[k++] = b[i].r[j];
r[i].res[k++] = ',';
}
}

//k = j;
len = strlen(r[i+1].res);
for(j=0;j<len;j+=2)
{
if(b[i].l[0] != r[i+1].res[j])
{
if(check(r[i+1].res[j], i))
{
r[i].res[k++] = r[i+1].res[j];
r[i].res[k++] = ',';
}
}
}

50
 2127210501090

r[i].res[k-1] = '\0';
//printf("\n%s", r[i].res);
}
printf("\n\nData flow - Liveliness Analysis :: \n");
for(i=0;i<n-1;i++)
{
len = strlen(r[i].res);
if(len == 1 && (r[i].res[0] >= '0' && r[i].res[0] < '9'))
printf("\n\t%s = %s\t\t--", b[i].l, b[i].r);
else
printf("\n\t%s = %s\t\t%s", b[i].l, b[i].r, r[i].res);
}
printf("\n\t%s %s\t\t%s", b[i].l, b[i].r, r[i].res);
}

51
 2127210501090

OUTPUT:

Enter no of values :: 6
Left :: a
Right :: 7

Left :: b
Right :: a+a

Left :: c
Right :: b+a

Left :: d
Right :: a+b

Left :: e
Right :: d+c

Left :: return
Right :: e

Code:
a=1
b = a+a
c = b+a
d = a+b
e = d+c
return e

Data flow - Liveliness Analysis ::

a=1 --
b = a+a a
c = b+a b,a
d = a+b a,b,c
e = d+c d,c
return e e

RESULT:

Thus a program to implement data flow analysis have been written and executed successfully.

52
EX.NO:12 IMPLEMENTATION OF DIRECTED ACYCLIC GRAPH
DATE:

Aim:
To implement directed acyclic graph using LEX and YACC.

Algorithm:
Lex.l:
1. Start.

2. Add the option noyywrap in the definition section.

3. Include the header files in the definition section.

4. In the rule section create the Regular expression along their actions to tokenize the string from the
program file.

5. Stop

Yacc.y:
1. Start.

2. Include the header file and also the tokens that are returned by the LEX and also give precedence to
the operators. 2127210501057

3. In the rule section write a grammar to find the index, left and right nodes of the current node in the
expression.

4. Then print the DAG as a table with index, right and left nodes with the current node.

5. Call yyparse() to get more tokens from the LEX.

6. Define a yyerror() function to display a error message if the token is invalid.

7. Also have addsym() to add symbols and addop() to add operators.

8. Stop

Source Code:

dag.l
%option noyywrap
%{
#include "y.tab.h"

57
 2127210501090

extern YYSTYPE yylval;

%}
%%
[_a-zA-Z][a-zA-Z0-9]* {yylval.name=strdup(yytext);return id;}
[0-9]+ {yylval.name=strdup(yytext);return num;}
[ \t]* {}
[\n] {return 0;}
. {return yytext[0];}
%%

dag.y
%{
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
struct DAG
{
char *sym;
int left,right;
}table[100];
char subexp[20][20];
int sub_exp_tbl_idx[20];
int tbl_entry=0,idx,sub_exp_count=0;
int search(char *);
int issubexp(char *);
int search_subexp(char *);
void add_subexp(char *);
%}
%union{char *name;}
%token <name> num id
%type <name> e start
%left '+' '-'
%left '*' '/'
%right '='
%%
start : id '=' e {
idx = search($1);
if(idx == -1)
addsym($1,45,45);
if(issubexp($3))

58
 2127210501090

addsym("=",search($1),search_subexp($3));
else
addsym("=",search($1),search($3));
}
| e {}
;
e : e '+' e {$$ = strdup($1); strcat($$,"+"); strcat($$,$3); addop("+",$1,$3,$$);}
| e '*' e {$$ = strdup($1); strcat($$,"*"); strcat($$,$3); addop("*",$1,$3,$$);}
| e '-' e {$$ = strdup($1); strcat($$,"-"); strcat($$,$3); addop("-",$1,$3,$$);}
| e '/' e {$$ = strdup($1); strcat($$,"/"); strcat($$,$3); addop("/",$1,$3,$$);}
| '(' e ')' {$$ = strdup($2);}
| id {
idx = search($1);
if(idx == -1)
addsym($1,45,45);
}
| num {
idx = search($1);
if(idx == -1)
addsym($1,45,45);
}
;
%%
int yyerror()
{
printf("\nInvalid expr!!");
return 0;
}
main()
{
int i;
printf("\nEnter an expr:");
yyparse();
printf("\nDAG for the given expr is:");
printf("\n------------------------------");
printf("\nIndex\tNode\tLeft\tRight");
printf("\n-------- ----------------------\n");
for(i=0;i<tbl_entry;i++)
{
if(isalnum(table[i].sym[0]))
printf("%d\t%s\t%c\t%c\n",i,table[i].sym,table[i].left,table[i].right);

59
 2127210501090

else
printf("%d\t%s\t%d\t%d\n",i,table[i].sym,table[i].left,table[i].right);
}
}
int search(char *sym)
{
int i;
for(i=0;i<tbl_entry;i++)
if(strcmp(table[i].sym,sym)==0)
return i;
return -1;
}
void addsym(char *sym, int l, int r)
{
table[tbl_entry].sym=strdup(sym);
table[tbl_entry].left = l;
table[tbl_entry].right = r;
tbl_entry++;
}
void addop(char *sym, char *l, char *r, char *exp)
{
int l_index,r_index;

if(!issubexp(l) && !issubexp(r))

{
if(search_subexp(exp)==-1)
{
addsym(sym,search(l),search(r));
add_subexp(exp);
}
}
else
{
if(issubexp(l))
l_index = search_subexp(l);
else
l_index = search(l);
if(issubexp(r))
r_index = search_subexp(r);
else
r_index = search(r);

60
 2127210501090

addsym(sym,l_index,r_index);
add_subexp(exp);
}
}
int search_subexp(char *exp)
{
int i;
for(i=0;i<sub_exp_count;i++)
{
if(strcmp(subexp[i],exp)==0)
return sub_exp_tbl_idx[i];
}
return -1;
}
int issubexp(char *exp)
{
int i,len=strlen(exp);
for(i=0;i<len;i++)
if(exp[i]=='+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/')
return 1;
return 0;
}
void add_subexp(char *exp)
{
strcat(subexp[sub_exp_count],exp);
sub_exp_tbl_idx[sub_exp_count] = tbl_entry - 1;
sub_exp_count++;
}

Sample Output:

Enter an expr:(a+b)*(a+b)

DAG for the given expr is:

------------------------------
Index Node Left Right
-------- ----------------------

61
 2127210501090

0 a - -
1 b - -
2 + 0 1
3 * 2 2

Enter an expr:(a+b)*(a-b)

DAG for the given expr is:

------------------------------
Index Node Left Right
-------- ----------------------
0 a - -
1 b - -
2 + 0 1
3 - 0 1
4 * 2 3

Result:
Thus the program for directed acyclic graph has been compiled and executed successfully.

62
 2127210501090

EX. NO : 13 IMPLEMENTATION OF CODE GENERATION

DATE:

AIM:

To implement code generation using LEX and YACC.

ALGORITHM:

Lex.l:

1. Start.
2. Add the option noyywrap and yylval as extern variable in the definition section.
3. Include the header files in the definition section.
4. In the rule section create the Regular expression along their actions to tokenize the string from the
program file.
5. Stop

Yacc.y:

1. Start.
2. Include the header file and also the tokens that are returned by the LEX and also give precedence to
the operators.
3. In the rule section write a grammar to generate the assembly code.
4. Call yyparse() to get more tokens from the LEX.
5. Define a yyerror() function to display a error message if the token is invalid.
6. Also have swapreg() to add symbols and inc_timer() and other required functions.
7. Stop.

63
 2127210501090

SOURCE CODE:

codegen.l:
%option noyywrap
%{
#include "y.tab.h"
extern YYSTYPE yylval;
%}
%%
[a-z][a-z]* {yylval.str=strdup(yytext);return id;}
[1-9][0-9]* {yylval.str=strdup(yytext);return num;}
[ \t]* {}
[=+-/*\n] {return *yytext;}
. {}
%%

codegen.y:
%{
#include<stdio.h>
#include<string.h>
char* getreg(char *);
void clr(char *);
void mk_instr(char*, char*, char*);
char *code;
enum reg {AX,BX,CX,DX};
char regname[4][3]={"AX","BX","CX","DX"};
char regcont[4][100] = {"$","$","$","$"};
char * swapreg_content(char*);
int regcont_timer[4]={0,0,0,0};
int yylex();
extern FILE *yyin;
%}
%union {char *str;}
%left '+' '-'
%left '*' '/'
%right '='
%type <str> e start line
%token <str> id num
%%
start : line '\n' {printf("\n");inc_timer();}
| start line '\n' {printf("\n");inc_timer();}

64
 2127210501090

;
line : id '=' e {printf("\nMOV %s,%s",$1,$3);clr($3);}
;
e : e '+' e {mk_instr("ADD ",$1,$3);}
| e '-' e {mk_instr("SUB ",$1,$3);}
| e '*' e {mk_instr("MUL ",$1,$3);}
| e '/' e {mk_instr("DIV ",$1,$3);}
| id {$$=getreg($1);}
| num {$$=strdup($1);strcat($$,"H");}
;
%%
void main()
{
yyin = fopen("intrcode.txt","r");
yyparse();
fclose(yyin);
}
char* getreg(char *iden)
{
int i,result=regchk(iden);
char *temp;
if(result==-1)
{
for(i=0;i<4;i++)
if(strcmp(regcont[i],"$")==0)
break;
if(i>4)
{
temp = swapreg_content(iden);
printf("\nMOV %s,%s",temp,iden);
return temp;
}
else
{
strcpy(regcont[i],iden);
printf("\nMOV %s,%s",regname[i],iden);
result = i;
}
}
return regname[result];
}

65
 2127210501090

void mk_instr(char *instr, char *op1, char *op2)

{
char *code;
code = strdup(instr);
strcat(code,op1);
strcat(code,",");
strcat(code,op2);
printf("\n%s",code);
}
void clr(char *reg)
{
int i;
for(i=0;i<4;i++)
{
if(strcmp(regname[i],reg)==0)
{
strcpy(regcont[i],"$");
regcont_timer[i] = 0;
break;
}
}
}
int yyerror(char *str)
{
printf("%s",str);
return -1;
}
int regchk(char *iden)
{
int i;
for(i=0;i<4;i++)
{
if(strcmp(regcont[i],iden)==0)
return i;
}
return -1;
}
void inc_timer(void)
{
int i=0;
while(i)

66
 2127210501090

{
regcont_timer[i]++;
i++;
}
}
char* swapreg_content(char *iden)
{
int i,max=0;
for(i=1;i<4;i++)
{
if(max<regcont_timer[i])
max = i;
}
printf("MOV %s,%s",regcont[max],regname[max]);
regcont_timer[max] = 0;
return regname[max];
}

SAMPLE INPUT:

intrcode.txt :

a=b+c
x=2
a=a*x
d = b *10
y = d/c
y = e -5

SAMPLE OUTPUT:

MOV AX,b
MOV BX,c
ADD AX,BX
MOV a,AX

MOV x,2H

MOV AX,a
MOV CX,x
MUL AX,CX

67
 2127210501090

MOV a,AX

MOV AX,b
MUL AX,10H
MOV d,AX

MOV AX,d
DIV AX,BX
MOV y,AX

MOV AX,e
SUB AX,5H
MOV y,AX

RESULT:

Thus the program for intermediate code generation has been compiled and executed successfully.

68
 2127210501090

EX NO. : 14 IMPLEMENTATION OF CODE OPTIMISATION

DATE :

AIM:-
To write a C program to implement the code generation algorithm.

ALGORITHM:-

1. Start.
2. Invoke a function getreg to determine the location L where the result of the computation y op z should be stored. L
will usually be a register, but it could also be a memory location. We shall describe getreg shortly.
3. Consult the address descriptor for y to determine y, (one of) the current location(s) of y. Prefer the register for y if the
value of y is currently both in memory and a register. If the value of y is not already in l, generate the instruction MOV
y, L to place a copy of y in L.
4. Generate the instruction op z, L where z is a current location of z. Again, prefer a register to a memory location if z is
in both. Update the address descriptor of x to indicate that x is in location L. If L is a register, update its descriptor to
indicate that it contains the value of x, and remove x from all other register descriptors.
5. If the current values of y and/or z have no next users, are not live on exit from the block, and are in register descriptor
to indicate that, after execution of x:=y op z, those registers no longer will contain y and/or z, respectively.
6. Stop.

PROGRAM:-

#include<stdio.h>
#include<string.h>
struct op
{
char l[5];
char r[20];
}op[10], pr[10];
void main()
{
int n, i, j, k=0, m, a, b;
char temp[10], t[10], *p, *q;
printf("Enter no of values :: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nLeft :: ");
scanf("%s",op[i].l);
printf("Right :: ");
scanf("%s",op[i].r);
}

printf("\nIntermediate Code :: \n");

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

69
 2127210501090

{
printf("\t%s = ",op[i].l);
printf("%s\n",op[i].r);
}

for(i=0;i<n-1;i++)
{
strcpy(temp, op[i].l);
for(j=0;j<n;j++)
{
p = strstr(op[j].r, temp);
if(p)
{
strcpy(pr[k].l, op[i].l);
strcpy(pr[k].r, op[i].r);
k++;
}
}
}
strcpy(pr[k].l, op[n-1].l);
strcpy(pr[k].r, op[n-1].r);
k++;

printf("\nAfter dead code elimination :: \n");

for(i=0;i<k;i++)
{
printf("\t%s = ",pr[i].l);
printf("%s\n",pr[i].r);
}

for(i=0;i<k;i++)
{
strcpy(temp,pr[i].r);
for(j=i+1;j<k;j++)
{
p = strstr(temp, pr[j].r);
if(p)
{
strcpy(t, pr[j].l);
strcpy(pr[j].l, pr[i].l);
for(m=0;m<k;m++)
{
q = strstr(pr[m].r,t);
if(q)
{
a = q-pr[m].r;
pr[m].r[a] = pr[i].l[0];

70
 2127210501090

}
}
}
}
}

printf("\nAfter common sub expression elimination :: \n");

for(i=0;i<k;i++)
{
printf("\t%s = ",pr[i].l);
printf("%s\n",pr[i].r);
}

//duplicate production elimination

for(i=0;i<k;i++)
{
for(j=i+1;j<k;j++)
{
a=strcmp(pr[i].l,pr[j].l);
b=strcmp(pr[i].r,pr[j].r);
if(!a&&!b)
{
strcpy(pr[i].l,"\0");
strcpy(pr[i].r,"\0");
}
}
}

printf("\nOptimized code ::\n");

for(i=0;i<k;i++)
{
if((strcmp(pr[i].l,"\0")) != 0)
{
printf("\t%s = ",pr[i].l);
printf("%s\n",pr[i].r);
}
}
}

OUTPUT :
Enter no of values :: 5
Left :: a
Right :: 7

Left :: b

71
 2127210501090

Right :: c+d

Left :: e
Right :: c+d

Left :: f
Right :: b+e

Left :: r
Right :: f

Intermediate Code ::
a=7
b = c+d
e = c+d
f = b+e
r=f

After dead code elimination ::

b = c+d
e = c+d
f = b+e
r=f
After common sub expression elimination ::
b = c+d
b = c+d
f = b+b
r=f

Optimized code ::
b = c+d
f = b+b
r=f

RESULT :

Thus the program for code optimization is executed successfully and implemented.

72