Meerut Institute of Technology, Meerut

Department of Computer Science &

Engineering
(Affiliated to DR. A.P.J KALAM TECHNICAL UNIVERSITY LUCKNOW)

PRACTICAL FILE
COMPUTER SCIENCE AND ENGINEERING
COMPILER DESIGN LAB
(BCS-652)
[Link]. VITH SEMESTER

Under the Supervision: Name: Sonu Kumar

Ms. Srishti Agarwal Roll No.: 2202920100110

(Assistant Professor)

Session (2024-2025)
 MEERUT INSTITUTE OF TECHNOLOGY, MEERUT
Department of Computer Science & Engineering
Compiler Design Lab (BCS – 652)
List of Experiments

Lab Problem Statement DATE SIGNATURE

No.
1. Write program to minimize any given DFA.

2. Write program to make a NFA from a regular expression.

3. Write program to find whether a given grammar is left

recursive or not.

4. Write program to find whether a given grammar is left

factored or not

5. Write program to find Simulate First and Follow of any given

grammar.

6. Design and implement a lexical analyzer for given language

using C .

7. A program for backtrack parser for the

grammar-S -> cAd, A ->a/ab

8. Construct a Shift Reduce Parser for a given language.

9. Construct a recursive descent parser for an expression.

10. Implement Intermediate code generation for simple expressions

11. Write a program to perform loop unrolling

12. Write a program to perform constant propagation.

1. Write program to minimize any given DFA.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX 20

int n_states, n_symbols;

int transi on[MAX][MAX];

int final_states[MAX], n_final;

int minimized[MAX][MAX];

int state_map[MAX];

int is_final(int state) {

for (int i = 0; i < n_final; i++)

if (final_states[i] == state)

return 1;

return 0;

void minimize_DFA() {

int dis nguishable[MAX][MAX] = {0};

for (int i = 0; i < n_states; i++) {

for (int j = 0; j < i; j++) {

if (is_final(i) != is_final(j)) {

dis nguishable[i][j] = 1;

int changed = 1;

while (changed) {

changed = 0;

for (int i = 0; i < n_states; i++) {

for (int j = 0; j < i; j++) {

if (!dis nguishable[i][j]) {
 for (int sym = 0; sym < n_symbols; sym++) {

int = transi on[i][sym];

int tj = transi on[j][sym];

if ( == tj) con nue;

int a = > tj ? : tj;

int b = > tj ? tj : ;

if (dis nguishable[a][b]) {

dis nguishable[i][j] = 1;

changed = 1;

break;

for (int i = 0; i < n_states; i++)

state_map[i] = i;

for (int i = 0; i < n_states; i++) {

for (int j = 0; j < i; j++) {

if (!dis nguishable[i][j]) {

state_map[i] = state_map[j];

break;

int new_states = 0;

int new_state_index[MAX];

for (int i = 0; i < n_states; i++)

new_state_index[i] = -1;

for (int i = 0; i < n_states; i++) {

 int rep = state_map[i];

if (new_state_index[rep] == -1)

new_state_index[rep] = new_states++;

prin ("\nMinimized DFA:\n");

prin ("States: %d\n", new_states);

prin ("Transi ons:\n");

for (int i = 0; i < n_states; i++) {

int from = new_state_index[state_map[i]];

if (from == -1) con nue;

for (int sym = 0; sym < n_symbols; sym++) {

int to = transi on[i][sym];

int new_to = new_state_index[state_map[to]];

prin ("δ(%d, %c) -> %d\n", from, 'a' + sym, new_to);

prin ("Final States: ");

int printed[MAX] = {0};

for (int i = 0; i < n_final; i++) {

int f = final_states[i];

int rep = new_state_index[state_map[f]];

if (!printed[rep]) {

prin ("%d ", rep);

printed[rep] = 1;

prin ("\n");

int main() {

prin ("Enter number of states: ");

scanf("%d", &n_states);
 prin ("Enter number of input symbols: ");

scanf("%d", &n_symbols);

prin ("Enter transi on table (δ(state, symbol) = next state):\n");

for (int i = 0; i < n_states; i++) {

for (int j = 0; j < n_symbols; j++) {

prin ("δ(%d, %c) = ", i, 'a' + j);

scanf("%d", &transi on[i][j]);

prin ("Enter number of final states: ");

scanf("%d", &n_final);

prin ("Enter final states: ");

for (int i = 0; i < n_final; i++)

scanf("%d", &final_states[i]);

minimize_DFA();

return 0;

Output:

Input:

Enter number of states: 4

Enter number of input symbols: 2

Enter transi on table:

δ(0, a) = 1

δ(0, b) = 2

δ(1, a) = 0

δ(1, b) = 3

δ(2, a) = 3

δ(2, b) = 0

δ(3, a) = 2

δ(3, b) = 1
Enter number of final states: 1

Enter final states: 3

Output:

Minimized DFA:

States: 3

Transi ons:

δ(0, a) -> 1

δ(0, b) -> 2

δ(1, a) -> 0

δ(1, b) -> 2

δ(2, a) -> 2

δ(2, b) -> 1

Final States: 2
2. Write program to make a NFA from a regular expression.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX 100

typedef struct State {

int id;

struct State *edge1;

struct State *edge2;

char symbol;

} State;

typedef struct NFA {

State *start;

State *end;

} NFA;

int state_id = 0;

State* new_state(char symbol, State *edge1, State *edge2) {

State *s = (State*)malloc(sizeof(State));

s->id = state_id++;

s->symbol = symbol;

s->edge1 = edge1;

s->edge2 = edge2;

return s;

NFA create_basic(char symbol) {

State *end = new_state(0, NULL, NULL);

State *start = new_state(symbol, end, NULL);

NFA nfa = {start, end};

return nfa;

NFA create_concat(NFA n1, NFA n2) {

 [Link]->symbol = 0;

[Link]->edge1 = [Link];

NFA nfa = {[Link], [Link]};

return nfa;

NFA create_union(NFA n1, NFA n2) {

State *start = new_state(0, [Link], [Link]);

State *end = new_state(0, NULL, NULL);

[Link]->symbol = 0;

[Link]->edge1 = end;

[Link]->symbol = 0;

[Link]->edge1 = end;

NFA nfa = {start, end};

return nfa;

NFA create_star(NFA n) {

State *start = new_state(0, [Link], NULL);

State *end = new_state(0, NULL, NULL);

[Link]->symbol = 0;

[Link]->edge1 = end;

start->edge2 = end;

NFA nfa = {start, end};

return nfa;

NFA build_nfa(char *regex) {

NFA stack[MAX];

int top = -1;

for (int i = 0; regex[i]; i++) {

char c = regex[i];

if (c == '*') {

NFA n = stack[top--];
 stack[++top] = create_star(n);

} else if (c == '.') {

NFA n2 = stack[top--];

NFA n1 = stack[top--];

stack[++top] = create_concat(n1, n2);

} else if (c == '|') {

NFA n2 = stack[top--];

NFA n1 = stack[top--];

stack[++top] = create_union(n1, n2);

} else {

stack[++top] = create_basic(c);

return stack[top];

void print_nfa(State *s, int visited[]) {

if (!s || visited[s->id]) return;

visited[s->id] = 1;

if (s->edge1) {

prin ("q%d --%c--> q%d\n", s->id, s->symbol ? s->symbol : 'ε', s->edge1->id);

print_nfa(s->edge1, visited);

if (s->edge2) {

prin ("q%d --%c--> q%d\n", s->id, s->symbol ? s->symbol : 'ε', s->edge2->id);

print_nfa(s->edge2, visited);

int main() {

char regex[MAX];

prin ("Enter pos ix regex: ");

scanf("%s", regex);
 NFA nfa = build_nfa(regex);

int visited[MAX] = {0};

prin ("Transi ons:\n");

print_nfa([Link], visited);

prin ("Start state: q%d\n", [Link]->id);

prin ("Accept state: q%d\n", [Link]->id);

return 0;

Output:

Input:

ab.

Output:

Transi ons:

q0 --a--> q1

q1 --ε--> q2

q2 --b--> q3

Start state: q0

Accept state: q3
3. Write program to find whether a given grammar is le recursive or not.

#include <stdio.h>

#include <string.h>

#define MAX 10

int main() {

int n;

char prod[MAX][20];

prin ("Enter number of produc ons: ");

scanf("%d", &n);

prin ("Enter produc ons (Format: A->Aa|b):\n");

for (int i = 0; i < n; i++) {

scanf("%s", prod[i]);

for (int i = 0; i < n; i++) {

char non_terminal = prod[i][0];

int is_le _recursive = 0;

char *rhs = strchr(prod[i], '>') + 1;

char *token = strtok(rhs, "|");

while (token != NULL) {

if (token[0] == non_terminal) {

is_le _recursive = 1;

break;

token = strtok(NULL, "|");

if (is_le _recursive)

prin ("Produc on %s is le recursive\n", prod[i]);

else

prin ("Produc on %s is not le recursive\n", prod[i]);

return 0;
}

Output:

Input:

Enter number of produc ons: 2

Enter produc ons (Format: A->Aa|b):

A->Aa|b

B->Ba|a

Output:

Produc on A->Aa|b is le recursive

Produc on B->Ba|a is le recursive

4. Write program to find whether a given grammar is le factored or not.

#include <stdio.h>

#include <string.h>

#define MAX 10

int main() {

int n;

char prod[MAX][50];

prin ("Enter number of produc ons: ");

scanf("%d", &n);

prin ("Enter produc ons (Format: A->ab|ac|d):\n");

for (int i = 0; i < n; i++) {

scanf("%s", prod[i]);

for (int i = 0; i < n; i++) {

char *rhs = strchr(prod[i], '>') + 1;

char *parts[MAX];

int count = 0, le _factored = 0;

char *token = strtok(rhs, "|");

while (token != NULL) {

parts[count++] = token;

token = strtok(NULL, "|");

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

for (int k = j + 1; k < count; k++) {

int len = strlen(parts[j]) < strlen(parts[k]) ? strlen(parts[j]) : strlen(parts[k]);

int match = 0;

for (int m = 0; m < len; m++) {

if (parts[j][m] == parts[k][m]) match++;

else break;

if (match > 0) {
 le _factored = 1;

break;

if (le _factored) break;

if (le _factored)

prin ("Produc on %s is not le factored\n", prod[i]);

else

prin ("Produc on %s is le factored\n", prod[i]);

return 0;

Output:

Input:

Enter number of produc ons: 2

Enter produc ons (Format: A->ab|ac|d):

A->ab|ac|d

B->x|y

Output:

Produc on A->ab|ac|d is not le factored

Produc on B->x|y is le factored

5. Write program to find Simulate First and Follow of any given grammar.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#define MAX 20

char produc on[MAX][MAX];

char firstResult[MAX][MAX];

char followResult[MAX][MAX];

int n;

int isNonTerminal(char c) {

return c >= 'A' && c <= 'Z';

void addToSet(char *set, char c) {

if (!strchr(set, c)) {

int len = strlen(set);

set[len] = c;

set[len + 1] = '\0';

void computeFirst(char symbol, char *result);

void first(char *alpha, char *result) {

if (alpha[0] == '\0') return;

if (!isNonTerminal(alpha[0])) {

addToSet(result, alpha[0]);

return;

for (int i = 0; i < n; i++) {

if (produc on[i][0] == alpha[0]) {

if (produc on[i][3] == '\0') con nue;

if (produc on[i][3] == '#') {

 if (alpha[1] != '\0')

first(alpha + 1, result);

else

addToSet(result, '#');

} else {

char temp[MAX] = "";

first(&produc on[i][3], temp);

for (int k = 0; temp[k]; k++) {

if (temp[k] == '#') {

if (alpha[1] != '\0')

first(alpha + 1, result);

else

addToSet(result, '#');

} else {

addToSet(result, temp[k]);

void computeFirst(char symbol, char *result) {

char temp[2] = {symbol, '\0'};

first(temp, result);

void computeFollow(char symbol, char *result) {

if (symbol == produc on[0][0]) {

addToSet(result, '$');

for (int i = 0; i < n; i++) {

char *rhs = strchr(produc on[i], '>') + 1;

 for (int j = 0; rhs[j]; j++) {

if (rhs[j] == symbol) {

if (rhs[j + 1] != '\0') {

char temp[MAX] = "";

first(rhs + j + 1, temp);

for (int k = 0; temp[k]; k++) {

if (temp[k] != '#')

addToSet(result, temp[k]);

else {

if (produc on[i][0] != symbol)

computeFollow(produc on[i][0], result);

} else {

if (produc on[i][0] != symbol)

computeFollow(produc on[i][0], result);

int main() {

prin ("Enter number of produc ons: ");

scanf("%d", &n);

prin ("Enter produc ons (e.g. A->aB or A-># for epsilon):\n");

for (int i = 0; i < n; i++) {

scanf("%s", produc on[i]);

for (int i = 0; i < n; i++) {

char nonTerminal = produc on[i][0];

if (strchr(firstResult[nonTerminal - 'A'], nonTerminal) == NULL) {

 computeFirst(nonTerminal, firstResult[nonTerminal - 'A']);

for (int i = 0; i < n; i++) {

char nonTerminal = produc on[i][0];

if (strchr(followResult[nonTerminal - 'A'], nonTerminal) == NULL) {

computeFollow(nonTerminal, followResult[nonTerminal - 'A']);

prin ("\nFIRST sets:\n");

for (int i = 0; i < n; i++) {

char nt = produc on[i][0];

if (i == 0 || produc on[i][0] != produc on[i - 1][0])

prin ("FIRST(%c) = { %s }\n", nt, firstResult[nt - 'A']);

prin ("\nFOLLOW sets:\n");

for (int i = 0; i < n; i++) {

char nt = produc on[i][0];

if (i == 0 || produc on[i][0] != produc on[i - 1][0])

prin ("FOLLOW(%c) = { %s }\n", nt, followResult[nt - 'A']);

return 0;

Output:

Input:

Enter number of produc ons: 4

Enter produc ons:

S->AB

A->aA

A->#

B->bB
Output:

FIRST sets:

FIRST(S) = { a }

FIRST(A) = { a, # }

FIRST(B) = { b }

FOLLOW sets:

FOLLOW(S) = { $ }

FOLLOW(A) = { b }

FOLLOW(B) = { $ }
6. Design and implement a lexical Analyzer for given language using C.

#include <stdio.h>

#include <ctype.h>

#include <string.h>

char keywords[][10] = {

"int", "float", "char", "if", "else", "while", "for", "return", "void", "main"

};

int isKeyword(char *word) {

for (int i = 0; i < 10; i++) {

if (strcmp(keywords[i], word) == 0)

return 1;

return 0;

int main() {

char ch, buffer[100];

FILE *fp;

int i, j = 0;

fp = fopen("[Link]", "r");

if (fp == NULL) {

prin ("File not found.\n");

return 0;

while ((ch = fgetc(fp)) != EOF) {

if (isalnum(ch)) {

buffer[j++] = ch;

} else {

buffer[j] = '\0';

j = 0;

if (strlen(buffer) > 0) {

if (isKeyword(buffer))
 prin ("%s : keyword\n", buffer);

else if (isalpha(buffer[0]))

prin ("%s : iden fier\n", buffer);

else

prin ("%s : constant\n", buffer);

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

prin ("%c : operator\n", ch);

else if (ch == ';' || ch == ',' || ch == '(' || ch == ')' || ch == '{' || ch == '}')

prin ("%c : symbol\n", ch);

fclose(fp);

return 0;

Output:

Input:

int main() {

int a = 5 + 10;

float b = 3.14;

Output:

int : keyword

main : iden fier

( : symbol

) : symbol

{ : symbol

int : keyword

a : iden fier

= : operator

5 : constant
+ : operator

10 : constant

; : symbol

float : keyword

b : iden fier

= : operator

3 : constant

. : symbol

14 : constant

; : symbol

} : symbol
7. A program for backtrack parser for the grammar-S -> cAd, A ->a/ab.

#include <stdio.h>

#include <string.h>

char input[100];

int pos = 0;

int A();

int S();

int match(char expected) {

if (input[pos] == expected) {

pos++;

return 1;

return 0;

int A() {

int saved_pos = pos;

if (match('a')) {

if (match('b')) {

return 1;

return 1;

pos = saved_pos;

return 0;

int S() {

int saved_pos = pos;

if (match('c')) {

if (A()) {

if (match('d')) {

return 1;
 }

pos = saved_pos;

return 0;

int main() {

prin ("Enter input string: ");

scanf("%s", input);

if (S() && input[pos] == '\0')

prin ("String is accepted by the grammar.\n");

else

prin ("String is rejected by the grammar.\n");

return 0;

Output:

Input:

S → cAd

A → a | ab

Output:

Accepted Strings (Examples):

 cad → matches c + a + d

 cabd → matches c + ab + d

Rejected Strings (Examples):

 cd → missing a or ab

 cbad → A rule fails

 cadx → extra character a er valid input

8. Construct a Shi Reduce Parser for a given language.

#include <stdio.h>

#include <string.h>

char input[100];

char stack[100];

int top = -1, ip = 0;

void push(char c) {

stack[++top] = c;

void pop() {

top--;

void display() {

for (int i = 0; i <= top; i++)

prin ("%c", stack[i]);

prin ("\t%s\n", input + ip);

int isReducible() {

if (top >= 2 && stack[top - 2] == 'E' && stack[top - 1] == '+' && stack[top] == 'E')

return 1;

if (top >= 2 && stack[top - 2] == 'E' && stack[top - 1] == '*' && stack[top] == 'E')

return 2;

if (top >= 2 && stack[top - 2] == '(' && stack[top - 1] == 'E' && stack[top] == ')')

return 3;

if (top >= 1 && stack[top - 1] == 'i' && stack[top] == 'd')

return 4;

return 0;

void reduce(int rule) {

if (rule == 1 || rule == 2) {

top -= 2;
 stack[top] = 'E';

prin ("Reduce by E -> E %c E\n", (rule == 1 ? '+' : '*'));

} else if (rule == 3) {

top -= 2;

stack[top] = 'E';

prin ("Reduce by E -> ( E )\n");

} else if (rule == 4) {

top -= 1;

stack[top] = 'E';

prin ("Reduce by E -> id\n");

int main() {

prin ("Enter input (e.g., id+id*id): ");

scanf("%s", input);

prin ("Stack\tInput\n");

while (1) {

display();

int reduced = 0;

while (1) {

int r = isReducible();

if (r) {

reduce(r);

display();

reduced = 1;

} else {

break;

if (input[ip] == '\0')

break;
 if (input[ip] == 'i' && input[ip + 1] == 'd') {

push('i');

push('d');

ip += 2;

prin ("Shi id\n");

} else {

push(input[ip++]);

prin ("Shi %c\n", stack[top]);

if (top == 0 && stack[top] == 'E')

prin ("String Accepted\n");

else

prin ("String Rejected\n");

return 0;

Output:

Input:

E→E+E

E→E*E

E→(E)

E → id

id+id*id

Output:

Stack Input

id+id*id

Shi id

Reduce by E -> id

String Accepted
9. Construct a recursive descent parser for an expression.

#include <stdio.h>

#include <string.h>

#include <ctype.h>

char input[100];

int pos = 0;

void E();

void Eprime();

void T();

void Tprime();

void F();

void error() {

prin ("Error at posi on %d\n", pos);

exit(1);

void match(char expected) {

if (input[pos] == expected) {

pos++;

} else {

error();

void E() {

T();

Eprime();

void Eprime() {

if (input[pos] == '+') {

match('+');

T();

Eprime();
 }

void T() {

F();

Tprime();

void Tprime() {

if (input[pos] == '*') {

match('*');

F();

Tprime();

void F() {

if (input[pos] == '(') {

match('(');

E();

match(')');

} else if (input[pos] == 'i' && input[pos + 1] == 'd') {

match('i');

match('d');

} else {

error();

int main() {

prin ("Enter the input string (e.g., id+id*id): ");

scanf("%s", input);

E();

if (input[pos] == '\0')

prin ("String is accepted.\n");

 else

prin ("String is rejected.\n");

return 0;

Output:

Input:

id+id*id

Output:

String is accepted.
10. Implement Intermediate code genera on for simple expressions.

#include <stdio.h>

#include <string.h>

#include <ctype.h>

char expr[100];

int tempCount = 1;

void generateTAC(char *exp) {

char lhs, op1, op2, op;

int i = 0;

while (expr[i] != '=') i++;

lhs = expr[0];

char rhs[100];

strcpy(rhs, expr + i + 1);

int len = strlen(rhs);

int pos = 0;

char temp1[10], temp2[10];

int t = 1;

for (i = len - 1; i >= 0; i--) {

if (rhs[i] == '+' || rhs[i] == '-' || rhs[i] == '*' || rhs[i] == '/') {

op = rhs[i];

op1 = rhs[i - 1];

op2 = rhs[i + 1];

sprin (temp1, "t%d", t++);

prin ("%s = %c %c %c\n", temp1, op1, op, op2);

rhs[i - 1] = temp1[1];

for (int j = i; j + 2 < len; j++)

rhs[j] = rhs[j + 2];

rhs[j] = '\0';

i = len;

len -= 2;

}
 }

sprin (temp2, "t%d", t - 1);

prin ("%c = %s\n", lhs, temp2);

int main() {

prin ("Enter expression (e.g., a=b+c*d): ");

scanf("%s", expr);

generateTAC(expr);

return 0;

Output:

Input:

a=b+c*d

Output:

t1 = c * d

t2 = b + t1

a = t2
11. Write a program to perform loop unrolling.

#include <stdio.h>

#define SIZE 16

int main() {

int arr[SIZE];

int i, sum1 = 0, sum2 = 0;

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

arr[i] = i + 1; // arr = {1, 2, 3, ..., 16}

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

sum1 += arr[i];

for (i = 0; i < SIZE; i += 4) {

sum2 += arr[i];

sum2 += arr[i + 1];

sum2 += arr[i + 2];

sum2 += arr[i + 3];

prin ("Sum using original loop: %d\n", sum1);

prin ("Sum using unrolled loop: %d\n", sum2);

return 0;

Output:

Output:

Sum using original loop: 136

Sum using unrolled loop: 136

12. Write a program to perform constant propaga on.

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#define MAX 50

typedef struct {

char var;

int value;

int isConst;

ConstMap;

int findVar(ConstMap map[], int size, char var) {

for (int i = 0; i < size; i++)

if (map[i].var == var)

return i;

return -1;

int main() {

int n;

char stmt[MAX][20];

ConstMap map[MAX];

int mapSize = 0;

prin ("Enter number of statements: ");

scanf("%d", &n);

prin ("Enter statements (e.g. a=5, b=a+3):\n");

for (int i = 0; i < n; i++) {

scanf("%s", stmt[i]);

for (int i = 0; i < n; i++) {

char *s = stmt[i];

char lhs = s[0];

int idx = findVar(map, mapSize, lhs);

if (idx == -1) {

idx = mapSize++;

map[idx].var = lhs;

map[idx].isConst = 0;

int isAllConst = 1, val = 0, tempVal = 0;

int j = 2;

int sign = 1;

while (s[j]) {

if (isdigit(s[j])) {

tempVal = tempVal * 10 + (s[j] - '0');

} else if (isalpha(s[j])) {

int id = findVar(map, mapSize, s[j]);

if (id != -1 && map[id].isConst) {

tempVal = map[id].value;

} else {

isAllConst = 0;

break;

} else if (s[j] == '+') {

val += sign * tempVal;

tempVal = 0;

sign = 1;

} else if (s[j] == '-') {

val += sign * tempVal;

tempVal = 0;

sign = -1;

j++;

}
 val += sign * tempVal;

if (isAllConst) {

map[idx].value = val;

map[idx].isConst = 1;

prin ("%c = %d\n", lhs, val);

} else {

map[idx].isConst = 0;

prin ("%s\n", s);

return 0;

Output:

Output:

a=5

b=8

c = 10

d=c+e

e=4