Compiler
Design
prACTiCAl
File
Name – Jatin Mittal
Branch – IT-2
Semester - 5th
Enrollment Number - 10113203121
inDeX
S. No. Title Date Sign.
9
10
1. What are compilers and explain the different types of compilers
A compiler is a specialized software tool that translates high-level programming
code written in languages like C, C++, or Java into machine code that can be
executed by a computer's central processing unit (CPU). The process involves
multiple stages, including lexical analysis, syntax analysis, semantic analysis,
optimization, and code generation. The primary goal of a compiler is to transform
human-readable source code into efficient and executable machine code.
There are various types of compilers, each designed for specific purposes:
1. Single-pass Compilers: These process the source code in a single pass,
generating machine code as they go. They are faster but may lack some
optimization opportunities.
2. Multi-pass Compilers: These go through the source code multiple times,
performing various analyses and optimizations in separate passes. This often
results in code that is more efficient but takes longer.
3. Just-In-Time (JIT) Compilers: Instead of translating the entire program before
execution, JIT compilers translate code as needed during runtime. This can lead to
faster startup times and adaptive optimization.
4. Cross-Compiler: Generates code for a platform different from the one on
which the compiler is running. This is useful for developing software for embedded
systems or different architectures.
Compilers play a crucial role in software development, facilitating the conversion of
human-readable code into machine-executable instructions.
2. Write a program to check whether a string belongs to the grammar or not
Code:
#include <stdio.h>
#include <string.h> int
main()
char string[50]; int flag, count = 0;
printf("The grammar is: S->aS, S->Sb, S->ab\n");
printf("Enter the string to be checked:\n");
gets(string); if(string[0] == 'a')
{ flag
= 0;
for(count = 1; string[count - 1] != '\0'; count++)
if(string[count] == 'b')
flag = 1;
continue;
else if((flag == 1) && (string[count] == 'a'))
printf("The string does not belong to the specified grammar");
break;
}
else if(string[count] == 'a')
continue;
else if((flag == 1) && (string[count] == '\0'))
printf("String accepted");
break;
else
printf("String not accepted");
return 0; }
Output:
3. Write a program to check whether a string include keyword or not
Code:
#include <stdio.h>
#include <string.h> int
main()
char keyword[32][10] =
"auto","double","int","struct","break","else","long",
"switch","case","enum","register","typedef","char",
"extern","return","union","const","float","short",
"unsigned","continue","for","signed","void","default",
"goto","sizeof","voltile","do","if","static","while"
};
char str[] = "for"; int flag = 0, i;
for(i = 0; i < 32; i++)
if(strcmp(str, keyword[i]) == 0)
flag = 1; if(flag == 1)
printf("%s is a keyword", str);
else
printf("%s is not a keyword", str);
return 0; }
Output:
4. Write a program to remove left recursion from a grammar
Code:
#include<stdio.h>
#include<string.h> int
main()
char input[100], l[50], r[50], temp[10], tempprod[20], productions[25][50];
int i = 0, j = 0, flag = 0, consumed = 0; printf("Enter the productions: ");
scanf("%1s -> %s", l, r); printf("%s", r); while(sscanf(r +
consumed,"%[^|]s", temp) == 1 && consumed <= strlen(r))
if(temp[0] == l[0])
flag = 1;
sprintf(productions[i++],"%s->%s%s'\0", l, temp + 1, l);
else
sprintf(productions[i++],"%s'->%s%s'\0", l, temp, l);
consumed += strlen(temp) + 1;
if(flag == 1)
sprintf(productions[i++],"%s->ε\0",l); printf("The
productions after eliminating Left Recursion are:\n");
for(j = 0; j < i; j++)
printf("%s\n", productions[j]);
else
printf("The Given Grammar has no Left Recursion");
return 0; }
Output:
5. Write a program to perform left factoring on a grammar
Code:
#include<stdio.h>
#include<string.h> int
main()
char gram[20], part1[20], part2[20], modifiedGram[20], newGram[20], tempGram[20];
int i, j = 0, k = 0, l = 0, pos;
printf("Enter Production : A->"); gets(gram);
for(i = 0; gram[i] != '|'; i++, j++) part1[j] =
gram[i]; part1[j] = '\0'; for(j=++i, i = 0;
gram[j] != '\0'; j++, i++) part2[i] = gram[j];
part2[i] = '\0'; for(i=0; i < strlen(part1) || i <
strlen(part2); i++)
{
if(part1[i] == part2[i])
modifiedGram[k] = part1[i];
k++;
pos = i + 1;
for(i = pos, j = 0; part1[i] != '\0'; i++, j++)
newGram[j] = part1[i];
newGram[j++] = '|';
for(i = pos; part2[i] != '\0'; i++, j++)
newGram[j] = part2[i];
modifiedGram[k] = 'X';
modifiedGram[++k] = '\0';
newGram[j] = '\0'; printf("\n A-
>%s", modifiedGram); printf("\n X-
>%s\n", newGram);
return 0; }
Output:
6. Write a program to show all the operations of a stack
Code:
#include <stdio.h>
#include <stdlib.h> struct
DLLNode
struct DLLNode* prev;
int data;
struct DLLNode* next;
};
struct myStack
struct DLLNode* head;
struct DLLNode* mid; int
count;
};
struct myStack* createMyStack()
{
struct myStack* ms = (struct myStack*)malloc(sizeof(struct myStack));
ms->count = 0; return ms;
};
void push(struct myStack* ms, int new_data)
struct DLLNode* new_DLLNode
= (struct DLLNode*)malloc(sizeof(struct DLLNode)); new_DLLNode->data
= new_data;
new_DLLNode->prev = NULL; new_DLLNode->next
= ms->head;
ms->count += 1; if (ms-
>count == 1) ms->mid =
new_DLLNode;
else
ms->head->prev = new_DLLNode;
if (ms->count & 1) ms-
>mid = ms->mid->prev;
ms->head = new_DLLNode;
int pop(struct myStack* ms)
if(ms->count == 0)
printf("Stack is empty\n");
return -1;
}
struct DLLNode* head = ms->head;
int item = head->data; ms->head =
head->next; if (ms->head != NULL)
ms->head->prev = NULL; ms-
>count -= 1; if (!((ms->count) & 1))
ms->mid = ms->mid->next;
free(head);
return item;
int findMiddle(struct myStack* ms)
if (ms->count == 0)
printf("Stack is empty now\n");
return -1;
return ms->mid->data;
void deleteMiddle(struct myStack* ms)
if(ms->count == 0)
printf("Stack is empty now\n");
return;
ms->count -= 1; ms->mid->next->prev
= ms->mid->prev; ms->mid->prev->next
= ms->mid->next; if (ms->count % 2 !=
0) ms->mid=ms->mid->next;
else
ms->mid=ms->mid->prev;
int main()
struct myStack* ms = createMyStack();
push(ms, 11); push(ms, 22); push(ms,
33); push(ms, 44); push(ms, 55);
push(ms, 66); push(ms, 77);
push(ms, 88); push(ms, 99);
printf("Popped : %d\n", pop(ms));
printf("Popped : %d\n", pop(ms));
printf("Middle Element : %d\n",
findMiddle(ms)); deleteMiddle(ms);
printf("New Middle Element : %d\n",
findMiddle(ms));
return 0; }
Output:
7. Write a program to find out the leading of the non-terminal in a grammar
Code:
#include <stdio.h> char
array[10][20], temp[10];
int c, n; void fun(int, int[]); int
fun2(int i, int j, int p[], int);
int main()
{ int p[2], i,
j;
printf("Enter the no. of productions : ");
scanf("%d", &n); printf("Enter the
productions :\n"); for(i = 0; i < n; i++)
scanf("%s", array[i]); for(i = 0; i < n; i++)
c = -1, p[0] = -1, p[1] = -1;
fun(i, p); printf("First(%c) : [ ",
array[i][0]); for(j = 0; j <= c; j++)
printf("%c,", temp[j]); printf("\b
].\n");
return 0;
int fun2(int i, int j, int p[], int key)
{ int k;
if(!key)
for(k = 0; k < n; k++)
if(array[i][j] == array[k][0])
break; p[0] =
i; p[1] = j + 1; fun(k,
p); return 0;
else
for(k = 0; k <= c; k++)
if(array[i][j] == temp[k])
break; if(k > c)
return 1; else
return 0;
void fun(int i, int p[])
{ int j, k, key; for(j = 2;
array[i][j] != NULL; j++)
{ if(array[i][j - 1] ==
'/') {
if(array[i][j] >= 'A' && array[i][j] <= 'Z')
key = 0;
fun2(i, j, p, key);
}
else {
key = 1; if(fun2(i, j, p,
key)) temp[++c] = array[i][j];
if(array[i][j] == '@' && p[0] != -1)
if(array[p[0]][p[1]] >= 'A' && array[p[0]][p[1]] <= 'Z')
key=0;
fun2(p[0],p[1],p,key);
else
if(array[p[0]][p[1]] != '/' && array[p[0]][p[1]] != NULL)
if(fun2(p[0], p[1], p, key))
temp[++c] = array[p[0]][p[1]];
Output:
8. Write a program to implement shift-reduce parsing for a string
Code:
#include<stdio.h>
#include<stdlib.h> #include<string.h>
int z = 0, i = 0, j = 0, c = 0;
char a[16], ac[20], stk[15], act[10]; void
check()
strcpy(ac,"REDUCE TO E -> ");
for(z = 0; z < c; z++)
{ if(stk[z] ==
'4')
printf("%s4", ac);
stk[z] = 'E';
stk[z + 1] = '\0';
printf("\n$%s\t%s$\t", stk, a);
for(z = 0; z < c - 2; z++)
if(stk[z] == '2' && stk[z + 1] == 'E' && stk[z + 2] == '2')
printf("%s2E2", ac);
stk[z] = 'E';
stk[z + 1] = '\0';
stk[z + 2] = '\0';
printf("\n$%s\t%s$\t", stk, a);
i = i - 2;
}
}
for(z=0; z<c-2; z++)
if(stk[z] == '3' && stk[z + 1] == 'E' && stk[z + 2] == '3')
printf("%s3E3", ac);
stk[z]='E';
stk[z + 1]='\0';
stk[z + 1]='\0';
printf("\n$%s\t%s$\t", stk, a);
i = i - 2;
return ;
int main()
printf("GRAMMAR is -\nE->2E2 \nE->3E3 \nE->4\n");
strcpy(a,"32423"); c=strlen(a);
strcpy(act,"SHIFT");
printf("\nstack \t input \t action");
printf("\n$\t%s$\t", a);
for(i = 0; j < c; i++, j++)
printf("%s", act);
stk[i] = a[j];
stk[i + 1] = '\0';
a[j]=' ';
printf("\n$%s\t%s$\t", stk, a);
check();
check(); if(stk[0] == 'E' &&
stk[1] == '\0')
printf("Accept\n");
else
printf("Reject\n"); }
Output:
9. Write a program to find out the first of the non-terminals in a grammar
Code:
#include<stdio.h>
#include<ctype.h> void
FIRST(char *, char); void
addToResultSet(char[],char); int
numOfProductions; char
productionSet[10][10]; main()
{ int
i;
char choice; char c; char result[20];
printf("How many number of productions ? : ");
scanf("%d", &numOfProductions); for(i = 0; i <
numOfProductions; i++)
printf("Enter productions Number %d : ",i + 1);
scanf("%s",productionSet[i]);
do
printf("\n Find the FIRST of : ");
scanf(" %c",&c);
FIRST(result,c); printf("\n
FIRST(%c)= { ",c); for(i = 0;
result[i] != '\0'; i++) printf(" %c
", result[i]); printf("}\n");
printf("press 'y' to continue : ");
scanf(" %c", &choice);
while(choice=='y'||choice =='Y');
void FIRST(char* Result,char c)
{ int
i,j,k;
char subResult[20];
int foundEpsilon;
subResult[0]='\0';
Result[0]='\0';
if(!(isupper(c)))
addToResultSet(Result,c);
return ;
for(i=0;i<numOfProductions;i++)
if(productionSet[i][0]==c)
if(productionSet[i][2]=='$')
addToResultSet(Result,'$');
else
j=2;
while(produ
ctionSet[i][j]
!='\0')
foundEpsilon=0;
FIRST(subResult,productionSet[i][j]);
for(k=0;subResult[k]!='\0';k++)
addToResultSet(Result,subResult[k]);
for(k=0;subResult[k]!='\0';k++)
if(subResult[k]=='$')
{
foundEpsilon=1;
break;
if(!foundEpsilon)
break;
j++;
return ;
void addToResultSet(char Result[], char val)
{ int
k;
for(k = 0; Result[k] != '\0'; k++)
if(Result[k] == val) return;
Result[k] = val;
Result[k + 1] = '\0';
Output:
10. Write a program to check whether a grammar is operator precedent
Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h> char
*input;
int i = 0; char lasthandle[6], stack[50], handles[][5] =
{")E(","E*E","E+E","i","E^E"};
int top = 0, l; char
prec[9][9] =
'>', '>','<','<','<','<','<','>','>',
'>', '>','<','<','<','<','<','>','>',
'>', '>','>','>','<','<','<','>','>',
'>', '>','>','>','<','<','<','>','>',
'>', '>','>','>','<','<','<','>','>',
'>', '>','>','>','>','e','e','>','>',
'<', '<','<','<','<','<','<','>','e',
'>', '>','>','>','>','e','e','>','>',
'<', '<','<','<','<','<','<','<','>',
};
int getindex(char c)
switch(c)
case '+' : return 0;
case '-' : return 1; case
'*' : return 2; case '/' :
return 3; case '^' :
return 4; case 'i' :
return 5; case '(' :
return 6; case ')' :
return 7; case '$' :
return 8;
} } int
shift()
stack[++top] =* (input + i++);
stack[top + 1] = '\0';
int reduce()
{ int i, len, found,
t; for(i = 0; i < 5;
i++)
len = strlen(handles[i]); if(stack[top] ==
handles[i][0] && top + 1 >= len)
found = 1;
for(t = 0; t < len; t++)
if(stack[top - t] != handles[i][t])
found = 0;
break;
if(found == 1)
{
stack[top - t + 1] = 'E';
top = top - t + 1;
strcpy(lasthandle, handles[i]);
stack[top + 1] = '\0'; return 1;
return 0;
void dispstack()
{ int
j;
for(j = 0; j <= top; j++)
printf("%c", stack[j]);
void dispinput()
{ int j; for(j = i; j < l; j++)
printf("%c", *(input + j));
int main()
{ int
j;
input
(char*
)mallo
c(50*s
izeof(c
har));
printf(
"\nEnt
er the
string:
");
scanf(
"%s",
input);
input
strcat(
input,
"$");
l=
strlen(
input);
strcpy(
stack,
"$");
printf(
"\nSTA
CK\tIN
PUT\t
ACTIO
N");
while(i <= l)
{ shift();
printf("\n");
dispstack();
printf("\t");
dispinput();
printf("\tShift");
if(prec[getindex(stack[top])][getindex(input[i])]=='>')
while(reduce())
printf("\n"); dispstack();
printf("\t"); dispinput();
printf("\tReduced: E->%s",lasthandle);
return 0;
Output:
