ST.

MOTHER THERESA ENGINEERING COLLEGE

(Approved by AICTE & Affliated to Anna University)

Vagaikulam,Tuticorin - 628 102

( A Unit of SCAD Group of Colleges)

DEPARTMENT OF COMPUTER SCIENCE AND

ENGINEERING

CS 8602 – COMPILER DESIGN

NAME :

REGISTER NUMBER :

YEAR :

BRANCH :

SEMESTER :
 [Link] THERESA ENGINEERING COLLEGE
(Approved by AICTE & Affliated to Anna University)

Vagaikulam,Tuticorin - 628 102

( A Unit of SCAD Group of Colleges)

BONAFIDE CERTIFICATE

Certified that tis is a Bonafide Certificate Record of Work done by Selvan/Selvi

With , Reg No
Of 5th semester of this instuitution in the CS8602 – COMPILER DESIGN LABORATORY
during 2023-2024.

Staff-inn-charge Head of the Department

Submitted for the University Practical Examination held on .

Internal Examiner External Examiner

[Link] Date Title Page No Marks Staff Sign
EX. NO: 1 DEVELOP A LEXICAL ANALYZER TO RECOGNIZE
A FEW PATTERNS IN C
AIM:

To write a C program to develop a lexical analyzer to recognize a few patterns in C.

ALGORITHM:
1. Start the program.
2. Include necessary header files.
3. Declare all the variables and file pointers.
4. Include the input program (input.c) using file function.
5. Read the file input file and display the tokens.
6. Display the header files of the input program.
7. Separate the operators of the input program and display it.
8. Print the punctuation marks.
9. Print the constant that are present in input program.
10. Print the identifiers of the input program.
11. Also count the numbers of each token that occurs in input file and print it.
12. Stop the program.

PROGRAM
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void keyw(char *p);
int i=0,id=0,kw=0,num=0,op=0;
char keys[32][10]={"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto","if","int","long","register","
return","short","signed","sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
main()
{
char ch,str[25],seps[15]=" \t\n,;(){}[]#\"<>",oper[]="!%^&*-+=~|.<>/?";
int j;
char fname[50];
FILE *f1;
//clrscr();
printf("enter file path (drive:\\fold\\filename)\n");
scanf("%s",fname);
f1 = fopen(fname,"r");
//f1 = fopen("Input","r");
if(f1==NULL)
{
goto END;
}
while((ch=fgetc(f1))!=EOF)
{
for(j=0;j<=14;j++)
{
if(ch==oper[j])
{
printf("%c is an operator\n",ch);
op++;
str[i]='\0';
keyw(str);
}
}
for(j=0;j<=14;j++)
{
if(i==-1)
break;
if(ch==seps[j])
{
if(ch=='#')
{
while(ch!='>')
{
printf("%c",ch);
ch=fgetc(f1);
}
printf("%c is a header file\n",ch);
i=-1;
break;
}
if(ch=='"')
{
do
{
ch=fgetc(f1);
printf("%c",ch);
}while(ch!='"');
printf("\b is an argument\n");
i=-1;
break;
}
str[i]='\0';
keyw(str);
}
}
if(i!=-1)
{
str[i]=ch;
i++;
}
else
i=0;
}
 printf("Keywords: %d\nIdentifiers: %d\nOperators: %d\nNumbers:
%d\n",kw,id,op,num);
//getch();
END:
printf("file not found");
}
void keyw(char *p)
{
int k,flag=0;
for(k=0;k<=31;k++)
{
if(strcmp(keys[k],p)==0)
{
printf("%s is a keyword\n",p);
kw++;
flag=1;
break;
}
}
if(flag==0)
{
if(isdigit(p[0]))
{
printf("%s is a number\n",p);
num++;
}
else
{
//if(p[0]!=13&&p[0]!=10)
if(p[0]!='\0')
{
printf("%s is an identifier\n",p);
id++;
}
}
}
i=-1;
}

INPUT: (INPUT.C)
#include<stdio.h>
#include<conio.h>
void main()
{
Int a,b,c;
a=10;
b=5;
c=a+b;
printf(“The sum is %d”,c);
getch();
}

OUTPUT

RESULT:
Thus the above program for developing the lexical the lexical analyzer and recognizing
the few patterns in C is executed successfully and the output is verified.
[Link] IMPLEMENTATION OF LEXICAL ANALYZER USING LEX
TOOL
AIM:
To write a program to implement the Lexical Analyzer using lex tool .

ALGORITHM:
1. Declare the variables which are used for C programs in the declaration section %{...%}.
2. Include the pattern (regular expression) in the transition rule section %%..%%
3. Write the regular expressions for keywords, identifiers, operators, delimiters and symbols.
4. In the main function open the file “[Link]” in read mode.
5. Then call the yylex() function to scan the input file and display the output.
6. Separate the keyword in the program and display it using lex.
7. Separate the operators of the input program and display it.
8. Print the punctuation marks.
9. Print the constant that are present in input program.
10. Print the identifiers of the input program using lex tool.

PROGRAM: (lexid.l)
%{
#include<stdio.h>
int e,k,c,d,i,s;
%}
%%
include|void|main|int|float|double|scanf|char|printf {printf("keyword"); i++;}
[a-z][a-zA-Z0-9]* {printf("Identifier"); k++;}
[0-9]* {printf("digit"); e++;}
[+|-|*|/|=]* {printf("operator"); c++;}
[;|:|(|)|{|}|"|'|,|\n|\t]* {printf("delimiter"); d++;}
[#|<|>|%]* {printf("symbols"); s++;}
%%
int main(void)
{
yyin=fopen("[Link]","r");
yylex();
printf("\nidentifier %d\n",k);
printf("Symbols %d\n",s);
printf("digits %d\n",e);
printf(" Operator %d\n",c);
printf(" keywords %d\n",i);
printf("delimiter %d\n",d);
return 1;
}
int yywrap()
{
return 1;
}
INPUT:
[Link]
int a=10;

OUTPUT:
C:/FlexWindow:/EditPlusPortable> lex lexid.l
C:/FlexWindow:/EditPlusPortable> cc [Link].c
C:/FlexWindow:/EditPlusPortable> a

Identifier 1
Digit 1
Keyword 1
Operator 1
Delimiter 1

RESULT

Thus the program for the exercise on lexical analysis using lex has been successfully
executed and output is verified.
EX. NO 3 (a) PROGRAM TO RECOGNIZE A VALID ARITHMETIC EXPRESSION
THAT USESOPERATOR +, - , * AND / USING YACC

AIM:
To write a Yacc program to validate arithmetic expression.

ALGORITHM:
1. Start the program.
2. Declare the variables which are used for C programs in the declaration section %{...%}.
3. Define the tokens, precedence and associativity of operators used in yacc.
4. Include the pattern (Context Free Grammar) in the transition rule section for validating the
expression between %%..%%
5. In main function get the expression from the user for validating it.
6. Call the yyparse() function to parse the given expression and it construct the LALR parsing
table using the grammar defined in transition rule .
7. Then call the yylex() function, it get the current token and store its value in yylval variable
and it is repeated until the value for given expression is computed.
8. Then it validates the expression with constructed LALR parser.
9. Print the expression is VALID if the expression given by user is derived by the grammar,
else print INVALID.
10. Stop the program.
PROGRAM
%{
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#define YYSTYPE double
%}

%token num
%left '+' '-'
%left '*' '/'

%%
st: st expr '\n' {printf("VALID");}
|st '\n'
|
|error '\n' {printf("INVALID");}
;
expr: num
|expr '+' expr
|expr '/' expr
|expr '-' expr
|expr '*' expr
%%

main()
{
printf(" ENTER AN EXPRESSION TO VALIDATE");
yyparse();
}
yylex()
{
int ch;
while((ch=getchar())==' ');
if(isdigit(ch)|ch=='.')
{
ungetc(ch,stdin);
scanf("%lf",&yylval);
return num;
}
return ch;
}
yyerror(char *s)
{
printf("%S",s);
}
OUTPUT
C:\Flex Windows\EditPlusPortable>yacc -d arithval.y
C:\Flex Windows\EditPlusPortable>cc [Link].c
C:\Flex Windows\EditPlusPortable>a
ENTER AN EXPRESSION TO VALIDATE 5+9
VALID
4+6
VALID
5-
INVALID

RESULT
Thus the program for validating arithmetic expression was done and executed
successfully.
Ex. No: 3 (b) PROGRAM TO RECOGNIZE A VALID VARIABLE WHICH STARTS
WITH A LETTER FOLLOWED BY ANY NUMBER OF LETTERS OR
DIGITS

AIM :
To write a yacc program to check valid variable followed by letter or digits

ALGORITHM:

1. Declare the variables which are used for C programs in the declaration section %{...%}.
2. Define the tokens let, dig used in yacc.
3. Include the pattern (Context Free Grammar) in the transition rule section for validating the
variable between %%..%%
4. In main function get the variable from the user for validating it.
5. Call the yyparse() function to parse the given expression and it construct the LALR parsing
table using the grammar defined in transition rule .
6. Then call the yylex() function, it get the current token and store its value in yylval variable
and it is repeated until the value for given variable.
7. Then it validates the variable with constructed LALR parser.
8. Print the variable is “accepted” if the variable given by user is derived by the grammar,
else print “rejected”.
9. Stop the program.

PROGRAM
%{
#include<stdio.h>
#include<ctype.h>
%}
%token let dig
%%
sad: let recld '\n' {printf("accepted\n"); return 0;}
| let '\n' {printf("accepted\n"); return 0;}
|
|error {yyerror("rejected\n");return 0;}
;
recld: let recld
| dig recld
| let
| dig
;
%%
yylex()
{
char ch;
while((ch=getchar())==' ');
if(isalpha(ch) ||ch=='_')
return let;
if(isdigit(ch))
return dig;
return ch;
}
yyerror(char *s)
{
printf("%s",s);
}
main()
{
printf("ENTER A variable : ");
yyparse();
}

OUTPUT:
C:\Flex Windows\EditPlusPortable>yacc -d valid.y
C:\Flex Windows\EditPlusPortable> cc [Link].c
C:\Flex Windows\EditPlusPortable> a

A1
accepted
10a
rejected

RESULT
Thus the program for checking letter followed by letter or digits were completed and
executed successfully.
Ex. No: 3d IMPLEMENTATION OF CALCULATOR USING LEX AND YACC

AIM
To write a yacc program to implement calculator using lex and yacc

ALGORITHM
1. Declare the variables and header files which are used for C programs in the declaration
section %{...%} of lex and yacc file.
2. Include the pattern (regular expression in lex and CFG in yacc) in the transition rule section
%%..%%
3. Define the tokens, precedence and associativity of operators used in yacc.
4. In main function get the expression from the user for calculation.
5. Call the yyparse() function to parse the given expression and it construct the LALR parsing
table using the grammar defined in transition rule of yacc.
6. Then call the yylex() function, it get the current token and store its value in yylval variable
and it is repeated until the value for given expression is computed.
7. Then it computes the expression with constructed LALR parser.
8. Print the value of expression.
9. Stop the program.

PROGRAM:
Cal.l
%{
#include<stdio.h>
#include "[Link].h"
extern int yylval;
%}
%%
[0-9]+ {
yylval=atoi(yytext);
return NUMBER;
}
[\t] ;
[\n] return 0;
. return yytext[0];
%%
int yywrap()
{
return 1;
}

Cal.y
%{
#include<stdio.h>
int flag=0;
%}
%token NUMBER
%left '+' '-'
%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 which can have operations Addition,
Subtraction, Multiplication, Divison, Modulus and Round brackets:\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:
C:\Flex Windows\EditPlusPortable>lex cal.l
C:\Flex Windows\EditPlusPortable>yacc -d cal.y
C:\Flex Windows\EditPlusPortable> cc [Link].c [Link].c
C:\Flex Windows\EditPlusPortable> a
Enter Any Arithmetic Expression which can have operations Addition, Subtraction,
Multiplication, Divison, Modulus and Round brackets:
5+2
7
Entered arithmetic expression is Valid

RESULT:
Thus the program to implement calculator using lex and yacc was done and executed
successfully.
 Ex. No : 4 GENERATE THREE ADDRESS CODE FOR A SIMPLE PROGRAM
USING LEX AND YACC

AIM :

To write a yacc program to Generate Three Address Code using lex and yacc

ALGORITHM:

1. Declare the variables and header files which are used for C programs in the
declaration section %{...%} of lex and yacc file.
2. Include the pattern (regular expression in lex and CFG in yacc) in the transition
rule section %%..%%
3. Define the tokens, precedence and associativity of operators used in yacc.
4. In main function get the expression from the user for calculation.
5. Call the yyparse() function to parse the given expression and it construct the
LALR parsing table using the grammar defined in transition rule of yacc.
6. Then call the yylex() function, it get the current token and store its value in
yylval variable and it is repeated until the value for given expression is
computed.
7. Then it computes the expression with constructed LALR parser.
8. Print the value of expression.
9. Stop the program.

PROGRAM:
Three.l
%{
#include "[Link].h"
%}

%%

[ \t]+ ; /* Ignore whitespace */

[0-9]+ { yylval = atoi(yytext); return NUM; }
"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"\n" { return EOL; }
. { return yytext[0]; }

%%

int yywrap() {
return 1;
}

Three.y
%{
#include <stdio.h>
#include <stdlib.h>

int temp_var = 0;

int generate_op(int left, int right, char op); // Function prototype

void yyerror(const char* s); // Function prototype
%}

%token NUM ADD SUB MUL DIV EOL

%left ADD SUB

%left MUL DIV

%%

program:
| program statement EOL
;

statement:
expr { printf("t%d = %s\n", ++temp_var, $1); }
;

expr:
expr ADD term { $$ = generate_op($1, $3, '+'); }
| expr SUB term { $$ = generate_op($1, $3, '-'); }
| term { $$ = $1; }
;

term:
term MUL factor { $$ = generate_op($1, $3, '*'); }
| term DIV factor { $$ = generate_op($1, $3, '/'); }
| factor { $$ = $1; }
;

factor:
NUM { $$ = $1; }
| '(' expr ')' { $$ = $2; }
;

%%

#include <stdlib.h>

int generate_op(int left, int right, char op) {

printf("t%d = t%d %c t%d\n", ++temp_var, left, op, right);
return temp_var;
}
 int main() {
yyparse();
return 0;
}

void yyerror(const char* s) {

fprintf(stderr, "%s\n", s);
}

OUTPUT:

C:\Flex Windows\EditPlusPortable>lex three.l

C:\Flex Windows\EditPlusPortable>yacc -d three.y

C:\Flex Windows\EditPlusPortable>cc [Link].c [Link].c

C:\Flex Windows\EditPlusPortable>a
5+6
t1 = t5 + t6

C:\Flex Windows\EditPlusPortable>a
10*3+7
t1 = t10 * t3
t2 = t1 + t7

RESULT:
Thus the yacc program to generate three address code using lex and yacc was
implemented and output was obtained.
Ex. No: 6 IMPLEMENTATION OF SIMPLE CODE OPTIMIZATION TECHNIQUES

AIM:

To write a C program to eliminate dead code as code optimization

ALGORITHM:

1. Start the program.

2. Include necessary header files.
3. Read the input from input file [Link].
4. Instructions are kept in the basic block, Consider the instructions in the same
basic block
5. Variables are initialized with values, If any variables are not used in the basic
block, identified such variables are unused variables
6. Such unused variable will be displayed as output.

PROGRAM
#include <stdio.h>
int main()
{
char all_var[11];
int ptr = 0, dup = 0, i, j, c, a = 0;
FILE *file;
file = fopen("[Link]", "r");
if (file)
{
while ((c = getc(file)) != EOF)
{
putchar(c);
if (c == ';' || c == ' ' || (c >= '0' && c <= '9') || c == '=' || c == '\n' || c == '+')
continue;
else
{
all_var[ptr] = c;
ptr++;
}
}
all_var[ptr] = '\0';
printf("\n The usage variables are:(Top to bottom) ");
for (i = 0; i < ptr; i++)
{
dup = 0;
for (j = i + 1; j < ptr; j++)
{
if (all_var[i] == all_var[j])
{
dup = 1;
break;
}
 }
if (dup == 0)
{
printf("%c\n", all_var[i]);
}
}
fclose(file);
}
return 0;
}

INPUT:
a;
b;
c;
a=34;
c=78;
j=45;
r=30;
b=5;

The usage variables are:(Top to bottom) a

c
j
r
b
OUTPUT:
The usage variables are:(Top to bottom) a
c
j
r
b

RESULT:
Thus the program for code optimization was implemented and output was obtained.
[Link]: 7 IMPLEMENTATION OF THE BACK END OF THE COMPILER

AIM:
To write a c program for implementing backend of a compiler.

ALGORITHM:
1. Start the program
2. Include the necessary header files.
3. Get the number of statements from the user.
4. For each variable allocate a separate register using Load or Move Instructions LD R,a or
Mov R,a
5. If the expression contains operator “+”, then generate the assembly code as ADD
6. If the expression contains operator “-”, then generate the assembly code as SUB
7. If the expression contains operator “*”, then generate the assembly code as MUL
8. If the expression contains operator “/”, then generate the assembly code as DIV
9. Result of the operand is stored to any variables ST x, Ro.
10. Stop the program.

PROGRAM:
#include<stdio.h>
#include<string.h>
int main()
{
char inp[100][100];
int n,i,j,len;
int reg = 1;
printf("Enter the no of statements");
scanf("%d",&n);
for(i = 0; i < n; i++)
scanf("%s",&inp[i]);
for(i = 0; i < n; i++)
{
len = strlen(inp[i]);
for(j=2; j < len; j++)
{
if(inp[i][j] >= 97 && inp[i][j] <= 122)
{
printf("LOAD R%d %c \n",reg++,inp[i][j]);
}
if(j == len-1 && inp[i][len-j] =='=')
{
j=3; if(inp[i][j] == '+')
{
printf("ADD R%d R%d\n",reg-2,reg-1);
printf("STORE %c R%d\n",inp[i][0],reg-2);
}
else if(inp[i][j]=='-')
{
printf("SUB R%d R%d\n",reg-2,reg-1);
printf("STORE %c R%d\n",inp[i][0],reg-2);
 }
else if(inp[i][j]=='*')
{
printf("MUL R%d R%d\n",reg-2,reg-1);
printf("STORE %c R%d\n",inp[i][0],reg-2);
}
else if(inp[i][j]=='/')
{
printf("DIV R%d R%d\n",reg-2,reg-1);
printf("STORE %c R%d\n",inp[i][0],reg-2);
}
break;
}
}
}
return 0;
}

OUTPUT:
Enter the no of statements3
a=4
b=5
c=a+b
LOAD R1 a
LOAD R2 b
ADD R1 R2
STORE c R1

RESULT:
Thus, the C program for implementing backend of the compiler was done successfully.