PRANVEER SINGH INSTITUTE OF TECHNOLOGY, KANPUR

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Even Semester 2024-25

B. Tech.- Third Year

Semester- VI

Lab File
Complier Design Lab
(BCS652)

Submitted To : Submitted By :
Faculty Name : Name :
Designation : Roll No. :
Section :
 Table of Contents
 Vision and Mission Statements of the Institute

 Vision and Mission Statements of the Department

 PEOs, POs, PSOs of the Department

 Course Objective and Outcomes

 List of Experiments

 Index
 Department Vision Statement
To be a recognized Department of Computer Science & Engineering that produces versatile computer
engineers, capable of adapting to the changing needs of computer and related industry.

Department Mission Statements

The mission of the Department of Computer Science and Engineering is:

i. To provide broad based quality education with knowledge and attitude to succeed in Computer
Science & Engineering careers.

ii. To prepare students for emerging trends in computer and related industry.

iii. To develop competence in students by providing them skills and aptitude to foster culture of
continuous and lifelong learning.

iv. To develop practicing engineers who investigate research, design, and find workable solutions to
complex engineering problems with awareness & concern for society as well as environment.

Program Educational Objectives (PEOs)

i. The graduates will be efficient leading professionals with knowledge of computer science &
engineering discipline that enables them to pursue higher education and/or successful careers in various
domains.

ii. Graduates will possess capability of designing successful innovative solutions to real life problems
that are technically sound, economically viable and socially acceptable.

iii. Graduates will be competent team leaders, effective communicators and capable of working in
multidisciplinary teams following ethical values.

iv. The graduates will be capable of adapting to new technologies/tools and constantly upgrading their
knowledge and skills with an attitude for lifelong learning
 Department Program Outcomes (POs)
The students of Computer Science and Engineering Department will be able:

1. Engineering knowledge: Apply the knowledge of mathematics, science, Computer 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 Computer Science & Engineering sciences.

3. Design/development of solutions: Design solutions for complex Computer Science &

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. Investigation: 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 modelling to complex Computer Science &
Engineering activities with an understanding of the limitations.

6. The Engineering 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 in the field of Computer Science and Engineering.

7. Environment and sustainability: Understand the impact of the professional Computer Science
& 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 Computer Science & 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 Computer Science & 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 Computer
Science & 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.
 Department Program Specific Outcomes (PSOs)
The students will be able to:

1. Use algorithms, data structures/management, software design, concepts of programming

languages and computer organization and architecture.

2. Understand the processes that support the delivery and management of information systems
within a specific application environment.

Course Outcomes
*Level of Bloom’s Level to be met
*Level of Bloom’s Taxonomy Level to be met Taxonomy
L1: Remember 1 L2: Understand 2
L3: Apply 3 L4: Analyze 4
L5: Evaluate 5 L6: Create 6

CO Number Course Outcomes

Ability to understand [1. Knowledge] different phases and passes of Compiler and recognize
BCS-652.1
different types of tokens by Lex tool.

Ability to observe [2. Comprehension] language translation by designing Parser generator of

BCS-652.2
a given language using YACC tool.

BCS-652.3 Construction [3. Application] of LL, SLR, CLR and LALR parse table.
List of Experiments
 INDEX
S Lab Experiment Date of Date of Marks Faculty
No Experiment Submission Signature
0

10
 Experiment No. 1

Objective: Design and implement a lexical analyzer for given language using C and the lexical analyzer
should ignore redundant spaces, tabs and new lines.
Code:
#include <stdio.h> // For standard input/output functions
#include <stdlib.h> // For file handling functions
#include <string.h> // For string operations like strcmp()
#include <ctype.h> // For character handling functions like isdigit(), isalpha()

// Function to check if a given word is a keyword or an identifier

void keyword(char str[10]) {
// Comparing the input string with predefined keywords
if (strcmp("for", str) == 0 || strcmp("while", str) == 0 || strcmp("do", str) == 0 ||
strcmp("int", str) == 0 || strcmp("float", str) == 0 || strcmp("char", str) == 0 ||
strcmp("double", str) == 0 || strcmp("static", str) == 0 || strcmp("switch", str) == 0 ||
strcmp("case", str) == 0 || strcmp("if", str) == 0 || strcmp("else", str) == 0 ||
strcmp("return", str) == 0 || strcmp("break", str) == 0 || strcmp("continue", str) == 0) {
printf("\n%s is a keyword", str); // Print if it is a keyword
} else {

printf("\n%s is an identifier", str); // Otherwise, it's an identifier

}
}

int main() {
FILE *f1, *f2, *f3; // File pointers for input, identifiers, and special characters
char c, str[10]; // Character variables to read input and store words
int num[100]; // Array to store numbers
int lineno = 1; // Line number counter, starts at 1
int tokenvalue = 0; // Variable to store numeric values
int i = 0, j = 0, k = 0; // Index variables

// Prompt user to enter a C program

printf("\nEnter the C program (Press Ctrl+Z to stop input):\n");

// Open a file named "input.txt" in write mode to store user input

f1 = fopen("input.txt", "w");
if (f1 == NULL) {
printf("Error opening file!\n");
return 1; // Exit if file opening fails
}

// Read input character by character and write it to "input.txt"

while ((c = getchar()) != EOF) {
putc(c, f1);
}
fclose(f1); // Close the file

// Open "input.txt" in read mode

f1 = fopen("input.txt", "r");
f2 = fopen("identifier.txt", "w"); // Open file to store identifiers
 f3 = fopen("specialchar.txt", "w"); // Open file to store special characters

// Check if any file opening failed

if (f1 == NULL || f2 == NULL || f3 == NULL) {
printf("Error opening files!\n");

return 1; // Exit the program if file operations fail

}

// Read each character from "input.txt"

while ((c = getc(f1)) != EOF) {
// Check if character is a digit (0-9)
if (isdigit(c)) {
tokenvalue = c - '0'; // Convert character to integer
c = getc(f1);
// Read additional digits to form a complete number
while (isdigit(c)) {
tokenvalue = tokenvalue * 10 + (c - '0');
c = getc(f1);
}
num[i++] = tokenvalue; // Store the number in the array
ungetc(c, f1); // Push back the last read character
}
// Check if character is an alphabet (A-Z or a-z)

else if (isalpha(c)) {
putc(c, f2); // Write the character to "identifier.txt"
c = getc(f1);
// Continue reading characters if they are letters, digits, _ or $
while (isalnum(c) || c == '_' || c == '$') {
putc(c, f2);
c = getc(f1);
}
putc(' ', f2); // Add a space to separate identifiers
ungetc(c, f1); // Push back the last read character
}
// Ignore spaces and tabs
else if (c == ' ' || c == '\t') {
continue;
}
// If a newline is encountered, increment line counter
else if (c == '\n') {
lineno++;
}
// If it is a special character, store it in "specialchar.txt"
else {
putc(c, f3);
}
}

// Close all files after processing input

fclose(f2);
fclose(f3);
fclose(f1);
// Print numbers detected in the input
 printf("\nThe numbers in the program are: ");
for (j = 0; j < i; j++) {
printf("%d ", num[j]);
}
printf("\n");

// Open "identifier.txt" to process identifiers and keywords

f2 = fopen("identifier.txt", "r");
k = 0;
printf("The keywords and identifiers are:\n");

// Read characters from the identifier file and check for keywords
while ((c = getc(f2)) != EOF) {
if (c != ' ') {
str[k++] = c; // Store characters in the buffer
} else {
str[k] = '\0'; // Terminate the string
keyword(str); // Check if it's a keyword or identifier
k = 0; // Reset buffer index
}
}
fclose(f2);

// Open "specialchar.txt" to display special characters

f3 = fopen("specialchar.txt", "r");

printf("\nSpecial characters are: ");

while ((c = getc(f3)) != EOF) {
printf("%c ", c); // Print each special character
}
printf("\n");
fclose(f3);

// Print the total number of lines in the input program

printf("\nTotal number of lines: %d\n", lineno);

return 0; // Exit program

}
INPUT:

OUTPUT:
 Experiment No. 2
Objective : Implementation of Lexical Analyzer using Lex Tool

%{
#include<stdio.h>
%}

%%
if |
else |
printf {printf("\n%s is a keyword", yytext);}
[0-9]+ {printf("\n%s is a number", yytext);}
[a-zA-Z]+ {printf("\n%s is a word", yytext);}
.|\n {ECHO;}
%%

int main()
{
printf("\n Enter the string: ");
yylex();
}
int yywrap()
{
return 1;
}
OUTPUT:
 Experiment No. 3
Objective : Construct a recursive descent parser for an expression grammer.

CODE:

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

char input[10];
int i = 0;

void E();
void E_();

int main() {
printf("Enter the input string: ");
scanf("%s", input);

E(); // Start parsing with the starting symbol E

if (input[i] == '$') {
printf("Parsing Successful!\n");
} else {
printf("Error: Unexpected symbol '%c' at position %d\n", input[i], i);
}

return 0;
}

void E() {
if (input[i] == 'i') {
i++;
E_();
} else {
printf("Error: Expected 'i'\n");
exit(1);
}

void E_() {
if (input[i] == '+') {
i++;
if (input[i] == 'i') {
i++;
E_();
} else {
printf("Error: Expected 'i' after '+'\n");
exit(1);
}
}
// else epsilon (do nothing)
}
OUTPUT:
 Experiment No. 4
Objective : Write program to find Simulate First and Follow of given grammar.

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

// Functions to calculate Follow

void followfirst(char, int, int);
void follow(char c);

// Function to calculate First

void findfirst(char, int, int);

int count, n = 0;

// Stores the final result

// of the First Sets
char calc_first[10][100];

// Stores the final result

// of the Follow Sets
char calc_follow[10][100];

int m = 0;

// Stores the production rules

char production[10][10];
char f[10], first[10];
int k;
char ck;
int e;

int main(int argc, char **argv)

{
int jm = 0;
int km = 0;
int i, choice;
char c, ch;
count = 8;

// The Input grammar

strcpy(production[0], "E=TR");
strcpy(production[1], "R=+TR");
strcpy(production[2], "R=#");
strcpy(production[3], "T=FY");
strcpy(production[4], "Y=*FY");
strcpy(production[5], "Y=#");
strcpy(production[6], "F=(E)");
strcpy(production[7], "F=i");

int kay;
char done[count];
int ptr = -1;

// Initializing the calc_first array

for(k = 0; k < count; k++) {
for(kay = 0; kay < 100; kay++) {
calc_first[k][kay] = '!';
}
}
int point1 = 0, point2, z;

for(k = 0; k < count; k++)

{
c = production[k][0];
point2 = 0;
z = 0;

// Checking if First of c has

// already been calculated
for(kay = 0; kay <= ptr; kay++)
if(c == done[kay])
z = 1;

if (z == 1)
continue;

// Function call
findfirst(c, 0, 0);
ptr += 1;

// Adding c to the calculated list

done[ptr] = c;
printf("\n First(%c) = { ", c);
calc_first[point1][point2++] = c;

// Printing the First Sets of the grammar

for(i = 0 + jm; i < n; i++) {
int lark = 0, chk = 0;

for(lark = 0; lark < point2; lark++) {

if (first[i] == calc_first[point1][lark])
{
chk = 1;
break;
}
}
if(chk == 0)
{
printf("%c, ", first[i]);
calc_first[point1][point2++] = first[i];
}
}
 printf("}\n");
jm = n;
point1++;
}
printf("\n");
printf("-----------------------------------------------\n\n");
char donee[count];
ptr = -1;

// Initializing the calc_follow array

for(k = 0; k < count; k++) {
for(kay = 0; kay < 100; kay++) {
calc_follow[k][kay] = '!';
}
}
point1 = 0;
int land = 0;
for(e = 0; e < count; e++)
{
ck = production[e][0];
point2 = 0;
z = 0;

// Checking if Follow of ck
// has already been calculated
for(kay = 0; kay <= ptr; kay++)
if(ck == donee[kay])
z = 1;

if (z == 1)
continue;
land += 1;

// Function call
follow(ck);
ptr += 1;

// Adding ck to the calculated list

donee[ptr] = ck;
printf(" Follow(%c) = { ", ck);
calc_follow[point1][point2++] = ck;

// Printing the Follow Sets of the grammar

for(i = 0 + km; i < m; i++) {
int lark = 0, chk = 0;
for(lark = 0; lark < point2; lark++)
{
if (f[i] == calc_follow[point1][lark])
{
chk = 1;
break;
}
}
if(chk == 0)
{
 printf("%c, ", f[i]);
calc_follow[point1][point2++] = f[i];
}
}
printf(" }\n\n");
km = m;
point1++;
}
}

void follow(char c)
{
int i, j;

// Adding "$" to the follow

// set of the start symbol
if(production[0][0] == c) {
f[m++] = '$';
}
for(i = 0; i < 10; i++)
{
for(j = 2;j < 10; j++)
{
if(production[i][j] == c)
{
if(production[i][j+1] != '\0')
{

// Non-Terminal in the production

followfirst(production[i][j+1], i, (j+2));
}

if(production[i][j+1]=='\0' && c!=production[i][0])

{
// Calculate the follow of the Non-Terminal
// in the L.H.S. of the production
follow(production[i][0]);
}
}
}
}
}

void findfirst(char c, int q1, int q2)

{
int j;

// The case where we

// encounter a Terminal
if(!(isupper(c))) {
first[n++] = c;
}

for(j = 0; j < count; j++)

 {
if(production[j][0] == c)
{
if(production[j][2] == '#')
{
if(production[q1][q2] == '\0')
first[n++] = '#';
else if(production[q1][q2] != '\0'
&& (q1 != 0 || q2 != 0))
{
// Recursion to calculate First of New
// Non-Terminal we encounter after epsilon
findfirst(production[q1][q2], q1, (q2+1));
}
else
first[n++] = '#';
}
else if(!isupper(production[j][2]))
{
first[n++] = production[j][2];
}
else
{
// Recursion to calculate First of
// New Non-Terminal we encounter
// at the beginning
findfirst(production[j][2], j, 3);
}
}}

void followfirst(char c, int c1, int c2)

{
int k;

// The case where we encounter

// a Terminal
if(!(isupper(c)))
f[m++] = c;
else
{
int i = 0, j = 1;
for(i = 0; i < count; i++)
{
if(calc_first[i][0] == c)
break;
}

//Including the First set of the

// Non-Terminal in the Follow of
// the original query
while(calc_first[i][j] != '!')
{
 if(calc_first[i][j] != '#')
{
f[m++] = calc_first[i][j];
}
Else

{
if(production[c1][c2] == '\0')
{
// Case where we reach the
// end of a production
follow(production[c1][0]);
}
else
{
// Recursion to the next symbol
// in case we encounter a "#"
followfirst(production[c1][c2], c1, c2+1);
}
}
j++;
}
}
}
OUTPUT:
 Experiment No. 5

Objective: Construct a Shift Reduce Parser for a given language

Code:

#include<stdio.h>
#include<string.h>
#define TSIZE 128
// If the input is jth non-terminal, table[i][j] retains the index of production that must be applied to the ith
variable.
int table[100][TSIZE];
// keeps a complete list of terminals
//When using the ASCII value to index terminals, terminal[i] = 1 indicates that the character has an ASCII
value.
char terminal[TSIZE];

// only saves the list of terminals that begin with the upper case letters "A" through "Z."
//Non-terminal[i] denotes that the grammar is non-terminal and the alphabet is present.
char non-terminal[26];
// structure to hold each production
// str[] stores the production
// len is the length of production
struct product {
char str[100];
int len;

}pro[20];
// no of productions in form A->ß
int no_pro;
char first[26][TSIZE];
char follow[26][TSIZE];
// stores first of each production in form A->ß
char first_rhs[100][TSIZE];
// check if the symbol is non-terminal
int isNT(char c) {
return c >= 'A' && c <= 'Z';
}
// reading data from the file
void readFromFile() {
FILE* fptr;
fptr = fopen("text.txt", "r");
char buffer[255];
int i;
int j;
while (fgets(buffer, sizeof(buffer), fptr)) {
printf("%s", buffer);
j = 0;
non-terminal[buffer[0] - 'A'] = 1;
for (i = 0; i<strlen(buffer) - 1; ++i) {
if (buffer[i] == '|') {
++no_pro;
pro[no_pro - 1].str[j] = '\0';
pro[no_pro - 1].len = j;
pro[no_pro].str[0] = pro[no_pro - 1].str[0];
pro[no_pro].str[1] = pro[no_pro - 1].str[1];
pro[no_pro].str[2] = pro[no_pro - 1].str[2];
j = 3;
}
else {
pro[no_pro].str[j] = buffer[i];
++j;
if (!isNT(buffer[i]) && buffer[i] != '-' && buffer[i] != '>') {
terminal[buffer[i]] = 1;
}
}
}
pro[no_pro].len = j;
++no_pro;
} }

void add_FIRST_A_to_FOLLOW_B(char A, char B) {

int i;
for (i = 0; i< TSIZE; ++i) {
if (i != '^')
follow[B - 'A'][i] = follow[B - 'A'][i] || first[A - 'A'][i];
}
}
void add_FOLLOW_A_to_FOLLOW_B(char A, char B) {
int i;
for (i = 0; i< TSIZE; ++i) {
if (i != '^')
follow[B - 'A'][i] = follow[B - 'A'][i] || follow[A - 'A'][i];
}
}
void FOLLOW() {
int t = 0;

int i, j, k, x;
while (t++ <no_pro) {
for (k = 0; k < 26; ++k) {
if (!non-terminal[k]) continue;
char nt = k + 'A';
for (i = 0; i<no_pro; ++i) {
for (j = 3; j < pro[i].len; ++j) {
if (nt == pro[i].str[j]) {
for (x = j + 1; x < pro[i].len; ++x) {
char sc = pro[i].str[x];
if (isNT(sc)) {
add_FIRST_A_to_FOLLOW_B(sc, nt);
if (first[sc - 'A']['^'])
continue;
}
else {
follow[nt - 'A'][sc] = 1;
}
break;
 }
if (x == pro[i].len)
add_FOLLOW_A_to_FOLLOW_B(pro[i].str[0], nt);
}
}
}
}
}
}
void add_FIRST_A_to_FIRST_B(char A, char B) {
int i;
for (i = 0; i< TSIZE; ++i) {
if (i != '^') {
first[B - 'A'][i] = first[A - 'A'][i] || first[B - 'A'][i];
}
}
}

void FIRST() {
int i, j;

int t = 0;
while (t <no_pro) {
for (i = 0; i<no_pro; ++i) {
for (j = 3; j < pro[i].len; ++j) {
char sc = pro[i].str[j];
if (isNT(sc)) {
add_FIRST_A_to_FIRST_B(sc, pro[i].str[0]);
if (first[sc - 'A']['^'])
continue;
}
else {
first[pro[i].str[0] - 'A'][sc] = 1;
}
break;
}
if (j == pro[i].len)
first[pro[i].str[0] - 'A']['^'] = 1;
}
++t;
}
}
void add_FIRST_A_to_FIRST_RHS__B(char A, int B) {

int i;
for (i = 0; i< TSIZE; ++i) {
if (i != '^')
first_rhs[B][i] = first[A - 'A'][i] || first_rhs[B][i];
}
}
// Calculates FIRST(ß) for each A->ß
void FIRST_RHS() {
int i, j;
int t = 0;
while (t <no_pro) {
 for (i = 0; i<no_pro; ++i) {
for (j = 3; j < pro[i].len; ++j) {
char sc = pro[i].str[j];
if (isNT(sc)) {
add_FIRST_A_to_FIRST_RHS__B(sc, i);
if (first[sc - 'A']['^'])
continue;
}
else {
first_rhs[i][sc] = 1;
}
break;
}
if (j == pro[i].len)
first_rhs[i]['^'] = 1;
}
++t;
} }

int main() {
readFromFile();

follow[pro[0].str[0] - 'A']['$'] = 1;
FIRST();
FOLLOW();
FIRST_RHS();
int i, j, k;

// display first of each variable

printf("\n");
for (i = 0; i<no_pro; ++i) {
if (i == 0 || (pro[i - 1].str[0] != pro[i].str[0])) {
char c = pro[i].str[0];
printf("FIRST OF %c: ", c);
for (j = 0; j < TSIZE; ++j) {
if (first[c - 'A'][j]) {
printf("%c ", j);
}
}
printf("\n");
}
}

// display follow of each variable

printf("\n");
for (i = 0; i<no_pro; ++i) {
if (i == 0 || (pro[i - 1].str[0] != pro[i].str[0])) {
char c = pro[i].str[0];
printf("FOLLOW OF %c: ", c);
for (j = 0; j < TSIZE; ++j) {

if (follow[c - 'A'][j]) {
printf("%c ", j);
}
}
printf("\n");
}
}
// display first of each variable ß
// in form A->ß
printf("\n");
for (i = 0; i<no_pro; ++i) {
printf("FIRST OF %s: ", pro[i].str);
for (j = 0; j < TSIZE; ++j) {
if (first_rhs[i][j]) {
printf("%c ", j);
}
}
printf("\n");
}
// the parse table contains '$'
// set terminal['$'] = 1
// to include '$' in the parse table
terminal['$'] = 1;

// the parse table do not read '^'

// as input

// so we set terminal['^'] = 0
// to remove '^' from terminals
terminal['^'] = 0;

// printing parse table

printf("\n");
printf("\n\t**************** LL(1) PARSING TABLE *******************\n");
printf("\t--------------------------------------------------------\n");
printf("%-10s", "");
for (i = 0; i< TSIZE; ++i) {
if (terminal[i]) printf("%-10c", i);
}
printf("\n");
int p = 0;
for (i = 0; i<no_pro; ++i) {
if (i != 0 && (pro[i].str[0] != pro[i - 1].str[0]))
p = p + 1;
for (j = 0; j < TSIZE; ++j) {
if (first_rhs[i][j] &&j != '^') {
table[p][j] = i + 1;
}
else if (first_rhs[i]['^']) {
for (k = 0; k < TSIZE; ++k) {
if (follow[pro[i].str[0] - 'A'][k]) {
table[p][k] = i + 1;
}
}
}
}
}
k = 0;
for (i = 0; i<no_pro; ++i) {
 if (i == 0 || (pro[i - 1].str[0] != pro[i].str[0])) {
printf("%-10c", pro[i].str[0]);

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

if (table[k][j]) {
printf("%-10s", pro[table[k][j] - 1].str);
}
else if (terminal[j]) {
printf("%-10s", "");
}
}
++k;
printf("\n");
}
}
}
OUTPUT: