Lab Manual: Subject Name: Subject Code: Programme Name: B.Tech. CSE Regulation: 2018

B.
Tech-CSE SYSTEM SOFTWARE AND COMPILER DESIGN BCS18L07

FORM NO. F/LAB/001 Rev.00 Date 01.01.2014
Subject Name: SYSTEM SOFTWARE AND COMPILER DESIGN LAB

Subject code: BCS18L07
Programme Name: B.Tech. CSE
Regulation: 2018
LAB MANUAL
B.Tech-CSE SYSTEM SOFTWARE AND COMPILER DESIGN BCS18L07
TABLE OF CONTENTS
S.NO EXPERIMENTS PAGE NO
1 Symbol Table 3
2 Assembler 7
3 Loader 10
13
4 Lexical Analyzer using “C”.
5 Constructing NFA from a regular expression 16
6 Constructing DFA from a regular expression 21
24
7 To eliminate Left Factoring
8 Constructing top down parsing table 29
9 Shift-reduce parsing algorithm. 34
10 Operator-Precedence parsing algorithm. 37
11 Constructing LR-Parsing table. 40
12 Generate a code for a given intermediate code 45
Generate Machine code.

13 48
SYMBOL TABLE
EX. No1
Aim:
To write a c program for implementing the symbol table.
Algorithm:
Step 1: start
Step 2: create a structure “syt” containing fields for the c datatypes and its associated memory
bytes.
Step 3: Create modules for performing the symbol table maintainence operation.
Step 4: Get the input file “out.c” from the user.
Step 5: compare the values from the input file with the structure variables.
Step 5.1: If a match occurs between the C Keywords like
“int”,”float”,”double”,”long”,”short” then they will be displayed under
Datatype columns of the symtab.
Step 5.1.1: then the corresponding bytes occupied will be displayed under the bytes
column of the symbol table.
Step 5.2: If no match occurs then display it under the variables column of the symtab.
Step 6: stop the Program.
PROGRAM:
# include<stdio.h>
# include<conio.h>
# include<string.h>
struct syt
{
char v[10],t[10];
int s;
} st[50];
char *tt[] = {"int","float","long","double","short"};
int vt[5]= {2,4,6,8,1};
FILE *fp;
void main()
{
char *fn,u[20],t[20],s[100],*p;
int i=0,j,k,l,y,sp=0;
clrscr();
printf("\n Enter file name: ");
scanf("%s",fn);
printf("\n The given file name is %s",fn);
fp=fopen(fn,"r");
printf("\nSymbol table maintenance");
3
printf("\n\tVariable\tType\t\tsize\n");
while(!feof(fp))
{
fscanf(fp,"%s",s);
for(i=0;i<5;i++)
if(strcmp(s,tt[i])==0)
{
fscanf(fp,"%s",s);
p=strchr(s,',');
if(p)
{
j=0;
while(s[j]!=',')
j++;
for(k=0;k<j;k++)
t[k]=s[k];
t[k]='\0';
printf("\n%10s\t%10s\t%10d",t,tt[i],vt[i]);
strcpy(st[sp].v,t);
strcpy(st[sp].t,tt[i]);
st[sp].s=vt[i];
sp++;
kjk:
y=j;
j++;
while(s[j]!='\0'&&s[j]!=',')
j++;
for(l=y;l<j;l++)
t[l-2]='\0';
printf("\n%10s\t%10s\t%10d",t,tt[i],vt[i]);
st[sp].s=vt[i];
sp++;
if(s[j]==',')
goto kjk;
} else {
printf("\n%10s\t%10s\t%10d",s,tt[i],vt[i]);
strcpy(st[sp].v,t);
st[sp].s=vt[i];
}
}
}
fclose(fp);
for(i=0;i<sp;i++)
strcpy(t,st[i].v);
k=0;
for(j=0;j<strlen(t);j++)
{
if(t[i]!=',')
{
u[k]=u[j];
k++;
}
u[k]='\0';
strcpy(st[i].v,u);
}
for(i=0;i<sp-2;i++)
for(j=i+1;j<sp;j++)
{
if(strcmp(st[i].v,st[j].v)==0)
printf("\n\nMultiple Declaration for %s",st[i].v);
}
getch(); }
5
INPUT FILE:
out.c
main()
{
int a
float b
double c
long d
}
OUTPUT:
Enter file name: out.c

The given file name is out.c
Symbol table maintenance
Variable Type size
a int 2
b float 4
c double 8
d long 6
Result:
Thus the C Program For implementing Symbol Table has been executed and verified
successfully.
ASSEMBLER
Ex. No.2:
Aim:
To write a c program for implementing the assembler
Algorithm:
step1: start
step2: Get the input file “res.cpp” containing the assembly codes from user
step3: if opcode is “MVI” read the operands from the input file and store it in the registers
‘AREG’ and ‘BREG’
step4:Create Modules For Performing the ‘ADD’,’SUB’,’Mul’ operations.
step5:compare the opcode from the input file with the keywords
Step 5.1:If opcode is ADD perform addition operation on the operands.
Step 5.2:If opcode is SUB perform subtraction operation on the operands
Step 5.3:If opcode is MUL perform Multiplication operation on the operands.
Step 6: If opcode is “STOP” then exit.
Step 7: stop.
PROGRAM:
# include<stdio.h>
# include<conio.h>
# include<string.h>
# include<ctype.h>
# include<stdlib.h>
void main()
{
FILE *f;
char x[40],data[40],reg[40];
int a=0,b=0,i,j,result=0,temp,c,d;
clrscr();
printf("\t\tOUTPUT\n");
f=fopen("res.cpp","r");
while(!feof(f))
{
fscanf(f,"%s",x);
if(strcmp(x,"STOP")==0)
exit(0);
else if(strcmp(x,"MVI")==0)
{
fscanf(f,"%s%s",reg,data);
if(strcmp(reg,"AREG,")==0)
a=atoi(data);
7
else if(strcmp(reg,"BREG,")==0)
b=atoi(data);
}
else
{
if(strcmp(x,"ADD")==0)
{
result=a+b;
printf("\n\tI:%d",a);
printf("\n\tJ:%d",b);
printf("\nRESULT(I+J):%d",result);
}
else if(strcmp(x,"SUB")==0)
{
result=a-b;
printf("\n\tI:%d",a);
printf("\n\tJ:%d",b);
printf("\nResult(I-J):%d",result);
}
else if(strcmp(x,"MUL")==0)
{
result=a*b;
printf("\nI:%d",a);
printf("\nJ:%d",b);
printf("\nresult(I*J):%d",result);
}
getch();
}
}
}
INPUT FILE:
MVI AREG, 10
MVI BREG, 15
ADD AREG, BREG
MOVE RES, AREG
PRINT RES
Res DS 1
STOP
OUTPUT:
OUTPUT
I:10
J:15
RESULT(I+J):25
Result:
Thus the C program for implementing assembler has been executed and verified successfully
9
LOADER
EX. No: 3
Aim
Implementation of Absolute loader using c program
Algorithm for absolute loader

Start the program
Assign the required variable
Open the files
fp1=fopen("input.dat","r");
fp2=fopen("output.dat","w");
Read the content
Using while loop perform the loop until character is not equal to E
while(strcmp(input,"E")!=0)
Then compare the character is equal to H
If H then
fscanf(fp1,"%d",&start);
Like that get length, and input
Else if the character is T
Then
Then perform the frprintf in fp1 for input file for ,
input[0],inuput[1] for address
input[2],inuput[3] for address+1
Else if it is not H or T
Then perform the frprintf in fp2 for output file for ,
input[0],inuput[1] for address
fprintf(fp2,"%d\t%c%c\n",address,input[0],input[1]);
fprintf(fp2,"%d\t%c%c\n",(address+1),input[2],input[3]);
address+=3;
fscanf(fp1,"%s",input);
Finally terminate the program
Source code program in c performing Absoluter Loader
# include <stdio.h>
# include <conio.h>
# include <string.h>
void main()
{
char input[10];
int start,length,address;
FILE *fp1,*fp2;
clrscr();
fp1=fopen("input.dat","r");
fp2=fopen("output.dat","w");
while(strcmp(input,"E")!=0)
{
if(strcmp(input,"H")==0)
{
fscanf(fp1,"%d",&start);
fscanf(fp1,"%d",&length);
}
else if(strcmp(input,"T")==0)
{
fscanf(fp1,"%d",&address);
address+=3;
}
else
{
address+=3;
}
}
fclose(fp1);
fclose(fp2);
printf("FINISHED");
getch();
}
11
INPUT FILE
INPUT.DAT
H 1000 232
T 1000 142033 483039 102036
T 2000 298300 230000 282030 302015
E
OUTPUT FILE
OUTPUT.DAT
1000 14
1001 20
1002 33
1003 48
1004 30
1005 39
1006 10
1007 20
1008 36
2000 29
2001 83
2002 00
2003 23
2004 00
2005 00
2006 28
2007 20
2008 30
2009 30
2010 20
2011 15
Result:
Thus the C Program For implementing Absolute Loader has been executed and verified
successfully.
LEXICAL ANALYZER
EX.NO:4
AIM:
To write a C program to generate the of the Lexical Analyzer
ALGORITHM:
 Reads an input stream of characters.
 Copies the input stream to an output stream.
 Breaks the input stream into smaller strings that match the extended regular expressions in
the lex specification file.
 Executes an action for each extended regular expression that it recognizes. These actions are C
language program fragments in the lex specification file. Each action fragment can call actions or
subroutines outside of itself.
PROGRAM:
#include<string.h>
#include<ctype.h>
#include<stdio.h>
void keyword(char str[10])
{ if(strcmp("for",str)==0||strcmp("while",str)==0||strcmp("do",str)==0||
strcmp("int",str)==0||strcmp("float",str)==0||strcmp("char",str)==0||
strcmp("double",str)==0||strcmp("static",str)==0||strcmp("switch",str)==0||
strcmp("case",str)==0)
printf("\n%s is a keyword",str);
else
printf("\n%s is an identifier",str);
}
main()
{
FILE *f1,*f2,*f3;
char c,str[10],st1[10];
int num[100],lineno=0,tokenvalue=0,i=0,j=0,k=0;
printf("\nEnter the c program");/*gets(st1);*/
f1=fopen("input","w");
while((c=getchar())!=EOF)
putc(c,f1);
fclose(f1);
13
f1=fopen("input","r");
f2=fopen("identifier","w");
f3=fopen("specialchar","w");
while((c=getc(f1))!=EOF)
{
if(isdigit(c))
{
tokenvalue=c-'0';
c=getc(f1);
while(isdigit(c))
{
tokenvalue*=10+c-'0';
c=getc(f1);
}
num[i++]=tokenvalue;
ungetc(c,f1);
} else if(isalpha(c))
{
putc(c,f2);
c=getc(f1);
while(isdigit(c)||isalpha(c)||c=='_'||c=='$')
{
putc(c,f2);
c=getc(f1);
}
putc(' ',f2);
ungetc(c,f1);
} else if(c==' '||c=='\t')
printf(" ");
else if(c=='\n')
lineno++;
else
putc(c,f3);
}
fclose(f2);
fclose(f3);
fclose(f1);
printf("\nThe no's in the program are");
for(j=0;j<i;j++)
printf("%d",num[j]);
printf("\n");
f2=fopen("identifier","r");
k=0;
printf("The keywords and identifiersare:");
{
if(c!=' ')
str[k++]=c;
else
{
str[k]='\0';
keyword(str);
k=0;
}
}
fclose(f2);
f3=fopen("specialchar","r");
printf("\nSpecial characters are");
printf("%c",c);
printf("\n");
fclose(f3);
printf("Total no. of lines are:%d",lineno);
}
OUTPUT:
RESULT:
Hence, the given program has been executed and the output has been verified successfully.
15
CONSTRUCTING NFA FROM A REGULAR EXPRESSION

EX.NO:5
AIM:
To write a C program to convert the regular expression to NFA.
ALGORITHM:
1. Start the program.

2. Declare all necessary header files.
3. Define the main function.
4. Declare the variables and initialize variables r & c to ‘0’.
5. Use a for loop within another for loop to initialize the matrix for NFA states.
6. Get a regular expression from the user & store it in ‘m’.
7. Obtain the length of the expression using strlen() function and store it in ‘n’.
8. Use for loop upto the string length and follow steps 8 to 12.
9. Use switch case to check each character of the expression.
10. If case is ‘/’, set the links as ‘E’ or suitable inputs as per rules.
11. If case is ‘*’, set the links as ‘E’ or suitable inputs as per rules.
12. If case is ‘+’, set the links as ‘E’ or suitable inputs as per rules.
13. Check the default case, i.e.,for single alphabet or 2 consecutive alphabets and set the links to
respective alphabet.
14. End the switch case.
15. Use for loop to print the states along the matrix.
16. Use a for loop within another for lop and print the value of respective links.
17. Print the states start state as ‘0’ and final state.
18. End the program.
PROGRAM:
#include<stdio.h>
#include<conio.h>
void main()
{
char m[20],t[10][10];
int n,i,j,r=0,c=0;
clrscr();
printf("\n\t\t\t\tSIMULATION OF NFA");
printf("\n\t\t\t\t*****************");
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
t[i][j]=' ';
}
}
printf("\n\nEnter a regular expression:");
scanf("%s",m);
n=strlen(m);
for(i=0;i<n;i++)
{
switch(m[i])
{
case '|' : {
t[r][r+1]='E';
t[r+1][r+2]=m[i-1];
t[r+2][r+5]='E';
t[r][r+3]='E';
t[r+4][r+5]='E';
t[r+3][r+4]=m[i+1];
r=r+5;
break;
}
case '*':{
t[r-1][r]='E';
t[r][r+1]='E';
t[r][r+3]='E';
t[r+1][r+2]=m[i-1];
t[r+2][r+1]='E';
t[r+2][r+3]='E';
r=r+3;
break;
17
}
case '+': {
t[r][r+1]=m[i-1];
t[r+1][r]='E';
r=r+1;
break;
}
default:
{
if(c==0)
{
if((isalpha(m[i]))&&(isalpha(m[i+1])))
{
t[r][r+1]=m[i];
t[r+1][r+2]=m[i+1];
r=r+2;
c=1;
}
c=1;
}
else if(c==1)
{
if(isalpha(m[i+1]))
{
t[r][r+1]=m[i+1];
r=r+1;
c=2;
}
}
else
{
if(isalpha(m[i+1]))
{
t[r][r+1]=m[i+1];
r=r+1;
c=3;
}
}
}
break;
}
}
printf("\n");
for(j=0;j<=r;j++)
printf(" %d",j);
printf("\n___________________________________\n");
printf("\n");
for(i=0;i<=r;i++)
{
for(j=0;j<=r;j++)
{
printf(" %c",t[i][j]);
}
printf(" | %d",i);
printf("\n");
}
printf("\nStart state: 0\nFinal state: %d",i-1);
getch();
}
19
OUTPUT:
Enter a regular Expression: a|b
SIMULATION OF NFA
*****************
Enter a regular expression:a|b
0 1 2 3 4 5
___________________________________
E E |0
a |1
E |2
b |3
E |4
|5
Start state: 0
Final state: 5
RESULT:
CONSTRUCTING DFA FROM A REGULAR EXPRESSION

EX.NO:6
AIM:
To write a C program to convert the regular expression to DFA.
ALGORITHM:

2. A structure is created and the variables are declared.
4. Declare the array for states and inpstr.
5. Define the readtt function to initialize the number of states, number of inputs and transition from
one state to other.
6. Get the no. of states and no. of inputs from the user.
7. Start the for loop and continue till it satisfies the condition.
8. Print the states according to the condition.
9. Generate the initial and final states of the string.
10. Define the dfasimul function to simulate it step 10-16.
11. Initialize the variable start to ‘0’ and begin for loop.
12. Check whether start is equal to ‘-1’, then print “DFA Halted”.
13. Get the string from the user and save in ‘inpstr’.
14. Read the string and until the end-of-string reached do step 15.
15. Go from one state to other based on the transition entered and update start by the final state.
16. Print “string is accepted” if a state is equal to nstates-1.
17. Else print “String is not accepted”.
18. Display the output.
21
PROGRAM:
#include<stdio.h>
#include<conio.h>
typedef struct
{
int input[2];
}state;
void readtt(state *states,int nstates,int ninps)

{
int state,inp;
printf("Enter the state transition:\n");
for(state=0;state<nstates;state++)
for(inp=0;inp<ninps;inp++)
{
printf("(state:%d,%d):",state,inp);
scanf("%d",&states[state].input[inp]);
}
}
void dfasimul(state *states,int nstates,char *inpstr)

{
int i,start;
start=0;
for(i=0;inpstr[i]!='\0';i++)
{
start=states[start].input[inpstr[i]-'0'];
}
if(start==-1)
{
printf("DFA halted");
return;
}
else if(start==nstates-1)
printf("String is accepted");
else
printf("String is not accepted");
}
void main()
{
state states[100];
int nstates,ninps;
char inpstr[20];
clrscr();
printf("\n\t\t\t SIMULATION OF DFA");
printf("\n\t\t\t *****************");
printf("\nEnter the no. of states: ");
scanf("%d",&nstates);
printf("Enter the no.of inputs: ");

scanf("%d",&ninps);
readtt(states,nstates,ninps);
printf("\nInitial state: 0\nFinal state: %d",nstates-1);
printf("\n\nEnter the string: ");
scanf("%s",inpstr);
dfasimul(states,nstates,inpstr);
getch();
}
OUTPUT:
SIMULATION OF DFA
*****************
Enter the no. of states: 2
Enter the no.of inputs: 2
Enter the state transition:
(state:0,0):0
(state:0,1):1
(state:1,0):0
(state:1,1):1
Initial state: 0
Final state: 1
Enter the string: 1001

String is accepted
Enter the no. of states: 2

Enter the no.of inputs: 2
Enter the state transition:
(state:0,0):0
(state:0,1):1
(state:1,0):0
(state:1,1):1
Initial state: 0
Final state: 1
Enter the string: 0110

String is not accepted
RESULT:
23
ELIMINATING LEFT FACTORING

Ex No:7
AIM:
To write a C program to eliminate left factoring.
ALGORITHM:
Step 1: Following the first rule, S->cAd to parse S
Step 2:The next non=term in line A is parsed using first rule, A -> ab , but turns out INCORRECT,
parser backtracks
Step 3:Next rule to parse A is taken A->a, turns out CORRECT. String parsed completely, parser stops.
PROGRAM :
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<string.h>
//Structure Declaration
struct production
{
char lf;
char rt[10];
int prod_rear;
int fl;
};
struct production prodn[20],prodn_new[20]; //Creation of object
//Variables Declaration
int b=-1,d,f,q,n,m=0,c=0;
char terminal[20],nonterm[20],alpha[10],extra[10];
char epsilon='^';
//Beginning of Main Program
void main()
{
clrscr();
//Input of Special characters

cout<<"\nEnter the number of Special characters(except non-terminals): ";

cin>>q;
cout<<"Enter the special characters for your production: ";
for(int cnt=0;cnt<q;cnt++)
{
cin>>alpha[cnt];
}
//Input of Productions
cout<<"\nEnter the number of productions: ";

cin>>n;
for(cnt=0;cnt<=n-1;cnt++)
{
cout<<"Enter the "<< cnt+1<<" production: ";
cin>>prodn[cnt].lf;
cout<<"->";
cin>>prodn[cnt].rt;
prodn[cnt].prod_rear=strlen(prodn[cnt].rt);
prodn[cnt].fl=0;
}
//Condition for left factoring
for(int cnt1=0;cnt1<n;cnt1++)
{
for(int cnt2=cnt1+1;cnt2<n;cnt2++)
{
if(prodn[cnt1].lf==prodn[cnt2].lf)
{
cnt=0;
int p=-1;
while((prodn[cnt1].rt[cnt]!='\0')&&(prodn[cnt2].rt[cnt]!='\0'))
{
if(prodn[cnt1].rt[cnt]==prodn[cnt2].rt[cnt])
{
extra[++p]=prodn[cnt1].rt[cnt];
prodn[cnt1].fl=1;
prodn[cnt2].fl=1;
}
else
{
if(p==-1)
break;
else
25
{
int h=0,u=0;
prodn_new[++b].lf=prodn[cnt1].lf;
strcpy(prodn_new[b].rt,extra);
prodn_new[b].rt[p+1]=alpha[c];
prodn_new[++b].lf=alpha[c];
for(int g=cnt;g<prodn[cnt2].prod_rear;g++)
prodn_new[b].rt[h++]=prodn[cnt2].rt[g];
for(g=cnt;g<=prodn[cnt1].prod_rear;g++)
prodn_new[b].rt[u++]=prodn[cnt1].rt[g];
m=1;
break;
}
}
cnt++;
}
if((prodn[cnt1].rt[cnt]==0)&&(m==0))
{
int h=0;
prodn_new[b].rt[0]=epsilon;
}
if((prodn[cnt2].rt[cnt]==0)&&(m==0))
{
int h=0;
prodn_new[b].rt[0]=epsilon;
}
c++;
m=0;
}
}
}
//Display of Output
cout<<"\n\n********************************";
cout<<"\n AFTER LEFT FACTORING ";
cout<<"\n********************************";
cout<<endl;
for(int cnt3=0;cnt3<=b;cnt3++)
{
cout<<"Production "<<cnt3+1<<" is: ";
cout<<prodn_new[cnt3].lf;
cout<<"->";
cout<<prodn_new[cnt3].rt;
cout<<endl<<endl;
}
for(int cnt4=0;cnt4<n;cnt4++)
{
if(prodn[cnt4].fl==0)
{
cout<<"Production "<<cnt3++<<" is: ";
cout<<prodn[cnt4].lf;
cout<<"->";
cout<<prodn[cnt4].rt;
cout<<endl<<endl;
}
}
getche();
} //end of main program
27
OUTPUT
RESULT:
TOP DOWN PARSING

Ex No. 8
AIM:
To write a C program to implement top down parsing using arrays.
ALGORITHM:

2. A structure is created and the variables are declared.
4. Declare the array for states and inpstr.
5. Define the readtt function to initialize the number of states ,number of inputs,and transition
from one state to other.
6. Get the no. of states and no. of inputs from the user.
7. Start the for loop and continue till it satisfies the condition.
8. Print the states according to the condition.
9. Generate the initial and final states of the string.
10. Define the dfasimul function to simulate it step 10-16.
11. Initialize the variable start to ‘0’ and begin for loop.
12. Check whether start is equal to ‘-1’, then print “DFA Halted”.
13. Get the string from the user and save in ‘inpstr’.
14. Read the string and until the end-of-string reached do step 15.
15. Go from one state to other based on the transition entered and update start by the final state.
16. Print “string is accepted” if a state is equal to nstates-1.
17. Else print “String is not accepted”.
18. Display the output.
PROGRAM:
#include<conio.h>
29
#include<string.h>
#include<stdlib.h>
void error()
{
cout<<"not accepted";
getch();
exit(0);
}
void main()
{
clrscr();
cout<<"Enter the string in single letter such as a+a*a \n\n";
char string[10],stack[10];
int i=0,k,top=0;
cout<<"Enter the Expression :";
cin>>string;
int j=strlen(string);
string[j]='$';
string[++j]='\0';
cout<<string<<endl;
stack[top]='E';
cout<<"$"<<stack<<"\t";
for(k=i;k<j;k++)
{
cout<<string[k];
}
cout<<endl;
top++;
while(top!=0)
{
if(stack[top-1]==string[i])
{
i++;
top--;
stack[top]='\0';
}
else if(stack[top-1]=='E')
{
if(string[i]=='a')
{
top--;
stack[top]='D';
stack[++top]='T';
top++;
stack[top]='\0';
}
else if(string[i]=='(')
{
top--;
stack[top]='D';
stack[++top]='T';
top++;
stack[top]='\0';
}
else error();
}
else if(stack[top-1]=='D')
{
if(string[i]=='+')
{
top--;
stack[top]='D';
stack[++top]='T';
stack[++top]='+';
top++;
stack[top]='\0';
}
else if(string[i]==')')
{
top--;
stack[top]='\0';
}
else if(string[i]=='$')
{
top--;
stack[top]='\0';
}
else error();
}
else if(stack[top-1]=='T')
{
if(string[i]=='a')
{
top--;
stack[top]='s';
stack[++top]='F';
top++;
stack[top]='\0';
}
{
top--;
stack[top]='s';
stack[++top]='F';
31
top++;
stack[top]='\0';
}
else error();
}
else if(stack[top-1]=='s')
{
if(string[i]=='+')
{
top--;
stack[top]='\0';
}
else if(string[i]=='*')
{
top--;
stack[top]='s';
stack[++top]='F';
stack[++top]='*';
top++;
stack[top]='\0';
}
else if(string[i]==')')
{
top--;
stack[top]='\0';
}
else if(string[i]=='$')
{
top--;
stack[top]='\0';
}
else error;
}
else if(stack[top-1]=='F')
{
if(string[i]=='a')
{
top--;
stack[top]='a';
top++;
stack[top]='\0';
}
{
top--;
stack[top]=')';
stack[++top]='E';
stack[++top]='(';
top++;
stack[top]='\0';
}
else error();
}
else error();
cout<<"$"<<stack<<"\t";
for(k=i;k<j;k++)
{
cout<<string[k];
}
cout<<endl;
}
cout<<"accepted";
getch();
}
OUTPUT:
Enter the string in single letter such as a+a*a
enter the expression :a*a
a*a$
$E a*a$
$DT a*a$
$DsF a*a$
$Dsa a*a$
$Ds *a$
$DsF* *a$
$DsF a$
$Dsa a$
$Ds $
$D $
$ $
accepted
RESULT:
SHIFT REDUCE PARSING

Ex No. 9
33
AIM:
To write a C program to perform the shift reduce parsing.
ALGORITHM:

3. Declare array for string and stack and other necessary variables.
4. Get the expression from the user and store it as string.
5. Append $ to the end of the string.
6. Store $ into the stack.
7. Print three columns as ‘Stack’, ‘String’ and ‘Action’ for the respective actions.
8. Use for loop from i as 0 till string length and check the string.
9. If string has some operator or id, push it to the stack.
10. Mark this action as ‘Shift’.
11. Print the stack, string and action values.
12. If stack contains some production on shifting, reduce it.
13. Mark this action as ‘Reduce’.
14. Print the stack, string and action values.
15. Repeat steps 9 to 14 again and again till the for loop is valid.
16. Now check the string and the stack.
17. If the string contains only $ and the stack has only $E within it, then print that the ‘given string is
valid’.
18. Else print that the ‘given string is invalid’.
PROGRAM:
#include<stdio.h>
#include<string.h>
#include<conio.h>
void main()
{
char str[25],stk[25];
int i,j,t=0,l,r;
clrscr();
printf("Enter the String : ");
scanf("%s",&str);
l=strlen(str);
str[l]='$';
stk[t]='$';
printf("Stack\t\tString\t\tAction\n-----------------------------------\n ");
for(i=0;i<l;i++)
{
if(str[i]=='i')
{
t++;
stk[t]=str[i];
stk[t+1]=str[i+1];
for(j=0;j<=t+1;j++)
printf("%c",stk[j]);
printf("\t\t ");
for(j=i+2;j<=l;j++)
printf("%c",str[j]);
printf("\t\tShift");
printf("\n ");
stk[t]='E';
i++;
}
else
{
t++;
stk[t]=str[i];
}
for(j=0;j<=t;j++)
printf("\t\t ");
for(j=i+1;j<=l;j++)
printf("%c",str[j]);
if(stk[t]=='+' || stk[t]=='*')
printf("\t\tShift");
else
printf("\t\tReduce");
printf("\n ");
}
while(t>1)
{
if(stk[t]=='E' && (stk[t-1]=='+' || stk[t-1]=='*') && stk[t-2]=='E')
{
35
t-=2;
for(j=0;j<=t;j++)
printf("\t\t");
printf(" %c",str[l]);
printf("\t\tReduce\n ");
}
else
t-=2;
}
if(t==1 && stk[t]!='+' && stk[t]!='*')

printf("\nThe Given String is Valid\n\n");
else
printf("\nThe Given String is Invalid\n\n");
getch();
}
OUTPUT:
Enter the String : id+id*id
Stack String Action

-----------------------------------
$id +id*id$ Shift
$E +id*id$ Reduce
$E+ id*id$ Shift
$E+id *id$ Shift
$E+E *id$ Reduce
$E+E* id$ Shift
$E+E*id $ Shift
$E+E*E $ Reduce
$E+E $ Reduce
$E $ Reduce
The Given String is Valid
RESULT:
OPERATOR PRECEDENCE PARSING

Ex No. 10
AIM:
To write a C program for implementing operator precedence parsing for given grammar.
ALGORITHM:

2. Declare all necessary header files and variables
3. Assign all the precedence relation for given grammar in a 2 d array
4. Get input from user in an array
5. Append $ symbol at the end of the input
6. Create stack using array and put $ as first element
7. Display the contents of stack and input array
8. If last element of stack and input is $ then the parsing is completed
9. Compare top of stack and top of input use find function to get element
10. If the symbol is space print parser error
11. If the symbol is < then shift top element of input to stack.
13. If the symbol is > then remove all elements from stack
15. End of the program.
PROGRAM:
#include<stdio.h>
#include<conio.h>
int find(char a)
{
switch(a)
{
case 'a':
return 0;
case '+':
return 1;
case '*':
return 2;
case '$':
return 3;
}
}
37
void display(char a[],int top1,char b[],int top2)

{
int i;
for(i=0;i<=top1;i++)
printf("%c",a[i]);
printf("\t");
for(i=top2;i<strlen(b);i++)
printf("%c",b[i]);
printf("\n");
}
int main()
{
char table[][4]= {' ','>','>','>','<','<','<','>','<','>','<','>','<','<','<',' '};
char input[10];
char stack[10]={'$'};
int top_stack=0,top_input=0,i,j;
clrscr();
printf("operator precedence parsing for E->E+E/E*E/a\n");
printf("enter the string\n");
scanf("%s",input);
strcat(input,"$");
printf("stack\tinput\n");
display(stack,top_stack,input,top_input);
while(1)
{
if((stack[top_stack]=='$')&&(input[top_input]=='$'))
{
printf("string accepted");
break;
}
if(table[find(stack[top_stack])][find(input[top_input])]==' ')
{
printf("parse error");
getch();
exit(0);
}
if(table[find(stack[top_stack])][find(input[top_input])]=='<')
{
stack[++top_stack]='<';
stack[++top_stack]=input[top_input];
top_input++;
continue;
}
if(table[find(stack[top_stack])][find(input[top_input])]=='>')
{
stack[++top_stack]='>';
top_stack-=3;
}
}
getch();
}
OUTPUT:
Operator precedence parsing for E->E+E/E*E/a

Enter the string
a+a*a
stack input
$ a+a*a$
$<a +a*a$
$<a> +a*a$
$ +a*a$
$<+ a*a$
$<+<a *a$
$<+<a> *a$
$<+ *a$
$<+<* a$
$<+<*<a $
$<+<*<a> $
$<+<* $
$<+<*> $
$<+ $
$<+> $
$ $
string accepted
RESULT:
SLR PARSING TABLE CONSTRUCTION
Ex No. 11
39
AIM:
To write a C++ program to generate a parsing table for SLR Parsing.
ALGORITHM:

2. Declare all necessary header files and variables.
3. construct SLR parsing table for all the states and fill the Action and Goto first.
4. Insert the initial state as 0 in the stack.
5. Compare with the first input symbol.
6. Action is taken according to general parsing table.
7. If action=Shift, goto step 8 else step 9
8. push the symbol in stack.
9. If action= Reduce, pop the symbol from the stack, replace by the non terminal symbol, else goto
step 10.
10. if action=goto, push the state number in the stack.
11. If action= accept, it implies the parsing is successful.
12. end the program.
PROGRAM:
#include<conio.h>
#include<fstream.h>
#include<string.h>
#include <cfg.h>
void main()
{
clrscr();
g.getdfg();
int h[100],count=0,rt=0,found=0;
set_of_item cc[20];
str t=putdot (g.p[0],2);
cc[0] = closure(t.ele);
int tab[20][20];
for(int i=0; i<20; i++)
for(int j=0; j<20;j++)
tab [i][j] =0;
int m=0;
count++;
char a[20];
int ll=0;
for (i=0; i<g.nv;i++)
{
a[i]=g.v[i];
}
for(j=0; j=g.nt;j++)
{
a[i]=g.t[j];
i++;
a[i]=’$’;
i++;
a[i]=’\0’;
for(i=0; i<count; i++)
{
m=0;
for(j=0; j<g.nv; j++)
{
found = 0;
set_of_item t=go_to(cc[i],g.v[j]);
if(t.c !=0)
{
for(int k =0; k<count ; k++)
if(cc[k] equals (t) ==1)
{
for(int ml=0; ml<strlen (a) ;ml++)
{
m=ml;
tab [i] [m] =k;
m++;
}
}
found=1;
break;
}
if (found != 1)
{
for (int ml=0; ml<strlen (a); ml++)
{
if (a[ml] == g.v[j];
{
m=ml;
tsb [i] [m] = count;
m++;
41
}
}
cc [count++] =t;
}
}
}
for (j=0; j<g.nt; j++)
{
found=0;
set_of_item t = go_to(cc [i], g.t[j]);
if(t.c != 0)
{
for(int k=0; k<count ;k++)
if(cc [k].equals (t) ==1)
{
fpr(int ml=0; ml<strlen(a) ;ml++)
{
if(a[ml] == g.t [j])
{
m=ml;
tab[i] [m] = k;
m++;
}
}
found=1;
break;
}
if(found !=1)
{
for(int ml=0;ml<strlen(a); ml++)
{
if(a[ml] == g.v[j]);
{
m=ml;
tab[i] [m] =count;
m++;
}
}
cc[count++]=t;
}
}
}
for(j=0;j<g.nt;j++)
{
found=0;
set_of_item t=go_to(cc[i],g.t[j]);
if(t.c !=0)
{
for(int ml=0;ml<strlen(a);ml++)
{
if(a[ml] ==g.t[j])
{
m=ml;
tab [i][m] =k;
m++;
}
}
found=1;
break;
}
if(poped==tab[0][j])
break;
}
}
else
{
cout<<”not accepted”;
getch();
exit(0);
}
}
cout<<”accepted”;
getch();
}
OUTPUT:
IN.DAT
3
5
7
E
T
F
+
*
(
)
I
S=E
E=E+T
43
E=T
T=T*F
T= F
F=(E)
F=i
SLR-TABLE
E T F + * ( ) I $
0 1 2 3 S4 S5
1 S6
2 r2 S7 r2 r2
3 r4 r4 r4 r4
4 8 2 3 S4 S5
5 r6 r6 r6 r6
6 9 3 S4 S5
7 10 S4 S5
8 S6 S11
9 r1 S7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
RESULT:
INTERMEDIATE CODE GENERATOR
Ex No. 12
AIM:
To write a C++ program to generate the intermediate code.
ALGORITHM:

2. Declare the array and other necessary variables.
4. Get the expression from the user.
5. Scan the expression and put it in array ‘t’.
6. Check the position of 2, 0 & 4 characters is alphabets.
7. Print the expression and MOV R t the character in 2nd position.
8. Else print “Enter the correct expression”.
9. Start switch case for 3rd symbol and follow the steps 10 to
10. If ‘*’ then print MUL character at 4th position with R.
11. Print MOV R to character at position 0.
12. If ‘+’ then print ADD character at 4th position with R.
14. If ‘-’ then print SUB character at 4th position with R.
16. If ‘/’ then print DIV character at 4th position with R.
18. For default case, print “Invalid operator”.
PROGRAM:
# include<stdio.h>
# include<conio.h>
# include<ctype.h>
45
char s[20],t[20];
void main()
{
clrscr();
printf("Enter the expression: ");
scanf("%s",&t);
if(isalpha(t[2])&&isalpha(t[0])&&isalpha(t[4]))
{
printf("Mov%c,R \n",t[2]);
}
else
printf("Enter correct exp: ");
switch(t[3])
{
case '*':
printf("MUL%c,R \n",t[4]);
printf("MOVR,%c \n",t[0]);
break;
case '+':
printf("ADD%c,R \n",t[4]);
break;
case '-':
printf("SUB%c,R \n",t[4]);
break;
case '/':
printf("DIV%c,R \n",t[4]);
break;
default:
printf("INVALID OPERATOR");
break;
}
getch();
}
OUTPUT:
Enter the expression: a=b+c

Mov b,R
ADD c,R
MOV R,a
RESULT:
GENERATE MACHINE CODE.

Ex No. 13
AIM:
To write a C program to generate the machine code.
47
ALGORITHM:
1. Loads each operand only once.

2. Performs each operation only once.
3. Does no stores.
4. Minimal number of registers having the above three properties.
1. Show need L registers to produce a result with label L.
2. Must compute one side and no use the register containing its answer before finishing the
other side.
3. Apply this argument recursively.
5. Load: LD R, x
1. Desc(R) = x (removing everything else from Desc(R))
2. Add R to Desc(x) (leaving alone everything else in Desc(x))
3. Remove R from Desc(w) for all w ≠ x (not in 2e please check)
6. Store: ST x, R
1. Add the memory location of x to Desc(x)
7. Operation: OP Rx, Ry, Rz implementing the quad OP x, y, z
1. Desc(Rx) = x
2. Desc(x) = Rx
3. Remove Rx from Desc(w) for all w ≠ x
8. Copy: For x = y after processing the load (if needed)
1. Add x to Desc(Ry) (note y not x)
2. Desc(x) = R
PROGRAM:
#include <stdlib.h>
#include <string.h>
int label[20];
int no = 0;
int main()
{
FILE *fp1, *fp2;
char fname[10], op[10], ch;
char operand1[8], operand2[8], result[8];
int i = 0, j = 0;
printf("\n Enter filename of the intermediate code");
scanf("%s", &fname);
fp1 = fopen(fname, "r");
fp2 = fopen("target.txt", "w");
if (fp1 == NULL || fp2 == NULL)
{
printf("\n Error opening the file");
exit(0);
}
while (!feof(fp1))
{
fprintf(fp2, "\n");
fscanf(fp1, "%s", op);
i++;
if (check_label(i))
fprintf(fp2, "\nlabel#%d", i);
if (strcmp(op, "print") == 0)
{
fscanf(fp1, "%s", result);
fprintf(fp2, "\n\t OUT %s", result);
}
if (strcmp(op, "goto") == 0)
{
fscanf(fp1, "%s %s", operand1, operand2);
fprintf(fp2, "\n\t JMP %s,label#%s", operand1, operand2);
label[no++] = atoi(operand2);
}
if (strcmp(op, "[]=") == 0)
{
fscanf(fp1, "%s %s %s", operand1, operand2, result);
fprintf(fp2, "\n\t STORE %s[%s],%s", operand1, operand2, result);
}
if (strcmp(op, "uminus") == 0)
{
fscanf(fp1, "%s %s", operand1, result);
fprintf(fp2, "\n\t LOAD -%s,R1", operand1);
fprintf(fp2, "\n\t STORE R1,%s", result);
}
switch (op[0])
{
case '*':
fprintf(fp2, "\n \t LOAD", operand1);
fprintf(fp2, "\n \t LOAD %s,R1", operand2);
fprintf(fp2, "\n \t MUL R1,R0");
fprintf(fp2, "\n \t STORE R0,%s", result);
break;
case '+':
fprintf(fp2, "\n \t ADD R1,R0");
break;
case '-':
49
fprintf(fp2, "\n \t SUB R1,R0");

break;
case '/':
fprintf(fp2, "\n \t DIV R1,R0");
break;
case '%':
fprintf(fp2, "\n \t DIV R1,R0");
break;
case '=':
fscanf(fp1, "%s %s", operand1, result);
fprintf(fp2, "\n\t STORE %s %s", operand1, result);
break;
case '>':
j++;
fprintf(fp2, "\n\t JGT %s,label#%s", operand2, result);
label[no++] = atoi(result);
break;
case '<':
fprintf(fp2, "\n\t JLT %s,label#%d", operand2, result);
label[no++] = atoi(result);
break;
}
}
fclose(fp2);
fclose(fp1);
fp2 = fopen("target.txt", "r");
if (fp2 == NULL)
{
printf("Error opening the file\n");
exit(0);
}
do
{
ch = fgetc(fp2);
printf("%c", ch);
}
while (ch != EOF);

fclose(fp1);
return 0;
}
int check_label(int k)
{
int i;
for (i = 0; i < no; i++)
{
if (k == label[i])
return 1;
}
return 0;
}
Input.txt
=t1 2
[]=a 0 1
[]=a 1 2
[]=a 2 3
*t1 6 t2
+a[2] t2 t3
-a[2] t1 t2
/t3 t2 t2
uminus t2 t2
print t2
goto t2 t3
=t3 99
uminus 25 t2
*t2 t3 t3
uminus t1 t1
+t1 t3 t4
print t4
Output.txt
Enter filename of the intermediate code: input.txt
STORE t1,2
STORE a[0],1
STORE a[1],2
STORE a[2],3
LOAD t1,R0
51
LOAD 6,R1
ADD R1,R0
STORE R0,t3
LOAD a[2],R0
LOAD t2,R1
ADD R1,R0
STORE R0,t3
LOAD a[t2],R0
LOAD t1,R1
SUB R1,R0
STORE R0,t2
LOAD t3,R0
LOAD t2,R1
DIV R1,R0
STORE R0,t2
LOAD t2,R1
STORE R1,t2
LOAD t2,R0
JGT 5,label#11
Label#11: OUT t2
JMP t2,label#13
Label#13: STORE t3,99
LOAD 25,R1
STORE R1,t2
LOAD t2,R0
LOAD t3,R1
MUL R1,R0
STORE R0,t3
LOAD t1,R1
STORE R1,t1
LOAD t1,R0
LOAD t3,R1
ADD R1,R0
STORE R0,t4
OUT t4
RESULT:
Hence, the given program has been executed and the output has been verified successfully

Lab Manual: Subject Name: Subject Code: Programme Name: B.Tech. CSE Regulation: 2018

Uploaded by

Copyright:

Available Formats

Lab Manual: Subject Name: Subject Code: Programme Name: B.Tech. CSE Regulation: 2018

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lab Manual: Subject Name: Subject Code: Programme Name: B.Tech. CSE Regulation: 2018

Uploaded by

Copyright:

Available Formats

B.

Tech-CSE SYSTEM SOFTWARE AND COMPILER DESIGN BCS18L07

Subject Name: SYSTEM SOFTWARE AND COMPILER DESIGN LAB

S.NO EXPERIMENTS PAGE NO

5 Constructing NFA from a regular expression 16

6 Constructing DFA from a regular expression 21

8 Constructing top down parsing table 29

9 Shift-reduce parsing algorithm. 34

10 Operator-Precedence parsing algorithm. 37

11 Constructing LR-Parsing table. 40

12 Generate a code for a given intermediate code 45

Generate Machine code.

Enter file name: out.c

Algorithm for absolute loader

Source code program in c performing Absoluter Loader

To write a C program to generate the of the Lexical Analyzer

 Reads an input stream of characters.

 Copies the input stream to an output stream.

CONSTRUCTING NFA FROM A REGULAR EXPRESSION

To write a C program to convert the regular expression to NFA.

1. Start the program.

Enter a regular Expression: a|b

CONSTRUCTING DFA FROM A REGULAR EXPRESSION

To write a C program to convert the regular expression to DFA.

1. Start the program.

void readtt(state *states,int nstates,int ninps)

void dfasimul(state *states,int nstates,char *inpstr)

printf("Enter the no.of inputs: ");

Enter the string: 1001

Enter the no. of states: 2

Enter the string: 0110

ELIMINATING LEFT FACTORING

To write a C program to eliminate left factoring.

Step 1: Following the first rule, S->cAd to parse S

//Beginning of Main Program

//Input of Special characters

cout<<"\nEnter the number of Special characters(except non-terminals): ";

cout<<"\nEnter the number of productions: ";

//Condition for left factoring

TOP DOWN PARSING

To write a C program to implement top down parsing using arrays.

1. Start the program.

enter the expression :a*a

SHIFT REDUCE PARSING

To write a C program to perform the shift reduce parsing.

1. Start the program.

if(t==1 && stk[t]!='+' && stk[t]!='*')

Enter the String : id+id*id

Stack String Action

The Given String is Valid

OPERATOR PRECEDENCE PARSING

1. Start the program.

void display(char a[],int top1,char b[],int top2)

Operator precedence parsing for E->E+E/E*E/a

SLR PARSING TABLE CONSTRUCTION

To write a C++ program to generate a parsing table for SLR Parsing.

1. Start the program.

INTERMEDIATE CODE GENERATOR

To write a C++ program to generate the intermediate code.

void dfasimul(state states,int nstates,char inpstr)