1a. Write a LEX program to recognize valid arithmetic expression.

Identifiers in the
expression could be only integers and operators could be + and *. Count the identifiers &
operators present and print them separately.
%{
#include<stdio.h>
int v=0,op=0,id=0,flag=0;
%}
%%
[0-9]* {id++; printf("\n Identifier:\t");ECHO;}
[\+\*] {op++; printf("\n Operator:\t");ECHO;}
"(" {v++;}
")" {v--;}
";" {flag=1;}
.|\n {;}
%%
main()
{
printf("Enter the Expression:\n");
yylex();
if((op+1)==id && v==0 && flag==0)
printf("valid\n");
else
printf("Invalid\n");
printf("Number of Identifiers : %d\n",id);
printf("Number of Operators : %d\n",op);
}
1 b. Write YACC program to evaluate arithmetic expression involving operators: +, -, *,and /.
Lex Part
%{
#include "1b.tab.h"
extern yylval;
%}
%%
[0-9]+ {yylval=atoi(yytext);return num;} /* convert the string to number and send the value*/
[\+\-\*\/] {return yytext[0];}
[( ] {return yytext[0];}
[ )] {return yytext[0];}
. {;}
\n {return 0;}
%%
YACC Part
%{
#include<stdio.h>
#include<stdlib.h>
%}
%token num
%left '+' '-'
%left '*' '/'
%%
input:exp {printf("%d\n",$$);exit(0);}
exp:exp'+'exp {$$=$1+$3;}
|exp'-'exp {$$=$1-$3;}
|exp'*'exp {$$=$1*$3;}
|exp'/'exp { if($3==0){printf("Divide by Zero error\n");exit(0);}
else
$$=$1/$3;}
|'('exp')'{$$=$2;}
|num{$$=$1;};
%%
int yyerror()
{
printf("error");
exit(0);
}
int main()
{
printf("Enter an expression:\n");
yyparse();
}
2. Develop, Implement and Execute a program using YACC tool to recognize all strings
ending with b preceded by n a’s using the grammar an b (note: input n value).

Lex Part
%{
#include "2.tab.h"
%}
%%
a {return A;}
b {return B;}
[\n] return '\n';
%%
YACC Part
%{
#include<stdio.h>
#include<stdlib.h>
%}
%token A B
%%
input:s'\n' {printf("Successful Grammar\n");exit(0);}
s: A s1 B| B
s1: ; | A s1
%%
main()
{
printf("Enter A String\n");
yyparse();
}
int yyerror()
{
printf("Error \n");
exit(0);
}
 6. a) Write a LEX program to eliminate comment lines in a C program and copy the
resulting program into a separate file.

%{
#include<stdio.h>
int count=0;
%}

%%
"//".* {count++;}
"/*" [a-z A-Z 0-9 \t \n]* "*/" {count++;}
%%

main(int argc,char *argv[])

{
if(argc!=3)
{
printf("not enough arguements");
exit(0);
}
yyin=fopen(argv[1],"r");
yyout=fopen(argv[2],"w");
yylex();
if(count==0)
printf("No comment lines");
else
printf("Number of Comment lines = %d",count);
}
6b. Write YACC program to recognize valid identifier, operators and keywords in the
given text (C program) file.
Lex File
%{
#include <stdio.h>
#include "6b.tab.h"
extern yylval;
%}
%%
[ \t] ;
[+|-|*|/|=|<|>] {printf("operator is %s\n",yytext);return OP;}
int|char|bool|float|void|for|do|while|if|else|return {printf("keyword is %s\n",yytext);return KEY;}
[a-zA-Z0-9]+ {printf("identifier is %s\n",yytext);return ID;}
.;
%%
Yacc File
%{
#include <stdio.h>
#include <stdlib.h>
int id=0, dig=0, key=0, op=0;
%}
%token ID KEY OP
%%
input: ID input { id++; }
| KEY input { key++; }
| OP input {op++;}
| ID { id++; }
| KEY { key++; }
| OP { op++;}
;
%%
#include <stdio.h>
extern FILE *yyin;
main() {
yyin = fopen("input.c", "r");
yyparse();
printf("numbers = %d\nKeywords = %d\nIdentifiers = %d\noperators =%d\n",key,id, op);
}
void yyerror() {
printf(“ parse error! Message: ");
exit(-1);
}
7. Design, develop and implement a C/C++/Java program to simulate the working of
Shortest remaining time and Round Robin (RR) scheduling algorithms. Experiment with
different quantum sizes for RR algorithm.

#include<stdio.h>
#include<stdlib.h>
struct J
{
int id,bt,tat,wt,at,ft;
} job[100];
void scheduler(struct J job[],int n,int q,int c)
{
int burst[100],x,t=0,done=0,curr=0,diff=q,i=0;
float tat_sum=0,wt_sum=0;
for(i=0;i<n;i++)
burst[i]=job[i].bt;
if(c==0)
curr=-1;
while(done<n)
{
if(c==1)
{
for(x=0;x<n;x++)
{
if(job[curr].bt==0)
curr=x;
if(job[x].bt<job[curr].bt && job[x].bt>0 && job[x].at<=t)
curr=x;
}
diff=1;
}
else
{
while(1)
{
curr=(curr+1)%n;
if(job[curr].bt!=0)
break;
}
diff=(q<=job[curr].bt)?q:job[curr].bt;
}
job[curr].bt-=diff;
t+=diff;
if(job[curr].bt==0)
{
done++;
job[curr].ft=t;
}
}
if(c==1)
 printf("SRJF Details are \n");
else
printf("RR Scheduling Details are \n");
for(i=0;i<n;i++)
{
job[i].bt=burst[i];
job[i].tat=job[i].ft-job[i].at;
job[i].wt=job[i].tat-job[i].bt;
tat_sum+=job[i].tat;
wt_sum+=job[i].wt;
}
printf("Job\tBT\tAT\tTAT\tWT\n");
for(i=0;i<n;i++)
printf("%d\t%d\t%d\t%d\t%d\n",i+1,job[i].bt,job[i].at,job[i].tat,job[i].wt);
printf("Avg TAT=%f\nAvg WT=%f\n",tat_sum/n,wt_sum/n);
}
void main()
{
int n,q,c,i;
printf("Enter the number of processes:\n");
scanf("%d",&n);
printf("Enter the arrival time and burst time\n");
for(i=0;i<n;i++)
{
printf("Job%d: ",i+1);
scanf("%d%d",&job[i].at,&job[i].bt);
}
while(1)
{
printf("1.RR\n2.SRJF\n3.Exit\n");
scanf("%d",&c);
switch(c)
{
case 1: printf("Enter time quantum: ");
scanf("%d",&q);
scheduler(job,n,q,0);
break;
case 2: scheduler(job,n,1,1);
break;
case 3: exit(0);
}
}
}
8. Design, develop and implement a C/C++/Java program to implement Banker’s algorithm.
Assume suitable input required to demonstrate the results.

#include <stdio.h>
#include <stdlib.h>
int main()
{
int Max[10][10], need[10][10], alloc[10][10], avail[10], completed[10], safeSequence[10];
int p, r, i, j, process, count = 0;
printf("Enter the no of processes : ");
scanf("%d", &p);
for(i = 0; i< p; i++)
completed[i] = 0;

printf("\n\nEnter the no of resources : ");

scanf("%d", &r);
printf("\n\nEnter the Max Matrix for each process : ");
for(i = 0; i < p; i++)
{
printf("\nFor process %d : ", i + 1);
for(j = 0; j < r; j++)
scanf("%d", &Max[i][j]);
}

printf("\n\nEnter the allocation for each process : ");

for(i = 0; i < p; i++)
{
printf("\nFor process %d : ",i + 1);
for(j = 0; j < r; j++)
scanf("%d", &alloc[i][j]);
}

printf("\n\nEnter the Available Resources : ");

for(i = 0; i < r; i++)
scanf("%d", &avail[i]);
for(i = 0; i < p; i++)
for(j = 0; j < r; j++)
need[i][j] = Max[i][j] - alloc[i][j];

do
{
printf("\n Max matrix:\tAllocation matrix:\n");
for(i = 0; i < p; i++)
{
for( j = 0; j < r; j++)
printf("%d ", Max[i][j]);
printf("\t\t");
for( j = 0; j < r; j++)
printf("%d ", alloc[i][j]);
printf("\n");
}
 process = -1;
for(i = 0; i < p; i++)
{
if(completed[i] == 0)//if not completed
{
process = i ;

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

{
if(avail[j] < need[i][j])
{
process = -1;
break;
}
}
}
if(process != -1)
break;
}
if(process != -1)
{
printf("\nProcess %d runs to completion!", process + 1);
safeSequence[count] = process + 1;
count++;
for(j = 0; j < r; j++)
{
avail[j] += alloc[process][j];
alloc[process][j] = 0;
Max[process][j] = 0;
completed[process] = 1;
}
}
} while(count != p && process != -1);

if(count == p)
{
printf("\nThe system is in a safe state!!\n"); printf("Safe Sequence : < ");
for( i = 0; i < p; i++)
printf("%d ", safeSequence[i]);
printf(">\n");
}
else
printf("\nThe system is in an unsafe state!!");
}
9. Design, develop and implement a C/C++/Java program to implement page replacement
algorithms LRU and FIFO. Assume suitable input required to demonstrate the results.

#include<stdio.h>
void fifo();
void lru();
main()
{
int ch;
do
{
printf("\n MENU\n");
printf("1.FIFO\n2.LRU\n3.EXIT\n");
printf("Enter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1: fifo();break;
case 2: lru();break;
case 3: exit(0);
default: printf("Invalid choice\n");
}
}while(ch!=3);
}
//*********FIFO FUNCTION************************8
void fifo()
{
int i,j,n,a[30],frame[10],no,k,avail,count=0;
printf("\n ENTER THE REFERENCE STRING LENGTH:\n");
scanf("%d",&n);
printf("\n ENTER THE REFERENCE STRING:\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("\n ENTER THE NUMBER OF FREE FRAMES :");
scanf("%d",&no);
for(i=0;i<no;i++)
frame[i]= -1;
j=0;
for(i=1;i<=n;i++)
{

avail=0;
for(k=0;k<no;k++)
if(frame[k]==a[i])
avail=1;
if (avail==0)
{
frame[j]=a[i];
j=(j+1)%no;
count++;
for(k=0;k<no;k++)
printf("%d\t",frame[k]);
}
printf("\n");
}
printf("Page Fault Is %d",count);

//************************ LRU FUNCTION *************************************

int findLRU(int time[], int n)
{
int i, minimum = time[0], pos = 0;

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

{
if(time[i] <minimum)
{
minimum = time[i];
pos = i;
}
}

return pos;
}

void lru()
{
int no_of_frames, no_of_pages, frames[10], pages[30], counter = 0, time[10], flag1, flag2, i, j, pos,
faults = 0;
printf("\n ENTER THE REFERENCE STRING LENGTH:\n");
scanf("%d", &no_of_pages);
printf("\n ENTER THE REFERENCE STRING:\n");
for(i = 0; i<no_of_pages; ++i)
{
scanf("%d", &pages[i]);
}
printf("\n ENTER THE NUMBER OF FREE FRAMES :");
scanf("%d", &no_of_frames);
for(i = 0; i<no_of_frames; ++i)
{
frames[i] = -1;
}

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

{
flag1 = flag2 = 0;

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

{
if(frames[j] == pages[i])
{
counter++;
time[j] = counter;
flag1 = flag2 = 1;
break;
}
}
 if(flag1 == 0){
for(j = 0; j <no_of_frames; ++j){
if(frames[j] == -1){
counter++;
faults++;
frames[j] = pages[i];
time[j] = counter;
flag2 = 1;
break;
}
}
}

if(flag2 == 0){
pos = findLRU(time, no_of_frames);
counter++;
faults++;
frames[pos] = pages[i];
time[pos] = counter;
}

printf("\n");

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

{
printf("%d\t", frames[j]);
}
}
printf("\n\nTotal Page Faults = %d", faults);
}
5. Design, develop and implement a C/Java program to generate the machine code using
Triples for the statement A = -B * (C +D) whose intermediate code in three-address form:
T1 = -B
T2 = C + D
T3 = T1 + T2
A = T3

#include<stdio.h>
#include<stdlib.h>
char op[5][5],arg1[5][5],arg2[5][5],result[5][5];
int i,n;
main()
{
printf("\n Input Statement is A=-B*(C+D)");
printf("\n Enter Input in Three Address Code : ");
printf("\n Enter number of lines in code : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("\n %s %s %s %s",result[i],arg1[i],op[i],arg2[i]);
}
printf("\n Machine Code Generation");
for(i=0;i<n;i++)
{
if(strcmp(op[i],"+")==0)
{
printf("\n Mov R0,%s",arg1[i]);
printf("\n ADD R0,%s",arg2[i]);
printf("\n Mov %s,R0",result[i]);
}
if(strcmp(op[i],"-")==0)
{
printf("\n Mov R0,%s",arg1[i]);
printf("\n SUB R0,%s",arg2[i]);
printf("\n Mov %s,R0",result[i]);
}
if(strcmp(op[i],"*")==0)
{
printf("\n Mov R0,%s",arg1[i]);
printf("\n MUL R0,%s",arg2[i]);
printf("\n Mov %s,R0",result[i]);
}
if(strcmp(op[i],"/")==0)
{
printf("\n Mov R0,%s",arg1[i]);
printf("\n DIV R0,%s",arg2[i]);
printf("\n Mov %s,R0",result[i]);
}
if(strcmp(op[i],"=")==0)
{
printf("\n Mov R0,%s",arg1[i]);
printf("\n Mov %s,R0",result[i]); }
}
}