RAJ KUMAR GOEL INSTITUTE OF
TECHNOLOGY AND MANAGEMENT,
GHAZIABADAffiliated to Dr. A.P.J. Abdul kalam
Technical University, Lucknow
COMPILER DESIGN LAB
(KCS-552)
Session: 2023-24
Submitted by: Submitted to:
Vashu Gupta Mr. Nitin Kumar
(2103330100089) (Assistant Professor)
Deptt. Of CSE
COMPILER DESIGN LAB (KCS – 552)
S.No. List of Programs
1 Write a program in C/C++ to show the transition table from a given transition diagram.
2 Write a program in C/C++ to implement a lexical analyzer.
3 Write a program in C/C++ to find the FIRST set for a given set of
production rule of a grammar.
4 Write a program in C/C++ to find a FOLLOW set from a given set of production rule.
5 Write a program in C/C++ to generate intermediate code from a given syntax tree
statement.
6 Write a program in C/C++ to generate Intermediate Code (Postfix Expression) from given
syntax tree
7 Write a program in C/C++ to implement the shift reduce parsing.
8 Write a program in C or C++ to Construct DAG for input expression.
Program No. 1
Write a program in C/C++ to show the transition table from a given transition diagram.
Algorithm:
Start
Enter the number of states.
Enter the number of input variables.
Enter the state and its information.
Enter the input variables.
Enter the transition function information i.e. transition value from a state with a input variable.
Show the Transition Table.
Stop
Program (tt.c):
// write a program to display transition table on the screen
#include<stdio.h>
#include<stdlib.h>
struct setStates
{
int state;
int final; // 0 - NO 1 - YES
int start; // 0 - NO 1 - YES
};
typedef struct setStates sstate;
void main()
{
int s,v,i,j;
int **sv,*var;
sstate *states;
printf("\nInput the number of finite set of states : ");
scanf("%d",&s);
printf("\nInput the number of finite set of input variables : ");
scanf("%d",&v);
// creating transition table
sv = (int **)malloc(v*sizeof(int));
//printf("\n1 sucess\n");
for(i=0;i<s;i++)
{
sv[i]=(int *)malloc(sizeof(int));
}
/*printf("\n2 sucess\n");
printf("\nThe Array : \n");
for(i=0;i<s;i++)
{
for(j=0;j<v;j++)
{
printf("%d\t",sv[i][j]);
}
printf("\n");
}*/
// storing state information
states = (sstate *)malloc(s*sizeof(sstate));
printf("\nInput the states and its info (state start final): \n");
for(i=0;i<s;i++)
{
scanf("%d%d%d",&states[i].state,&states[i].start,&states[i].final);
}
// storing input veribale
var = (int *)malloc(v*sizeof(int));
printf("\nInput the veriables : \n");
for(i=0;i<v;i++)
{
scanf("%d",&var[i]);
}
// storing inputs of transition function
for(i=0;i<s;i++)
{
for(j=0;j<v;j++)
{
printf("\nThe sates %c with input veribale %c move to state : ",states[i].state,var[j]);
scanf("%d",&sv[i][j]);
}
}
// display transition table on screen
printf("\nThe Transition Table : \n");
printf("\t");
for(i=0;i<v;i++)
{
printf("%c\t",var[i]);
}
printf("\n ");
for(i=0;i<s;i++)
{
printf("\n%c %c %c\t",states[i].state,(states[i].start==0)?' ':'$',(states[i].final==0)?' ':'*'); for(j=0;j<v;j++)
{
printf("%c\t",sv[i][j]);
}
printf("\n");
}
}
Output:
Input the number of finite set of states : 4
Input the number of finite set of input veriables : 2
Input the states and its info (state start final): 97 1 1
98 0 0
99 0 0
100 0 0
Input the variables :
48
49
The sates a with input variable 0 move to state : 98 The sates
a with input variable 1 move to state : 99 The sates b with
input variable 0 move to state : 100 The sates b with input
variable 1 move to state : 97 The sates c with input variable 0
move to state : 97
The sates c with input variable 1 move to state : 100 The
sates d with input variable 0 move to state : 100 The sates d
with input variable 1 move to state : 98
The Transition Table : 0 1
a $ *b c
d a
a d
d b
Result: The Program Executed successfully
Program No. 2
Aim: Write a program in C/C++ to implement a lexical analyzer.
Algorithm:
1. Start
2. Get the input expression from the user.
3. Store the keywords and operators.
4. Perform analysis of the tokens based on the ASCII values.
5.
ASCII Range TOKEN TYPE
97-122 Keyword else identifier
48-57 Constant else operator
Greater than 12 Symbol
6. Print the token types.
7. Stop
Program (lexi.c):
/* Lexical Analyzer */
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<string.h>
void main()
char key[11][10]={"for","while","do","then","else","break","switch","case","if","continue"};
char oper[13]={'+','-','*','/','%','&','<','>','=',';',':','!'};
char a[20],b[20],c[20];
int i,j,l,m,k,flag;
clrscr();
printf("\n Enter the expression: ");
gets(a);
i=0;
while(a[i])
flag=0;
j=0;
l=0;
b[0]='\0';
if((toascii(a[i]>=97))&&(toascii(a[i]<=122)))
if((toascii(a[i+1]>=97))&&(toascii(a[i+1]<=122)))
while((toascii(a[i]>=97))&&(toascii(a[i]<=122)))
b[j]=a[i];
j++; i++;
} b[j]='\
0';
else
b[j]=a[i]; i+
+; b[j+1]='\
0';
for(k=0;k<=9;k++)
if(strcmpi(b,key[k])==0)
flag=1;
break;
if(flag==1)
printf("\n %s is the keyword",b);
else
printf("\n %s is the identifier",b);
else if((toascii(a[i]>=48))&&(toascii(a[i]<=57)))
if((toascii(a[i+1]>=48))&&(toascii(a[i+1]<=57)))
while((toascii(a[i]>=48))&&(toascii(a[i]<=57)))
c[l]=a[i];
l++; i++;
else
c[l]=a[i];
i++;l++;
} c[l]='\
0';
printf("\n %s is the constant",c);
}//second ifelse
else
for(m=0;m<13;m++)
{
if(a[i]==oper[m])
printf("\n %c is the operator",a[i]);
break;
if(m>=13)
printf("\n %c is the symbol",a[i]);
i++;
}//last else
} //while
getch();
Output:
Enter the expression: while(i<5)break
while is the keyword
( is the symbol
i is the identifier
< is the operator
5 is the constant
) is the symbol
break is the keyword
Enter the expression: if(b>20)continue
if is the keyword
( is the symbol
b is the identifier
> is the operator
20 is the constant
) is the symbol
continue is the keyword
Result: The Program Executed successfully
Program No. 3
Aim: Write a program in C/C++ to find the FIRST set for a given set of production rule of a
grammar.
Algorithm:
Procedure First
1. Input the number of production N.
2. Input all the production rule PArray
3. Repeat steps a, b, c until process all input production rule i.e. PArray[N]
a. If Xi ≠ Xi+1 then
i. Print Result array of Xi which contain FIRST(Xi)
b. If first element of Xi of PArray is Terminal or ε Then
i. Add Result = Result U first element
c. If first element of Xi of PArray is Non-Terminal Then
i. searchFirst(i, PArray, N)
4. End Loop
5. If N (last production) then
a. Print Result array of Xi which contain FIRST(Xi)
6. End
Procedure searchFirst(i, PArray, N)
1. Repeat steps Loop j=i+1 to N
a. If first element of Xj of PArray is Non-Terminal Then
i. searchFirst(j, of PArray, N)
b. If first element of Xj of PArray is Terminal or ε Then
i. Add Result = Result U first element
ii. Flag=0
2. End Loop
3. If Flag = 0 Then
a. Print Result array of Xj which contain FIRST(Xj)
4. End
Program:
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
void searchFirst(int n, int i, char pl[], char r[], char result[], int k)
int j,flag;
for(j=i+1;j<n;j++)
if(r[i]==pl[j])
if(isupper(r[j]))
searchFirst(n,j,pl,r,result,k);
if(islower(r[j]) || r[j]== '+' || r[j]=='*' || r[j]==')' || r[j]=='(')
result[k++]=r[j];
result[k++]=','; flag=0;
if(flag==0)
for(j=0;j<k-1;j++)cout<<result[j];
void main()
clrscr();
char pr[10][10],pl[10],r[10],prev,result[10];
int i,n,k,j;
cout<<"\nHow many production rule : ";
cin>>n;
if(n==0) exit(0);
for(i=0;i<n;i++)
cout<<"\nInput left part of production rules : ";
cin>>pl[i];
cout<<"\nInput right part of production rules : ";
gets(pr[i]);
r[i]=pr[i][0];
cout<<"\nProduction Rules are : \n";
for(i=0;i<n;i++)
cout<<pl[i]<<"->"<<pr[i]<<"\n";//<<";"<<r[i]<<"\n";
cout<<"\n----O U T P U T---\n\n";
prev=pl[0];k=0;
for(i=0;i<n;i++)
if(prev!=pl[i])
cout<<"\nFIRST("<<prev<<")={";
for(j=0;j<k-1;j++)cout<<result[j];
cout<<"}";
k=0;prev=pl[i];
//cout<<"\n3";
if(prev==pl[i])
if(islower(r[i]) || r[i]== '+' || r[i]=='*' || r[i]==')' || r[i]=='(')
{
result[k++]=r[i];
result[k++]=',';
if(isupper(r[i]))
cout<<"\nFIRST("<<prev<<")={";
searchFirst(n,i,pl,r,result,k);
cout<<"}";
k=0;prev=pl[i+1];
if(i==n)
cout<<"\nFIRST("<<prev<<")={";
for(j=0;j<k-1;j++)cout<<result[j];
cout<<"}";
k=0;prev=pl[i];
getch();
Output:
How many production rule : 8
Input left part of production rules : E
Input right part of production rules : TX
Input left part of production rules : X
Input right part of production rules : +TX
Input left part of production rules : X
Input right part of production rules : e
Input left part of production rules : T
Input right part of production rules : FY
Input left part of production rules : Y
Input right part of production rules : *FY
Input left part of production rules : Y
Input right part of production rules : e
Input left part of production rules : F
Input right part of production rules : (E)
Input left part of production rules : F
Input right part of production rules : i
Production Rules are :
E->TX
X- >+TX
X->e
T->FY
Y->*FY
Y->e
F->(E)
F->i
----O U T P U T---
FIRST(E)={(,i}
FIRST(X)={+,e}
FIRST(T)={(,i}
FIRST(Y)={*,e}
FIRST(F)={(,i}
How many production rule : 5
Input left part of production rules : E
Input right part of production rules : aTX
Input left part of production rules : E
Input right part of production rules : TX
Input left part of production rules : T
Input right part of production rules : FY
Input left part of production rules : F
Input right part of production rules : (E)
Input left part of production rules : F
Input right part of production rules : i
Production Rules are :
E->aTX
E->TX
T->FY
F->(E)
F->i
----O U T P U T---
FIRST(E)={a,(,i}
FIRST(T)={(,i}
FIRST(F)={(,i}
Result: The Program Executed successfully
Program No. 4
Aim: Write a program in C/C++ to find a FOLLOW set from a given set of production rule.
Algorithm:
1. Declare the variables.
2. Enter the production rules for the grammar.
3. Calculate the FOLLOW set for each element call the user defined function follow().
4. If x->aBb
a. If x is start symbol then FOLLOW(x)={$}.
b. If b is NULL then FOLLOW(B)=FOLLOW(x).
c. If b is not NULL then FOLLOW(B)=FIRST(b).
END.
Program:
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
int n,m=0,p,i=0,j=0;
char a[10][10],f[10];
void follow(char c);
void first(char c);
void main()
{clrscr();
int i,z;
char c,ch;
14
printf("Enter the no.of productions:");
scanf("%d",&n);
printf("Enter the productions(epsilon=$):\n");
for(i=0;i<n;i++)
scanf("%s%c",a[i],&ch);
do
{ m=
0;
printf("Enter the element whose FOLLOW is to be found:");
scanf("%c",&c);
follow(c);
printf("FOLLOW(%c) = { ",c);
for(i=0;i<m;i++)
printf("%c ",f[i]);
printf(" }\n");
printf("Do you want to continue(0/1)?");
scanf("%d%c",&z,&ch);
while(z==1);
void follow(char c)
{ if(a[0][0]==c)f[m+
+]='$';
for(i=0;i<n;i++)
15
for(j=2;j<strlen(a[i]);j++)
if(a[i][j]==c)
if(a[i][j+1]!='\0')first(a[i][j+1]);
if(a[i][j+1]=='\0'&&c!=a[i][0])
follow(a[i][0]);
}
}void first(char c)
int k; if(!
(isupper(c)))f[m++]=c;
for(k=0;k<n;k++)
if(a[k][0]==c)
if(a[k][2]=='$') follow(a[i][0]);
else if(islower(a[k][2]))f[m++]=a[k][2];
else first(a[k][2]);
Output:
Enter the no of productions :3
Enter the production (epsion =$):
E=E+T
T=T*F
F=a
Enter the element whose FOLLOW is to be found
;E FOLLOW(E)={$ +}
Do you want to continue (0/1)?1
Enter the element whose FOLLOW is to be found ;T
FOLLOW(T)={$ +}
Do you want to continue (0/1)?1
Enter the element whose FOLLOW is to be found ;F
FOLLOW(F)={$ +}
Do you want to continue (0/1)?0
Result: The Program Executed successfully
Program No. 5
Write a program in C/C++ to generate intermediate code from a given syntax tree statement.
Algorithm:
1. Start the process.
2. Input an expression EXP from user.
3. Process the expression from right hand side to left hand side.
4. FLAG:=0; TOP = -1;
5. IF EXP = ‘=’ then
i. IF EXP(index – 1) = 0 then
1. PRINT EXP element from index to (index – 1) and POP STACK[TOP]. Terminate
Else
i. PRINT Wrong Expression
[EndIF]
IF an operator is found and FLAG = 0 then
i. TOP:= TOP + 1
ii. add to STACK[TOP].
Else iii. FLAG:=1
i. pop twice the STACK and result add to the newID(identifier) and
PRINT.
ii. TOP:=TOP-2. Save newID to STACK[TOP]
iii. FLAG:=0
[EndIF]
6. IF an operand is found then
i. TOP:=TOP+1
ii. move to STACK [TOP]
iii. IF TOP > 1 then
1. pop twice the STACK and result add to the newID(identifier)
and PRINT.
2. TOP:=TOP-2. Save newID to STACK[TOP]
3. FLAG:=0
[End]
7.
s
s
(i
):
/* Intermediate Code Generator */
// Here consideration is any input expression
// only
contain
digits at
the end
#includ
e<iostre
am.h>
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
void main()
char g,exp[20],stack[20];
int m=0,i,top=-1,flag=0,len,j;
cout<<"\nInput an expression : ";
gets(exp);
cout<<"\nIntermediate code generator\n";
len=strlen(exp);
//If expression contain digits
if(isdigit(exp[len-1]))
cout<<"T = inttoreal(";
i=len-1;
while(isdigit(exp[i]))
i--;
for(j=i+1;j<len;j++)
cout<<exp[j];
cout<<".0)\n";
exp[i+1]='T';len=i+2;
}
else //If expression having no digit
cout<<"T = "<<exp[len-1]<<"\n";
exp[len-1]='T';
for(i=len-1;i>=0;i--)
if(exp[i]=='=')
if((i-1)==0)
// If expression contains unary operator in RHS near = operator
if(isalpha(stack[top]))
cout<<exp[i-1]<<" "<<exp[i]<<" "<<stack[top];
else
cout<<exp[i-1]<<" "<<exp[i]<<" "<<stack[top]<<stack[top-1];
break;
else
cout<<"\nWrong Expression !!!";
break;
if(exp[i]=='+'||exp[i]=='/'||exp[i]=='*'||exp[i]=='-'||exp[i]=='%')
{
if(flag==0)
flag=1;top=top+1;
stack[top]=exp[i];
else
g=char('A' + m);m++;
cout<<g<<" = "<<stack[top]<<stack[top-1]<<"\n";
stack[top-1]=g;
stack[top]=exp[i];
flag=0;
else
top=top+1;
stack[top]=exp[i];
if(top>1)
g=char('A' + m);m++;
cout<<g<<" = "<<stack[top]<<stack[top-1]<<stack[top-2]<<"\n";
top=top-2;
stack[top]=g;flag=0;
}
Output:
Input an expression : a=b+c-6
Intermediate code generator
T=6
A = c-T
B = b+A
a=B
Input an expression : d=e+f*-c%-a+k
Intermediate code generator
T=k
A = a+T
B = -A
C = c%B
D = -C
E = f*D
F = e+E
d=F
Result: The Program Executed successfully
Program No. 6
Write a program in C/C++ to generate Intermediate Code (Postfix Expression) from given syntax tree.
#include<stdio.h>
#include<conio.h>
char stack[20];
int top=-1;
void push(char x)
stack[++top]=x;
char pop()
if(top==-1){
return -1;
Else
return stack[top--];
//Check the priority of the operator.
int priority(char x)
if(x == ‘(‘)
return 0;
if(x == ‘+’ || x == ‘-‘)
return 1;
if(x == ‘*’ || x == ‘/’)
return 2;
}main()
char exp[20];
char *e , x;
clrscr();
printf(“Ënter the expression:”);
scanf(“%s”,&exp);
e = exp ;
while(*e != ‘\0’)
if(isalnum(*e))
printf(“%c”,*e);
else if(*e == ‘(‘)
push(*e);
else if(*e == ‘)’ )
while(( x =pop() ) != ‘( ‘ )
printf(“%c”,x);
else
//check greater priority operator.
while(priority(stack[top]) >= priority(*e) )
printf(“%c”, pop());
push(*e);
} e+
+;
while(top != -1)
{printf(“%c”,pop());
Output:
Result: The program executed successfully.
Program No. 7
Write a program in C/C++ to implement the shift reduce parsing.
Algorithm:
1. Start the Process.
2. Symbols from the input are shifted onto stack until a handle appears on top of the stack.
3. The Symbols that are the handle on top of the stack are then replaces by the left hand side of the
production (reduced).
4. If this result in another handle on top of the stack, then another reduction is done, otherwise we go back to
shifting.
5. This combination of shifting input symbols onto the stack and reducing productions when handles appear
on the top of the stack continues until all of the input is consumed and the goal symbol is the only thing on
the stack - the input is then accepted.
6. If we reach the end of the input and cannot reduce the stack to the goal symbol, the input is rejected.
7. Stop the process.
Program (srp.cpp):
/* Shift Reduce Parsing */
#include<stdio.h>
#include<conio.h>
#include<string.h>
void check();
void check1();
void copy();
void print(int val);
char stack[20];
char temp[10];
char result[10];
int i,j;
void main()
clrscr();
printf("Enter Your Expression:");
scanf("%s",&stack);
check();
getch();
void check()
for(;i<strlen(stack)+1;i++)
if(stack[i]=='+' || stack[i]=='-' || stack[i]=='*' || stack[i]=='/'|| stack[i]=='\0')
temp[j]='E';
j++;
temp[j]=stack[i];
j++;
check1();
void check1()
printf("\n STACK VALUES\tINPUT \n");
l: for(j=0,i=0;i<strlen(temp);)
if(temp[i]=='+' || temp[i]=='-' || temp[i]=='*' || temp[i]=='/')
{printf("\n\t
%c",temp[i]); i++;
print(i);
printf("\n\t %c",temp[i]);
i++;
print(i);
i--;
copy();
goto l;
else
printf("\n\t %c",temp[i]);
i++;
print(i);
printf("\n\n\t Expressions Output:%s",temp);
void copy()
j=0;
while(temp[i]!='\0')
temp[j]=temp[i];
j++;
i++;
temp[j]='\0';
}void print(int val)
printf("\t\t");
for(;val<strlen(temp);val++)
printf("%c",temp[val]);
Output:
Enter Your Expression:E+E*E-E
STACK VALUES INPUT
E +E*E-E
+ E*E-E
E *E-E
E *E-E
* E-E
E -E
E -E
- E
Expressions Output: E
Result: The Program Executed successfully
Program No. 8
Aim: Write a program C or C++to Construct DAG for input expression.
#include<iostream>
#include<string>
using namespace std;
int main()
string exp;
cout<<"Enter the expression:-";
cin>>exp;
int j=0,k=0;
char q;
for(int i=exp.length()-1;i>1;i--)
if(islower(exp[i]) || (exp[i]>=48 && exp[i]<=57))
cout<<j<<"->"<<exp[i]<<endl; j+
+;
for(int i=exp.length()-1;i>1;i--)
if(!(islower(exp[i])|| (exp[i]>=48 && exp[i]<=57)))
cout<<j<<"->"<<exp[i]<<k<<k+1<<endl;
j++;
k+=2;
}
}cout<<j<<"->"<<exp[0]<<endl;
j++;
cout<<j<<"->"<<exp[1]<<j-1<<j-2<<endl;
return 0;
Result: The Program Executed successfully
