In this post, we will see Recursive Descent Parser with an example and its implementation in C Language.
Recursive Descent Parser (RDP) is a Top Down Parser. It works in terms of recursive function call.
Lets see an example (CFG) as follows:
S->AA
A->aB/ϵ
B->b
In RDP, for each Non-terminal, a function is called.
That function body consists of a traversal of RHS (Right Hand Side) of productions. If we get a Terminal, then we read it and increment the input pointer while if we get Non-terminal, then we call a function for that Non-terminal.
Check following C langauge program having RDP implementation for above grammar:
Recursive Descent Parser (RDP) is a Top Down Parser. It works in terms of recursive function call.
Lets see an example (CFG) as follows:
S->AA
A->aB/ϵ
B->b
In RDP, for each Non-terminal, a function is called.
That function body consists of a traversal of RHS (Right Hand Side) of productions. If we get a Terminal, then we read it and increment the input pointer while if we get Non-terminal, then we call a function for that Non-terminal.
Check following C langauge program having RDP implementation for above grammar:
#include<stdio.h>
#include <stdlib.h>
char l;
void match(char c)
{
if(l==c)
l=getchar();
else
{
printf("Invalid Input\n");
exit(0);
}
}
void B()
{
if(l=='b')
{
match('b');
}
else
{
printf("Invalid Input\n");
exit(0);
}
}
void A()
{
if(l=='a')
{
match('a');
B();
}
else
return;
}
void S()
{
A();
A();
}
void main()
{
char input[10];
printf("Enter String with $ at the end\n");
l=getchar();
S();
if(l=='$')
{
printf("\nParsing Successful\n");
}
else
{
printf("Invalid Input\n");
}
}
#include <stdlib.h>
char l;
void match(char c)
{
if(l==c)
l=getchar();
else
{
printf("Invalid Input\n");
exit(0);
}
}
void B()
{
if(l=='b')
{
match('b');
}
else
{
printf("Invalid Input\n");
exit(0);
}
}
void A()
{
if(l=='a')
{
match('a');
B();
}
else
return;
}
void S()
{
A();
A();
}
void main()
{
char input[10];
printf("Enter String with $ at the end\n");
l=getchar();
S();
if(l=='$')
{
printf("\nParsing Successful\n");
}
else
{
printf("Invalid Input\n");
}
}
For Invalid Input
No comments:
Post a Comment