SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &

Research,Bareilly

COMPILER DESIGN
LAB SOLUTION
KCS552
Semester: V Year: THIRD
Session: 2023-24
Department of Computer Science and Engineering

1
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly

1.Design and implement a lexical analyzer for given language using C and the lexical analyzer should
ignore redundant
spaces, tabs and new lines.

2. Implementation of Lexical Analyzer using Lex Tool

3. Generate YACC specification for a few syntactic categories.

a) Program to recognize a valid arithmetic expression that uses operator +, – , * and /.
b) Program to recognize a valid variable which starts with a letter followed by any number of letters or
digits.
c) Implementation of Calculator using LEX and YACC
d) Convert the BNF rules into YACC form and write code to generate abstract syntax tree

4. Write program to find ε – closure of all states of any given NFA with ε transition.

5. Write program to convert NFA with ε transition to NFA without ε transition.

6. Write program to convert NFA to DFA

7. Write program to minimize any given DFA.

8. Develop an operator precedence parser for a given language.

9. Write program to find Simulate First and Follow of any given grammar.

10. Construct a recursive descent parser for an expression.

11. Construct a Shift Reduce Parser for a given language.

12. Write a program to perform loop unrolling.

13. Write a program to perform constant propagation.

14. Implement Intermediate code generation for simple expressions.

2
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
15. Implement the back end of the compiler which takes the three address code and produces the 8086
assembly language
instructions that can be assembled and run using an 8086 assembler. The target assembly instructions can
be simple move,
add, sub, jump etc.

3
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly

Program-1

Objective:-Design and implement a lexical analyzer for given language using C and the lexical analyzer
should ignore redundant spaces, tabs and new lines.

Solution:-
#include<string.h>
#include<conio.h>
#include<ctype.h>
#include<stdio.h>
void main( )
{
FILE *f1;
char c,str[10];
int lineno=1,num=0,i=0;
clrscr();
printf("\nEnter the C Program\n");
f1=fopen("input.txt","w");
while((c=getchar())!=EOF)
putc(c,f1);
fclose(f1);
f1=fopen("input.txt","r");
while((c=getc(f1))!=EOF) // TO READ THE GIVEN FILE
{
if(isdigit(c)) // TO RECOGNIZE NUMBERS
{
num=c-48;
c=getc(f1);
while(isdigit(c))
{
num=num*10+(c-48);
c=getc(f1);
}
printf("%d is a number \n",num);
ungetc(c,f1);
}
else if(isalpha(c)) // TO RECOGNIZE KEYWORDS AND IDENTIFIERS
{
str[i++]=c;
c=getc(f1);
while(isdigit(c)||isalpha(c)||c=='_'||c=='$')
{
str[i++]=c;
c=getc(f1);
}
str[i++]='\0';

4
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
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) // TYPE 32 KEYWORDS
printf("%s is a keyword\n",str);
else
printf("%s is a identifier\n",str);
ungetc(c,f1);
i=0;
}
else if(c==' '||c=='\t') // TO IGNORE THE SPACE
printf("\n");
else if(c=='\n') // TO COUNT LINE NUMBER
lineno++;
else // TO FIND SPECIAL SYMBOL
printf("%c is a special symbol\n",c);
}
printf("Total no. of lines are: %d\n",lineno);
fclose(f1);
getch( );
}

Output:
Enter the C Program
int main( )
{
int a=10,20;
charch;
float f;
}^Z

The numbers in the program are: 10 20

The keywords and identifiersare:
int is a keyword
main is an identifier
int is a keyword
a is an identifier
char is a keyword
ch is an identifier
float is a keyword
f is an identifier
Special characters are ( ) { = , ; ; ; }
Total no. of lines are:5

5
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
Program- 2

Objective: Implementation of Lexical Analyzer using Lex Tool.

Lex:-

 The lex is used in the manner depicted. A specification of the lexical analyzer is preferred by
creating a program lex.1 in the lex language.
 Then lex.1 is run through the lex compiler to produce a ‘c’ program lex.yy.c.
 The program lex.yy.c consists of a tabular representation of a transition diagram constructed
from the regular expression of lex.1 together with a standard routine that uses table of
recognize lexemes.
 Lex.yy.c is run through the ‘C’ compiler to produce as object program a.out, which is the
lexical
analyzer that transform as input stream into sequence of tokens.

Algorithm:
1. First, a specification of a lexical analyzer is prepared by creating a program lexp.l
in the LEX language.
2. The Lexp.l program is run through the LEX compiler to produce an equivalent
code in C language named Lex.yy.c
3. The program lex.yy.c consists of a table constructed from the Regular
Expressions of Lexp.l, together with standard routines that uses the table to
recognize lexemes.
4. Finally, lex.yy.c program is run through the C Compiler to produce an object
program a.out, which is the lexical analyzer that transforms an input stream into a
sequence of tokens.

lexp.l
%{
int COMMENT=0;
%}
identifier [a-zA-Z][a-zA-Z0-9]*
%%
#.* {printf ("\n %s is a Preprocessor
Directive",yytext);} int |
float |
main | if |
else |
printf |
scanf | for
| char |
6
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
getch |
while {printf("\n %s is a
Keyword",yytext);} "/*"
{COMMENT=1;}
"*/" {COMMENT=0;}
{identifier}\( {if(!COMMENT) printf("\n Function:\t %s",yytext);}
\{ {if(!COMMENT) printf("\n Block Begins");
\} {if(!COMMENT) printf("\n Block Ends");}
{identifier}(\[[0-9]*\])? {if(!COMMENT) printf("\n %s is an Identifier",yytext);}
\".*\" {if(!COMMENT) printf("\n %s is a String",yytext);}
[0-9]+ {if(!COMMENT) printf("\n %s is a Number",yytext);}
\)(\;)? {if(!COMMENT) printf("\t");ECHO;printf("\n");}
\( ECHO;
= {if(!COMMENT) printf("\n%s is an Assmt oprtr",yytext);}
\<= |
\>= |
\< |
== {if(!COMMENT) printf("\n %s is a Rel. Operator",yytext);}
.|\n
%%
int main(int argc, char **argv)
{
if(argc>1)
{
FILE *file;
file=fopen(argv[1],"r"); if(!
file)
{
printf("\n Could not open the file:
%s",argv[1]); exit(0);
}
yyin=file;
}
yylex( ); printf("\n\
n"); return 0;
}
int yywrap( )
{
return 0;
}
7
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly

Output:
test.c
#include<stdio.h>
main()

{
int fact=1,n;
for(int i=1;i<=n;i++)
{ fact=fact*i; }
printf("Factorial Value of N is",
fact); getch();
}
$ lex lexp.l
$ cc lex.yy.c
$ ./a.out test.c
#include<stdio.h> is a Preprocessor
Directive Function: main( )
Block Begins
int is a Keyword
fact is an Identifier
= is an Assignment Operator
1 is a Number
n is an Identifier
Function: for( int
is a Keyword i is
an Identifier
= is an Assignment Operator
1 is a Number
i is an Identifier
<= is a Relational Operator
n is an Identifier
i is an Identifier
);
Block Begins
fact is an Identifier
= is an Assignment Operator
fact is an Identifier
i is an Identifier Block
Ends Function:
8
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
printf(
"Factorial Value of N is" is a
String fact is an Identifier );
Function: getch( );
Block Ends

Program-3

Objective: Program to recognize a valid arithmetic expression that uses operator +, – , * and /.
9
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly

Solution:-
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void removeduplicate( );
void final( );
int Isiden(char ch);
int Isop(char ch);
int Isdel(char ch);
int Iskey(char * str);
void removeduplicate( );

char op[8]={'+','-','*','/','=','<','>','%'};
char del[8]={'}','{',';','(',')','[',']',','};
char *key[]={"int","void","main","char","float"};

//char *operato[]={"+","-","/","*","<",">","=","%","<=",">=","++"};

int idi=0,idj=0,k,opi=0,opj=0,deli=0,uqdi=0,uqidi=0,uqoperi=0,kdi=0,liti=0,ci=0;
int uqdeli[20],uqopi[20],uqideni[20],l=0,j;
char uqdel[20],uqiden[20][20],uqop[20][20],keyword[20][20];
char iden[20][20],oper[20][20],delem[20],litral[20][20],lit[20],constant[20][20];
void lexanalysis(char *str)
{
int i=0;
while(str[i]!='\0')
{
if(Isiden(str[i])) //for identifiers
{
while(Isiden(str[i]))
{
iden[idi][idj++]=str[i++];
}
iden[idi][idj]='\0';
idi++;idj=0;
}
else
if(str[i]=='"') //for literals
{
lit[l++]=str[i];

for(j=i+1;str[j]!='"';j++)
{
lit[l++]=str[j];
}

10
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
lit[l++]=str[j];lit[l]='\0';
strcpy(litral[liti++],lit);
i=j+1;
}
else
if(Isop(str[i])) // for operators
{
while(Isop(str[i]))
{
oper[opi][opj++]=str[i++];
}
oper[opi][opj]='\0';
opi++;opj=0;
}
else
if(Isdel(str[i])) //for delemeters
{
while(Isdel(str[i]))
{
delem[deli++]=str[i++];
}
}
else
{
i++;
}
}
removeduplicate( );
final( );

11
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
}
int Isiden(char ch)
{
if(isalpha(ch)||ch=='_'||isdigit(ch)||ch=='.')
return 1;
else
return 0;
}
int Isop(char ch)
{
int f=0,i;
for(i=0;i<8&&!f;i++)
{
if(ch==op[i])
f=1;
}
return f;
}
int Isdel(char ch)
{
int f=0,i;
for(i=0;i<8&&!f;i++)
{
if(ch==del[i])
f=1;
}
return f;
}
12
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
int Iskey(char * str)
{
int i,f=0;
for(i=0;i<5;i++)
{
if(!strcmp(key[i],str))
f=1;
}
return f;
}
void removeduplicate( )
{
int i,j;
for(i=0;i<20;i++)
{
uqdeli[i]=0;
uqopi[i]=0;
uqideni[i]=0;
}
for(i=1;i<deli+1;i++) //removing duplicate delemeters
{
if(uqdeli[i-1]==0)
{
uqdel[uqdi++]=delem[i-1];
for(j=i;j<deli;j++)
{
if(delem[i-1]==delem[j])
uqdeli[j]=1;
13
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
}
}
}
for(i=1;i<idi+1;i++) //removing duplicate identifiers
{
if(uqideni[i-1]==0)
{
strcpy(uqiden[uqidi++],iden[i-1]);
for(j=i;j<idi;j++)
{
if(!strcmp(iden[i-1],iden[j]))
uqideni[j]=1;
}
}
}
for(i=1;i<opi+1;i++) //removing duplicate operators
{
if(uqopi[i-1]==0)
{
strcpy(uqop[uqoperi++],oper[i-1]);
for(j=i;j<opi;j++)
{
if(!strcmp(oper[i-1],oper[j]))
uqopi[j]=1;
}
}
}
}
14
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
void final( )
{
int i=0;
idi=0;
for(i=0;i<uqidi;i++)
{
if(Iskey(uqiden[i])) //identifying keywords
strcpy(keyword[kdi++],uqiden[i]);
else
if(isdigit(uqiden[i][0])) //identifying constants
strcpy(constant[ci++],uqiden[i]);
else
strcpy(iden[idi++],uqiden[i]);
}
// printing the outputs

printf("\n\tDelemeter are : \n");

for(i=0;i<uqdi;i++)
printf("\t%c\n",uqdel[i]);

printf("\n\tOperators are : \n");

for(i=0;i<uqoperi;i++)
{
printf("\t");
puts(uqop[i]);
}
printf("\n\tIdentifiers are : \n");
for(i=0;i<idi;i++)
15
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
{
printf("\t");
puts(iden[i]);
}
printf("\n\tKeywords are : \n");
for(i=0;i<kdi;i++)
{
printf("\t");
puts(keyword[i]);
}

printf("\n\tConstants are :\n");

for(i=0;i<ci;i++)
{
printf("\t");
puts(constant[i]);
}

printf("\n\tLiterals are :\n");

for(i=0;i<liti;i++)
{
printf("\t");
puts(litral[i]);
}
}
void main( )
{
char str[50];
16
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
//clrscr( );
printf("\nEnter the string : ");
scanf("%[^\n]c",str);
lexanalysis(str);
//getch( );
}

Program-4

17
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly

Objective: Program to recognize a valid variable which starts with a letter followed by any number of
letters or digits.

Solution:-

#include <stdio.h>
#include <conio.h>
int main( )
{
char ch;
clrscr( );
/* Reads a character from user */
printf ("Enter any character: ");
scanf("%c", &ch);
/* Checks if it is an alphabet */
if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
{
printf("%c is ALPHABET.\n", ch);
}
else if(ch >= '0' && ch <= '9')
{
printf("%c is DIGIT.\n", ch);
}
else
{
printf("%c is SPECIAL CHARACTER.\n", ch);
}
getch( );
return 0;
}
OUTPUT

18
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
Program-6

Objective: Write program to convert NFA to DFA.

Solution:

#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 findfinalstate(void);
void unionclosure(int);
void print_e_closure(int);
static int set[20],nostate,noalpha,s,notransition,nofinal,start,finalstate[20],c,r,buffer[20];
char alphabet[20];
static int e_closure[20][20]={0};
struct node * transition[20][20]={NULL};
void main()
{
int i,j,k,m,t,n;

struct node *temp;

printf("enter the number of alphabets?\n");
scanf("%d",&noalpha);
getchar();
printf("NOTE:- [ use letter e as epsilon]\n");

printf("NOTE:- [e must be last character ,if it is present]\n");

printf("\nEnter alphabets?\n");
for(i=0;i<noalpha;i++)
{

alphabet[i]=getchar();
getchar();
}
printf("Enter the number of states?\n");
scanf("%d",&nostate);
printf("Enter the start state?\n");
scanf("%d",&start);
19
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
printf("Enter the number of final states?\n");
scanf("%d",&nofinal);
printf("Enter the final states?\n");
for(i=0;i<nofinal;i++)
scanf("%d",&finalstate[i]);
printf("Enter no of transition?\n");
scanf("%d",&notransition);
printf("NOTE:- [Transition is in the form--> qno alphabet qno]\n",notransition);
printf("NOTE:- [States number must be greater than zero]\n");
printf("\nEnter transition?\n");
for(i=0;i<notransition;i++)
{

scanf("%d %c%d",&r,&c,&s);
insert_trantbl(r,c,s);

printf("\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("Equivalent NFA without epsilon\n");
printf("-----------------------------------\n");
printf("start state:");
print_e_closure(start);
printf("\nAlphabets:");
for(i=0;i<noalpha;i++)
printf("%c ",alphabet[i]);
printf("\n States :" );
for(i=1;i<=nostate;i++)
print_e_closure(i);

printf("\nTnransitions are...:\n");

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

20
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly

for(j=0;j<noalpha-1;j++)
{
for(m=1;m<=nostate;m++)
set[m]=0;
for(k=0;e_closure[i][k]!=0;k++)
{

t=e_closure[i][k];
temp=transition[t][j];
while(temp!=NULL)
{

unionclosure(temp->st);
temp=temp->link;
}
}
printf("\n");
print_e_closure(i);
printf("%c\t",alphabet[j] );
printf("{");
for(n=1;n<=nostate;n++)
{
if(set[n]!=0)
printf("q%d,",n);
}
printf("}");
}
}
printf("\n Final states:");
findfinalstate();
}
void findclosure(int x,int sta)
{
struct node *temp;
int i;
if(buffer[x])
return;
e_closure[sta][c++]=x;
buffer[x]=1;
if(alphabet[noalpha-1]=='e' && transition[x][noalpha-1]!=NULL)
{
temp=transition[x][noalpha-1];
while(temp!=NULL)
{

findclosure(temp->st,sta);

21
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
temp=temp->link;
}
}
}

void insert_trantbl(int r,char c,int s)

{
int j;
struct node *temp;
j=findalpha(c);
if(j==999)
{
printf("error\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 unionclosure(int i)
{
int j=0,k;
while(e_closure[i][j]!=0)
{
k=e_closure[i][j];
set[k]=1;
j++;
}
}
void findfinalstate()
{
int i,j,k,t;
for(i=0;i<nofinal;i++)
{
for(j=1;j<=nostate;j++)

22
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
{
for(k=0;e_closure[j][k]!=0;k++)
{
if(e_closure[j][k]==finalstate[i])
{

print_e_closure(j);
}
}
}
}

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("}\t");
}

Output:-

23
SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly

24
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
Program-8

Objective: Develop an operator precedence parser for a given language

Solution:-

#include<stdio.h>
#include<string.h>
char *input;
int i=0;
char lasthandle[6],stack[50],handles[][5]={")E(","E*E","E+E","i","E^E"};
//(E) becomes )E( when pushed to stack
int top=0,l;
char prec[9][9]={

/*input*/

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

/* + */ '>', '>','<','<','<','<','<','>','>',

/* - */ '>', '>','<','<','<','<','<','>','>',

/* * */ '>', '>','>','>','<','<','<','>','>',

/* / */ '>', '>','>','>','<','<','<','>','>',

/* ^ */ '>', '>','>','>','<','<','<','>','>',

/* i */ '>', '>','>','>','>','e','e','>','>',

/* ( */ '<', '<','<','<','<','<','<','>','e',

/* ) */ '>', '>','>','>','>','e','e','>','>',

/* $ */ '<', '<','<','<','<','<','<','<','>',

};

int getindex(char c)
{
switch(c)
{
case '+':return 0;
case '-':return 1;
case '*':return 2;
case '/':return 3;
25
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
case '^':return 4;
case 'i':return 5;
case '(':return 6;
case ')':return 7;
case '$':return 8;
}
}

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

int reduce()
{
int i,len,found,t;
for(i=0;i<5;i++)//selecting handles
{
len=strlen(handles[i]);
if(stack[top]==handles[i][0]&&top+1>=len)
{
found=1;
for(t=0;t<len;t++)
{
if(stack[top-t]!=handles[i][t])
{
found=0;
break;
}
}
if(found==1)
{
stack[top-t+1]='E';
top=top-t+1;
strcpy(lasthandle,handles[i]);
stack[top+1]='\0';
return 1;//successful reduction
}
}
}
return 0;
}

26
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
void dispstack()
{
int j;
for(j=0;j<=top;j++)
printf("%c",stack[j]);
}

void dispinput()
{
int j;
for(j=i;j<l;j++)
printf("%c",*(input+j));
}

void main()
{
int j;

input=(char*)malloc(50*sizeof(char));
printf("\nEnter the string\n");
scanf("%s",input);
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)

27
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
printf("\nAccepted;");
else
printf("\nNot Accepted;");
getch();
}

OUTPUT:

Program- 9

28
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
FIRST and FOLLOW of a Given Grammar using C program

(a) FIRST of a Given Grammar using C program

Solution

#include<stdio.h>
#include<ctype.h>
void FIRST(char[],char );
void addToResultSet(char[],char);
int numOfProductions;
char productionSet[10][10];
main()
{
int i;
char choice;
char c;
char result[20];
printf("How many number of productions ? :");
scanf(" %d",&numOfProductions);
for(i=0;i<numOfProductions;i++)//read production string eg: E=E+T
{
printf("Enter productions Number %d : ",i+1);
scanf(" %s",productionSet[i]);
}
do
{
printf("\n Find the FIRST of :");
scanf(" %c",&c);
FIRST(result,c); //Compute FIRST; Get Answer in 'result' array
printf("\n FIRST(%c)= { ",c);
for(i=0;result[i]!='\0';i++)
printf(" %c ",result[i]); //Display result
printf("}\n");
printf("press 'y' to continue : ");
scanf(" %c",&choice);
}
while(choice=='y'||choice =='Y');
}
/*
*Function FIRST:
*Compute the elements in FIRST(c) and write them
*in Result Array.
*/
void FIRST(char* Result,char c)
{
int i,j,k;
char subResult[20];
29
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
int foundEpsilon;
subResult[0]='\0';
Result[0]='\0';
//If X is terminal, FIRST(X) = {X}.
if(!(isupper(c)))
{
addToResultSet(Result,c);
return ;
}
//If X is non terminal
//Read each production
for(i=0;i<numOfProductions;i++)
{
//Find production with X as LHS
if(productionSet[i][0]==c)
{
//If X → ε is a production, then add ε to FIRST(X).
if(productionSet[i][2]=='$') addToResultSet(Result,'$');
//If X is a non-terminal, and X → Y1 Y2 … Yk
//is a production, then add a to FIRST(X)
//if for some i, a is in FIRST(Yi),
//and ε is in all of FIRST(Y1), …, FIRST(Yi-1).
else
{
j=2;
while(productionSet[i][j]!='\0')
{
foundEpsilon=0;
FIRST(subResult,productionSet[i][j]);
for(k=0;subResult[k]!='\0';k++)
addToResultSet(Result,subResult[k]);
for(k=0;subResult[k]!='\0';k++)
if(subResult[k]=='$')
{
foundEpsilon=1;
break;
}
//No ε found, no need to check next element
if(!foundEpsilon)
break;
j++;
}
}
}
}
return ;
}

30
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
/* addToResultSet adds the computed
*element to result set.
*This code avoids multiple inclusion of elements
*/
void addToResultSet(char Result[],char val)
{
int k;
for(k=0 ;Result[k]!='\0';k++)
if(Result[k]==val)
return;
Result[k]=val;
Result[k+1]='\0';
}

Program:-
31
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
(b) FOLLOW of a Given Grammar using C program

Solution:

#include<stdio.h>
#include<string.h>
int n,m=0,p,i=0,j=0;
char a[10][10],followResult[10];
void follow(char c);
void first(char c);
void addToResult(char);
int main()
{
int i;
int choice;
char c,ch;
printf("Enter the no.of productions: ");
scanf("%d", &n);
printf(" Enter %d productions\nProduction with multiple terms should be give as separate productions \
n", n);
for(i=0;i<n;i++)
scanf("%s%c",a[i],&ch);
// gets(a[i]);
do
{
m=0;
printf("Find FOLLOW of -->");
scanf(" %c",&c);
follow(c);
printf("FOLLOW(%c) = { ",c);
for(i=0;i<m;i++)
printf("%c ",followResult[i]);
printf(" }\n");
printf("Do you want to continue(Press 1 to continue....)?");
scanf("%d%c",&choice,&ch);
}
while(choice==1);
}
void follow(char c)
{
if(a[0][0]==c)addToResult('$');
for(i=0;i<n;i++)
{
for(j=2;j<strlen(a[i]);j++)
{
if(a[i][j]==c)
{
if(a[i][j+1]!='\0')first(a[i][j+1]);
32
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
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;
addToResult(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];
addToResult(a[k][2]);
else first(a[k][2]);
}
}
}
void addToResult(char c)
{
int i;
for( i=0;i<=m;i++)
if(followResult[i]==c)
return;
followResult[m++]=c;
}

33
SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly

34
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
Program-10

Construct a recursive descent parser for an expression.

Solution:

#include<stdio.h>
#include<conio.h>
int c=0;
char p[20];
void s( );
void l( );
void lprime( );
void l( )
{
s( );
lprime( );
}
void lprime( )
{
if(p[c]==',')
{
c++;
s( );
lprime( );
}
}
void s( )
{
if(p[c]=='a')

35
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
c++;
else if(p[c]=='( ' )
{
c++;
l();
if(p[c]==')')
c++;
else
c--;
}
else
printf("\nInvalid Expression");
}
void main( )
{
clrscr( );
printf("\nImplementation of RECURSIVE DESCENT PARSER\n");
printf("\nEnter the Expression:\n");
scanf("%s",p);
s( );
if(p[c]=='$')
printf("\nThe String is accepted");
else
printf("\nThe string is rejected");
getch( );
}

36
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
Output:
Implementation of RECURSIVE DESCENT PARSER
Enter the Expression:
a
The string is rejected
Implementation of RECURSIVE DESCENT PARSER
Enter the Expression:
a$
The String is accepted
Recursive Descent Parsing
Implementation of RECURSIVE DESCENT PARSER
Enter the Expression:
(a)$
The String is accepted
Implementation of RECURSIVE DESCENT PARSER
Enter the Expression:
b*c
Invalid Expression
The string is rejected

37
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly

Program- 11

Objective: - Construct a Shift Reduce Parser for a given language.

Solution:-
#include<stdio.h>
#include<string.h>
int k=0,z=0,i=0,j=0,c=0;
char a[16],ac[20],stk[15],act[10];
void check();
int main()
{
puts("GRAMMAR is E->E+E \n E->E*E \n E->(E) \n E->id");
puts("enter input string ");
gets(a);
c=strlen(a);
strcpy(act,"SHIFT->");
puts("stack \t input \t action");
for(k=0,i=0; j<c; k++,i++,j++)
{
if(a[j]=='i' && a[j+1]=='d')
{
stk[i]=a[j];
stk[i+1]=a[j+1];
stk[i+2]='\0';
a[j]=' ';
a[j+1]=' ';
printf("\n$%s\t%s$\t%sid",stk,a,act);
check();
}
else
{
stk[i]=a[j];
stk[i+1]='\0';
a[j]=' ';
printf("\n$%s\t%s$\t%ssymbols",stk,a,act);
check();
}
}

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

38
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
for(z=0; z<c; z++)
if(stk[z]=='i' && stk[z+1]=='d')
{
stk[z]='E';
stk[z+1]='\0';
printf("\n$%s\t%s$\t%s",stk,a,ac);
j++;
}
for(z=0; z<c; z++)
if(stk[z]=='E' && stk[z+1]=='+' && stk[z+2]=='E')
{
stk[z]='E';
stk[z+1]='\0';
stk[z+2]='\0';
printf("\n$%s\t%s$\t%s",stk,a,ac);
i=i-2;
}
for(z=0; z<c; z++)
if(stk[z]=='E' && stk[z+1]=='*' && stk[z+2]=='E')
{
stk[z]='E';
stk[z+1]='\0';
stk[z+1]='\0';
printf("\n$%s\t%s$\t%s",stk,a,ac);
i=i-2;
}
for(z=0; z<c; z++)
if(stk[z]=='(' && stk[z+1]=='E' && stk[z+2]==')')
{
stk[z]='E';
stk[z+1]='\0';
stk[z+1]='\0';
printf("\n$%s\t%s$\t%s",stk,a,ac);
i=i-2;
}
}

39
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly

OUTPUT:-

40
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
Program- 12

Implement Intermediate code generation for simple expressions.

#include"stdio.h"
#include"conio.h"
#include"string.h"
int i=1,j=0,no=0,tmpch=90;
char str[100],left[15],right[15];
void findopr();
void explore();
void fleft(int);
void fright(int);
struct exp
{
int pos;
char op;
}k[15];
void main()
{
clrscr();
printf("\t\tINTERMEDIATE CODE GENERATION\n\n");
printf("Enter the Expression :");
scanf("%s",str);
printf("The intermediate code:\t\tExpression\n");
findopr();
explore();
getch();
}
void findopr()
{
for(i=0;str[i]!='\0';i++)
if(str[i]==':')
{
k[j].pos=i;
k[j++].op=':';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='/')
{
k[j].pos=i;
k[j++].op='/';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='*')
{
k[j].pos=i;

41
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
k[j++].op='*';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='+')
{
k[j].pos=i;
k[j++].op='+';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='-')
{
k[j].pos=i;
k[j++].op='-';
}
}
void explore()
{
i=1;
while(k[i].op!='\0')
{
fleft(k[i].pos);
fright(k[i].pos);
str[k[i].pos]=tmpch--;
printf("\t%c := %s%c%s\t\t",str[k[i].pos],left,k[i].op,right);
for(j=0;j <strlen(str);j++)
if(str[j]!='$')
printf("%c",str[j]);
printf("\n");
i++;
}
fright(-1);
if(no==0)
{
fleft(strlen(str));
printf("\t%s := %s",right,left);
getch();
exit(0);
}
printf("\t%s := %c",right,str[k[--i].pos]);
getch();
}
void fleft(int x)
{
int w=0,flag=0;
x--;
while(x!= -1 &&str[x]!= '+' &&str[x]!='*'&&str[x]!='='&&str[x]!='\0'&&str[x]!='-'&&str[x]!
='/'&&str[x]!=':')

42
 SRMS CET R- Shri Ram Murti Smarak College Of Engineering, Technology &
Research,Bareilly
{
if(str[x]!='$'&& flag==0)
{
left[w++]=str[x];
left[w]='\0';
str[x]='$';
flag=1;
}
x--;
}
}
void fright(int x)
{
int w=0,flag=0;
x++;
while(x!= -1 && str[x]!= '+'&&str[x]!='*'&&str[x]!='\0'&&str[x]!='='&&str[x]!=':'&&str[x]!
='-'&&str[x]!='/')
{
if(str[x]!='$'&& flag==0)
{
right[w++]=str[x];
right[w]='\0';
str[x]='$';
flag=1;
}
x++;
}
}

43