DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

INTRODUCTION TO COMPILER DESIGN LAB

Every software has to be translated to its equivalent machine instruction form so that it will
be executed by the underlying machine. There are many different types of system softwares
that help during this translation process. Compiler is one such an important System Software
that converts High level language programs to its equivalent machine (low level) language. It
is impossible to learn and use machine language in software development for the users.
Therefore we use high level computer languages to write programs and then convert such
programs into machine understandable form with the help of mediator softwares such as
compilers, interpreters, assemblers etc. Thus compiler bridges the gap between the user and
the machine, i.e., computer.
To build compiler software we must understand the principles, tools, and techniques used in
its working. The compiler goes through the following sequence of steps called phases of a
compiler.
1) Lexical Analysis
2) Syntax Analysis
3) Semantic Analysis
4) Intermediate Code Generation
5) Code Optimization
6) Code Generation.
The objective of the Compiler Design Laboratory is to understand and implement the
principles, techniques, and also available tools used in compiler construction process. This
will enable the students to work in the development phase of new computer languages in
industry.

CS431- COMPILER DESIGN LAB Page 1 LAB MANUAL

 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 1: Lexical analyzer for given language using C.

Aim
Write a C program to design a Lexical analyzer to recognize the tokens defined by the given
grammar.

Algorithm
1) Start
2) Declare an array of characters, an input file to store the input;
3) Read the character from the input file and put it into character type of variable, say
‘c’.
4) If ‘c’ is blank then do nothing.
5) If ‘c’ is new line character line=line+1.
6) If ‘c’ is digit, set token Val, the value assigned for a digit and return the ‘NUMBER’.
7) If ‘c’ is proper token then assign the token value.
8) Print the complete table with
9) Token entered by the user,
10) Associated token value.
11) Stop

Program
#include<string.h>
#include<conio.h>
#include<ctype.h>
#include<stdio.h>
void main()
{
FILE *f1;
char c,str[10];
int lineno=1,num=0,i=0;
clrscr();
printf("\nEnter the c program\n");
f1=fopen("input.txt","w");
while((c=getchar())!=EOF)
putc(c,f1);
fclose(f1);
f1=fopen("input.txt","r");
while((c=getc(f1))!=EOF)
{
if(isdigit(c))
{
num=c-48;
c=getc(f1);
while(isdigit(c))
{
num=num*10+(c-48);
c=getc(f1);
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 2
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

}
printf("%d is a number \n",num);
ungetc(c,f1);
}
else if(isalpha(c))
{
str[i++]=c;
c=getc(f1);
while(isdigit(c)||isalpha(c)||c=='_'||c=='$')
{
str[i++]=c;
c=getc(f1);
}
str[i++]='\0';
if(strcmp("for",str)==0||strcmp("while",str)==0||strcmp("do",str)==0||
strcmp("int",str)==0||strcmp("float",str)==0||strcmp("char",str)==0||
strcmp("double",str)==0||strcmp("static",str)==0||
strcmp("switch",str)==0||strcmp("case",str)==0)
printf("%s is a keyword\n",str);
else
printf("%s is a identifier\n",str);
ungetc(c,f1);
i=0;
}
else if(c==' '||c=='\t')
printf("\n");
else if(c=='\n')
lineno++;
else
printf("%c is a special symbol\n",c);
}
printf("Total no. of lines are: %d\n",lineno);
fclose(f1);
getch();
}

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 3
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

OUTPUT

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 4
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 2: Recursive descent parser for an expression

Aim
To Implement the Recursive Descent Parser for the given grammar / language

Algorithm
1) Start.
2) Read the input string.
3) Write procedures for the non terminals
4) Verify the next token equals to non terminals if it satisfies match the non terminal.
5) If the input string does match print string accepted.
6) Else print string not accepted.
7) Stop.

Program
#include<stdio.h>
//#include<conio.h>
#include<string.h>
#define epsilon 238

int flag=0,len,pt=0;
char st[25];
void E();
void T();
void F();
void EPRIME();
void TPRIME();
void ADVANCE();

int main()
{
//clrscr();
printf("\nRecursive Descent parser\n");
printf("\nE ->TE'\nE' ->+TE' /%c\nT ->FT'\nT' ->*FT'/%c\nF -> (E)/a\n",epsilon,epsilon);
printf("enter the string :");
scanf("%s",st);
len=strlen(st);
E();
if((flag==0)&&(len==pt))
printf("\n\nstringis accepted\n\n");
else
printf("\nstring rejected\n");
//getch();
return 0;
}
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 5
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

void E()
{
T();
EPRIME();
}
void T()
{
F();
TPRIME();
}
void EPRIME()
{
if(st[pt]=='+')
{
ADVANCE();
T();
EPRIME();
}
}
void TPRIME()
{
if(st[pt]=='*')
{
ADVANCE();
F();
TPRIME();
}
}
void F()
{
if(st[pt]=='(')
{
ADVANCE();
E();
if(st[pt]==')')
ADVANCE();
else
flag=1;
}
else if(st[pt]=='a')
ADVANCE();
else
flag=1;
}
void ADVANCE()
{
pt++;
}

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 6
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 7
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 3: Program to simulate First and Follow of any

grammar
Aim
Write a program to compute First and Follow for any given terminal or non-terminal.

Algorithm
To compute First(X) for all grammar symbol X, apply the following rules.

1) If x is a terminal, then FIRST(x) = { ‘x’ }

2) If x-> Є, is a production rule, then add Є to FIRST(x).
3) If X->Y1 Y2 Y3….Yn is a production,
a) FIRST(X) = FIRST(Y1)
b) If FIRST(Y1) contains Є then FIRST(X) = { FIRST(Y1) – Є } U
{ FIRST(Y2) }
c) If FIRST (Yi) contains Є for all i = 1 to n, then add Є to FIRST(X).

To compute Follow(A) for all non-terminal A, apply the following rules.

1) FOLLOW(S) = { $ } // where S is the starting non-terminal

2) If A -> pBq is a production, where p, B and q are any grammar symbols, then
everything in FIRST(q) except Є is in FOLLOW(B).
3) If A -> pB is a production, then everything in FOLLOW(A) is in FOLLOW(B).
4) If A -> pBq is a production and FIRST(q) contains Є, then FOLLOW(B) contains
{ FIRST(q) – Є } U FOLLOW(A)

Program
#include<iostream.h>
#include<stdio.h>
#include<string.h>
#include<conio.h>
int ister(char);
void first(char);
void follow(char);
char grammar[20][20]={"E->TX","X->+TX","X->i","T->FY","Y->*FY","Y->i","F-
>(E)","F->i"};
char ter[]={'+','*','(',')','i'};
char nonter[]={'E','X','T','Y','F'};
char FIRST[10],FOLLOW[10];
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 8
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

int fi,fo;
void main()
{
int i,j;
clrscr();
cout<<"\n\n\n\t\t\tGRAMMAR\n\t\t\t----\n";
cout<<"\n\t\t\tE->TX"<<"\n\n\t\t\tX->+TX"<<"\n\n\t\t\tX->i";
cout<<"\n\n\t\t\tT->FY"<<"\n\n\t\t\tY->*FY"<<"\n\n\t\t\tY->i";
cout<<"\n\n\t\t\tF->(E)"<<"\n\n\t\t\tF->i";
printf("\n\n\t\tFIRST\n\t\t-----\n");
for(i=0;i<5;i++)
{
fi=0;
for(j=0;j<10;j++)
FIRST[j]='\0';
printf("\n\tFIRST(%c)={ ",nonter[i]);
first(nonter[i]);
for(j=0;j<strlen(FIRST);j++)
printf("%c,",FIRST[j]);
printf("\b }");
}
printf("\n\t\tFOLLOW\n\t\t------\n");
for(i=0;i<5;i++)
{
fo=0;
for(j=0;j<10;j++)
FOLLOW[j]='\0';
printf("\n\tFOLLOW(%c)={ ",nonter[i]);
follow(nonter[i]);
for(j=0;j<strlen(FOLLOW);j++)
printf("%c,",FOLLOW[j]);
printf("\b }");
}
getch();
}
void first(char x)
{
int i;
if(ister(x))
{
FIRST[fi]=x;
fi++;
}
else
for(i=0;i<8;i++)
if(grammar[i][0]==x)
if(grammar[i][3]=='i')
{
FIRST[fi]='i';
fi++;
}
else
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 9
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

first(grammar[i][3]);
}
void follow(char x)
{
int i,j,k,flag;
if(x=='E')
{
FOLLOW[fo]='$';
fo++;
}
for(i=0;i<8;i++)
for(j=4;grammar[i][j]!='\0';j++)
if(grammar[i][j]==x)
if(grammar[i][j+1]=='\0')
{
follow(grammar[i][0]);
return;
}
else
{
fi=flag=0;
first(grammar[i][j+1]);
for(k=0;k<fi;k++)
if(FIRST[k]!='i')
{
FOLLOW[fo]=FIRST[k];
fo++;
}
else
flag=1;
if(flag)
{
follow(grammar[i][0]);
return;
}
}
}
int ister(char a)
{
int i;
for(i=0;i<5;i++)
if(ter[i]==a)
return 1;
return 0;
}

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 10
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 11
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 4: C program to count the number of words and

lines
Aim
Write a C program to count the number of words and lines in a file.

Algorithm
1) Start.
2) Read the input file.
3) Read character by character.
4) If the read character in new line or end of line, increment the counter for number of
lines.
5) If the read character in space, tab, new line or end of line, increment the counter for
number of words.
6) If the number of characters read is greater than zero then print the values of word
counter and line counter.
7) Stop.

Program
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
int main()
{
FILE * file;
char path[100];
char ch;
int characters, words, lines;
printf("Enter source file path: ");
scanf("%s", path);
file = fopen(path, "r");
if (file == NULL)
{
printf("\nUnable to open file.\n");
printf("Please check if file exists and you have read privilege.\n");
exit(EXIT_FAILURE);
}
characters = words = lines = 0;

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 12
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

while ((ch = fgetc(file)) != EOF)

{
characters++;
if (ch == '\n' || ch == '\0')
lines++;
if (ch == ' ' || ch == '\t' || ch == '\n' || ch == '\0')
words++;
}
if (characters > 0)
{
words++;
lines++;
}
printf("\n");
printf("Total characters = %d\n", characters);
printf("Total words = %d\n", words);
printf("Total lines = %d\n", lines);
fclose(file);
getch();
return 0;
}

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 13
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 5: Intermediate code generation for simple

expressions
Aim
Write a program to implement three address codes for a set of tokens.

Algorithm
1) Invoke a function getreg to find out the location L where the result of computation b
op c should be stored.

2) Consult the address description for y to determine y'. If the value of y currently in
memory and register both then prefer the register y' . If the value of y is not already in
L then generate the instruction MOV y' , L to place a copy of y in L.

3) Generate the instruction OP z' , L where z' is used to show the current location of z. if
z is in both then prefer a register to a memory location. Update the address descriptor
of x to indicate that x is in location L. If x is in L then update its descriptor and
remove x from all other descriptor.

4) If the current value of y or z have no next uses or not live on exit from the block or in
register then alter the register descriptor to indicate that after execution of x : = y op z
those register will no longer contain y or z.

Program
#include<stdio.h>
#include<stdlib.h>
//#include<conio.h>
#include<math.h>
#include<ctype.h>
#include<string.h>
char in[25],post[25],stack[25],st[25][25],three[10][10],u[5];
int i,s,p,r,item,top,b,th=0,tr=0;
int pre(char t)
{
int r;
if((t=='+')||(t=='-'))
r=1;
if((t=='*')||(t=='/'))
r=2;
if(t=='^')
r=3;
if((t=='(')||(t==')'))
r=0;
return(r);
}
int main()
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 14
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

{
int j,k,p,q,a,b;
char *buff;
//clrscr();
r=1;
printf("\t\tOUTPUT\n");
printf("****************************************\n");
printf("Enter the expression:\n");
scanf("%s",in);
s=1;
p=0;
stack[0]='(';
for(i=2;in[i]!='\0';i++)
{
if((in[i]!='+')&&(in[i]!='-')&&(in[i]!='*')&&(in[i]!='/')&&(in[i]!='^')&&(in[i]!='(')&&(in[i]!
=')'))
{
post[p]=in[i];
p++;
}
else
{
if(in[i]=='(')
{
stack[s]=in[i];
s++;
}
else
{
if(in[i]==')')
{
while(stack[s-1]!='(')
{
post[p]=stack[s-1];
stack[s-1]=' ';
s--;
p++;
}
stack[s-1]=' ';
s--;
}
else
{
a=pre(in[i]);
b=pre(stack[s-1]);
j=p;
while(a<=b)
{
post[j]=stack[s-1];
stack[s-1]=' ';
s--;
j++;
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 15
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

p=j;
b=pre(stack[s-1]);
}
stack[s]=in[i];
s++;
}}}}
for(i=s-1;i>0;i--)
if(stack[i]!='(')
{
post[p]=stack[i];
p++;
}
printf("\n\nThe postfix notation for the given expression:\n\n");
for(p=0;post[p]!='\0';p++)
printf("%c",post[p]);
printf("\n\nThree address code\n\n");
top=0;
for(p=0;post[p]!='\0';p++)
{
if((post[p]!='+')&&(post[p]!='-')&&(post[p]!='*')&&(post[p]!='/')&&(post[p]!='^'))
{
st[top][0]=post[p];
st[top][1]='\0';
top++;
}
else
{
printf("t%d=%s%c%s\n",tr,st[top-2],post[p],st[top-1]);

top--;
top--;
snprintf (u, sizeof(u), "%d",tr);
//itoa(tr,u,10);
strcpy(st[top],"t");
strcat(st[top],u);
tr++;
top++;
}}
printf("%c=%s",in[0],st[0]);
//getch();
}

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 16
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Output

Experiment No 6: Implement the back end of a compiler

Aim
To implement the back end of the compiler which takes the three address code and produces
the 8086 assembly language instructions that can be assembled and run using a 8086
assembler. The target assembly instructions can be simple move, add, sub, jump. Also simple
addressing modes are used.

Algorithm
1) Start the program
2) Open the source file and store the contents as quadruples.
3) Check for operators, in quadruples, if it is an arithmetic operator generator it or if
assignment operator generates it, else perform unary minus on register C.
4) Write the generated code into output definition of the file in outp.c
5) Print the output.
6) Stop the program.

Program
#include<stdio.h>
#include<string.h>
int main()
{
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 17
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

char icode[10][30],str[20],opr[10];
int i=0;
//clrscr();
printf("\n Enter the set of intermediate code (terminated by exit):\n");
do
{
scanf("%s",icode[i]);
} while(strcmp(icode[i++],"exit")!=0);
printf("\n target code generation");
printf("\n************************");
i=0;
do
{
strcpy(str,icode[i]);
switch(str[3])
{
case '+':
strcpy(opr,"ADD");
break;
case '-':
strcpy(opr,"SUB");
break;
case '*':
strcpy(opr,"MUL");
break;
case '/':
strcpy(opr,"DIV");
break;
}
printf("\n\tMov %c,R%d",str[2],i);
printf("\n\t%s%c,R%d",opr,str[4],i);
printf("\n\tMov R%d,%c",i,str[0]);
}while(strcmp(icode[++i],"exit")!=0);
//getch();
return 0;
}
Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 18
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 7: Implementation of lexical analyzer using Lex

tool
Aim
To implement lexical analyzer using Lex tool.

Algorithm
1) Start the program
2) Lex program consists of three parts.
3) Declaration %%
4) Translation rules %%
5) Auxiliary procedure.
6) The declaration section includes declaration of variables, main test, constants and regular
definitions.
7) Translation rule of lex program are statements of the form
8) P1{action}
9) P2{action}
10) …..
11) …..
12) Pn{action}
13) Write program in the vi editor and save it with .1 extension.
14) Compile the lex program with lex compiler to produce output file as lex.yy.c.
15) Eg. $ lex filename.1
16) $gcc lex.yy.c-11
17) Compile that file with C compiler and verify the output.

Program
math[+|-|*|/|^]
eq[=|>|<|]
sp[,|;]
%%
"if"|"else"|"int"|"char"|"double" printf("\n%s\t is a keyword",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("\n%s\t is an identifier",yytext);
[0-9] printf("\n%s\t is a constant",yytext);
{sp} printf("\n%s\t is a special character",yytext);
{math} printf("\n%s\t is an arithmetic operator",yytext);
{eq} printf("\n%s\t is an equality operator",yytext);
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 19
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

%%
int yywrap()
{
return 1;
}
int main(int argc, char **argv)
{
yyin=fopen(argv[1],"r");
yylex();
fclose(yyin);
return 0;
}

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 20
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 8: Yacc program to recognize a valid variable

Aim
Write a Yacc program to recognize a valid variable which starts with a letter followed by any
number of letters or digits.

Algorithm
1) Start the program.
2) Write code for the parser. l in the declaration part.
3) Write code for the ‘y’ parser.
4) Also write code for validating the input variable name.
5) Write additional code to print the result of computation.
6) Execute and verify it.
7) Stop the program.

Program
Lex File
%{
#include "y.tab.h"
%}
%%
[a-zA-Z][a-zA-Z0-9]* return letter;
[0-9] return digit;
. return yytext[0];
\n return 0;
%%
int yywrap()
{
return 1;
}
YACC File
%{
#include<stdio.h>
int valid=1;
%}
%token digit letter
%%
start : letter s
s : letter s
| digit s
|
;
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 21
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

%%
int yyerror()
{
printf("\nIt is not a valid variable!\n");
valid=0;
return 0;
}
int main()
{
printf("\nEnter a variable name.\n ");
yyparse();
if(valid)
{
printf("\nIt is a valid variable!\n");
}
}

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 22
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 9: Yacc program to recognize a valid arithmetic

expression
Aim
Write a Yacc program to recognize a valid arithmetic expression that uses operator +,-,*,
and /.

Algorithm
1) Start the program.
2) Write code for the parser. l in the declaration part.
3) Write code for the ‘y’ parser.
4) Also write the code for different arithmetical operations.
5) Write additional code to print the result of computation.
6) Execute and verify it.
7) Stop the program.

Program
Lex File
%{
#include "y.tab.h"
%}
%%
[a-zA-Z] {return ID;}
[0-9]+ {return NUMBER;}
[\t] {;}
\n {return 0;}
. {return yytext[0];}
%%
int yywrap()
{
return 1;
}
Yacc File
%{
#include<stdio.h>
%}
%token ID NUMBER
%left '+''-'
%left '*''/'
%%
stmt:expr
;
expr: expr'+'expr
|expr'-'expr
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 23
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

|expr'*'expr
|expr'/'expr
|'('expr')'
|NUMBER
|ID
;
%%
void main()
{
printf("\n Enter an expression : \n");
yyparse();
printf("\n Valid expression \n");
exit(0);
}
void yyerror()
{
printf("\n Invalid expression \n");
exit(0);
}

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 24
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 10: Implementation of calculator using Lex and

Yacc
Aim
Write a program to implement a calculator using Lex and Yacc.

Algorithm
1) Start the program.
2) Write code for the parser. l in the declaration part.
3) Write code for the ‘y’ parser.
4) Also write the code for different arithmetical operations.
5) Write additional code to print the result of computation.
6) Execute and verify it.
7) Stop the program.

Program
Lex File
%{
#include<stdio.h>
#include"y.tab.h"
extern int yylval;
%}
%%
[0-9]+ {
yylval=atoi(yytext);
return NUMBER;
}
[\t];
[\n] return 0;
. return yytext[0];
%%
int yywrap()
{
return 1;
}

Yacc File
%{
#include<stdio.h>
int flag=0;
%}
%token NUMBER;
%left '+''-'

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 25
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

%left '*''/''%'
%left '('')'
%%
ArithmeticExpression: E{
printf("\nResult=%d\n",$$);
return 0;
};
E:E'+'E {$$=$1+$3;}
|E'-'E {$$=$1-$3;}
|E'*'E {$$=$1*$3;}
|E'/'E {$$=$1/$3;}
|E'%'E {$$=$1%$3;}
|'('E')' {$$=$2;}
|NUMBER {$$=$1;}
;
%%
void main()
{
printf("\nEnter any arithmetic expression:\n");
yyparse();
if(flag==0)
printf("\nEntered arithmetic expression is valid\n\n");
}
void yyerror()
{
printf("\nEntered arithmetic expression is invalid\n\n");
flag=1;
}

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 26
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 11: Program to perform constant propagation

Aim
Write a C program to perform constant propagation.

Algorithm
worklist = all statements in SSA
while worklist ≠ ∅
remove some statement S from worklist
if S is x = phi(c,c,…c) for some constant c
replace S with v = c
if S is x = c for some constant c
delete S form the program
for each statement T that uses v, substitute c for x in T
worklist = worklist union {T}

Program
#include<stdio.h>
#include<string.h>
#include<ctype.h>
//#include<conio.h>
void input();
void output();
void change(int p,char *res);
void constant();
struct expr
{
char op[2],op1[5],op2[5],res[5];
int flag;
}arr[10];
int n;
int main()
{
//clrscr();
input();
constant();
output();
//getch();
return 0;
}
void input()
{
int i;
printf("\n\nEnter the maximum number of expressions : ");
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 27
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

scanf("%d",&n);
printf("\nEnter the input : \n");
for(i=0;i<n;i++)
{
scanf("%s",arr[i].op);
scanf("%s",arr[i].op1);
scanf("%s",arr[i].op2);
scanf("%s",arr[i].res);
arr[i].flag=0;
}
}
void constant()
{
int i;
int op1,op2,res;
char op,res1[5];
for(i=0;i<n;i++)
{
if(isdigit(arr[i].op1[0]) && isdigit(arr[i].op2[0]) || strcmp(arr[i].op,"=")==0)
{

sscanf(arr[i].op1, "%d", &op1);

sscanf(arr[i].op1, "%d", &op2);
op=arr[i].op[0];
switch(op)
{
case '+':
res=op1+op2;
break;
case '-':
res=op1-op2;
break;
case '*':
res=op1*op2;
break;
case '/':
res=op1/op2;
break;
case '=':
res=op1;
break;
}
sprintf(res1,"%d",res);
arr[i].flag=1;
change(i,res1);
}
}
}
void output()
{
int i=0;
printf("\nOptimized code is : ");
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 28
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

for(i=0;i<n;i++)
{
if(!arr[i].flag)
{
printf("\n%s %s %s %s",arr[i].op,arr[i].op1,arr[i].op2,arr[i].res);
}
}
}
void change(int p,char *res)
{
int i;
for(i=p+1;i<n;i++)
{
if(strcmp(arr[p].res,arr[i].op1)==0)
strcpy(arr[i].op1,res);
else if(strcmp(arr[p].res,arr[i].op2)==0)
strcpy(arr[i].op2,res);
}
}

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 29
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 12: Shift reduce parser for a given language

Aim
Write a program to construct a shift reduce parser for a given language.

Algorithm
loop forever:
for top-of-stack symbol, s, and next input symbol, a
case action of T[s,a]
shift x: (x is a STATE number)
push a, then x on the top of the stack and advance ip to point to the
next input symbol.
reduce y: (y is a PRODUCTION number)
assume that the production is of the form
A => beta
pop 2 * |beta| symbols of the stack. At this point the top of the stack
should be a state number, say s’. Push A, then goto of T[s’,A] (a state
number) on the top of the stack. Output the production
A =>beta
accept:
return --- a successful parse.
default:
error --- the input string is not in the language.

Program
#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();
int main()
{

//clrscr();

printf("\n\t\t SHIFT REDUCE PARSER\n");

printf("\nGRAMMER\n");
printf("\n E->E+E\n E->E/E");
printf("\n E->E*E\n E->a/b");
printf("\n enter the input symbol:\t");
gets(ip_sym);
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 30
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

printf("\n\t stack implementation table");

printf("\nstack\t\tinputsymbol\t\taction");
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,"a"))||(!strcmp(temp2,"b")))

stack[st_ptr]='E';if(!strcmp(temp2,"a"))
printf("\n$%s\t\t%s$\t\t\tE->a",stack,ip_sym);

else

printf("\n $%s\t\t%s$\t\t\tE->b",stack,ip_sym);
flag=1;
}

if((!strcmp(temp2,"+"))||(strcmp(temp2,"*"))||(!strcmp(temp2,"/")))

flag=1;

if((!strcmp(stack,"E+E"))||(!strcmp(stack,"E\E"))||(!strcmp(stack,"E*E")))

{
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 31
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

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\E"))

printf("\n$%s\t\t%s$\t\t\tE->E\E",stack,ip_sym);

else

if(!strcmp(stack,"E*E"))

printf("\n $%s\t\t%s$\t\t\tE->E*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\t%s\t\t reject",stack,ip_sym);exit(0);
}

Output
GRAMMAR is –
E->2E2
E->3E3

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 32
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

E->4
stack input action

$ 32423$ SHIFT

$3 2423$ SHIFT

$32 423$ SHIFT

$324 23$ REDUCE TO E -> 4

$32E 23$ SHIFT

$32E2 3$ REDUCE TO E -> 2E2

$3E 3$ SHIFT

$3E3 $ REDUCE TO E -> 3E3

$E $ Accept

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 33
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 13: LEX program vowels and consonants

Aim
Write a Lex program to find out total no: of vowels and consonants from the given input
string.

Algorithm

1) Start the program

2) Lex program consists of three parts.
3) Declaration %%
4) Translation rules %%
5) Auxiliary procedure.
6) The declaration section includes declaration of variables, main test, constants and regular
definitions.
7) Translation rule of lex program are statements of the form
8) P1{action}
9) P2{action}
10) …..
11) …..
12) Pn{action}
13) Define the vowels and consonants in the translation rule.
14) Compile the lex program as lex program .
15) Run as cc lex.yy.c
16) verify the output

Program
%{
int v=0;
int c=0;
%}

%%
[aeiouAEIOU] {v++;}
[a-zA-Z] {c++;}
"\n" { printf("Number of vowels are: %d\n",v); v=0;
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 34
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

printf("Number of consonants are: %d\n",c); c=0; }

%%

int main()
{
printf("Enter the string of vowels and consonents:");
yylex();

return 0;
}
int yywrap()
{
return 1;
}

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 35
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 14: program to convert NFA to DFA

Aim
Write a program to convert NFA to DFA.

Algorithm

1) Initially Q’= φ
2) Add q0 for NFA to Q’. Then find the transitions from this start state.
3) In Q’, Find the possible set of states for each input symbol. If this set of states is not
in Q’, then add it to Q’.
4) In DFA, the find state will be all the states which contain F (final states of NFA)

Program

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

int ninputs;
int dfa[100][2][100] = {0};
int state[10000] = {0};
char ch[10], str[1000];
int go[10000][2] = {0};
int arr[10000] = {0};

int main()
{
int st, fin, in;
int f[10];
int i,j=3,s=0,final=0,flag=0,curr1,curr2,k,l;
int c;

printf("\nFollow the one based indexing\n");

printf("\nEnter the number of states::");

scanf("%d",&st);

printf("\nGive state numbers from 0 to %d",st-1);

CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 36
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

for(i=0;i<st;i++)
state[(int)(pow(2,i))] = 1;

printf("\nEnter number of final states\t");

scanf("%d",&fin);

printf("\nEnter final states::");

for(i=0;i<fin;i++)
{
scanf("%d",&f[i]);
}

int p,q,r,rel;

printf("\nEnter the number of rules according to NFA::");

scanf("%d",&rel);

printf("\n\nDefine transition rule as \"initial state input symbol final state\"\n");

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

{
scanf("%d%d%d",&p,&q,&r);
if (q==0)
dfa[p][0][r] = 1;
else
dfa[p][1][r] = 1;
}

printf("\nEnter initial state::");

scanf("%d",&in);

in = pow(2,in);

i=0;

printf("\nSolving according to DFA");

int x=0;
for(i=0;i<st;i++)
{
for(j=0;j<2;j++)
{
int stf=0;
for(k=0;k<st;k++)
{
if(dfa[i][j][k]==1)
stf = stf + pow(2,k);
}

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 37
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

go[(int)(pow(2,i))][j] = stf;
printf("%d-%d-->%d\n",(int)(pow(2,i)),j,stf);
if(state[stf]==0)
arr[x++] = stf;
state[stf] = 1;
}

//for new states

for(i=0;i<x;i++)
{
printf("for %d ---- ",arr[x]);
for(j=0;j<2;j++)
{
int new=0;
for(k=0;k<st;k++)
{
if(arr[i] & (1<<k))
{
int h = pow(2,k);

if(new==0)
new = go[h][j];
new = new | (go[h][j]);

}
}

if(state[new]==0)
{
arr[x++] = new;
state[new] = 1;
}
}
}

printf("\nThe total number of distinct states are::\n");

printf("STATE 0 1\n");

for(i=0;i<10000;i++)
{
if(state[i]==1)
{
//printf("%d**",i);
int y=0;
if(i==0)
printf("q0 ");
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 38
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

else
for(j=0;j<st;j++)
{
int x = 1<<j;
if(x&i)
{
printf("q%d ",j);
y = y+pow(2,j);
//printf("y=%d ",y);
}
}
//printf("%d",y);
printf(" %d %d",go[y][0],go[y][1]);
printf("\n");
}
}

j=3;
while(j--)
{
printf("\nEnter string");
scanf("%s",str);
l = strlen(str);
curr1 = in;
flag = 0;
printf("\nString takes the following path-->\n");
printf("%d-",curr1);

for(i=0;i<l;i++)
{
curr1 = go[curr1][str[i]-'0'];
printf("%d-",curr1);
}

printf("\nFinal state - %d\n",curr1);

for(i=0;i<fin;i++)
{
if(curr1 & (1<<f[i]))
{
flag = 1;
break;
}
}

if(flag)
printf("\nString Accepted");
else
printf("\nString Rejected");
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 39
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

return 0;
}

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 40
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Experiment No 15: program to find epsilon closure of all states of

any given NFA with epsilon transitions.
Aim
Write a program to find epsilon closure of all states of any given NFA with epsilon
transitions.

Algorithm

1. Enter the number of states and the states given

2. Set a transition table with ε moves
3. Read the current state
4. Check the ε moves from each state to all other states.
5. Display the output stats.

Program
#include<stdio.h>

#include<string.h>

char result[20][20], copy[3], states[20][20];

void add_state(char a[3], int i) {

strcpy(result[i], a);
}

void display(int n) {
int k = 0;
printf("Epsilon closure of %s = { ", copy);
while (k < n) {
printf(" %s", result[k]);
k++;
}
printf(" } nnn");
}

int main() {
FILE * INPUT;
INPUT = fopen("input.dat", "r");

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 41
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

char state[3];
int end, i = 0, n, k = 0;
char state1[3], input[3], state2[3];
printf("Enter the no of states: ");
scanf("%d", & n);
printf("Enter the states");
for (k = 0; k < 3; k++) {
scanf("%s", states[k]);

for (k = 0; k < n; k++) {

i = 0;
strcpy(state, states[k]);
strcpy(copy, state);
add_state(state, i++);
while (1) {
end = fscanf(INPUT, "%s%s%s", state1, input, state2);
if (end == EOF) {
break;
}

if (strcmp(state, state1) == 0) {
if (strcmp(input, "e") == 0) {
add_state(state2, i++);
strcpy(state, state2);
}
}

}
display(i);
rewind(INPUT);
}

return 0;
}

Output

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 42
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

VIVA QUESTIONS WITH ANSWERS

1. What is a compiler?
A compiler is a program that reads a program written in one language –the source
language and translates it into an equivalent program in another language-the target
language. The compiler reports to its user the presence of errors in the source
program.

2. What are the two parts of a compilation? Explain briefly.

Analysis and Synthesis are the two parts of compilation. The analysis part breaks up
the source program into constituent pieces and creates an intermediate representation
of the source program.
The synthesis part constructs the desired target program from the intermediate
representation.

3. List the subparts or phases of analysis part.

Analysis consists of three phases:
Linear Analysis.
Hierarchical Analysis.
Semantic Analysis.

4. What is linear analysis?

Linear analysis is one in which the stream of characters making up the source
program is read from left to right and grouped into tokens that are sequences of
characters having a collective meaning. Also called lexical analysis or scanning.

5. List the various phases of a compiler.

The following are the various phases of a compiler:
Lexical Analyzer
Syntax Analyzer
Semantic Analyzer
Intermediate code generator
Code optimizer
Code generator

6. What are the classifications of a compiler?

Compilers are classified as:
Single- pass
Multi-pass
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 43
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Load-and-go

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 44
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

7. What is a symbol table?

A symbol table is a data structure containing a record for each identifier, with fields
for the attributes of the identifier. The data structure allows us to find the record for
each identifier quickly and to store or retrieve data from that record quickly.
Whenever an identifier is detected by a lexical analyzer, it is entered into the symbol
table. The attributes of an identifier cannot be determined by the lexical analyzer.

8. Mention some of the cousins of a compiler.

Cousins of the compiler are:
Preprocessors
Assemblers
Loaders and Link-Editors

9. List the phases that constitute the front end of a compiler.

The front end consists of those phases or parts of phases that depend primarily on the
source language and are largely independent of the target machine. These include
Lexical and Syntactic analysis
The creation of symbol table
Semantic analysis
Generation of intermediate code
A certain amount of code optimization can be done by the front end as well. Also
includes error handling that goes along with each of these phases.

10. Mention the back-end phases of a compiler.

The back end of compiler includes those portions that depend on the target machine
and generally those portions do not depend on the source language, just the
intermediate language. These include
Code optimization
Code generation, and along with error handling and symbol- table operations.

11. Define compiler-compiler.

Systems to help with the compiler-writing process are often been referred to as
compiler-compilers, compiler-generators or translator-writing systems.
Largely they are oriented around a particular model of languages , and they are
suitable for generating compilers of languages similar model.

12. List the various compiler construction tools.

The following is a list of some compiler construction tools:
Parser generators
Scanner generators
Syntax-directed translation engines
Automatic code generators
Data-flow engines

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 45
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

13. Differentiate tokens, patterns, lexeme.

Tokens- Sequence of characters that have a collective meaning.
Patterns- There is a set of strings in the input for which the same token is produced as
output. This set of strings is described by a rule called a pattern associated with the
token
Lexeme- A sequence of characters in the source program that is matched by the
pattern for a token.

14 List the operations on languages.

Union – L U M ={s | s is in L or s is in M}
Concatenation – LM ={st | s is in L and t is in M}
Kleene Closure – L* (zero or more concatenations of L)
Positive Closure – L+ ( one or more concatenations of L)

15. Mention the various notational shorthands for representing regular expressions.
One or more instances (+)
Zero or one instance (?)
Character classes ([abc] where a,b,c are alphabet symbols denotes the regular
expressions a | b | c.)
Non regular sets

16. What is the function of a hierarchical analysis?

Hierarchical analysis is one in which the tokens are grouped hierarchically into nested
collections with collective meaning. It also termed as Parsing.

17. What does a semantic analysis do?

Semantic analysis is one in which certain checks are performed to ensure that
components of a program fit together meaningfully. Mainly performs type checking.

18. List the various error recovery strategies for a lexical analysis.
Possible error recovery actions are:
Panic mode recovery
Deleting an extraneous character
Inserting a missing character
Replacing an incorrect character by a correct character
Transposing two adjacent characters

19. Define parser.

Hierarchical analysis is one in which the tokens are grouped hierarchically into nested
collections with collective meaning. It also termed as Parsing.

20. Mention the basic issues in parsing.

There are two important issues in parsing.
Specification of syntax
Representation of input after parsing.

21. Why lexical and syntax analyzers are separated out?

Reasons for separating the analysis phase into lexical and syntax analyzers:
Simpler to design.
Compiler efficiency is improved.
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 46
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Compiler portability is enhanced.

22. Define a context free grammar.

A context free grammar G is a collection of the following
V is a set of non terminals
T is a set of terminals
S is a start symbol
P is a set of production rules
G can be represented as G = (V,T,S,P)

23. Briefly explain the concept of derivation.

Derivation from S means generation of string w from S. For constructing derivation
two things are important.
i) Choice of non-terminal from several others.
ii) Choice of rule from production rules for corresponding non terminal.
Instead of choosing the arbitrary non terminal one can choose
i) either leftmost derivation – leftmost non terminal in a sentinel form
ii) or rightmost derivation – rightmost non terminal in a sentinel form

24. Define ambiguous grammar.

A grammar G is said to be ambiguous if it generates more than one parse tree for
some sentence of language L(G). i.e. both leftmost and rightmost derivations are same
for the given sentence.

25. What is a operator precedence parser?

A grammar is said to be operator precedence if it possess the following properties:
1. No production on the right side is ε.
2. There should not be any production rule possessing two adjacent non terminals at
the right hand side.

26. List the properties of LR parser.

1. LR parsers can be constructed to recognize most of the programming languages for
which the context free grammar can be written.
2. The class of grammar that can be parsed by LR parser is a superset of class of
grammars that can be parsed using predictive parsers.
3. LR parsers work using non backtracking shift reduce technique yet it is efficient
one.

27. Mention the types of LR parser.

SLR parser- simple LR parser
LALR parser- lookahead LR parser
Canonical LR parser

28. What are the problems with top down parsing?

The following are the problems associated with top down parsing:
Backtracking
Left recursion
CS-341 COMPILER DESIGN LAB LAB MANUAL
Page 47
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Left factoring
Ambiguity

29. Write the algorithm for FIRST and FOLLOW.

FIRST():
1. If X is terminal, then FIRST(X) IS {X}.
2. If X → ε is a production, then add ε to FIRST(X).
3. If X is non terminal and X → Y1,Y2..Yk is a production, then place a in FIRST(X)
if for some i , a is in FIRST(Yi) , and ε is in all of FIRST(Y1),…FIRST(Yi-1);
FOLLOW():
1. Place $ in FOLLOW(S),where S is the start symbol and $ is the input right end-
marker.
2. If there is a production A → αBβ, then everything in FIRST(β) except for ε is
placed in FOLLOW(B).
3. If there is a production A → αB, or a production A→ αBβ where FIRST(β)
contains ε , then everything in FOLLOW(A) is in FOLLOW(B).

30. List the advantages and disadvantages of operator precedence parsing.

Advantages
This typeof parsing is simple to implement.
Disadvantages
1. The operator like minus has two different precedence(unary and binary).Hence it is
hard to handle tokens like minus sign.
2. This kind of parsing is applicable to only small class of grammars.

31. Write short notes on YACC.

YACC is an automatic tool for generating the parser program.
YACC stands for Yet Another Compiler Compiler which is basically the utility
available from UNIX. Basically YACC is LALR parser generator. It can report
conflict or ambiguities in the form of error messages.

32. What is meant by handle pruning?

A rightmost derivation in reverse can be obtained by handle pruning. If w is a
sentence of the grammar at hand, then w = γn, where γn is the nth right-sentential
form of some as yet unknown rightmost derivation.
S = γ0 => γ1…=> γn-1 => γn = w

33. Define LR(0) items.

An LR(0) item of a grammar G is a production of G with a dot at some position of the
right side. Thus, production A → XYZ yields the four items
A→.XYZ
A→X.YZ
A→XY.Z
A→XYZ.

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 48
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

34. Define handle.

A handle of a string is a substring that matches the right side of a production, and
whose reduction to the nonterminal on the left side of the production represents one
step along the reverse of a rightmost derivation.
A handle of a right – sentential form γ is a production A→β and a position of γ where
the string β may be found and replaced by A to produce the previous right-sentential
form in a rightmost derivation of γ. That is , if S =>αAw =>αβw,then A→β in the
position following α is a handle of αβw.

35. What are kernel & non-kernel items?

Kernel items, whish include the initial item, S’→ .S, and all items whose dots are not
at the left end.
Non-kernel items: which have their dots at the left-end.

36. What is phrase level error recovery?

Phrase level error recovery is implemented by filling in the blank entries in the
predictive parsing table with pointers to error routines. These routines may change,
insert, or delete symbols on the input and issue appropriate error messages. They may
also pop from the stack.

37. What are the benefits of intermediate code generation?

A Compiler for different machines can be created by attaching different back end to
the existing front ends of each machine. A Compiler for different source languages
can be created by proving different front ends for corresponding source languages t
existing back end. A machine independent code optimizer can be applied to
intermediate code in order to optimize the code generation.

38. Define back-patching.

Back-patching is the activity of filling up unspecified information of labels using
appropriate semantic actions in during the code generation process.In the semantic
actions the functions used are mklist(i),merge_list(p1,p2) and backpatch(p,i)

39. What is the intermediate code representation for the expression a or b and not c?
The intermediate code representation for the expression a or b and not c is the three
address sequence
t1 := not c
t2 := b and t1
t3 := a or t2

40. What are the various methods of implementing three address statements?
The three address statements can be implemented using the following methods.
Quadruple : a structure with atmost four fields such as operator(OP),arg1,arg2,result.
Triples : the use of temporary variables is avoided by referring the pointers in the
symbol table.

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 49
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Indirect triples : the listing of triples has been done and listing pointers are used
instead of using statements.

41. Give the syntax-directed definition for if-else statement.

1. S → if E then S1
E.true := new_label()
E.false :=S.next
S1.next :=S.next
S.code :=E.code | | gen_code(E.true ‘: ‘) | | S1.code
2. S → if E then S1 else S2
E.true := new_label()
E.false := new_label()
S1.next :=S.next
S2.next :=S.next
S.code :=E.code | | gen_code(E.true ‘: ‘) | | S1.code| | gen_code(‘go to’,S.next) | |
gen_code(E.false ‘:’) | | S2.code

42. What is a flow graph?

A flow graph is a directed graph in which the flow control information is added to the
basic blocks.
 The nodes to the flow graph are represented by basic blocks
 The block whose leader is the first statement is called initial block.
 There is a directed edge from block B1 to block B2 if B2 immediately follows B1
in the given sequence. We can say that B1 is a predecessor of B2.

43. What is a DAG? Mention its applications.

Directed acyclic graph (DAG) is a useful data structure for implementing
transformations on basic blocks. DAG is used in
 Determining the common sub-expressions.
 Determining which names are used inside the block and computed outside the
block.
 Determining which statements of the block could have their computed value
outside the block.
 Simplifying the list of quadruples by eliminating the common su-expressions and
not performing the assignment of the form x := y unless and until it is a must.

44. List the characteristics of peephole optimization.

 Redundant instruction elimination
 Flow of control optimization
 Algebraic simplification
 Use of machine idioms

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 50
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

45. How do you calculate the cost of an instruction?

The cost of an instruction can be computed as one plus cost associated with the source
and destination addressing modes given by added cost.
MOV R0,R1 1
MOV R1,M 2
SUB 5(R0),*10(R1) 3

46. What is a basic block?

A basic block is a sequence of consecutive statements in which flow of control enters
at the beginning and leaves at the end without halt or possibility of branching.
Eg.
t1:=a*5
t2:=t1+7
t3:=t2-5
t4:=t1+t3
t5:=t2+b

47. How would you represent the following equation using DAG?
a:=b*-c+b*-c

48. What are the basic goals of code movement?

To reduce the size of the code(space complexity). To reduce the frequency of
execution of code(time complexity).

49. List the different storage allocation strategies.

The strategies are:
Static allocation
Stack allocation

50. What is dynamic scoping?

In dynamic scoping a use of non-local variable refers to the non-local data declared in
most recently called and still active procedure. Therefore each time new findings are
set up for local names called procedure. In dynamic scoping symbol tables can be
required at run time.

51. Define symbol table.

Symbol table is a data structure used by the compiler to keep track of semantics of the
variables. It stores information about scope and binding information about names.

52. What is code motion?

Code motion is an optimization technique in which amount of code in a loop is
decreased. This transformation is applicable to the expression that yields the same
result independent of the number of times the loop is executed. Such an expression is
placed before the loop.

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 51
 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

53. What are the properties of optimizing compiler?

The source code should be such that it should produce minimum amount of target
code. There should not be any unreachable code. Dead code should be completely
removed from source language.
The optimizing compilers should apply following code improving transformations on
source language.
i) common subexpression elimination
ii) dead code elimination
iii) code movement
iv) strength reduction

54. What is meant by viable prefixes?

The set of prefixes of right sentential forms that can appear on the stack of a shift-
reduce parser are called viable prefixes. An equivalent definition of a viable prefix is
that it is a prefix of a right sentential form that does not continue past the right end of
the rightmost handle of that sentential form.

55. Define semantics of a programming language?

The rules that tell whether a string is a valid program or not are called syntax of the
language. The rules that give meaning to programs are called the semantics of a
programming language.

CS-341 COMPILER DESIGN LAB LAB MANUAL

Page 52