Recursive Descent Parser Example in C language

              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:       

#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");
        }
    
}

Output:

For Valid Input

For Invalid Input

Check Other Posts on Compiler