Lab Manual

for
Compiler Design

Regulation 2021
CS3501 – V Semester

ADHIPARASAKTHI ENGINEERING COLLEGE

Melmaruvathur, Chengalpet District- 603319.
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

GENERAL INSTRUCTION FOR LABORATORY

DO'S

 Get prior permission to enter the laboratory.

 Wear their ID cards and coats before entering the lab.
 The students should enter and exit the lab on time.
 Students should sign in to the login register before commencing their work in the lab.
 Students should bring the observation and record to the lab.
 Report any broken plugs or exposed electrical wires to the teacher immediately.
 Always save your progress.
 Always maintain an extra copy of all your data files.
 Make sure your external devices are virus-free.
 Feel free to ask for assistance.
 Behave properly.
 Students should maintain silence inside the lab.
 Turn off the machine when you are no longer using it.
 After completing the lab work, make sure to Shut down the system properly.

DONT'S

 Do not eat or drink inside the laboratory.

 Avoid stepping on electrical wires or any other computer cables.
 Do not insert metal objects such as clips, pins, and needles into the computer casings.
 Do not remove anything from the computer laboratory without permission.
 Do not touch, connect, or disconnect any plug or cable without permission.
 Do not touch any circuit boards or power sockets when something is connected to them or
switched.
 Do not open an external device without scanning it for computer viruses.
 Do not change the icons on the computer screen.
 Do not switch the keyboard letters around.
 Do not install any other programs unless it is mentioned in the curriculum.
 Do not unplug anything unless the computer has been properly shut down.
 Do not copy the work of other students.
 Do not attempt to repair, open, tamper with, or interfere with anything inside the lab.
 Do not plug in any other devices.
 Do not open the system unit casing or monitor casing, particularly when the power is turned
on (30,000 volts).
CS3501 COMPILER DESIGN LTPC
3 0 2 4

COURSE OBJECTIVES:
 To learn the various phases of compiler.
 To learn the various parsing techniques.
 To understand intermediate code generation and run-time environment.
 To learn to implement the front-end of the compiler.
 To learn to implement code generator.
 To learn to implement code optimization.

LIST OF EXPERIMENTS
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, the students should be able to:
CO1:Understand the techniques in different phases of a compiler.
CO2:Design a lexical analyser for a sample language and learn to use the LEX tool.
CO3:Apply different parsing algorithms to develop a parser and learn to use YACC tool
CO4:Understand semantics rules (SDT), intermediate code generation and run-time
environment.
CO5:Implement code generation and apply code optimization techniques.
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 the engineering practice.
9. Individual and team work: Function effectively as an individual, and as a member or
Leader in diverse teams, 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)
The Students will be able to
1. Exhibit design and programming skills to build and automate business solutions using
cutting edge technologies.
2. Strong theoretical foundation leading to excellence and excitement towards research, to
Provide elegant solutions to complex problems.
3. Ability to work effectively with various engineering fields as a team to design, build and
Develop system applications.

CO’s-PO’s & PSO’s MAPPING

CO’s PO’s PSO’s

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3
1 3 3 3 3 - - - - 3 3 1 3 2 3 2
2 3 3 3 3 3 - - - 3 2 3 2 2 1 2
3 3 3 2 2 3 - - - 3 1 1 1 2 2 3
4 3 2 2 1 1 - - - 2 3 2 3 1 2 1
5 3 3 3 2 1 - - - 2 1 1 3 2 1 2
AVg. 3.00 2.80 2.60 2.20 2.00 - - - 2.60 2.00 1.60 2.40 1.80 1.80 2.00

1 - low, 2 - medium, 3 - high, ‘-“- no correlation

 INDEX

Exp.no Name of the Experiments Page no

1A. IMPLEMENTATION OF LEXICAL ANALYZER 2
1B. IMPLEMENTATION OF SYMBOL TABLE 7

2. IMPLEMENTATION OF LEXICAL ANALYZER USING LEX 11

TOOL
3A. PROGRAM TO RECOGNIZE A VALID ARITHMETIC 18
EXPRESSION THAT USES OPERATOR +, - , * AND /.
PROGRAM TO RECOGNIZE A VALID VARIABLE WHICH
3B. STARTS WITH A LETTER FOLLOWED BY ANY NUMBER 24
OF LETTERS OR DIGITS.
PROGRAM TO RECOGNIZE A VALID CONTROL
3C. STRUCTURES SYNTAX OF C LANGUAGE (FOR LOOP, 28
WHILE LOOP, IF-ELSE, IF-ELSE-IF, SWITCH-CASE, ETC.).
3D. IMPLEMENTATION OF CALCULATOR USING LEX AND 34
YACC.
4. GENERATE THREE ADDRESS CODE USING LEX AND 39
YACC.
5. IMPLEMENT TYPE CHECKING 43

6. IMPLEMENTATION OF SIMPLE CODE OPTIMIZATION 48

TECHNIQUES
7. CONSTRUCTION OF DAG 52
8. IMPLEMENTATION OF BACKEND 58

1
EX. NO: 1A IMPLEMENTATION OF LEXICAL ANALYZER

Aim:
To write a C program to implement a lexical analyzer.

Algorithm:
1. Start the program.
2. Declare the file pointer and necessary variables.
3. Open the input file in the read mode.
4. Use the analyze function to analyze the input program and store the identifiers,
keywords and operators on idhd, keyhd and ophd respectively.
5. Stores the tokens in data structure linked lists.
6. Increment the line number of each token and its occurrences.
7. Using the show function print the linked lists in a tabular format.
8. Stop the program.

Program:
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <stdlib.h>

void main() {
char ipstr[300], temp, tmp[15], fname[50];
char parn[6] = {'(', ')', '{', '}', '[', ']'};
char symb[10] = {'.', ',', ':', ';', '<', '>', '?', '$', '#'};
char ops[6] = {'+', '-', '=', '/', '*', '^'};
char keywd[8][10] = {"main", "if", "else", "switch", "void", "do", "while", "for"};
char daty[6][10] = {"int", "char", "float", "double", "string", "longint"};
int pos = 0, i, j, k, flagi, ip;

2
FILE* fid;

printf("Enter the filename to be parsed: ");

scanf("%s", fname);

fid = fopen(fname, "r");

while ((ip = getc(fid)) != EOF) {
ipstr[pos++] = ip;
}
ipstr[pos] = '\0';

printf("%s\n", ipstr);
printf("\t\tLexical Analysis\n\n");

for (i = 0; ipstr[i] != '\0'; i++) {

if ((ipstr[i] != ' ') && (ipstr[i] != '\0') && (ipstr[i] != '@') && (ipstr[i] != '\n')) {
temp = ipstr[i];

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

if (temp == parn[j]) {
printf("\n%c \t Parenthesis", temp);
}
}

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

if (temp == symb[j]) {
printf("\n%c \t Symbol", temp);
}
}

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

if (temp == ops[j]) {
3
 printf("\n%c \t Operator", temp);
}
}

if (isdigit(ipstr[i])) {
k = 0;
while ((isdigit(ipstr[i]) || ipstr[i] == '.')) {
tmp[k++] = ipstr[i++];
}
tmp[k] = '\0';
i--;
printf("\n%s \t Number", tmp);
}

if (isalpha(ipstr[i])) {
k = 0;
while (isalpha(ipstr[i])) {
tmp[k++] = ipstr[i++];
}
tmp[k] = '\0';
i--;
flagi = 1;

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

if ((strcmp(tmp, keywd[j])) == 0) {
printf("\n%s \t Keyword", tmp);
flagi = 0;
break;
}
}

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

4
 if ((strcmp(tmp, daty[j])) == 0) {
printf("\n%s \t Data Type", tmp);
flagi = 0;
break;
}
}

if (flagi == 1) {
printf("\n%s \t Identifier", tmp);
}
}
}
}
}

5
Input:
Enter filename which is to parsed D:\cd.txt
Void main()
{
int a=b=c;
B=234;
}

Output:
Lexical analysis
Void keyword
Main keyword
{ Parenthesis
} parenthesis
int datatype
A identifiers
= operator
A identifiers
- identifiers
; symbol
B identifiers
= operator
234 number
; symbol

Result:
Thus, the C program to implement the lexical analyzer is executed and verified
successfully.
6
EX. NO: 1B IMPLEMENTATION OF SYMBOL TABLE

Aim:
To write a C program to implement a symbol table

Algorithm:
1. Start the program.
2. Define the structure of the symbol table.
3. Give the expression ending with the $ symbol.
4. Hence, entered expression is displayed.
5. Type of data is identified.
6. Data is stored in a symbol table.
7. Display the output.
8. Stop and execute the program.

Program:
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

void main() {
int i = 0, j = 0, x = 0, n, flag = 0;
void *p, *add[5];
char ch, srch, b[15], d[15], c;

printf("Expression terminated by $ : ");

while ((c = getchar()) != '$') {
b[i] = c;
7
 i++;
}
n = i - 1;

printf("Given Expression : ");

i = 0;
while (i <= n) {
printf("%c", b[i]);
i++;
}

printf("\nSymbol Table\n");
printf("Symbol\taddr\ttype");

while (j <= n) {
c = b[j];
if (isalpha(c)) {
if (j == n) {
p = malloc(1); // Allocate 1 byte for the address (assuming a single character
identifier)
add[x] = p;
d[x] = c;
printf("\n%c\t%p\tidentifier", c, p);
} else {
ch = b[j + 1];
if (ch == '+' || ch == '-' || ch == '*' || ch == '=') {
p = malloc(1); // Allocate 1 byte for the address (assuming a single character
identifier)
add[x] = p;
d[x] = c;
printf("\n%c\t%p\tidentifier", c, p);
x++;
8
 }
}
}
j++;
}

printf("\nThe symbol to be searched: ");

srch = getch();

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

if (srch == d[i]) {
printf("\nSymbol Found");
printf("\n%c @address %p\n", srch, add[i]);
flag = 1;
}
}

if (flag == 0)
printf("\nSymbol Not Found");
}

9
Input:
Expression Terminated by $: C+D+E$
Output:
Given expression: C+D+E
Symbol Table
Symbol address type
C 8130536 identifier
D 813616 identifier
E 813696 identifier

Result:
Thus, the C program to implement the symbol table is executed and verified
successfully.
10
EX. NO: 2 IMPLEMENTATION OF LEXICAL ANALYZER USING LEX TOOL

Aim:
To write a C program to implement a lexical analyzer using the Lex tool.

Algorithm:
1. Start the program.
2. Declare necessary variables and creates token representation using Regular.
3. Print the pre-processor, directives and keywords by analysis of the input program.
4. In the program, check whether there are arguments.
5. Declare a file and open it in read mode.
6. Read the file and if any taken in source program matches with RE that all returned as
integer value.
7. Print the token identified using the YYdex() function.
8. Stop the program.

Program:
%{
int COMMENT=0;
%}

identifier [a-z|A-Z][a-z|A-Z|0-9]*

%%

#.* {
printf("\n%s is a preprocessor directive", yytext);
}

int {
printf("\n\t%s is a keyword", yytext);

11
}
float {
printf("\n\t%s is a keyword", yytext);
}
double {
printf("\n\t%s is a keyword", yytext);
}
char {
printf("\n\t%s is a keyword", yytext);
}
if {
printf("\n\t%s is a keyword", yytext);
}
else {
printf("\n\t%s is a keyword", yytext);
}
while {
printf("\n\t%s is a keyword", yytext);
}
do {
printf("\n\t%s is a keyword", yytext);
}
return {
printf("\n\t%s is a keyword", yytext);
}
break {
printf("\n\t%s is a keyword", yytext);
}
continue {
printf("\n\t%s is a keyword", yytext);
}

12
void {
printf("\n\t%s is a keyword", yytext);
}
switch {
printf("\n\t%s is keyword", yytext);
}
for {
printf("\n\t%s is a keyword", yytext);
}
typedef {
printf("\n\t%s is a keyword", yytext);
}
struct {
printf("\n\t%s is a keyword", yytext);
}
goto {
printf("\n\t%s is a keyword", yytext);
}

"/*" {
COMMENT=1;
}
"*/" {
COMMENT=0;
}

{identifier}\( {
if (!COMMENT)
printf("\nFUNCTIONS\n\t%s", yytext);
}

\{ {
13
 if (!COMMENT)
printf("\nBLOCK BEGINS");
}

\} {
if (!COMMENT)
printf("\nBLOCK ENDS");
}

{identifier} {
if (!COMMENT)
printf("\n%s IDENTIFIER", yytext);
}

{identifier}(\[[0-9]*\])?\( {
if (!COMMENT)
printf("\n%s IDENTIFIER", yytext);
}

\".*\" {
if (COMMENT)
printf("\n\t%s is a string", yytext);
}

[0-9]+ {
if (COMMENT)
printf("\n\t%s is a number", yytext);
}

\)(\;)? {
if (!COMMENT) {
printf("\n\t");
14
 ECHO;
printf("\n");
}
}

\(ECHO;

={
if (!COMMENT)
printf("\n\t%s is an assignment operator", yytext);
}

\> {
if (!COMMENT)
printf("\n\t%s is a relational operator", yytext);
}

\< {
if (!COMMENT)
printf("\n\t%s is a relational operator", yytext);
}

.|\n ; // Default rule to catch any other characters or newlines

%%

int main() {
yylex();
printf("\n\n");
return 0;
}

15
int yywrap() {
return 0;
}

16
Output:
a<=b
a IDENTIFIER
<= is a relational operator
b IDENTIFIER

Result:
Thus, the C program to implement lexical analyzer using the Lex tool is executed and
verified successfully.

17
 PROGRAM TO RECOGNIZE A VALID ARITHMETIC EXPRESSION
EX. NO: 3A
THAT USES OPERATOR +, - , * AND /.

Aim:
To write a program to recognize a valid arithmetic expression that uses the operators
+, - , *and /.

Algorithm:
LEX
1. Declare the required header file and variable declaration with ‘%{‘ and ‘%}’.
2. LEX requires regular expressions to identify valid arithmetic expression tokens of
lexemes.
3. LEX calls the yywrap() function after input is over. It should return 1 when work is
done or 0 when more processing is required.
YACC
1. Declare the required header file and variable declaration with ‘%{‘ 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 is the first value, $2 is the second
value in the stack.
5. Call yyparse() to initiate the parsing process.
6. The yyerror() function is called when all productions in the grammar in the second
section don't match with the input statement.

Program:
LEX program
%{
#include "y.tab.h"
#include <math.h>
extern yylval;
%}

18
%%

[0-9]+ {
yylval = atoi(yytext);
return NUM;
}

[+] {
return '+';
}

[-] {
return '-';
}

[*] {
return '*';
}

[/] {
return '/';
}

[\t]+ ; // Ignore tabs

[\n] {
return 0; // Ignore newlines
}

.{
return yytext[0]; // Return any other character as is
}
19
%%

YACC program
%{
#include <stdio.h>
%}

%token NUM

%left '-' '+'

%right '*' '/'

%%

start: exp { printf("%d\n", $$); }

;

exp : exp '+' exp { $$ = $1 + $3; }

| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp {
if ($3 == 0) {
yyerror("Division by zero error");
} else {
$$ = $1 / $3;
}
}
| '(' exp ')' { $$ = $2; }
| NUM { $$ = $1; }
;

20
%%

int main() {
printf("Enter the expression in terms of integers:\n");
if (yyparse() == 0)
printf("Success\n");
return 0;
}

int yywrap() {
return 1;
}

void yyerror(char *s) {

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

Compile and run lex and yacc program

1. Process the yacc grammar file using the -d optional flag (which tells the yacc
command to create a file that defines the tokens used in addition to the C language
source code): yacc -d arith.yacc
2. Use the li command to verify that the following files were created:
y.tab.c The C language source file that the yacc command created for the parser.

y.tab.h A header file containing define statements for the tokens used by the parser.
3. Process the lex specification file:
lex arith.lex
4. Use the li command to verify that the following file was created:
lex.yy.c The C language source file that the lex command created for the lexical analyzer.
5. Compile and link the two C language source files:cc
y.tab.c lex.yy.c
6. Use the li command to verify that the following files were created:

21
 y.tab.h The object file for the y.tab.c source file
lex.yy.h The object file for the lex.yy.c source file
a.out The executable program file
7. To then run the program directly from the a.out file, enter: $ a.out

22
Output:
[client@fosserver.mm]$ lex arith.lex
[client@fosserver.mm]$ yacc -d arith.yacc
[client@fosserver.mm]$ cc y.tab.c lex.yy.c
[client@fosserver.mm]$ls
a.out calc.lex calc.yacc lex.yy.c y.tab.c y.tab.h
[client@fosserver.mm]$ ./a.out
Enter the expression in terms of integers
50+6*3
62
Success!

Result:
Thus, the program to recognize a valid arithmetic expression that uses the operators
+, - , * and / is executed and verified successfully.

23
 PROGRAM TO RECOGNIZE A VALID VARIABLE WHICH STARTS
EX. NO: 3B WITH A LETTER FOLLOWED BY ANY NUMBER OF LETTERS OR
DIGITS.

Aim:
To write a program to recognize a valid variable.

Algorithm:
1. Start the program.
2. In the Lex program, declare the identifier for memory.
3. Identify the identifier and return the ID to the parser.
4. In the yac program, declare the possible symbol types, which are the tokens which are
returned by Lex.
5. Define precedence and associativity.
6. Define the rule in CFG for non-terminal.
7. In main(), get the expression from user and print the output.
8. Stop the program.

Program:
YACC Program
%{
#include <stdio.h>
int valid = 1;
%}

%token digit letter

%%

start : letter ss
| letter s
| digit s

24
 | /* empty */
;

%%

int yyerror() {
printf("\nIt is not an identifier!\n");
valid = 0;
return 0;
}

int main() {
printf("\nEnter a name to test for identifier: ");
yyparse();
if (valid) {
printf("\nIt is an identifier!\n");
}
return 0;
}

LEX Program
%{
#include "y.tab.h"
%}

%%

[a-zA-Z] return letter;

[0-9] return digit;
. return yytext[0];
\n return 0;

25
%%

int yywrap() {
return 0;
}

26
Output:
Enter a name to tested for identifier@
It is not an identifier a
It is an identifier

Result:
Thus, the program to recognize a valid variable is executed and verified successfully.
27
 PROGRAM TO RECOGNIZE A VALID CONTROL STRUCTURES
EX. NO: 3C SYNTAX OF C LANGUAGE (FOR LOOP, WHILE LOOP, IF-ELSE,
IF-ELSE-IF, SWITCH-CASE, ETC.).

Aim:
To write a program to recognize a valid control structure syntax in the C language (for
loop, while loop, if-else, if-else-if, switch case, etc.).

Algorithm:
1. Take the C code as input.
2. Tokenize the input code. Split the code into individual tokens (keywords, identifiers,
operators, etc.) for easier processing.
3. Syntax Checking:
For Loop:
Check for tokens that match the pattern: for (initialization; condition; increment) {/*
code */} Ensure proper semicolons separate initialization, condition, and increment
parts. Recursively check the code inside the loop using the same steps.
While Loop:
Check for tokens that match the pattern. while (condition) {/* code */} Ensure proper
parentheses and braces. Recursively check the code inside the loop.
If-Else Statements:
Check for tokens that match the pattern: if (condition) {/* code */} else {/* code */}
Ensure proper parentheses and braces for both the if and else parts. Recursively check
the code inside both if and else blocks.
Else-If Ladder:
Check for tokens that match the pattern:
if (condition) { /* code */ } else if (condition) { /* code */ } ... else { /* code */ }
Ensure proper parentheses and braces for each if and else block. Recursively check
the code inside each block.
Switch-Case Statements:
Check for tokens that match the pattern:

28
 switch (variable) { case constant1: /* code */ break; case constant2: /* code */ break;
... default:/* code */ break; }
Ensure proper parentheses, colons after cases, and break statements. Recursively
check the code inside each case and default block.
4. If the code passes all syntax checks, output a message indicating that the control
structures are valid. Otherwise, indicate the specific error encountered during the
parsing process.

Program:

Lex Program : ex3c.l

%{
#include<stdio.h>
#include "ex3c.tab.h"
%}

%%
"if" { return IF; }
"else" { return ELSE; }
"while" { return WHILE; }
"for" { return FOR; }
"switch" { return SWITCH; }
"case" { return CASE; }
"default" { return DEFAULT; }
"break" { return BREAK; }
"(" { return OPEN_BRACKET; }
")" { return CLOSE_BRACKET; }
"{" { return OPEN_BRACE; }
"}" { return CLOSE_BRACE; }
";" { return SEMICOLON; }
[\t\n] ; // Ignore tabs and newlines
. ; // Ignore any other character

29
%%

int yywrap() {
return 1;
}

YACC Program: ex3c.y

%{
#include <stdio.h>
int yylex();
%}

%token IF ELSE WHILE FOR SWITCH CASE DEFAULT OPEN_BRACE

CLOSE_BRACE SEMICOLON BREAK

%%

program : statement
| program statement
;

statement : if_statement
| while_loop
| switch_case_statement
| for_loop
;

if_statement : IF OPEN_BRACKET expression_opt CLOSE_BRACKET OPEN_BRACE

expression_opt CLOSE_BRACE ELSE OPEN_BRACE expression_opt CLOSE_BRACE
{
printf("Recognized IF Else statement\n");
30
 }
;

while_loop : WHILE OPEN_BRACKET expression_opt CLOSE_BRACKET

OPEN_BRACE expression_opt CLOSE_BRACE
{
printf("Recognized WHILE loop\n");
}
;

switch_case_statement : SWITCH OPEN_BRACKET expression_opt CLOSE_BRACKET

OPEN_BRACE case_list CLOSE_BRACE
{
printf("Recognized SWITCH_CASE statement with DEFAULT\n");
}
;

for_loop : FOR OPEN_BRACKET expression_opt SEMICOLON expression_opt

CLOSE_BRACKET OPEN_BRACE expression_opt CLOSE_BRACE
{
printf("Recognized FOR loop\n");
}
;

case_list : CASE expression COLON expression BREAK SEMICOLON DEFAULT

COLON expression_opt
;

expression_opt : /*empty*/
| expression
| expression SEMICOLON
;
31
expression :
;

%%

int yyerror(const char *s) {

fprintf(stderr, "Error=%s\n", s);
return 1;
}

int main() {
if (yyparse() == 0) {
printf("Parsing completed successfully\n");
} else {
fprintf(stderr, "Parsing encountered errors\n");
}
return 0;
}

32
Output:
for(i=0;i<10;i++)
{
a=c+b
}
Recognized FOR loop
if(a<b)
{
a=a+b
}
else
{
a=a-b
}
Recognized IF ELSE statement

Result:
Thus, the program to recognize valid control structure syntax in the C language is
executed successfully.

33
EX. NO: 3D IMPLEMENTATION OF CALCULATOR USING LEX AND YACC

Aim:
To write a C program to implement a calculator using Lex and Yacc.

Algorithm:
1. Start the program.
2. In the Lex program, declare the identifier for log, cos, sin, tan and memory.
3. Identify the identifier and return the ID to the parser.
4. In the YAAC program, declare the possible symbol types, which are the tokens
returned by Lex.
5. Define precedence and associativity.
6. Define rule in CFG for nonterminal.
7. In main(), get the expression from the user and print the output.
8. Stop the program.

Program:
LEX Program
%{
#include <stdio.h>
#include "y.tab.h"
int c;
extern int yylval;
%}

%%

"" ; /* Skip whitespace */

[a-z] {
c = yytext[0];
34
 yylval = c - 'a';
return LETTER;
}

[0-9] {
c = yytext[0];
yylval = c - '0';
return DIGIT;
}

[^a-z0-9\b] {
c = yytext[0];
return c;
}

%%

YACC Program
%{
#include <stdio.h>
int regs[26];
int base;
%}

%start list
%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'
%left UMINUS /* supplies precedence for unary minus */

35
%%

list:
/* empty */
|
list stat '\n'
|
list error '\n' { yyerrok; }
;

stat:
expr { printf("%d\n", $1); }
|
LETTER '=' expr { regs[$1] = $3; }
;

expr:
'(' expr ')' { $$ = $2; }
|
expr '*' expr { $$ = $1 * $3; }
|
expr '/' expr { $$ = $1 / $3; }
|
expr '%' expr { $$ = $1 % $3; }
|
expr '+' expr { $$ = $1 + $3; }
|
expr '-' expr { $$ = $1 - $3; }
|
expr '&' expr { $$ = $1 & $3; }
|
expr '|' expr { $$ = $1 | $3; }
36
 |
'-' expr %prec UMINUS { $$ = -$2; }
|
LETTER { $$ = regs[$1]; }
|
number
;

number:
DIGIT { $$ = $1; base = ($1 == 0) ? 8 : 10; }
|
number DIGIT { $$ = base * $1 + $2; }
;

%%

int main() {
return yyparse();
}

void yyerror(char *s) {

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

int yywrap() {
return 1;
}

37
Output:
[client@fosserver.mm]$ lex calc.lex
[client@fosserver.mm]$ yacc -d calc.yacc
[client@fosserver.mm]$ cc y.tab.c lex.yy.c
[client@fosserver.mm]$ ls
a.out calc.lex calc.yacc lex.yy.c y.tab.c y.tab.h
[client@fosserver.mm]$ ./a.out 60*3
180
72+9
81

Result:
Thus, the program to implement a calculator using Lex and YACC is executed and
verified successfully.

38
EX. NO: 4 GENERATE THREE ADDRESS CODE USING LEX AND YACC

Aim:
To write a program to generate three address code using lex and yacc.

Algorithm:
1. Lex reads characters, categorizes digits as `NUM`, and treats all other characters
individually.
2. Lex matches input against predefined patterns (like digits for `NUM` tokens) and
generates corresponding tokens.
3. Lex passes identified tokens to Yacc, which validates their sequence and structure
using grammar rules.
4. Yacc defines grammar rules for expressions (e.g., arithmetic operations) and
specifies actions upon recognizing valid syntax.
5. Yacc generates intermediate code based on recognized grammar rules and input
tokens.
6. Lex detects lexical errors (unrecognized characters or patterns), while Yacc
identifies syntax errors and reports them.
7. The main program initiates parsing using `yyparse()`, coordinating Lex and Yacc to
process and validate input.
8. Lex and Yacc together convert human-readable input into structured tokens and
intermediate code, crucial for compiling and interpreting languages.

Program:
%{
#include <stdio.h>
#include "y.tab.h"
int k = 1;
%}

%%

39
[0-9]+ {
yylval.dval = yytext[0];
return NUM;
}

\n {
return 0;
}

.{
return yytext[0];
}
%%

void yyerror(char* str) {

printf("\n%s", str);
}

char* gencode(char word[], char first, char op, char second) {

char temp[10];
sprintf(temp, "%d", k);
strcat(word, temp);
k++;
printf("%s = %c %c %c\n", word, first, op, second);
return word; // Returns variable name like t1, t2, t3... properly
}

int yywrap() {
return 1;
}

int main() {
40
 yyparse();
return 0;
}

41
Input:
(2+3)*5

Output:
t1= 2 + 3
t2= t1 * 5

Result:
Thus, the program to generate three address codes using Lex and YACC is executed
and verified successfully.
42
EX. NO: 5 IMPLEMENT TYPE CHECKING

Aim:
To write a program to implement type checking.

Algorithms:
1. Start the Program.
2. In this program, the given expression is checked and its type is expressed.
3. Initialize values and convert them into corresponding tokens. The obtained tokens are
given as input for the YACC program.
4. Enter the expression of your choice; if it’s correct, then it displays valid information
or else part will be executed.
5. Print the desired output.
6. Stop the program.

Program:
LEX Program
%{
#include <stdio.h>
#include "y.tab.h"
extern int yylval;
%}

%%

[0-9]+ {
yylval = atoi(yytext);
return NUMBER;
}
[\t] ;
[\n] return 0;

43
. return yytext[0];

%%

int yywrap() {
return 1;
}

YACC Program
%{
#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 {
44
 $$ = $1 * $3;
}
| E '/' E {
if ($3 == 0) {
yyerror("Division by zero");
} else {
$$ = $1 / $3;
}
}
| E '%' E {
$$ = $1 % $3;
}
| '(' E ')' {
$$ = $2;
}
| NUMBER {
$$ = $1;
}
;

%%

void main() {
printf("\n Enter any arithmetic expression which can have operations: Addition,
Subtraction, Multiplication, Division, 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");
45
 flag = 1;
}

46
Output:
[client@fosserver.mm]$lex int.lex
[client@fosserver.mm]$yacc –d int.yacc
[client@fosserver.mm]$cc lex.yy.c y.tab.c
[client@fosserver.mm]$./a.out
Enter Any Arithmetic Expression which can have operations Addition, Subtraction,
Multiplication, Divison, Modulus and Round brackets
4+5
Result=9
Entered arithmetic expression is Valid

Result:
Thus, the program to implement type checking is executed and verified successfully.

47
 IMPLEMENTATION OF SIMPLE CODE OPTIMIZATION
EX. NO: 6
TECHNIQUES

Aim:
To write a C program to implement simple code optimization techniques.

Algorithms:
1. Read the unoptimized input block.
2. Identify the types of optimization.
3. Optimize the input block.
4. Print the optimized input block.
5. Execute the same with a different set of unoptimized inputs and obtain the optimized
input block.

Program:
#include <stdio.h>
#include <conio.h>
#include <ctype.h>

void main() {
char a[25][25], u, op1 = '*', op2 = '+', op3 = '/', op4 = '-';
int p, q, r, l, o, ch, i = 1, c, k, j, count = 0;
FILE *fi, *fo;
printf("Enter three address code\n");
printf("Enter the ctrl-z to complete:\n");
fi = fopen("infile.txt", "w");
while ((c = getchar()) != EOF)
fputc(c, fi);
fclose(fi);
printf("\nUnoptimized input block\n");
fi = fopen("infile.txt", "r");
while ((c = fgetc(fi)) != EOF) {
48
 k = 1;
while (c != ';' && c != EOF) {
a[i][k] = c;
printf("%c", a[i][k]);
k++;
c = fgetc(fi);
}
printf("\n");
i++;
}
count = i;
fclose(fi);
printf("\nOptimized three address code\n");
i = 1;
while (i < count) {
if (strcmp(a[i][4], &op1) == 0 && strcmp(a[i][5], &op1) == 0) {
printf("\ntype 1 reduction in strength");
if (strcmp(&a[i][6], "2") == 0) {
for (j = 1; j <= 4; j++)
printf("%c", a[i][j]);
printf("%c", a[i][3]);
}
} else if (isdigit(a[i][3]) && isdigit(a[i][5])) {
printf("\ntype 2 constant folding");
p = a[i][3] - '0';
q = a[i][5] - '0';
if (strcmp(&a[i][4], &op1) == 0)
r = p * q;
if (strcmp(&a[i][4], &op2) == 0)
r = p + q;
if (strcmp(&a[i][4], &op3) == 0)
r = p / q;
49
 if (strcmp(&a[i][4], &op4) == 0)
r = p - q;
for (j = 1; j <= 2; j++)
printf("%c", a[i][j]);
printf("%d\n", r);
} else if (strcmp(&a[i][5], "0") == 0 || strcmp(&a[i][5], "1") == 0) {
printf("\ntype 3 algebraic expression elimination");
if ((strcmp(&a[i][4], &op1) == 0 && strcmp(&a[i][5], "1") == 0) ||
(strcmp(&a[i][4], &op3) == 0 && strcmp(&a[i][5], "1") == 0)) {
for (j = 1; j <= 3; j++)
printf("%c", a[i][j]);
printf("\n");
} else {
printf("\nsorry cannot optimize\n");
}
} else {
printf("\nError input\n");
}
i++;
}
getch();
}

50
Output:

Result:
Thus, the C program for the implementation of code optimization was executed
successfully.
51
EX. NO: 7 CONSTRUCTION OF DAG

Aim:
To write a C program to construct DAG.

Algorithms:
1. Read the intermediate code as input from the file.
2. Store argument 1 as a left node and argument 2 as a right node.
3. Attach the result variable to the root node of an expression.
4. Use the same node if the variables and values are same.
5. Finally, construct the DAG.

Program:
#include<stdio.h>
#include <conio.h>

struct node {
struct node *next;
char id[10];
char left[10];
char right[10];
char attach[3][10];
};

struct node *head;

FILE *f;
int i, s = 0;
char str[25], store[10][25];

void construct_tree() {
struct node *temp;
52
struct node *t;
struct node *ptr;
int flag = 0, f1 = 0;
temp = head;
if (s == 5 || s == 6) {
while (temp->next != NULL) {
if (!strcmp(store[2], temp->next->left))
flag += 1;
if (!strcmp(store[4], temp->next->right))
flag += 2;
if (flag != 0)
break;
temp = temp->next;
}
t = head;
while (t->next != NULL)
t = t->next;
if (flag == 0) {
ptr = (struct node*)malloc(sizeof(struct node));
t->next = ptr;
if (s == 5)
strcpy(ptr->id, store[3]);
else
strcpy(ptr->id, strcat(store[3], store[5]));
t = head;
while (t->next != NULL) {
if (!strcmp(t->next->attach[0], store[2])) {
f1 = 1;
break;
}
if (strcmp(t->next->attach[1], "") != 0) {
if (!strcmp(t->next->attach[1], store[2])) {
53
 f1 = 1;
break;
}
}
t = t->next;
}
if (f1)
strcpy(ptr->left, t->next->id);
else
strcpy(ptr->left, store[2]);
f1 = 0;
t = head;
while (t->next != NULL) {
if (!strcmp(t->next->attach[0], store[4])) {
f1 = 1;
break;
}
if (strcmp(t->next->attach[1], "") != 0) {
if (!strcmp(t->next->attach[1], store[4])) {
f1 = 1;
break;
}
}
t = t->next;
}
if (f1)
strcpy(ptr->right, t->next->id);
else
strcpy(ptr->right, store[0]);
strcpy(ptr->attach[1], "");
ptr->next = NULL;
} else if (flag == 3) {
54
 while (temp->next != NULL) {
if (!strcmp(store[2], temp->next->attach[0]))
break;
temp = temp->next;
}
strcpy(temp->next->attach[1], store[0]);
}
}
}

int main() {
struct node *temp;
clrscr();
f = fopen("C:\\DAG.txt", "r");
head = (struct node*)malloc(sizeof(struct node));
head->next = NULL;
while (!feof(f)) {
fscanf(f, "%s", str);
if (!strcmp(str, ";")) {
construct_tree();
s = 0;
} else
strcpy(store[s++], str);
}
printf("\n\nID\tLEFT\tRIGHT\tATTACHED IDs\n\n");
temp = head;
while (temp->next != NULL) {
printf("\n\n%s\t%s\t%s\t%s\t", temp->next->id,
temp->next->left, temp->next->right, temp->next->attach[0]);
if (strcmp(temp->next->attach[1], ""))
printf("\t%s", temp->next->attach[1]);
temp = temp->next;
55
 }
getch();
return 0;
}

56
Input:
t1=4*i;
t2=a[t1];
t3=4*i;
t4=b[t3];
t5=t2*t4;
t6=prod+t5;
prod=t6;
t7=i+1;
i=t7;
Output:
ID LEFT RIGHT ATTACHED IDs
* 4 I t1 t3
[] a * t2
[] b * t4
* [] [] t5
+ prod * t6 prod
+ I t7 i

Result:
Thus, the program for the construction of DAG is executed and verified.

57
EX. NO: 8 IMPLEMENTATION OF BACKEND

Aim:
To write a ‘C’ program to generate the machine code for the given intermediate code.

Algorithm:
1. Get the input expression from the user.
2. The given expression is transformed into tokens.
3. Display the assembly code according to the operators present in the given
expression.
4. Use the temporary registers (R0, R1) while storing the values in assembly code
programs.

Program:
#include<stdio.h>
#include<string.h>
#include<ctype.h>

int count = 0, i = 0, l = 0;
char str[100][100];

void gen();

void main()
{
printf("\n CODE GENERATOR \n");
printf("\n ENTER THREE ADDRESS CODE \n\n");

do
{
printf("\t");
58
 gets(str[i]);
i++;
} while(strcmp(str[i-1], "QUIT") != 0);
i = 0;
printf("\n ASSEMBLY LANGUAGE CODE: \n");
while(strcmp(str[i-1], "QUIT") != 0)
{
gen();
printf("\n");
i++;
}
printf("\n PRESS ENTER TO EXIT FROM CODE GENERATOR\n");
getchar();
}

void gen()
{
int j;
printf("\n");

for(j = strlen(str[i]) - 1; j >= 0; j--)

{
char reg = 'R';

if(isdigit(str[i][j]) || (isalpha(str[i][j])) || str[i][j] == '+' || str[i][j] == '-' ||

str[i][j] == '*' || str[i][j] == '/' || str[i][j] == ' ' || str[i][j] == '|' ||
str[i][j] == '&' || str[i][j] == ':' || str[i][j] == '=')
{
switch(str[i][j])
{
case '+':
printf("\n\t MOV\t%c,%c%d", str[i][j-1], reg, count);
59
 printf("\n\t ADD\t%c,%c%d", str[i][j+1], reg, count);
break;
case '-':
printf("\n\t MOV\t%c,%c%d", str[i][j-1], reg, count);
printf("\n\t SUB\t%c,%c%d", str[i][j+1], reg, count);
break;
case '*':
printf("\n\t MOV\t%c,%c%d", str[i][j-1], reg, count);
printf("\n\t MUL\t%c,%c%d", str[i][j+1], reg, count);
break;
case '/':
printf("\n\t MOV\t%c,%c%d", str[i][j-1], reg, count);
printf("\n\t DIV\t%c,%c%d", str[i][j+1], reg, count);
break;
case '|':
printf("\n\t MOV\t%c,%c%d", str[i][j-1], reg, count);
printf("\n\t OR\t%c,%c%d", str[i][j+1], reg, count);
break;
case '&':
printf("\n\t MOV\t%c,%c%d", str[i][j-1], reg, count);
printf("\n\t AND\t%c,%c%d", str[i][j+1], reg, count);
break;
case ':':
if(str[i][j+1] == '=')
{
printf("\n\t MOV\t%c%d,%c", reg, count, str[i][j-1]);
count++;
}
else
{
printf("\n syntax error...\n");
}
60
 break;
default:
break;
}
}
else
{
printf("\n Error\n");
}
break;
}
}

61
Output:
CODE GENERATION
ENTER THE THREE ADDRESS CODE
A:=B+C
D:=E/F
QUIT
ASSEMBLY LANGUAGE CODE:
MOV B,R0
ADD C,R0
MOV R0,A
MOV E,R1
DIV F,R1
MOV R1,D
PRESS ENTER TO EXIT FROM CODE GENERATOR

Result:
Thus, the program for the generation of machine code for the given intermediate code
is executed and verified.

62