A→Bbc
B→Cbcd
C→cdef
D→d
Input String: cdefbedbeedefbedabcdefdef
THEORY
Recursive descent parsing is probably the most well-known and intuitive technique applicable to a subclass of context-free grammars. A subroutine for each non-terminal should determine a rule according to which the substring shall be parsed.
Parse Tree:
SOURCE CODE:
#include<stdio.h>
#include<string.h>
int S();
int A();
int B();
int C();
int D();
char input[100];
int i;
void main()
{
printf ("enter the string\n");
gets(input);
if(S()==1)
{
printf("\n string is accepted");
}
else
{
printf("\n string is not accepted\n");
}
}
int S()
{
if(A()==1)
if(B()==1)
if(input[i]=='a')
{
i++;
if(input[i]=='b')
{
i++;
if(C()==1)
if(D()==1)
if(input[i]=='e')
{
i++;
if(input[i]=='f')
{
i++;
return 1;
}
else return 0;
}
else return 0;
else return 0;
else return 0;
}
else return 0;
}
else return 0;
else return 0;
else return 0;
}
int A()
{
if(B()==1)
if(input[i]=='b')
{
i++;
if(input[i]=='c')
{
i++;
return 1;
}
else return 0;
}
else return 0;
else return 0;
}
int B()
{
if(C()==1)
if(input[i]=='b')
{
i++;
if(input[i]=='c')
{
i++;
if(input[i]=='d')
{
i++;
return 1;
}
else return 0;
}
else return 0;
}
else return 0;
else return 0;
}
int C()
{
if(input[i]=='c')
{
i++;
if(input[i]=='d')
{
i++;
if(input[i]=='e')
{
i++;
if(input[i]=='f')
{
i++;
return 1;
}
else return 0;
}
else return 0;
}
else return 0;
}
else return 0;
}
int D()
{
if(input[i]=='d')
{
i++;
return 1;
}
else return 0;
}
output:
enter the string
cdefbcdbccdefbcdabcdefdef
string is accepted
output2:
enter the string
himanshu
string is not accepted
Output3:
enter the string
Himzo
String is not accepted
