ARIFA INSTITUTE OF TECHNOLOGY, ESANOOR

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

CS3501 COMPILER DESIGN LABORATORY

MANUAL

REGULATION 2021

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

B.E. COMPUTER SCIENCE AND ENGINEERING

 ARIFA INSTITUTE OF TECHNOLOGY, ESANOOR
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

CS3501 COMPILER DESIGN LABORATORY

MANUAL

REGULATION 2021

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
VISION AND MISSION STATEMENTS OF THE INSTITUTE

Vision:

We endeavor to impart futuristic technical education of the highest quality to the student community
and to inculcate discipline in them to face the world with self-confidence and thus we prepare them
for life as responsible citizens to uphold human values and to be of services at large. We strive to bring
up the Institution as an Institution of Academic excellence of International standard.

Mission:

We transform persons into personalities by the state-of-the-art infrastructure, time

consciousness, quickresponse and the best academic practices through assessment and advice.

VISION AND MISSION STATEMENTS OF THE

DEPARTMENT

Name of the Department: Department of Computer Science and Engineering

Vision:

To offer a quality education in computer science and Engineering, encourage life-long learning and
make graduates responsible for society by upholding social values in the field of emerging technology.

Mission:

⮚ To produce graduates with sound technical knowledge and good skills that prepare them

for rewarding career in prominent industries.

⮚ To promote collaborative learning and research with Industry, Government and

International organizations for continuous knowledge transfer and enhancement.

⮚ To promote entrepreneurship and mould the graduates to be leaders by cultivating the

spirit of social ethical values.

 PEO, PO and PSO Statements

Program Educational Objectives (PEO):

PEO1 - Graduates will have successful careers with high level of technical competency
and problem-solving skills to produce innovative solutions for industrial needs.

PEO2 – Graduates will have good professionalism, team work, effective communication, leadership
qualities and life-long learning for the welfare of mankind.

PEO3 – Graduates will be familiar with recent trends in industry for delivering and
implementing innovative system in collaboration.

Program Outcomes (POs):

1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering

fundamentals, and an engineering specialization to the solution of complex engineering problems.

2. Problem analysis: Identify, formulate, review research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of mathematics, natural
sciences, and engineering sciences.

3. Design/development of solutions: Design solutions for complex engineering problems and

design system components or processes that meet the specified needs with appropriate consideration
for the public health and safety, and the cultural, societal, and environmental considerations.

4. Conduct investigations of complex problems: Use research-based knowledge and research

methods including design of experiments, analysis and interpretation of data, and synthesis of the
information to provide valid conclusions.

5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern
engineering and IT tools including prediction and modeling to complex engineering activities with an
understanding of the limitations.

6. The engineer and society: Apply reasoning informed by the contextual knowledge to assess
societal, health, safety, legal and cultural issues and the consequent responsibilities relevant to the
professional engineering practice.

7. Environment and sustainability: Understand the impact of the professional engineering

solutions in societal and environmental contexts, and demonstrate the knowledge of, and need for
sustainable development.

8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and
norms of theengineering practice.
9. Individual and team work: Function effectively as an individual, and as a member or leader
in diverseteams, and in multidisciplinary settings.

10. Communication: Communicate effectively on complex engineering activities with the

engineering community and with society at large, such as, being able to comprehend and write
effective reports and design documentation, make effective presentations, and give and receive clear
instructions.

11. Project management and finance: Demonstrate knowledge and understanding of the
engineering and management principles and apply these to one’s own work, as a member and leader in
a team, to manage projects and in multidisciplinary environments.

12. Life Long Learning: Recognize the need for, and have the preparation and ability to engage
in independent and life-long learning in the broadest context of technological change.

Program Specific Outcomes (PSOs):

PSO1 - Students will be apply programming skills to develop new software with assured

quality. PSO2 - Students will be ability to demonstrate specific coding skills to improve

employability.

Name of the Faculty Member HOD

 DEPARTMENT OF COMPUTER SCIENCE AND
ENGINEERING

CS3501 Compiler Design Laboratory

COs Knowledg Course outcomes

e level
Students will be able to develop algorithmic solutions to simple
1. K6
computational problems.
2. K3 Students will be able to develop and execute simple compiler programs.
Students will be able to implement programs in compiler using symbol table for
3. K6
solving problems.
4. K4 Students will be able to deploy functions to decompose a compiler program.
5. K6 Students will be able to process compound data using compiler.
Students will be able to utilize compiler packages in developing software
6. K4
applications.

List of Experiments Mapping with COs, POs & PSOs

Exp.No Name of the Experiment COs POs PSOs
1. Using the LEX tool, Develop a
lexical analyzer to recognize a
few patterns in C. (Ex. identifiers,
constants, comments, operators 4 1,2,3,4,5,10,12 1,2
etc.). Create a symbol table, while
recognizing identifiers.
2. Implement a Lexical
Analyzer using LEX Tool. 4 1,2,3,4,5,10,12 1,2
3. Generate YACC specification for a
few syntactic categories.
a. Program to recognize a valid
arithmetic expression that uses
operator +, -, * and /. b. Program to
recognize a valid variable which
starts with a letter followed by any
4 1,2,3,4,5,10,12 1,2
number of letters or digits. c.
Program to recognize a valid
control structures syntax of C
language (For loop, while loop, if-
else, if-else-if, switch-case, etc.). d.
Implementation of calculator using
LEX and YACC.
4. Generate three address code for a
simple program using LEX and 2 1,2,3,4,5,10,12 1,2
YACC.
5. Implement type checking
using Lex and Yacc. 4 1,2,3,4,5,10,12 1,2
 6. Implement simple code
optimization techniques
4 1,2,3,4,5,10,12 1,2
(Constant folding, Strength
reduction and
Algebraic transformation)
7. Implement back-end of the compiler
for which the three address code is
given as input and the 8086 4 1,2,3,4,5,10,12 1,2
assembly language code is produced
as output.
Additional Experiments
8. Write a Python program to
construct the stars(*) 2 1,2,3,4,5,10,12 1,2
pattern,
usinga nested for loop
9 Write a Python class to convert
2 1,2,3,4,5,10,12 1,2
aninteger to a roman numeral.

COURSE OUTCOME Versus PO& PSO MAPPING (DETAILED; HIGH:3; MEDIUM:2; LOW:1):

CO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2
1 3 3 3 3 2 - - - - - 2 2 3 3
2 3 3 3 3 2 - - - - - 2 2 3 -
3 3 3 3 3 2 - - - - - 2 - 3 -
4 2 2 - 2 2 - - - - - 1 - 3 -
5 1 2 - - 1 - - - - - 1 - 2 -
6 2 2 - - 2 - - - - - 1 - 2 -
Avg. 2 3 3 3 2 - - - - - 2 2 3 3

* For Entire Course, PO /PSO Mapping; 1 (Low); 2(Medium); 3(High) Contribution to PO/PSO

PO1 Engineering Knowledge PO7 Environment & Sustainability PSO1 Professional Skills
PO2 Problem Analysis PO8 Ethics PSO2 Competency
PO3 Design & Development PO9 Individual & Team Work
PO4 Investigations PO10 Communication Skills
Project Management
PO5 Modern Tools PO11
& Finance
PO6 Engineer & Society PO12 Life Long Learning
JUSTIFICATION FOR MAPPING

SNO PO/PSO JUSTIFICATION

MAPPED

PO1-H Strongly mapped as students gain knowledge of Identification and solving of LEX
problems.
PO2-H Strongly mapped as students areable to analyze complex problems.
PO3-H Strongly mapped as students understand the symbol table ,lex analyzer which help in
designing solutions for complex engineering problems
PO4-H Strongly mapped as students will have the knowledge of compilers which help in analysis
ofsolutions that provide valid conclusions.
C502.1 PO5-M Moderately mapped as the students will be able to work as a team and jointly find a
solution for the problem.
PO11-M Moderately mapped as the students will be able to manage the financial constraints for
complex problems.
PO12-M Moderately mapped as Information acquired from the Compilers program can be applied to
solve various problems which provides lifelong learning in the context of technological
change.
PO1-H Strongly mapped as students will have the knowledge of simple statements and expressions
can be applied to solve complex engineering problems.
PO2-H Strongly mapped as students will apply various programming methodologies them in
problem analysis.
PO3-H Strongly mapped as students understand the programming methodologies which help in
designing solutions for complex engineering problems.
PO4-H Strongly mapped as students will have the knowledge of python which help inanalysis of
solutions to complex problems.
C502.2 PO5-M Moderately mapped as the students will be able to work as a team and present their work
carried out.
PO11-M Moderately mapped as the students will be able to manage the various solutions for
complex engineering problems.
PO12-M Moderately mapped as Information acquired from programming provides lifelong Learning
in the context of technological change.
PO1-H Strongly mapped as students will have the knowledge of simple statements and expressions
can be applied to solve complex engineering problems.
PO2-H Strongly mapped as students will apply various programming methodologies them in
problem analysis.
PO3-H Strongly mapped as students understand the programming methodologies which help in
designing solutions for complex engineering problems
PO4-H Moderately mapped as students will have the knowledge of python which help in analysis
of solutions to complex problems.
PO5-M Moderately mapped as the students will be able to work as a team and jointly find a
C502.3
solution for the non linear data structures problem.
PO11-M Moderately mapped as the students will be able to manage and resolve the issues
during implement of non linear data structures.
PO1-M Moderately mapped as students will have the knowledge of simple statements and
expressions can be applied to solve complex engineering problems.
 Moderately mapped as students will apply various programming methodologies them in
PO2-M problem analysis.
Moderately mapped as students will have the knowledge of python which help in analysis
PO4-M ofsolutions to complex problems.
C502.4 Moderately mapped as the students will be able to work as a team and jointly find a
PO5-M solution for the problem in graph.
Slightly mapped as the students will be able to manage the various solutions for complex
PO11-L engineering problems.
PO1-L Slightly mapped as students will have the knowledge of simple statements and expressions
can be applied to solve complex engineering problems.
PO2-M Moderately mapped as students will apply various programming methodologies them in
problem analysis.
C502.5 PO5-L Slightly mapped as the students will be able to work as a team and jointly find a solutionfor
the problem in graph.
PO11-L Slightly mapped as the students will be able to manage the various solutions for complex
engineering problems.

PO/PSO
SNO JUSTIFICATION
MAPPED
Strongly mapped as students will gain, knowledge of compiler programming which can
PSO1-H beapplied to design solutions to complex engineering problems.
C502.1 Strongly Knowledge of different modules help students to solve complex problems
PSO2-H
Strongly mapped as students will gain, knowledge of compiler programming which can be
C502.2 PSO1-H
applied to design solutions to complex engineering problems.
Strongly mapped as students will gain, knowledge of compiler programming which can
C502.3 PSO1-H beapplied to design solutions to complex engineering problems..
Strongly mapped as students will gain, knowledge of compiler programming which can
C502.4 PSO1-H beapplied to design solutions to complex engineering problems.
Strongly mapped as students will gain, knowledge of compiler programming which can
C502.5 PSO1-L beapplied to design solutions to complex engineering problems.

Name of the Faculty Member HOD

 CS3501 COMPILER DESIGN LABORATORY LT
PC004
2
COURSE OBJECTIVES:
● To understand the compiler problem solving approaches.
● To learn the basic programming constructs in compiler
● To practice various computing strategies for compiler solutions to real world problems.
● To use compiler structures – six analyzers, symbol table ,YAAC
● To do input/output with files in compiler.
EXPERIMENTS:
Note: The examples suggested in each experiment are only indicative. The lab instructor is expected to
design other problems on similar lines. The Examination shall not be restricted to the sample
experiments listed here.

1. Using the LEX tool, Develop a lexical analyzer to recognize a few patterns in
C. (Ex. identifiers, constants, comments, operators etc.). Create a symbol table, while
recognizing identifiers.
2. Implement a Lexical Analyzer using LEX Tool
3. Generate YACC specification for a few syntactic categories.
a. Program to recognize a valid arithmetic expression that uses operator +, -, * and /.
b. Program to recognize a valid variable which starts with a letter
followed by any number of letters or digits.
c. Program to recognize a valid control structures syntax of C language
(For loop, while loop, if-else, if-else-if, switch-case, etc.).
d. Implementation of calculator using LEX and YACC
4. Generate three address code for a simple program using LEX and YACC.
5. Implement type checking using Lex and Yacc.
6. Implement simple code optimization techniques (Constant folding, Strength
reduction and Algebraic transformation)
7. Implement back-end of the compiler for which the three address code is given as
input and the 8086 assembly language code is produced as output.
TOTAL: 30 PERIODS
COURSE OUTCOMES:
On completion of the course, students will be able to:
CO1: Develop compiler solutions to simple computational problems
CO2: Develop and execute simple Lex programs.
CO3: Implement programs in compiler using conditionals and loops for solving problems.
CO4: Deploy functions to decompose a compiler program.
CO5: Process compound data using compiler programs.
CO6: Utilize LEX, YAAC tools in developing software applications.
 LIST OF EXPERIMENTS

S.No Name of the Experiments

1 (a) Using the LEX tool, Develop a lexical analyzer to recognize a few patterns in C.
(Ex. identifiers, constants, comments, operators etc.).
(b) Create a symbol table, while
recognizing identifiers.
2 Implement a Lexical Analyzer using LEX Tool
3 Generate YACC specification for a few syntactic categories.
(a) Program to recognize a valid arithmetic expression that uses operator +, -, * and /.
(b). Program to recognize a valid variable which starts with a letter followed by any
number of letters or digits.
(c). Program to recognize a valid control structures syntax of C language (For loop,
while loop, if-else, if-else-if, switch-case, etc.).
(d). Implementation of calculator using LEX and YACC.
4 Generate three address code for a simple programusing LEX and YACC.

5 Implement type checking using Lex and Yacc.

6 Implement simple code optimization techniques (Constant folding, Strength reduction and
Algebraic transformation)

7 Implement back-end of the compiler for which the three address code is given as input
and the 8086 assembly language code is produced as output.

Additional Experiments
8 Construction of DAG.

9 Implementation of Stack.

1
EX. NO:1 DATE: 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.

INTRODUCTION:

Lexical analysis is the process of converting a sequence of characters (such as in a

computer program of web page) into a sequence of tokens (strings with an identified
“meaning”). A program that perform lexical analysis may be called a lexer, tokenize or
scanner.

TOKEN

A token is a structure representing a lexeme that explicitly indicates its

categorization for the Purpose of parsing. A category of token is what in linguistics
might be called a part-of- speech. Examples of token categories may include
“identifier” and “integer literal”, although the set of Token differ in different
programming languages.The process of forming tokens from an input stream of
characters is called tokenization.
Consider this expression in the C programming
language: Sum=3 + 2;
Tokenized and represented by the following table:

Lexem Token category

e
Sum “identifier”
= “assignment operator”
3 “integer literal”
+ “addition operator”
2 “integer literal”
; “end of the statement”

ALGORITHM:

1. Start the program

2. Include the header files.
3. Allocate memory for the variable by dynamic memory allocation function.
4. Use the file accessing functions to read the file.
5. Get the input file from the user.
6. Separate all the file contents as tokens and match it with the functions.
7. Define all the keywords in a separate file and name it as key.c
8. Define all the operators in a separate file and name it as open.c
9. Give the input program in a file and name it as input.c
10. Finally print the output after recognizing all the tokens.
11. Stop the program.
PROGRAM:
(DEVELOP A LEXICAL ANALYZER TO RECOGNIZE A FEW PATTERNS IN C)

#include<stdio.
h>
#include<conio.
h>
#include<ctype.
h>
#include<string
.h> void main()
{
FILE *fi,*fo,*fop,*fk;int
flag=0,i=1;
char c,t,a[15],ch[15],file[20];
clrscr();
printf("\n Enter the File
Name:"); scanf("%s",&file);
fi=fopen(file,"r");
fo=fopen("inter.c","w");

fop=fopen("oper.c","r");
fk=fopen("key.c","r");
c=getc(fi);
while(!feof(fi))
{
if(isalpha(c)||isdigit(c)||(c=='['||c==']'||c=='.'==1))
fputc(c,fo);
else
{
if(c=='\n')
fprintf(fo,"\t$\t
");
else fprintf(fo,"\t%c\t",c);
}
c=getc(fi);
}
fclose(f
i);
fclose(f
o);
fi=fopen("inter.c","r");
printf("\n Lexical
Analysis");
fscanf(fi,"%s",a);
printf("\n Line: %d\n",i++);
while(!feof(fi))
{
if(strcmp(a,"$")==0)
{
printf("\n Line: %d \n",i++);
fscanf(fi,"%s",a);
}
fscanf(fop,"%s",c
h);
while(!feof(fop))
{
if(strcmp(ch,a)==0)
{
fscanf(fop,"%s",ch);
printf("\t\t%s\t:\t%s\n",a,c
h); flag=1;

} fscanf(fop,"%s",ch);
}
rewind(fop);
fscanf(fk,"%s",c
h);
while(!feof(fk))
{
if(strcmp(ch,a)==0)
{
fscanf(fk,"%k",ch);
printf("\t\t%s\t:\tKeyword\n",a);flag=1;
}
fscanf(fk,"%s",ch);
}
rewind(f
k);
if(flag=
=0)
{
if(isdigit(a[0]))
printf("\t\t%s\t:\tConstant\n",a);else
printf("\t\t%s\t:\tIdentifier\n",a);
}
flag=0;
fscanf(fi,"%s",a)
; } getch();
}
Key.C:
int
void
main
charif
for
wh
il
e
el
se
printfsc
anf FILE
Include stdio.h
conio.h
iostrea
m.h
Oper.C:
( open para
) closepara
{ openbrace
} closebrace
< lesser
> greater
" doublequote ' singlequote
: colon
; semicolon
# preprocessor
= equal
== asign
% percentage
^ bitwise
& reference
* star
+ add
- sub
\ backslash
/ slash

Input.C:
#include "stdio.h"
#include "conio.h"
void main()
{
int
a=10,b,c;a=b*c;
getch();
}
 OUTPUT:

RESULT:

Thus the above program for developing the lexical the lexical analyzer and recognizingthe few
pattern s in C is executed successfully and the output is verified.
8
EX. NO: 1b
DATE: IMPLEMENTATION OF SYMBOL TABLE

AIM:

To write a C program to implement a symbol table.

INTRODUCTION:

A Symbol table is a data structure used by a language translator such as a

compiler or interpreter, where each identifier in a program’s source code is
associated with information relating to its declaration or appearance in the source
Possible entries in a symbol table:
● Name : a string
● Attribute:
1. Reserved word
2. Variable name
3. Type Name
4. Procedure name
5. Constant name
● Data type
● Scope information: where it can be used.
● Storage allocation
SYMBOL
TABLE
ALGORITHM:

IMPLEMENTATION OF SYMBOL TABLE

1. Start the Program.

2. Get the input from the user with the terminating symbol ‘$’.
3. Allocate memory for the variable by dynamic memory allocation function.
4. If the next character of the symbol is an operator then only the memory is allocated.
5. While reading , the input symbol is inserted into symbol table along with its
memory address.
6. The steps are repeated till ”$” is reached.
7. To reach a variable, enter the variable to the searched and symbol table has been
checkedfor corresponding variable, the variable along its address is displayed as result.
8. Stop the program.
PROGRAM: ( IMPLEMENTATION OF SYMBOL TABLE)

#include<stdio.

h>

#include<conio.

h>

#include<malloc

.h>

#include<string

.h>

#include<math.h

>

#include<ctype.

h> void main()

int i=0,j=0,x=0,n,flag=0; void

*p,*add[15]; char ch,srch,b[15],d[15],c;

//clrscr();

printf("expression terminated by

$:"); while((c=getchar())!='$')

b[i]=c; i++;

n=i-1;

printf("given

expression:"); i=0;

while(i<=n)

printf("%c",b[i]); i++;

printf("symbol table\n");

printf("symbol\taddr\ttype\n
 ");

while(j<=n)

{
c=b[j]; if(isalpha(toascii(c)))

if(j==n)

p=malloc(c);

add[x]=p; d[x]=c;

printf("%c\t%d\tidentifier\n",c,p);

else

ch=b[j+1];

if(ch=='+'||ch=='-'||ch=='*'||ch=='=')

p=malloc(

c);

add[x]=p;

d[x]=c;

printf("%c\t%d\tidentifier\n",c,

p); x++;

} j++;

}
printf("the symbol is to be

searched\n"); srch=getch();

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

if(srch==d[i])

{
sprintf("symbol found\n");

printf("%c%s%d\n",srch,"@address",add[i

]); flag=1;

if(flag==0)

printf("symbol not found\n");

//getch();
OUTPUT:

RESULT:

Thus the C program to implement the symbol table was executed and the output is verified.
 Ex.
No: 2
DAT
E:

IMPLEMENTATION OF LEXICAL ANALYZER USING LEX TOOL

AIM:

To write a program to implement the Lexical Analyzer using lex tool.

INTRODUCTION:

THEORY:

⮚ A language for specifying lexical analyzer.

⮚ There is a wide range of tools for construction of lexical analyzer.
The majority ofthese tools are based on regular expressions.
⮚ The one of the traditional tools of that kind is lex.
LEX:
⮚ The lex is used in the manner depicted. A specification of the
lexical analyzer ispreferred by creating a program lex.1 in the lex
language.
⮚ Then lex.1 is run through the lex compiler to produce a ‘c’ program lex.yy.c.
⮚ The program lex.yy.c consists of a tabular representation of a
transition diagram constructed from the regular expression of lex.1
together with a standard routine thatuses table of recognize leximes.
⮚ Lex.yy.c is run through the ‘C’ compiler to produce as object program
a.out, which isthe lexical analyzer that transform as input stream into
sequence of tokens.

LEX SOURCE:
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
7. Definitions.
8. Translation rule of lex program are statements of the form
9. P1{action}
10. P2
{action}
11. …..
12. …..
13. Pn{action}
14. Write program in the vi editor and save it with .1 extension.
15. Compile the lex program with lex compiler to produce output file as lex.yy.c.
16. Eg. $ lex filename.1
17. $gcc lex.yy.c-11
18. Compile that file with C compiler and verify the output.
PROGRAM: (LEXICAL ANALYZER USING LEX TOOL)

#include<stdio.h>
#include<ctype.h>
#include<conio.h>
#include<string.h
> char
vars[100][100];
int vcnt;
char
input[1000],c;
char
token[50],tlen;
int state=0,pos=0,i=0,id;
char *getAddress(char
str[])
{
for(i=0;i<vcnt;i++)
if(strcmp(str,vars[i])=
=0)

return vars[i];
strcpy(vars[vcnt],st
r); return
vars[vcnt++];
}
int isrelop(char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='%'||c=='^')
return 1;
else
return
0;
}
int main(void)
{
clrscr();
printf("Enter the Input
String:"); gets(input);
do
{
c=input[pos];
putchar(c)
;
switch(sta
te)
{
case 0:
if(isspace(
c))
printf("\b"
);
if(isalpha(
c))
{
token[0]
=c;
tlen=1;
state=1;
}
if(isdigit(
c))
state=2;
if(isrelop(
c))
state=3;
if(c==';')
printf("\t<3,3>\n");
if(c=='=')
printf("\t<4,4>\n
"); break;
case 1:
if(!isalnum(c))
{
token[tlen]='\o';
printf("\b\t<1,%p>\n",getAddress(token));
state=0;
pos--;
}
else
token[tlen++]
=c; break;
case 2:
if(!isdigit(
c))
{
printf("\b\t<2,%p>\n",&input[pos
]); state=0;
pos--;
}
brea
k;
case
3:
id=input[pos-
1];
if(c=='=')
printf("\t<%d,%d>\n",id*10,id*1
0); else{
printf("\b\t<%d,%d>\n",id,id);
pos--;
}state
=0;
break;
}
pos++;
}
while(c!=0);
getch(
);
return
0;
}
 OUTPUT

RESULT:

Thus the program for the exercise on lexical analysis using lex has been successfullyexecuted and output
is verified.

20
EX.N
O:3a
DATE:

GENERATE YACC SPECIFICATION FOR A FEW SYNTACTIC

CATEGORIES.

AIM :
To write a c program to do exercise on syntax analysis using YACC.
INTRODUCTION :
YACC (yet another compiler) is a program designed to produce designed to
compile a LALR (1) grammar and to produce the source code of the synthetically analyses
of the language produced by the grammar.

ALGORITHM :
1. Start the program.
2. Write the code for parser. l in the declaration port.
3. Write the 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 TO RECOGNIZE A VALID ARITHMETIC EXPRESSION THAT USES
OPERATOR +, - , * AND /.

PROGRAM:
f("\nLess than");
break;
case'=': if(s[1]=='=')
printf("\nEqual
to"); else
printf("\nAssignment
");
break;
case'!':
if(s[1]=='=')
printf("\nNot
Equal"); else
printf("\n Bit
Not"); break;
case'&': if(s[1]=='&')
printf("\nLogical
AND"); else
printf("\n Bitwise AND");
 break;
case'|':
if(s[1]=='|')
printf("\nLogical OR");
else
printf("\nBitwise
OR"); break;
case'+': printf("\n
Addition"); break;
case'-':
printf("\nSubstraction
"); break;
case'*':
printf("\nMultiplication
"); break;
case'/': printf("\nDivision");
break;
case'%': printf("Modulus");
break;
default: printf("\n Not a operator");
}
getch();
}
 OUTPUT:

RESULT:

Thus the program for the exercise on the syntax using YACC has been executedsuccessfully
and Output is verified.
Ex. No: 3 (b)
DATE:
RECOGNIZING A VALID VARIABLE

AIM:

To write a program to recognize a valid variable which starts with a letter followed by any number of
letters ordigits using YACC tool.

ALGORITHM:
LEX
1. Declare the required header file and variable declaration with in ‘%{‘ and ‘%}’.
2. LEX requires regular expressions or patterns to identify token of lexemes for recognize a
valid variable.
3. Lex call yywrap() function after input is over. It should return 1 when work is done or should
return 0when more processing is required.
YACC
1. Declare the required header file and variable declaration with in ‘%{‘ and ‘%}’.
2. Define tokens in the first section and also define the associativity of the operations
3. Mention the grammar productions and the action for each production.
4. $$ refer to the top of the stack position while $1 for the first value, $2 for the second value in
the stack.
5. Call yyparse() to initiate the parsing process.
6. yyerror() function is called when all productions in the grammar in second section doesn't
match to theinput statement.
 TO RECOGNISE A VALID VARIABLE WHICH STARTS WITH A
LETTER FOLLOWED BY ANY NUMBER OF LETTERS
ORDIGITS

PROGRAM :

variable_test.l

%{
/* This LEX program returns the tokens for the Expression */
#include "y.tab.h"
%}
%%
"int " {return INT;}
"float" {return FLOAT;}
"double" {return
DOUBLE;}
[a-zA-Z]*[0-9]*{
printf("\nIdentifier is
%s",yytext); return ID;
}
return yytext[0];
\n return
0; int
yywrap()
{
return 1;
}

variable_test.y

%{
#include
/* This YACC program is for recognising the Expression*/
%}
%token ID INT FLOAT DOUBLE
%%
D;
T
L
;
L:L
,ID
|ID
;
T:
IN
T
|FLOAT
|DOUBLE
;
%%
extern FILE
*yyin; main()

26
{
do
{
yyparse();
}while(!feof(yyin));
}
yyerror(char*s)
{
}
 OUTPUT:

RESULT:

Thus the program for the exercise on the syntax using YACC has been executedsuccessfully
and Output is verified.
Ex.No:3(c

) DATE:

RECOGNITION OF VALID CONTROL STRUCTURES

AIM:

To Program to recognize a valid control structures syntax of C language (For loop, while loop, if-else,
if-else-if, switch-case, etc.).

ALGORITHM:

1. Start the program.

2. Reading an input file line by line.
3. Convert it in to abstract syntax tree using three address codes.
4. Represent three address codes in the form of quadruple tabular form.
PROGRAM:
<int.l>

%{

"

"

<

d
i o

o =

. 1

h ;

> % }

# identif

i ier [a-

n zA-Z][_

c a-zA-Z0

l -9]*

u number

d [0-9]+|

e ([0-

< 9]*\.[0

s -9]+)

t %%

r m

i a

n i

g n

. \

h (

> \

i )

n r
t e
L t
i u
n r
e n
N M
A h

I i

N l

; e

i r

f e

r t

e u

t r

u n

r W

n H

I I

F L

; E

e ;

l i

s n

e t

r |

e char |

t float return TYPE;

u {identifier}

r {strcpy(yylva

n l.var,yytext)

E ; return

L VAR;}

S {number}

E {strcpy(yy

; lval.var,y

w ytext);
return

NUM;}

\< |

\> |

\>= |

\<= |

==

{st

rcp

y(y

ylv

al.

var

,yy

tex

t);

ret

urn

REL

OP;

}
[ \t] ;

\n LineNo++;

return

yytext[0];

%%

<int.y>

%{

#include<string

.h>

#include<stdio.

h> struct quad

char op[5];

char

arg1[10];

char

arg2[10];

char result[10];

}QUAD[30];

struct stack

int

items[100];

int top;

}stk;

int

Index=0,tIndex=0,StNo,Ind,tInd;

extern int LineNo;

%}

%union

{
 char var[10];

%token <var> NUM VAR RELOP

%token MAIN IF ELSE WHILE TYPE

%type <var> EXPR ASSIGNMENT CONDITION IFST ELSEST WHILELOOP

%left '-' '+'

%left '*' '/'

%%

PROGRAM : MAIN BLOCK

BLOCK: '{' CODE '}'

CODE: BLOCK

| STATEMENT CODE

| STATEMENT

STATEMENT: DESCT ';'

| ASSIGNMENT ';'

| CONDST

| WHILEST

DESCT: TYPE VARLIST

VARLIST: VAR ',' VARLIST

| VAR

ASSIGNMENT: VAR '=' EXPR{

strcpy(QUAD[Index].op,"=");

strcpy(QUAD[Index].arg1,$3)

strcpy(QUAD[Index].arg2,"")

strcpy(QUAD[Index].result,$

1);
strcpy($$,QUAD[Index++].result);

EXPR: EXPR '+' EXPR {AddQuadruple("+",$1,$3,$$);}

| EXPR '-' EXPR {AddQuadruple("-",$1,$3,$$);}

| EXPR '*' EXPR { AddQuadruple("*",$1,$3,$$);}

| EXPR '/' EXPR { AddQuadruple("/",$1,$3,$$);}

| '-' EXPR { AddQuadruple("UMIN",$2,"",$$);}

| '(' EXPR ')' {strcpy($$,$2);}

| VAR

| NUM

CONDST: IFST{

Ind=pop();

sprintf(QUAD[Ind].result,"%d",Index);

Ind=pop();

sprintf(QUAD[Ind].result,"%d",Index);

| IFST ELSEST

IFST: IF '(' CONDITION ')' {

strcpy(QUAD[Index].op,"==");

strcpy(QUAD[Index].arg1,$3);

strcpy(QUAD[Index].arg2,"FALSE"

); strcpy(QUAD[Index].result,"-

1"); push(Index);
Index++;

BLOCK {

strcpy(QUAD[Index].op,"GOTO");

strcpy(QUAD[Index].arg1,"");

strcpy(QUAD[Index].arg2,"");

strcpy(QUAD[Index].result,"-

1"); push(Index);

Index++;

};

ELSEST: ELSE{

tInd=pop

();

Ind=pop(

);

push(tIn

d);

sprintf(QUAD[Ind].result,"%d",Index);

BLO

CK{

Ind=pop();

sprintf(QUAD[Ind].result,"%d",Index);

};

CONDITION: VAR RELOP VAR

{AddQuadruple($2,$1,$3,$$); StNo=Index- 1;

| VAR

| NUM

WHILEST: WHILELOOP{
Ind=pop();

sprintf(QUAD[Ind].result,"%d",StN

o);
Ind=pop();

sprintf(QUAD[Ind].result,"%d",Inde

x);

WHILELOOP: WHILE '(' CONDITION ')' {

strcpy(QUAD[Index].op,"==");

strcpy(QUAD[Index].arg1,$3);

strcpy(QUAD[Index].arg2,"FALSE"

); strcpy(QUAD[Index].result,"-

1");

push(Index);Index++;
}

BLOCK {

strcpy(QUAD[Index].op,"GOTO

");

strcpy(QUAD[Index].arg1,"")

strcpy(QUAD[Index].arg2,"");

strcpy(QUAD[Index].result,"-

1"); push(Index);

Index++;

%%

extern FILE *yyin;

int main(int argc,char *argv[])

FILE

*fp;

int i;
if(argc

>1)

fp=fopen(argv[1],"r");
 (!fp)

printf("\n File not

found"); exit(0);

yyin=fp;

yyparse();

printf("\n\n\t\t ""\n\t\t
Pos Operator Arg1 Arg2 Result" "\n\t\t --------------------
");

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

printf("\n\t\t %d\t %s\t %s\t %s\t

%s",i,QUAD[i].op,QUAD[i].arg1,QUAD[i].arg2,QUAD[i].result);

printf("\n\t\t

"); printf("\n\n");

return 0;

}
void push(int data)

stk.top++;

if(stk.top==100)

printf("\n Stack overflow\n");

exit(0);

stk.items[stk.top]=data;

int pop()

int data;

if(stk.top==- 1)

printf("\n Stack underflow\n");

exit(0);

data=stk.items[stk.top--];return

data;

void AddQuadruple(char op[5],char arg1[10],char arg2[10],char

result[10])

strcpy(QUAD[Index].op,op);

strcpy(QUAD[Index].arg1,arg1);

strcpy(QUAD[Index].arg2,arg2);

sprintf(QUAD[Index].result,"t%d",tIndex++)

; strcpy(result,QUAD[Index++].result);
}

yyerror()

printf("\n Error on line no:%d",LineNo);

Input:
$vi test.c

main()

int a,b,c;

if(a<b)

a=a+b;

while(a<b)

{ a=a+b;

if(a<=b)

{ c=a- b;

else

{ c=a+b;

}
 OUTPUT:

$ lex int.l

$ yacc –d int.y

$ gcc lex.yy.c y.tab.c –ll –lm

$ ./a.out test.c

RESULT:

Thus the program for the exercise on the syntax using YACC has been executed
successfully and output is verified.
Ex.NO: 3(d)

DATE:

IMPLEMENTATION OF CALCULATOR USING LEX AND YACC

AIM:
To write a program to implement Calculator using LEX and YACC.

ALGORITHM:

Step 1: Start the program.

Step 2: In the declaration part of lex, includes declaration of regular definitions as digit.
Step 3: In the translation rules part of lex, specifies the pattern and its action that is to be executed
whenever alexeme matched by pattern is found in the input in the cal.l.
Step 4: By use of Yacc program,all the Arithmetic operations are done such as +,-,*,/.
Step 5: Display error is persist.
Step 6: Provide the
input. Step 7: Verify the
output.Step 8: End.
PROGRAM:

IMPLEMENTATION OF CALCULATOR USING LEX AND YACC

%{

#include<stdio

.h> int

op=0,i; float

a,b;

%}

dig[0-9]+|([0-9]*)"."([0-9]+)

add

"+"

sub

"-"

mul"

*"

div "/"

pow

"^"

ln

\n

%%

{dig}{digi();}

{add}{op=1;}

{sub}{op=2;}

{mul}{op=3;}

{div}{op=4;}

{pow}{op=5;}

{ln}{printf("\n the result:%f\n\n",a);}

%%

digi()

{
if(op==0)

a=atof(yytex

t);
else

b=atof(yytex

t);

switch(op)

case

1:a=a+b;

break;

case

2:a=a-b;

break;

case

3:a=a*b;

break;

case

4:a=a/b;

break;

case

5:for(i=a;b>1;b--)

a=a*i;

break;

op=0;

main(int argv,char *argc[])

yylex();

yywrap()
{

return 1;

}
 OUTPUT:

Lex cal.l

Cc lex.yy.c-lla.out

4*8

The result=32

RESULT:
Thus the program for the exercise on the syntax using YACC has been executed

Successfully and Output is verified.

Ex.NO: 4

DATE:

GENERATION OF THREE
AIM: ADDRESS CODE

To write a program to Generate three address code

for a simple program using LEX and YACC.

ALGORITHM:

Step1: Begin the program

Step2 : The expression is read from the file using a file pointer

Step3 : Each string is read and the total no. of strings in the file is calculated.

Step4: Each string is compared with an operator; if any operator is seen then the previous string

and

next string are concatenated and stored in a first temporary value and the three address code

expression is printed

Step5 : Suppose if another operand is seen then the first temporary value is concatenated to the next

string using the operator and the expression is printed.

Step6 : The final temporary value is replaced to the left operand value.

Step7 : End the program

PROGRAM:

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

struct three

{
char data[10],temp[7];

s[30];

void main() {
char d1[7],d2[7]="t";

int i=0,j=1,len=0;

FILE *f1,*f2;

clrscr();

f1=fopen("sum.txt","r");

f2=fopen("out.txt","w");

while(fscanf(f1,"%s",s[len].data)!=EOF

) len++;

itoa(j,d1,7);

strcat(d2,d1);

strcpy(s[j].temp,d2);

strcpy(d1,"");

strcpy(d2,"t");

if(!strcmp(s[3].data,"+")) {

fprintf(f2,"%s=%s+%s",s[j].temp,s[i+2].data,s[i+4].data)

; j++; }

else if(!strcmp(s[3].data,"-"))

fprintf(f2,"%s=%s-%s",s[j].temp,s[i+2].data,s[i+4].data)

; j++; }
for(i=4;i<len-2;i+=2)

itoa(j,d1,7);

strcat(d2,d1);

strcpy(s[j].temp,d2);

if(!strcmp(s[i+1].data,"+")

fprintf(f2,"\n%s=%s+%s",s[j].temp,s[j-1].temp,s[i+2].data);

else if(!strcmp(s[i+1].data,"-"))

fprintf(f2,"\n%s=%s-%s",s[j].temp,s[j-1].temp,s[i+2].data);

strcpy(d1,"");

strcpy(d2,"t");

j++; }

fprintf(f2,"\n%s=%s",s[0].data,s[j-1].temp);

fclose(f1);

fclose(f2);

getch();

}
 Input: sum.txt

out = in1 + in2 + in3 -

in4 Output : out.txt

t1=in1+in2

t2=t1+in

t3=t2-in4

out=t3

RESULT:

Thus a C program to generate a three address code for a given expression is written, executed and
the output is verified.
Ex.No: 5

DATE:

IMPLEMENTATION OF TYPE CHECKING

AIM:

To write a C program to implement type checking.

INTRODUCTION:

The type analysis and type checking is an important activity done in the semantic analysis
phase. The need for type checking is
1. To detect the errors arising in the expression due to incompatible operand.
2. To generate intermediate code for expressions due to incompatible operand

ALGORITHM:

1. Start the program for type checking of given expression

2. Read the expression and declaration
3. Based on the declaration part define the symbol table
4. Check whether the symbols present in the symbol table or not. If it is found in the symbol
table it displays“Label already defined”.
5. Read the data type of the operand 1, operand 2 and result in the symbol table.
6. If the both the operands’ type are matched then check for result variable. Else, print “Type mismatch”.
7. If all the data type are matched then displays “No type mismatch”.
PROGRAM: ( TYPE CHECKING)

#include<stdio.h>
char str[50],opstr[75];
int f[2][9]={2,3,4,4,4,0,6,6,0,1,1,3,3,5,5,0,5,0};
int
col,col1,col2;
char c;
swt()
{
switch(c)
{
case'+':col=0;bre
ak;
case'-':col=1;bre
ak;
case'*':col=2;bre
ak;
case'/':col=3;bre
ak;
case'^':col=4;bre
ak;
case'(':col=5;bre
ak;
case')':col=6;bre
ak;
case'd':col=7;bre
ak;
case'$':col=8;bre
ak;
default:printf("\nTERMINAL
MISSMATCH\n"); exit(1);
}
// return 0;
}
main()
{
int
i=0,j=0,col1,cn,k=0;
int t1=0,foundg=0;
char
temp[20];
clrscr();
printf("\nEnter arithmetic
expression:"); scanf("%s",&str);
while(str[i]!='\
0') i++;
str[i]='$';
str[++i]='\0';
 printf("%s\n",st
r); come:
i=0;
opstr[0]='
$'; j=1;
c='$';
swt();
col1=c
ol;
c=str[
i];
swt();
col2=c
ol;

if(f[1][col1]>f[2][col2])
{
opstr[j]='
>'; j++;
}
else if(f[1][col1]<f[2][col2])
{
o
p
s
}
t
else
r
{
[
j
}
]
=
'
<
'
;
j
+
+
;
 opstr[j]='=';j++;

while(str[i]!='$')
{
c=str[i];
swt();
col1=col
;
c=str[++
i];
swt();
col2=col
;
opstr[j]=str[--
i]; j++;
 if(f[0][col1]>f[1][col2])
{
opstr[j]='
>'; j++;
}
else if(f[0][col1]<f[1][col2])
{
opstr[j]='
<'; j++;
}
else
{
opstr[j]='=';j++;
}
i
+
+
;
}
opstr[j]='$';
opstr[++j]='\0';
printf("\nPrecedence
Input:%s\n",opstr); i=0;
j=0;
while(opstr[i]!='\0')
{
foundg=0;
while(foundg!
=1)
{
if(opstr[i]=='\0')goto
redone;
if(opstr[i]=='>')foundg=1;
t1=i;
i++;
}
if(foundg==1)
for(i=t1;i>0;i
--)
if(opstr[i]=='<')break;
 if(i==0){printf("\nERROR\n");exit(1
);}
cn
=
i
;
j
=
0
;
 i=t1+1;
while(opstr[i]!='\0')
{
temp[j]=opstr[
i]; j++;i++;
}
temp[j]='\0';
opstr[cn]='E';
opstr[++cn]='\0';
strcat(opstr,temp)
;
printf("\n%s",opst
r);
i=1;
}
redone:k=0;
while(opstr[k]!='\0')
{
k++;
if(opstr[k]=='<')
{
Printf("\nError
"); exit(1);
}
}
if((opstr[0]=='$')&&(opstr[2]=='$'))goto
sue; i=1
while(opstr[i]!='\0')
{
c=opstr[i];
if(c=='+'||c=='*'||c=='/'||c=='$')
{
temp[j]=c;j+
+;} i++;
}
temp[j]='\0';
strcpy(str,tem
p); goto come;
 sue:
printf("\n
success"); return
0;
}
OUTPUT:

RESULT:

Thus the program has been executed successfully and Output is verified.
Ex.No:6

DATE:

IMPLEMENTATION OF CODE OPTMIZATION

TECHNIQUES

AIM:

To write a C program to implement Simple Code Optimization Techniques.

ALGORITHM:

1. Read the un-optimized input block.

2. Identify the types of optimization
3. Optimize the input block
4. Print the optimized input block
5. Execute the same with different set of un-optimized inputs and obtain the optimized input block.

INTRODUCTION:

Optimization is a program transformation technique, which tries to improve the code by making it
consume less resource (i.e. CPU, memory) and deliver high speed.

In optimization, high-level general programming constructs are replaced by very efficient low level
programming codes. A code optimizing process must follow the three rules given below:

The output code must not, in any way, change the meaning of the program.

⮚ Optimization should increases the speed of the program and if possible, the program
should demand less number of resources.
⮚ Optimization should itself be fast and fast and should not delay the overall compiling
process.

Efforts for an optimized code can be made at various levels of compiling the process.
⮚ At the beginning, users can change/rearrange the code or use better algorithms to writethe
code.
⮚ After generating intermediate code, the compiler can modify the intermediate code by
address calculations and improving loops.
⮚ While producing the target machine code, the compiler can make use of memoryhierarchy
and cpu registers.
Optimization can be categorized broadly into two types: Machine independent and Machine dependent.
Machine independent optimization

In this optimization, the compiler takes in the intermediate code and transforms a part of the code that
does not involve any CPU registers and/or absolute memory locations.

For Example:
do

item=10; value=value+item;

} while(value<100);

This code involves repeated assignment of the identifier item, which if we put this way:

item=10;do

value=value+item;

}while(value<100);

Should not only save the cpu cycles, but can be used on any processor.

Machine dependent optimization

Machine dependent optimization is done after the target code has been generated and whenthe code is
transformed according to the target machine architecture. It involves CPU registers and may have
absolute memory references rather than relative references. Machine- dependent optimizers put
efforts to take maximum advantage of memory hierarchy.
PROGRAM: (SIMPLE CODE OPTIMIZATION TECHNIQUE)

Before

Using

for :

#include<iostream

.h> #include

<conio.h> int

main()

int i,

n; int

fact=1;

cout<<"\nEnter a number:

"; cin>>n;

for(i=n;i>=1;i--)
fact=fact *i;

cout<<"The factoral value is:

"<<fact; getch();

return 0;

}
OUTPUT:
After: (SIMPLE CODE OPTIMIZATION TECHNIQUE)

Using do-while:

#include<iostream.h>

#include<conio
.h> void
main()

clrscr
();
int
n,f;

f=1;

cout<<"Enter the

number:\n"; cin>>n;

do

f=f

*n;

n--

}while(n>0);

cout<<"The factorial value

is:"<<f; getch();

}
 OUTPUT:

RESULT:

Thus the Simple Code optimization technique is successfully executed

Ex.No: 7
DATE: IMPLEMENTATION OF BACK END OF THE 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.
INTRODUCTION:
A compiler is a computer program that implements a programming language specification to “translate”
programs, usually as a set of files which constitute the source code written in source language, into their
equivalent machine readable instructions(the target language, often having a binary form known as object
code). This translation process is called compilation.
BACK END:
⮚ Some local optimization
⮚ Register allocation
⮚ Peep-hole optimization
⮚ Code generation
⮚ Instruction scheduling
The main phases of the back end include the following:
⮚ Analysis: This is the gathering of program information from the intermediate representation
derived from the input; data-flow analysis is used to build use-define chains, together with
dependence analysis, alias analysis, pointer analysis, escape analysis etc.
⮚ Optimization: The intermediate language representation is transformed into functionally equivalent
but faster (or smaller) forms. Popular optimizations are expansion, dead, constant, propagation,
loop transformation, register allocation and even automatic parallelization.
⮚ Code generation: The transformed language is translated into the output language, usually the
native machine language of the system. This involves resource and storage decisions, such as
deciding which variables to fit into registers and memory and the selection and scheduling of
appropriate machine instructions along with their associated modes. Debug data may also need to
be generated to facilitate debugging.
ALGORITHM:

Step1: Get the input expression from the user.

Step2: The given expression is transformed into tokens.

Step3: Display the assembly code according to the operators present in the given expression.

Step4: Use the temporary registers (R0, R1) while storing the values in assembly code programs.
PROGRAM: (BACK END OF THE COMPILER)
#include<stdio

.h>

#include<stdio

.h>

//#include<conio

.h>

#include<string.

h> void main()

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();

}
OUTPUT:

RESULT:

Thus the program was implemented to the TAC has been successfully executed.
Ex.No:8

DATE:

CONSTRUCTION OF DAG

AIM:

To write a C program to construct DAG.

INTRODUCTION:

The code optimization is required to produce an efficient target code. These are two
importantissues that used to be considered while applying the techniques for code
optimization.
They are:
⮚ The semantics equivalences of the source program must not be changed.
⮚ The improvement over the program efficiency must be achieved without changing
thealgorithm.
ALGORITHM:

Step 1: Read the intermediate code as input from the file.

Step 2: Store the argument1 as left node and argument2 as right node.
Step 3:Attach the result variable to the root node of an expression.
Step4: Use the same node if the variable and values are same.
Step5: Finally construct the DAG
PROGRAM: (TO CONSTRUCT OF DAG(DIRECTED ACYCLIC GRAPH))

#include<stdio

.h> main()

{
struct da

int
ptr,left,right;
char label;

}dag[25];
int
ptr,l,j,change,n=0,i=0,state=1,x,y,k;
char store,*input1,input[25],var;
clrscr();

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

{
dag[i].ptr=NULL

dag[i].left=NUL

L;

dag[i].right=NU

LL;

dag[i].label=NU

LL;

}
printf("\n\nENTER THE

EXPRESSION\n\n"); scanf("%s",input1);

/*EX:((a*b-c))+((b-c)*d)) like this give with

paranthesis.limit is 25 char ucan change that*/

for(i=0;i<25;i

++)

input[i]=NULL;

l=strlen(input

1); a:
for(i=0;input1[i]!=')';i++);
for(j=i;input1[j]!='(';j--);

for(x=j+1;x<i;x++)

if(isalpha(input1[x]))

input[n++]=input1[x];
else

if(input1[x]!='

0')

store=input1[x]

input[n++]=stor

e;

for(x=j;x<=i;x+

+)

input1[x]='0';

if(input1[0]!='0')goto

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

{
dag[i].label=input[

i]; dag[i].ptr=i;

if(!isalpha(input[i])&&!isdigit(input[i]))
{

dag[i].right=i
-1; ptr=i;

var=input[i-1

];

if(isalpha(va

r))

ptr=ptr-2;

else

ptr=i

-1;

b:

if(!isalpha(var)&&!isdigit(var))

ptr=dag[ptr].le
ft;
var=input[ptr];
goto b;

else

ptr=ptr

-1;

}
dag[i].left=ptr;

printf("\n SYNTAX TREE FOR GIVEN EXPRESSION\n\n");

printf("\n\n PTR \t\t LEFT PTR \t\t RIGHT PTR \t\t LABEL
\n\n");

for(i=0;i<n;i++)/* draw the syntax tree for the following

output with pointer value*/

printf("\n
%d\t%d\t%d\t%c\n",dag[i].ptr,dag[i].left,dag[i].right,dag[i].l
a bel);

getch();

for(i=0;i<n;i

++)

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

if((dag[i].label==dag[j].label&&dag[i].left==dag[j].left)&&dag
[ i].right==dag[j].right)

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

if(dag[k].left==dag[j].ptr)dag[k].left=dag[i].ptr;

if(dag[k].right==dag[j].ptr)dag[k].right=dag[i].ptr;

} dag[j].ptr=dag[i].ptr;
}}}

printf("\n DAG FOR GIVEN EXPRESSION\n\n");

printf("\n\n PTR \t LEFT PTR \t RIGHT PTR \t LABEL \n\n");

for(i=0;i<n;i++)/*draw DAG for the following output with

pointer value*/

printf("\n %d
\t\t%d\t\t%d\t\t%c\n",dag[i].ptr,dag[i].left,dag[i].right,dag[
i
].label);

getch();

}
 OUTPUT:

RESULT:
Thus the program for implementation of DAG has been successfully executed and output is verified.
Ex.No:9

DATE:

IMPLEMENTATION OF STACK

AIM:

To implement a storage allocation using stack.

INTRODUCTION:
Storage Allocation
Runtime environment manages runtime memory requirements for the following entities:
⮚ Code: It is known as the part of a program that does not change at runtime. Its memory
requirements are at the compile time
⮚ Procedures: Their text part is static but they are called in a random manner. That is why, stack
storage is used to manage procedure calls and activations.
⮚ Variables: Variables are known at the runtime only, unless they are global or constant. Heap
memory allocation scheme is used for managing allocation and de-allocation of memory for
variables in runtime.

ALGORITHM:

Step 1: Get the size of the stack.

Step 2: Read the choice of operation.
Step 3: If the choice is 1push the items into the stack
1) To push the elements perform the following.
a) If the top of stack is equal to size of stack elements can’t be pushed.
b) Read item to be pushed.
c) Set or increment the top by one.
d) Assign the item to the stack [top].
e) Repeat the steps until it is required.
2) If choice is 2 pop the items from the stack
a) Check for empty stack.
b) Decrement the top by one.Return the popped item.
3) If choice is 3 display the contents of Stack.
PROGRAM:

#include

<stdio.h>

#include

<conio.h>

#include

<process.h>

#include

<alloc.h> struct

node

int label;
struct node *next;

};

void main()

int ch =

0; int

k;

struct node *h, *temp, *head;

head = (struct node*) malloc(sizeof(struct

node)); head->next = NULL;

while(1)

printf("\n Stack using Linked List

\n"); printf("1->Push ");

printf("2->Pop ");

printf("3->View");

printf("4->Exit

\n");

printf("Enter your choice :

"); scanf("%d", &ch);

switch(ch)

{
case 1:

temp=(struct node *)(malloc(sizeof(struct

node))); printf("Enter label for new node : ");

scanf("%d", &temp->label);

h = head;

temp->next =

h->next; h->next =

temp; break;

case 2:

h = head->next;

head->next = h->next;

printf("Node %s deleted\n",

h->label); free(h);

brea

k;

case

3:

printf("\n HEAD ->

"); h = head;

while(h->next != NULL)

h = h->next;

printf("%d -> ",h->label);

printf("NULL

\n"); break;

case

4:

exit(

0);

}
}}
OUTPUT:

RESULT:

Thus the program for implement storage allocation to use dynamic process for stack has
been successfully.