Steps to install lex and yaac tool

1. Go to google classroom and download mingw

2. In Downloads you will find this

3. Double click on that, this window you get click next

4. Do nothing click next

5. Create a folder in C: (or) in C drive and give it a name

6. Click on browse and select the folder where you have created
7. Click next, wait until the download completes. See to that your internet connection is on

8. Sir has sent this zip file in whatsapp, download this and extract

9. Click on this

10. you will see this, copy all files

11. go to the folder where mingw is installed. In my case it is C:/lexandyaac/mingw32/bin

Paste all these files in bin folder.

12. That’s it with your installation.

13. Now to check whether it is working fine or not

Go to the folder where mingw is installed

In my case C:/lexandyaac/

Click on this a command prompt opens

Notepad opens type in below code

Save the file with “.l”(l for leg), save as type should be always “All files”

Finally for compiling and running see below pic

This is what he taught on 27/04/2021 lab session.

05/05/2021

1. test1.l
2. Using command line arguments and getting input from r.txt -test1.l is used

3. test2.l and l.txt is used

4. vowel and consonant count – test3.l and vowel.txt is used

5. using yyless(n) concept

5. Demonstration of yymore() -using test5.l (note: yytext value can be read through printf or just
by giving {ECHO;yymore();} )
Concept of YYLESS(N) and YYMORE(N)

YYLESS(N):

Example: YYLESS(3) is given and input string is: jit-is in bangalore

Jit- {yyless(2);} //jit- will be printed,only first 2 characters are kept in yytext and remaining t- is
appended to input. Now input will become:

t-is in bangalore // t is also matched by the rule [a-z]+ and is printed on screen, when it sees
“-“ it is not matched so it is printed as it is.

And finally “is”,”in” and “bangalore” is printed so the final o/p is

Jit-

Is

In

Bangalore

Note new line characters are printed so it is printed in same line:

Jit-t-is in bangalore.

6. Demonstration of “a1{1,3}”, this regular expression matches a 1-3 times. Test6.l is used
7. ^ and $ demonstration
8. Program 1 to check whether a given expression is a valid arthmetic expression or not. Prg1.l is
used

11/05/2021

9. Program to recognize how many lines, words, characters ,spaces in a file. Pg1.l and count.txt is
used.

Meta characters: *,+,?,{ ^: surcumflex symbol }

$, {}, () , . ,/,[]

Jit is in Bengaluru

Bengaluru is green city

Mysore is in Karnataka

For the above 3 statements we write rules like below:

[a-z]+ { wc++; cc+=yyleng;}

\n {lc++;cc++};

“ “ {cc++;}
Another way of writing the above code. Pg2.l and count.txt is used

Removal of single line comments pg5.l and comments.txt and comment1.txt is used

Removal of multi line comments,pg6.l ,comments.txt and comment2.txt is used

Program to read data from multiple files and display the line, word and letter count.

Pg7.l,star.txt and star1.txt is used

Check valid email id-pg9.l is used
To detect multiple spaces and tabs and convert that to single -pg10.l,star2.txt and star3.txt is used

YACC tool: -25/05/2021

Tool which will produce a parser for a given grammar that recognizes valid sentences in the
grammar.

->YACC(Yet Another Compiler Compiler) is a program designed to compile LALR(1)

Structure:

1. Definition section: header files, global variables

2. Specify tokens: Precedency, associativity, specify start symbol

3. Rule section: Grammar rules along with action part.

4. User-defined functions

General Instructions:

 Extension for YACC program is “.y”.

 Parser will have yyparse(). Yyparse() has the parse table.
 Upon error it calls yyerror(char *s). In the string S the error is stored.
 Lex program that in-turn recognizes the input and passes the token to the parser.
 Lex program can be written in 2 ways
 One is through writing yylex() in yaac program.
 Second is by writing separate lex program with “.l” extension (dot L).
 Description of table is present in y.out
 WORKING:

 Yyparse() will call yylex()

 Yylex() read input and identify tokens
 yylex() pases the tokens to parser.
 Parser will apply shift,reduce operations. And asks or next token.

Compilation process:

 Win_bison -d filename1.y
 -d is used because, token information is there in filename1.tab.h, to create this we use -d.
 This filename1.tab.h is used in lex program in the declaration section. #include
“filename1.tab.h” .
 Filename1.tab.h is specified in double quotes because wherever that file is present it will
load to the current program. If specified within a pair of angular brackets
{#include<stdio.h> } It searches in the current directory in the include folder.
 Once you get no errors, compile lex program using win_flex filename2.l
 Now run as : gcc filename1.tab.c lex.yy.c.

What Yaac cannot parse

Although yacc's parsing technique is general, you can write grammars which yacc cannot handle.
It cannot deal with ambiguous grammars, ones in which the same input can match more than
one parse tree.* It also cannot deal with grammars that need more than one token of lookahead
to tell whether it has matched a rule

Example 1: Program to generate equal number of a’s followed by equal number of b’s.

Yaccexample.y and lexo.l programs are used.

Lab program: to check anb, lab.y and lexo.l programs are used.
Lex program in yaac for the same code, lab1.y is used
Program to recognized declarative statement
Output:

YAAC PROGRAM TO IDENTIFY VARIABLES

S: L A NOTE: L(letters), D(digits), U(underscore) and S,A are non terminals.

|U A

A: L A

|D A

|U A

LAB PROGRAM:

Write a Yaac program to identify operators, keywords, numbers and identifiers.

 Extern is used to import an external variable yyin.

Output:

Write a YAAC program to check whether a given expression is valid Arithmetic Expression or
not

If

%left '+' '-'

%left '*' '/'

This is not written then we get 16 shift/reduce conflicts

Note: “aa+-“ this string was treated invalid in above program

After changes

Here -c is considered as negation and “aa+-c” is considered as aa+(-c).

Lab program:Simple Calculator yaac program , cal.y is used

To read a two digit number – cal1.y is used

Ungetc – reads a first number and checks if it is a digit, and then put back that digit back to input
stream.
Floating point expression- cal3.y is used

Lab program: Demonstrate shift reduce parser

Calculator with lex program separately -cal5.y

To read multiple expressions -cal6.y and cal6.l is used

Error recovery in yaac program

yyerrok() will remove all the elements on the stack whenever a error occurs.

Arithmetic expression using Floating point numbers

Binary to decimal yaac program

1011

Sum=0

Sum=sum+d

Sum=0+1=1

Sum=sum*2+d

Sum=1*2+0=2+0=2

Sum=2*2+1=5

Sum=5*2+1=11

Fractional binary 111.011

111 is 7 in binary by above method 0*(1/2)+ 1*(1/4) + 1*(1/8)

Or 011 in binary 3/2^3 = 3/8 = 0.375 that highlighted 3 indicates number of digits after dot

SDD FOR THIS

LAB PROGRAM:

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

Solution:

A= -B * (C + D)

3 address code:

T1=uminus b

T2= c+d

T3 = T1*T2

a=T3
assembly code:

mov destination,src

add destination,src

sub destination,src

mul destination,src

div destination,src

Assembly code for the above expression:

Mov r0, -b

Mov t1, r0

Mov r0,c

Add r0,d

Mov t2,r0

Mov r0,t1

Mul r0,t2

Mov t3,r0

Mov r0,t3

Mov a,r0

Input for the program is 3 address code which will be in a file.

Input file contains:

Result arg1 operator arg2

T1 -b = ?

T2 c + d

T3 t1 * t2

A t3 =

We will use: fscanf(fp1,”%s%s%s%s”,result,arg1,op,arg2) //where fp1 is a file pointer

If(strcmp(op,”=”)==0)

Fprintf(fp2,”MOV r0,%s\n,arg1);
Fprintf(fp2,”Mov %s,r0”,result);

If(strcmp(op,’+’)==0)

Fprintf(fp2,Mov r0,%s\n”,arg1);

Fprintf(fp2,”Add r0,%s\n”,arg2);

Fprintf(fp2,”Mov %s,r0\n”,result);

Program:

#include<stdio.h>
#include<string.h>
void main(int argc,char *argv[])
{
FILE *fp1,*fp2;
char res[10], arg1[10], arg2[10],op[10];
fp1 = fopen(argv[1],"r");
fp2 = fopen(argv[2],"w");
while(!feof(fp1))
{
fscanf(fp1,"%s%s%s%s",res,arg1,op,arg2);
if(strcmp(op,"=")==0)
{
fprintf(fp2,"MOV r0,%s\n",arg1);
fprintf(fp2,"Mov %s,r0\n",res);
}
if(strcmp(op,"+")==0)
{
fprintf(fp2,"Mov r0,%s\n",arg1);
fprintf(fp2,"Add r0,%s\n",arg2);
fprintf(fp2,"Mov %s,r0\n",res);
}
if(strcmp(op,"*")==0)
{
fprintf(fp2,"Mov r0,%s\n",arg1);
fprintf(fp2,"MUL r0,%s\n",arg2);
fprintf(fp2,"Mov %s,r0\n",res);
}
if(strcmp(op,"-")==0)
{
fprintf(fp2,"Mov r0,%s\n",arg1);
fprintf(fp2,"SUB r0,%s\n",arg2);
fprintf(fp2,"Mov %s,r0\n",res);
}
if(strcmp(op,"/")==0)
{
fprintf(fp2,"Mov r0,%s\n",arg1);
fprintf(fp2,"DIV r0,%s\n",arg2);
fprintf(fp2,"Mov %s,r0\n",res);
}
}
fclose(fp1);
fclose(fp2);
}
Input_file.txt
T1 -b = ?
T2 c + d
T3 t1 * t2
A t3 = ?
Output_file.txt
Lab program
A->aBa, B->bB|epsilon
First(A)={a}
First(B)={b,epsilon}
Follow(A)={$}
Follow(B)={a,Follow(B)}
Follow(B)={a}

a b $

A A->aBa
B B->epsilon B->bB

Stack input action

A$ abba$ A->aBa
aBa$ abba$ match a
Ba$ bba$ B->Bb
bBa$ ba$ match b
Ba$ ba$ B->Bb
bBa$ ba$ match b
Ba$ a$ B->epsilon
a$ a$ match a
$ $ accept
Char table[3][4][20]
Char production[3][20]={“A->aBa”,”B->Bb”,”B->@”}
Char first[3][20]={“a”,”b”,”@”}
Char follow[3][20]={“$”,”a”,”a”}
Char stack[30]
Int top=-1
Char input[30];
Void push(char item)
{
Stack[++top]=item;
}
Void pop()
{
Top--;
}
Int pos(char c)
{
Switch(c):
{ case ‘A’: return 1;
Case ‘B’: return 2;
Case ‘a’: return 1;
Case ‘b’: return 2;
Case ‘c’: return 3;
}
}
I=0;
While(stack[top]!=’$’ && input
Program-7:
#include<stdio.h>
#include<stdlib.h>
int p,ar[20],bt[20],tat[20],wt[20],ct[20],i,j,k,sq=0,temp,count=0,r[10],tq,swt=0,stat=0,end,time;
void roundrobin()
{
while(1)
{
for(i=0;i<p;i++)
{temp=tq;
if(bt[i]==0)
{
count++;
continue;
}
if(bt[i]>tq)
{
bt[i]=bt[i]-tq;
}
else if(bt[i]>0)
{
temp=bt[i];
bt[i]=0;
}
sq=sq+temp;
tat[i]=sq;

}
if(p==count)
{
break;
}
 }
for(i=0;i<p;i++)
{
wt[i]=tat[i]-r[i];
swt=swt+wt[i];
stat=stat+tat[i];
}
printf("process\tbt\ttat\twt\n");
for(i=0;i<p;i++)
{
printf("%d\t%d\t%d\t%d\n",i,r[i],tat[i],wt[i]);
}
printf("average turn-arround time=%f\naverage waiting time=%f\n",(float)swt/p,
(float)stat/p);
}
void strs()
{ int smallest;
bt[p]=9999;
for(time=0;count!=p;time++)
{
smallest=p;
for(i=0;i<p;i++)
{
if(ar[i]<=time && bt[i]<bt[smallest] && bt[i]>0)
{
smallest=i;
}
}
bt[smallest]--;
if(bt[smallest]==0)
{
count++;
 end=time+1;
ct[smallest]=end;
tat[smallest]=ct[smallest]-ar[smallest];
wt[smallest]=tat[smallest]-r[smallest];
swt=swt+wt[smallest];
stat+=tat[smallest];
}
}

printf("process\tbt\ttat\twt\n");
for(i=0;i<p;i++)
{
printf("%d\t%d\t%d\t%d\n",i,r[i],tat[i],wt[i]);
}
printf("average turn-arround time=%f\naverage waiting time=%f\n",(float)swt/p,(float)stat/p);

}
main()
{
int ch;
printf("enter number of processes:\n");
scanf("%d",&p);
printf("Enter burst time of all processes\n");
for(i=0;i<p;i++)
{
printf("enter burst time of %d\n",i);
scanf("%d",&bt[i]);
r[i]=bt[i];
}
while(1)
{
 printf("1. Round robin\n2. Strf\n 3. exit\n");
printf("enter choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("enter time quantum");
scanf("%d",&tq);
roundrobin();
break;
case 2: printf("enter arrival time\n");
for(i=0;i<p;i++)
{
scanf("%d",&ar[i]);
}
strs();
break;
case 3:
return(0);
}
}
}

Round-Robin Scheduling algorithm

Shortest remaining time first