PROGRAM 1: Design and implement a lexical analyzer for given

language using C and the lexical analyzer should ignore redundant

spaces, tabs and new lines.

To design and implement a lexical analyzer in C for a given language, you need to define
the language's tokens (keywords, identifiers, operators, etc.) and create a scanner that
processes the input and identifies those tokens. The lexical analyzer will also ignore
redundant spaces, tabs, and new lines.

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

int isKeyword(char buffer[]){

char keywords[32][10] = {
"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","unsigned",
"void","while","main"
};

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

if(strcmp(keywords[i], buffer) == 0)
return 1;
}
return 0;
}

int main(){
char ch, buffer[50];
char operators[] = "+-*/%=";
char separators[] = ",;(){}[]";
int i, j = 0;

printf("Enter code (Press Ctrl+D or Ctrl+Z to stop):\n");

while((ch = getchar()) != EOF){

for(i = 0; i < strlen(operators); i++){

if(ch == operators[i])
printf("%c is operator\n", ch);
}

for(i = 0; i < strlen(separators); i++){

if(ch == separators[i])
printf("%c is separator\n", ch);
}
 if(isalnum(ch)){
buffer[j++] = ch;
}
else if(j != 0){
buffer[j] = '\0';
j = 0;

if(isKeyword(buffer))
printf("%s is keyword\n", buffer);
else
printf("%s is identifier\n", buffer);
}
}

if(j != 0){
buffer[j] = '\0';
if(isKeyword(buffer))
printf("%s is keyword\n", buffer);
else
printf("%s is identifier\n", buffer);
}

return 0;
}
Output:
PROGRAM 2: Implementation of Calculator using LEX and YACC.

To implement a calculator using LEX and YACC, we'll create a simple expression
evaluator that can handle arithmetic operations such as addition, subtraction,
multiplication, division, and parentheses for grouping.

Steps to Implement:
1. LEX: The lexical analyzer (lexer) will tokenize the input expression into tokens
such as numbers, operators, and parentheses.
2. YACC: The parser (using YACC) will build an abstract syntax tree (AST) or
directly evaluate the expression based on the tokens generated by the lexer.

LEX PART:
%{
#include<stdio.h>
#include<stdlib.h>
#include "[Link].h"
%}

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

int yywrap()
{
return 1;
}
YACC PART:
%{
#include<stdio.h>
#include<stdlib.h>

int flag = 0;
void yyerror(const char *s);
int yylex();
%}

%token NUMBER
%left '+' '-'
%left '*' '/' '%'

%%
 input:
E '\n'
{
printf("Result = %d\n", $1);
printf("Expression is valid\n");
}
;

E:
E '+' E { $$ = $1 + $3; }
| E '-' E { $$ = $1 - $3; }
| E '*' E { $$ = $1 * $3; }
| E '/' E { $$ = $1 / $3; }
| E '%' E { $$ = $1 % $3; }
| '(' E ')' { $$ = $2; }
| NUMBER { $$ = $1; }
;

%%

int main()
{
printf("Enter arithmetic expression:\n");
yyparse();
return 0;
}

void yyerror(const char *s)

{
printf("Invalid Expression\n");
}

Output:
PROGRAM 3: Write program to find ε – closure of all states of any given
NFA with ε transition.

The ε-closure (epsilon-closure) of a state in a Non-deterministic Finite Automaton (NFA)

is the set of states that can be reached from the given state by traversing only ε (epsilon)
transitions. In other words, it includes the state itself and all states reachable through ε-
transitions.

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

struct node
{
int st;
struct node *link;
};

void findclosure(int, int);

void insert_trantbl(int, char, int);
int findalpha(char);
void print_e_closure(int);

static int nostate, noalpha, notransition;

static int buffer[20], e_closure[20][20], c;
char alphabet[20];

struct node *transition[20][20] = {NULL};

int main()
{
int i, j, r, s;
char ch;

printf("Enter the number of alphabets: ");

scanf("%d", &noalpha);
getchar();

printf("Enter alphabets (use 'e' for epsilon and keep it last):\n");

for(i = 0; i < noalpha; i++)
{
alphabet[i] = getchar();
getchar();
}

printf("Enter the number of states: ");

scanf("%d", &nostate);

printf("Enter number of transitions: ");

scanf("%d", &notransition);

printf("Enter transitions (format: state alphabet state)\n");

 for(i = 0; i < notransition; i++)
{
scanf("%d %c %d", &r, &ch, &s);
insert_trantbl(r, ch, s);
}

printf("\nE-closure of states:\n");

for(i = 1; i <= nostate; i++)

{
c = 0;

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

{
buffer[j] = 0;
e_closure[i][j] = 0;
}

findclosure(i, i);

printf("e-closure(q%d): ", i);

print_e_closure(i);
printf("\n");
}

return 0;
}

void findclosure(int x, int sta)

{
struct node *temp;

if(buffer[x])
return;

e_closure[sta][c++] = x;
buffer[x] = 1;

/* epsilon assumed last alphabet */

if(alphabet[noalpha-1] == 'e' && transition[x][noalpha-1] != NULL)
{
temp = transition[x][noalpha-1];
while(temp != NULL)
{
findclosure(temp->st, sta);
temp = temp->link;
}
}
}
void insert_trantbl(int r, char ch, int s)
{
int j;
struct node *temp;

j = findalpha(ch);

if(j == 999)
{
printf("Invalid alphabet\n");
exit(0);
}

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

temp->st = s;
temp->link = transition[r][j];
transition[r][j] = temp;
}

int findalpha(char c)
{
int i;
for(i = 0; i < noalpha; i++)
if(alphabet[i] == c)
return i;

return 999;
}

void print_e_closure(int i)
{
int j;
printf("{ ");
for(j = 0; e_closure[i][j] != 0; j++)
printf("q%d ", e_closure[i][j]);
printf("}");
}
Output:
PROGRAM 4: Write a program to convert NFA to DFA.

To convert a Non-Deterministic Finite Automaton (NFA) to a Deterministic Finite

Automaton (DFA), we can use the subset construction algorithm. The core idea is to
represent each DFA state as a set of NFA states.

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

int dfa[100][2][100] = {0};

int state[10000] = {0};
char str[1000];
int go[10000][2] = {0};
int arr[10000] = {0};

int main()
{
int st, fin, in;
int f[10];
int i,j=3,flag=0,curr1,k,l;

printf("\nEnter the number of states: ");

scanf("%d",&st);

printf("\nStates are from 0 to %d\n",st-1);

/* Initialize DFA state representation */

for(i=0;i<st;i++)
state[(int)(pow(2,i))] = 1;

printf("\nEnter number of final states: ");

scanf("%d",&fin);

printf("\nEnter final states:\n");

for(i=0;i<fin;i++)
scanf("%d",&f[i]);

int p,q,r,rel;
printf("\nEnter number of transition rules in NFA: ");
scanf("%d",&rel);

printf("\nEnter transitions (initial_state input_symbol final_state)\n");

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

{
scanf("%d%d%d",&p,&q,&r);
dfa[p][q][r] = 1;
}

printf("\nEnter initial state: ");

scanf("%d",&in);

in = pow(2,in);

printf("\nDFA Transitions:\n");

int x=0;

/* First level DFA transitions */

for(i=0;i<st;i++)
{
for(j=0;j<2;j++)
{
int stf = 0; /* fixed declaration */

for(k=0;k<st;k++)
{
if(dfa[i][j][k]==1)
stf += pow(2,k);
}

go[(int)(pow(2,i))][j] = stf;

printf("%d --%d--> %d\n",(int)(pow(2,i)),j,stf);

if(state[stf]==0)
arr[x++] = stf;

state[stf] = 1;
}
}

/* Subset construction */
for(i=0;i<x;i++)
{
printf("Processing state %d\n",arr[i]); /* fixed printing */

for(j=0;j<2;j++)
{
int newState = 0;

for(k=0;k<st;k++)
{
if(arr[i] & (1<<k))
{
int h = pow(2,k);
newState |= go[h][j];
}
}

go[arr[i]][j] = newState;
 if(state[newState]==0)
{
arr[x++] = newState;
state[newState] = 1;
}
}
}

printf("\nDFA Transition Table:\n");

printf("STATE 0 1\n");

for(i=0;i<10000;i++)
{
if(state[i]==1)
{
int y=0;

if(i==0)
printf("q0 ");
else
{
for(j=0;j<st;j++)
{
int mask = 1<<j;
if(mask & i)
{
printf("q%d ",j);
y += pow(2,j);
}
}
}

printf(" %d %d\n",go[y][0],go[y][1]);
}
}

/* String testing */
j=3;
while(j--)
{
printf("\nEnter string: ");
scanf("%s",str);

l = strlen(str);
curr1 = in;
flag = 0;

printf("Path: %d-",curr1);

for(i=0;i<l;i++)
 {
curr1 = go[curr1][str[i]-'0'];
printf("%d-",curr1);
}

printf("\nFinal state: %d\n",curr1);

for(i=0;i<fin;i++)
{
if(curr1 & (1<<f[i]))
{
flag = 1;
break;
}
}

if(flag)
printf("String Accepted\n");
else
printf("String Rejected\n");
}

return 0;
}
Output:
PROGRAM 5: Write program to minimize any given DFA.

DFA minimization stands for converting a given DFA to its equivalent DFA with
minimum number of states. DFA minimization is also called as Optimization of DFA and
uses partitioning algorithm.

#include <stdio.h>

/* input format
row 1: input symbols
row 2: non-final states
row 3: final states
rows>3: transition table
*/

int table[10][10];
int matrix[10][10] = {0};

int indexOf(char *array, char x, int max){

int i;
for(i = 0; i < max; i++){
if(array[i] == x)
return i;
}
return -1;
}

int movesToMarked(int i, int j, int l){

int k, x, y;
for(k = 0; k < l; k++){
x = table[i][k];
y = table[j][k];
if(x != -1 && y != -1 && matrix[x][y] == 1){
return 1;
}
}
return 0;
}

void printStates(char *states, int n, int f){

int i, j;
int store = 0;
int bin, final;

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

bin = 1 << i;

if((store & bin) != 0)

continue;

final = (i >= n) ? 1 : 0;
 store = store | bin;
printf("%c", states[i]);

for(j = i + 1; j < n + f; j++){

if(matrix[j][i] == 0){
bin = 1 << j;
store = store | bin;
if(j >= n) final = 1;
printf("%c", states[j]);
}
}

if(final == 1)
printf(" (f)");

printf("\n");
}
}

int main(){
char language[10], ch;
int l = 0;

/* read input symbols */

while(1){
language[l++] = getchar();
if(getchar() == '\n')
break;
}

int n = 0, f = 0;
char states[10];

/* read non-final states */

while(1){
states[n++] = getchar();
if(getchar() == '\n')
break;
}

char *finalstates = states + n;

/* read final states */

while(1){
finalstates[f++] = getchar();
if(getchar() == '\n')
break;
}

int i, j;
/* read transition table */
for(i = 0; i < n + f; i++){
for(j = 0; j < l; j++){
scanf(" %c", &ch);
table[i][j] = indexOf(states, ch, n + f);
}
}

/* initialize matrix */
for(i = 0; i < n + f; i++){
matrix[i][i] = -1;
}

/* mark final vs non-final pairs */

for(i = n; i < n + f; i++){
for(j = 0; j < n; j++){
matrix[i][j] = 1;
matrix[j][i] = 1;
}
}

/* marking algorithm */
int change = 1;
while(change){
change = 0;
for(i = 0; i < n + f; i++){
for(j = 0; j < n + f; j++){
if(matrix[i][j] == 0){
if(movesToMarked(i, j, l)){
matrix[i][j] = 1;
matrix[j][i] = 1;
change = 1;
}
}
}
}
}

/* print matrix */
printf(" ");
for(i = 0; i < n + f; i++)
printf("%c ", states[i]);
printf("\n");

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

printf("%c ", states[i]);
for(j = 0; j < i; j++)
printf("%d ", matrix[i][j]);
printf("\n");
}
 /* print minimized states */
printf("\nMinimized DFA states:\n");
printStates(states, n, f);

return 0;
}

Output:
PROGRAM 6: Write program to find Simulate First and Follow of any
given grammar.

The First and Follow sets are important in syntax analysis, mainly in parsing. All sets help in
making predictive parsers and are integral to identifying how a given grammar can be parsed
effectively.
 The First Set for a non-terminal symbol represents all possible terminals that can
appear at the beginning of any string derived from that non-terminal.
 The follow set contains terminals that can appear immediately after a non-terminal in
the derivation of the grammar.

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

void followfirst(char, int, int);

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

int count, n = 0;
char calc_first[10][100];
char calc_follow[10][100];
int m = 0;
char production[10][10];
char f[10], first[10];
int k;
char ck;
int e;

int main()
{
int jm = 0;
int km = 0;
int i;
char c;
count = 8;

/* Grammar */
strcpy(production[0], "X=TnS");
strcpy(production[1], "X=Rm");
strcpy(production[2], "T=q");
strcpy(production[3], "T=#");
strcpy(production[4], "S=p");
strcpy(production[5], "S=#");
strcpy(production[6], "R=om");
strcpy(production[7], "R=ST");

char done[count];
int ptr = -1;
/* Initialize FIRST array */
for (k = 0; k < count; k++) {
for (int kay = 0; kay < 100; kay++) {
calc_first[k][kay] = '!';
}
}

int point1 = 0, point2, xxx;

/* FIRST calculation */
for (k = 0; k < count; k++) {
c = production[k][0];
point2 = 0;
xxx = 0;

for (int kay = 0; kay <= ptr; kay++)

if (c == done[kay])
xxx = 1;

if (xxx == 1)
continue;

findfirst(c, 0, 0);
ptr += 1;
done[ptr] = c;

printf("\nFirst(%c) = { ", c);

calc_first[point1][point2++] = c;

for (i = jm; i < n; i++) {

int chk = 0;
for (int 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-----------------------------------------------\n\n");

char donee[count];
ptr = -1;
 /* Initialize FOLLOW array */
for (k = 0; k < count; k++) {
for (int kay = 0; kay < 100; kay++) {
calc_follow[k][kay] = '!';
}
}

point1 = 0;

/* FOLLOW calculation */
for (e = 0; e < count; e++) {
ck = production[e][0];
point2 = 0;
xxx = 0;

for (int kay = 0; kay <= ptr; kay++)

if (ck == donee[kay])
xxx = 1;

if (xxx == 1)
continue;

follow(ck);
ptr += 1;
donee[ptr] = ck;

printf("Follow(%c) = { ", ck);

calc_follow[point1][point2++] = ck;

for (i = km; i < m; i++) {

int chk = 0;
for (int 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++;
}

return 0;
}
/* FOLLOW function */
void follow(char c)
{
int i, j;

if (production[0][0] == c) {
f[m++] = '$';
}

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

for (j = 2; j < 10; j++) {
if (production[i][j] == c) {
if (production[i][j + 1] != '\0') {
followfirst(production[i][j + 1], i, j + 2);
}
if (production[i][j + 1] == '\0' && c != production[i][0]) {
follow(production[i][0]);
}
}
}
}
}

/* FIRST function */
void findfirst(char c, int q1, int q2)
{
int j;

if (!(isupper(c))) {
first[n++] = c;
return;
}

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

if (production[j][0] == c) {
if (production[j][2] == '#') {
if (production[q1][q2] == '\0')
first[n++] = '#';
else
findfirst(production[q1][q2], q1, q2 + 1);
}
else if (!isupper(production[j][2])) {
first[n++] = production[j][2];
}
else {
findfirst(production[j][2], j, 3);
}
}
}
}
 /* FOLLOWFIRST helper */
void followfirst(char c, int c1, int c2)
{
if (!(isupper(c))) {
f[m++] = c;
}
else {
int i, j = 1;
for (i = 0; i < count; i++) {
if (calc_first[i][0] == c)
break;
}

while (calc_first[i][j] != '!') {

if (calc_first[i][j] != '#') {
f[m++] = calc_first[i][j];
}
else {
if (production[c1][c2] == '\0')
follow(production[c1][0]);
else
followfirst(production[c1][c2], c1, c2 + 1);
}
j++;
}
}
}
Output:
PROGRAM 7: Develop an operator precedence parser for a given
language.

An operator-precedence parser is a simple shift-reduce parser that is capable of parsing a

subset of LR(1) grammars. More precisely, the operator-precedence parser can parse all
LR(1) grammars where two consecutive nonterminal and epsilon never appear in the right-
hand side of any rule.

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

char *input;
int i = 0;
char lasthandle[6];
char stack[50];
char handles[][5] = {")E(", "E*E", "E+E", "i", "E^E"};

int top = 0, l;

char prec[9][9] = {

/* stack vs input precedence table */

/* + - * / ^ i ( ) $ */

{'>','>','<','<','<','<','<','>','>'}, /* + */
{'>','>','<','<','<','<','<','>','>'}, /* - */
{'>','>','>','>','<','<','<','>','>'}, /* * */
{'>','>','>','>','<','<','<','>','>'}, /* / */
{'>','>','>','>','<','<','<','>','>'}, /* ^ */
{'>','>','>','>','>','e','e','>','>'}, /* i */
{'<','<','<','<','<','<','<','>','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;
}
return -1;
}

void shift()
{
stack[++top] = input[i++];
stack[top+1] = '\0';
}

int reduce()
{
int j, len, found, t;

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

{
len = strlen(handles[j]);
if(stack[top] == handles[j][0] && top + 1 >= len)
{
found = 1;
for(t = 0; t < len; t++)
{
if(stack[top - t] != handles[j][t])
{
found = 0;
break;
}
}

if(found == 1)
{
stack[top - t + 1] = 'E';
top = top - t + 1;
strcpy(lasthandle, handles[j]);
stack[top+1] = '\0';
return 1;
}
}
}
return 0;
}

void dispstack()
{
for(int j = 0; j <= top; j++)
printf("%c", stack[j]);
}

void dispinput()
{
for(int j = i; j < l; j++)
printf("%c", input[j]);
}
int main()
{
input = (char*)malloc(50 * sizeof(char));

printf("Enter the string (use i for identifier): ");

scanf("%s", input);

strcat(input, "$");
l = strlen(input);

strcpy(stack, "$");

printf("\nSTACK\tINPUT\tACTION");

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

if(strcmp(stack, "$E$") == 0)
printf("\nAccepted\n");
else
printf("\nNot Accepted\n");

return 0;
}
Output:
PROGRAM 8: Construct a Shift Reduce Parser for a given language.

Shift Reduce Parser is a type of Bottom-Up Parser. It generates the Parse Tree from Leaves
to the Root. In Shift Reduce Parser, the input string will be reduced to the starting symbol.
This reduction can be produced by handling the rightmost derivation in reverse, i.e., from
starting symbol to the input string.
Shift reduce parsing performs the two actions: shift and reduce. That's why it is known as
shift reduces parsing.
 At the shift action, the current symbol in the input string is pushed to a stack.
 At each reduction, the symbols will replaced by the non-terminals. The symbol is the
right side of the production and non-terminal is the left side of the production.

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

int z = 0, i = 0, j = 0, c = 0;
char a[20], ac[20], stk[20], act[10];

void check()
{
strcpy(ac, "REDUCE TO E->");

/* Rule E -> 4 */
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);
}
}

/* Rule E -> 2E2 */

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;
}
}

/* Rule E -> 3E3 */

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+2] = '\0';
printf("\n$%s\t%s$\t", stk, a);
i = i - 2;
}
}
}

int main()
{
printf("Grammar is:\n");
printf("E -> 2E2\n");
printf("E -> 3E3\n");
printf("E -> 4\n");

strcpy(a, "32423"); /* Input string */

c = strlen(a);
strcpy(act, "SHIFT");

printf("\nStack\tInput\tAction");
printf("\n$\t%s$\t", a);

for(i = 0, j = 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");

return 0;
}

Output:
PROGRAM 9: Implement Intermediate code generation for simple
expressions.
During the translation of a source program into the object code for a target machine, a compiler
may generate a middle-level language code, which is known as intermediate code or intermediate
text. The complexity of this code lies between the source language code and the object code. The
intermediate code can be represented in the form of postfix notation, syntax tree, directed acyclic
graph (DAG), three-address code, quadruples, and triples. Intermediate code is machine
independent, which makes it easy to retarget the compiler to generate code for newer and different
processors.

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

char expr[100];
char temp = 'Z';

/* replace operand1 op operand2 with temp variable */

void replaceExp(int pos)
{
char newexpr[100];
int i, j = 0;

for(i = 0; i < pos-1; i++)

newexpr[j++] = expr[i];

newexpr[j++] = temp;

for(i = pos+2; expr[i] != '\0'; i++)

newexpr[j++] = expr[i];

newexpr[j] = '\0';
strcpy(expr, newexpr);
}

int main()
{
int i;

printf("INTERMEDIATE CODE GENERATION\n");

printf("Enter the Expression: ");
scanf("%s", expr);

printf("\nThe intermediate code:\n");

 /* handle * and / first */
for(i = 0; expr[i] != '\0'; i++)
{
if(expr[i] == '*' || expr[i] == '/')
{
printf("%c := %c %c %c\n", temp, expr[i-1], expr[i], expr[i+1]);
replaceExp(i);
temp--;
i = -1;
}
}

/* handle + and - */
for(i = 0; expr[i] != '\0'; i++)
{
if(expr[i] == '+' || expr[i] == '-')
{
printf("%c := %c %c %c\n", temp, expr[i-1], expr[i], expr[i+1]);
replaceExp(i);
temp--;
i = -1;
}
}

/* final assignment */
if(strchr(expr,'='))
{
char lhs = expr[0];
char rhs = expr[strlen(expr)-1];
printf("%c := %c\n", lhs, rhs);
}

return 0;
}
Output:
PROGRAM 10: Write a program to perform loop unrolling.
Loop unrolling is a technique used in compiler design to optimize the performance of loops in a
program.
#include <stdio.h>

int countbit1(unsigned int n);

int countbit2(unsigned int n);

int main()
{
unsigned int n;
int x;
char ch;

printf("Enter N: ");
scanf("%u", &n);

printf("\n1. Loop Roll");

printf("\n2. Loop Unroll");
printf("\nEnter your choice: ");
scanf(" %c", &ch);

switch(ch)
{
case '1':
x = countbit1(n);
printf("\nLoop Roll: Count of 1's = %d\n", x);
break;

case '2':
x = countbit2(n);
printf("\nLoop Unroll: Count of 1's = %d\n", x);
break;

default:
printf("\nWrong Choice\n");
}

return 0;
}

/* Normal loop (1 bit per iteration) */

int countbit1(unsigned int n)
{
int bits = 0, i = 0;

while(n != 0)
{
if(n & 1)
bits++;
 n >>= 1;
i++;
}

printf("Number of iterations = %d\n", i);

return bits;
}

/* Loop unrolling (4 bits per iteration) */

int countbit2(unsigned int n)
{
int bits = 0, i = 0;

while(n != 0)
{
if(n & 1) bits++;
if(n & 2) bits++;
if(n & 4) bits++;
if(n & 8) bits++;

n >>= 4; // shift 4 bits at a time

i++;
}

printf("Number of iterations = %d\n", i);

return bits;
}

Output: